離散構造2
担当教員
授業の到達目標及びテーマ
離散構造2では、グラフ及びネットワークとして表される構造を持った対象を扱う数学の分野を扱う。また、それを実世界にあてはめた応用事例について最適化手法などを学ぶ。
最短経路探索、最小な木を求める問題、ネットワークを流れる最大流量を求める問題や最小の費用フローを求める問題などを扱う。
授業の概要と方法
講義資料は下記のWebサイトより配布する。
http://cis.k.hosei.ac.jp/~koike/Risan2/
講義資料に基づき講義形式で実施し、ほぼ毎回、理解度チェックのため、課題を課す。
授業計画
後期
| 回 | テーマ | 内容 |
|---|---|---|
| 1 | 序論、グラフの定義、表現 | グラフとネットワークにかかわる数学の導入と、実際に適用される事例を紹介する。 |
| 2 | グラフ探索 | グラフ探索問題で最も基本的な算法である、奥優先探索と幅優先探査問題を学ぶ。 |
| 3 | 連結性、木と閉路 | グラフのさまざまな特性を見る。特に木と閉路の概念を学ぶ。 |
| 4 | 木と閉路、カットセット | グラフにおける木と閉路を見付ける問題、グラフを切断するカットセットとそれらの関係を見る。 |
| 5 | マトロイド、オイラーグラフ、ハミルトングラフ、その他の概念1 | グラフをマトリックス的に扱う考え方、一筆書きの経路探索問題、やその他のグラフに関する概念を見る。 |
| 6 | グラフに関するその他の概念2、ネットワーク、最小木問題 | グラフに関するその他の話題について言及しひとまずグラフ問題を終え、ネットワーク問題に入る。 |
| 7 | 中間試験 | グラフに関する理解を深めるために、中間試験を実施する。 |
| 8 | ネットワーク・最小木問題(続)、最短路問題 | ネットワークで最小木を求める問題の続きと、2点間の最短経路を求める問題。 |
| 9 | 最短路問題(続)、フローとカット、2端子フロー | 最短路を求める別の手法、フローとカットの関連、2端子フロー問題を学ぶ |
| 10 | 2端子フロ(続)、循環フロー | 2端子フローの続きと、循環フローを求めるアルゴリズムについて学ぶ。 |
| 11 | 循環フロ(続)、無向ネットワークにおける流とカット | 循環フローを求める手法のの続きと、無向ネットワークの場合のフローとカットの関連を調べる。 |
| 12 | 最小費用フロー、最小費用循環フロー、最小費用2端子ネットワークフロー | 最小費用、循環フロー、最小フロー2端子フローのそれぞれについてフローの存在とフローを見つける問題。 |
| 13 | 最小費用費用フローのまとめ | 最小費用フローのさまざまな場合についてのフローの求め方。 |
| 14 | PERT/CPM | 最小費用フローの応用問題としてPRET/CPMとして知られる問題にこれまでの手法を適用する。 |
| 15 | マッチングと被覆、離散構造2のまとめ | 最後にマッチングと被覆と呼ばれる問題にネットワークフロー的アプローチから見る。最後に離散構造2のまとめを行う |
授業外に行うべき学習活動
特に教科書は定めないので、事前に提供される講義資料に、予習として目を通し、疑問点、問題点を整理しておくこと。
また、ほぼ毎回課題を出すので、講義時間の終わりか、課外で復習をし課題の答えを次回の講義開始時に提出すること。
テキスト
下記のWebサイトより、毎回の講義資料は配布するので、ダウンロードして使うか、ネットワークに接続してオンラインで参照すること。
http://cis.k.hosei.ac.jp/~koiike/Risan2/
参考書
”グラフ・ネットワーク・組合せ論”、藤重悟、共立出版
”情報科学のためのグラフ理論”、加納幹雄、朝倉書店
成績評価基準
期末試験50%、中間試験30%、課題提出20%
毎回授業出席が原則なので欠席は1回につき-5点加算する。
情報機器使用
授業にノートPCを持参し、ネットワークにて当該ページを参照すると良い。