| 授業のねらい |
| 離散数学の面白さを、UNIX上でＣ言語を用いる実践的な演習を通して、体験する。たま、理論的な結果と実験でえられる結果との関係を理解し、論理的な考え方の理解を深める。 |
|
| 授業の目標 |
１．離散最適化問題を学び、離散構造とアルゴリズムの理解を深める。
２．実践的な演習を通して離散最適化問題の理解を深める。
３．離散数学問題を通じて論理的な思考を養う。
|
|
| 授業計画 |
1週目：グラブの表現(講義と実験)
２週目：最大流問題と最小カット（講義と実験）
３週目：Ford-Fulkersonのアルゴリズムとその正当性（講義と実験）
４週目：Ford-Fulkersonのアルゴリズムの計算量，欠点とその改善(講義と実験）
５週目：離散最適化の歴史と離散数学の幾つかの話題(講義と実験）
|
|
| 教科書及び教材 |
|
| 参考書 |
岩野和生（1993），ネットワークフロー問題の最近の発展，藤重 悟 編:離散構造とアルゴリズムII， 近代科学社 pp79-153．
（工大図書館にあり）
浅野孝夫（1994），情報の構造ーデータ構造とグラフアルゴリズムー，日本評論社 |
|
| 成績評価方法 |
| レポート（5回）の平均で評価する．提出期限までにレポートの提出が無いものは成績評価の対象とせず不合格とする。 |
|
| 履修条件等 |
| 本演習は、Ｃ言語によるプログラミングが可能なことを履修条件とする。 |
|
| 教員からのメッセージ |
離散最適化が難しいが、理論的結果を実践的な演習を通して、その面白さを実感できることが期待されます。
たま、質問があったら、積極的に聞きに来て下さい。
オフィスアワー：13：30-14：30（毎週木曜日） |
|
| その他 |
|