講義資料
========

.. contents:: 
    :depth: 1
    :local:
    :backlinks: none

総研大 統計科学コース 組合せ最適化特論
--------------------------------------

スライド
^^^^

1. `多面体的組合せ論 <tokuron/polyhedra.pdf>`_

   - 組合せ最適化とは
   - 線形計画の復習
   - 整数多面体，完全単模行列

2. `二部マッチング① <tokuron/bipartite.pdf>`_

   - 二部マッチングの最大最小定理
   - 重みなし二部マッチング
   - 重み付き二部マッチング

3. `二部マッチング② <tokuron/bipartite2.pdf>`_

   - 最短路問題
   - 逐次最短路法と主双対法
   - 最適性条件からの見方

4. `最大流① <tokuron/maxflow1.pdf>`_

   - 最大流問題
   - 最大流を用いたモデリング

5. `最大流② <tokuron/maxflow2.pdf>`_

   - Ford–Fulkerson 法
   - Edmonds–Karp 法

6. `最小費用流 <tokuron/mcf.pdf>`_

   - 最小費用流問題
   - アルゴリズム

7. `マトロイド <tokuron/matroid.pdf>`_

   - マトロイドとは
   - 最小重み独立集合と貪欲法
   - マトロイド多面体

8. `独立マッチング・マトロイド交差 <tokuron/indepmatching.pdf>`_

   - 独立マッチング
   - サーキット
   - アルゴリズム

9. `劣モジュラ最小化 <tokuron/sfmin1.pdf>`_ [`補足資料 <tokuron/sfmin2.pdf>`_]

   - 劣モジュラ関数の例
   - Lovász拡張
   - 最小ノルム点法

10. `劣モジュラ最大化 <tokuron/sfmax.pdf>`_

    - 定式化
    - モデリング例
    - 貪欲法


Githubリポジトリ
^^^^^^^^^^^^^^^^

https://github.com/tasusu/tokuron

総研大 統計科学コース 計算数理基礎（相馬担当分「組合せ最適化」）
--------------------------------------------------------------

スライド
^^^^^^^^

- `多面体的組合せ論 <polyhedra.pdf>`_
- `二部マッチング <bipartite.pdf>`_

Githubリポジトリ
^^^^^^^^^^^^^^^^

https://github.com/tasusu/keisansuuri

東大計数 演習第二2019 (Multiplicative Weight Update)
--------------------------------------------------------------
- `講義ノート <mwunote.pdf>`_ 
- `レポート問題 <mwu.pdf>`_

東大計数 演習第二2018 (完全マッチングに対する代数的アルゴリズム)
--------------------------------------------------------------
- `講義ノート <algalg.pdf>`_