組合せ論
「数え上げ」や「グラフ理論」などの組合せ論の初歩を学習する.
組合せ論は,離散数学の一分野であり,
アルゴリズム論,計算量理論,暗号理論,符号理論といった
コンピュータサイエンスの様々な分野で応用されている.
本講義では,
集合・論理といった離散数学の導入部分の復習から始め,
前半は数え上げに関する基礎事項,
後半はグラフ理論の初歩を学習する.
講義スケジュール
- 離散数学の復習(集合・論理)
- 順列と組合せ
- 二項係数
- 鳩ノ巣原理
- 包除原理
- 演習
- 到達度確認テスト1
- グラフ(グラフとは,完全グラフ・正則グラフ)
- 色々なグラフ1(二部グラフ)
- 色々なグラフ2(オイラーグラフ,ハミルトングラフ)
- 色々なグラフ3(木,根付き木)
- マッチング
- グラフ彩色(頂点彩色・辺彩色)
- 到達度確認テスト2
Last Update: 01/September/2021