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