|
|||||
※学期中に内容が変更になることがあります。 | |||||
2020年度
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
<概要/Course Content Summary> ネットワーク最適化問題の代表例である,最大流問題と最小費用流問題を取り上げ,それらの理論的な枠組みと解法アルゴリズムおよび計算量について講義する.最大流問題については,増加道法の一つであり,もっとも古いアルゴリズムであるラベリング法と,現在最も高速なアルゴリズムとして知られるプリフロープッシュ法を取り上げ,そのアルゴリズムと計算量評価について述べる.最小費用流問題については,基本事項と代表的な解法アルゴリズムを紹介する.取り上げるアルゴリズムは負閉路消去法,正カット消去法等である. <到達目標/Goals,Aims> グラフ上のネットワーク最適化問題の代表例である最大流問題と最小費用流問題について,その問題の意味を理解するとともに,代表的なアルゴリズムと計算量を理解し,簡単な例題をアルゴリズムを用いて解くことができるようになる. <授業計画/Schedule>
受講者の予備知識などを考慮して,場合によっては,最大流から始めないで,もっと基本的な問題である最短路問題から講義をスタートすることもある.その場合はマッチング問題の講義時間が少なるなり,場合によってはマッチング問題の部分がなくなることもあり得る. <成績評価基準/Evaluation Criteria>
<成績評価結果/Results of assessment> 成績評価の見方について/Notes for assessment
<テキスト/Textbook> テキストは使わず,ノート講義を行う. <参考文献/Reference Book>
|
|
お問合せは同志社大学 各学部・研究科事務室まで
|
Copyright(C) 2020 Doshisha University All Rights Reserved. 無断転載を禁止します。 |