組合せ論

「数え上げ」や「グラフ理論」などの組合せ論の初歩を学習する． 組合せ論は，離散数学の一分野であり， アルゴリズム論，計算量理論，暗号理論，符号理論といった コンピュータサイエンスの様々な分野で応用されている． 本講義では， 集合・論理といった離散数学の導入部分の復習から始め， 前半は数え上げに関する基礎事項， 後半はグラフ理論の初歩を学習する．

• テキスト

講義スケジュール

1. 離散数学の復習（集合・論理）
2. 順列と組合せ
3. 二項係数
4. 鳩ノ巣原理
5. 包除原理
6. 演習
7. 到達度確認テスト１
8. グラフ（グラフとは，完全グラフ・正則グラフ）
9. 色々なグラフ１（二部グラフ）
10. 色々なグラフ２（オイラーグラフ，ハミルトングラフ）
11. 色々なグラフ３（木，根付き木）
12. マッチング
13. グラフ彩色（頂点彩色・辺彩色）
14. 到達度確認テスト２