シラバス
※学期中に内容が変更になることがあります。

2020年度


31650012 

△離散数理特論
Advanced Discrete Mathematics
2単位/Unit  秋学期/Fall  京田辺/Kyotanabe  講義/Lecture

  渡邊　芳英

＜概要/Course Content Summary＞

ネットワーク最適化問題の代表例である，最大流問題と最小費用流問題を取り上げ，それらの理論的な枠組みと解法アルゴリズムおよび計算量について講義する．最大流問題については，増加道法の一つであり，もっとも古いアルゴリズムであるラベリング法と，現在最も高速なアルゴリズムとして知られるプリフロープッシュ法を取り上げ，そのアルゴリズムと計算量評価について述べる．最小費用流問題については，基本事項と代表的な解法アルゴリズムを紹介する．取り上げるアルゴリズムは負閉路消去法，正カット消去法等である．

＜到達目標/Goals,Aims＞

グラフ上のネットワーク最適化問題の代表例である最大流問題と最小費用流問題について，その問題の意味を理解するとともに，代表的なアルゴリズムと計算量を理解し，簡単な例題をアルゴリズムを用いて解くことができるようになる．

＜授業計画/Schedule＞

（実施回/
Week） 		（内容/
Contents） 		（授業時間外の学習/
Assignments）
（実施回/ Week） 第1回  （内容/ Contents） グラフの基礎事項の複習（１）　
グラフの基礎概念，隣接行列，接続行列  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第2回  （内容/ Contents） グラフの基礎事項の複習（２）　
木と全域木，グラフ上のネットワーク  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第3回  （内容/ Contents） 最大流問題とは何か  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第4回  （内容/ Contents） 補助ネットワークと増加道定理  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第5回  （内容/ Contents） 最大流問題の解法アルゴリズムーラベリング法  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第6回  （内容/ Contents） エドモンド・カープによるラベリング法の改良と計算量  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第7回  （内容/ Contents） 最大流問題の解法アルゴリズムープリフロープッシュ法（１）プリフロー，有効な距離ラベル，可能辺  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第8回  （内容/ Contents） 最大流問題の解法アルゴリズムープリフロープッシュ法　
（２）プッシュ操作とリラベル操作  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第9回  （内容/ Contents） プリフロープッシュ法の計算量評価  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第10回  （内容/ Contents） 最小費用流問題とはなにか  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第11回  （内容/ Contents） 補助ネットワーク，ポテンシャル，被約コスト  （授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第12回  （内容/ Contents） 最小費用流問題の解法アルゴリズム（１）　
様々なアルゴリズムの設計  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第13回  （内容/ Contents） 最小費用流問題の解法アルゴリズム（２）　
負閉路消去法  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第14回  （内容/ Contents） 最小費用流問題の解法アルゴリズム（３）　
正カット消去法  		（授業時間外の学習/ Assignments） 復習を行うこと 
（実施回/ Week） 第15回  （内容/ Contents） 総括  （授業時間外の学習/ Assignments） 出来なかった問題をもう一度考えてみること 

受講者の予備知識などを考慮して，場合によっては，最大流から始めないで，もっと基本的な問題である最短路問題から講義をスタートすることもある．その場合はマッチング問題の講義時間が少なるなり，場合によってはマッチング問題の部分がなくなることもあり得る．

＜成績評価基準/Evaluation Criteria＞

オンライン授業への参加  30%  オンランで授業を行うがその際，Google Formでアンケートを行う．授業に積極的に参加して建設的な意見を寄せたかどうかを評価する．． 
レポート  70%  アルゴリズムの理論的な理解と実際にアルゴリズムを動させるかどうかを問うレポート課題を出す．そのレポートの出来を評価する．レポート提出は2回程度の予定である． 

 

＜成績評価結果/Results of assessment＞   成績評価の見方について/Notes for assessment

    

登録者数

成績評価（%)

評点
平均値

備考
A+ A B+ B C+ C F 他
120 10.0 33.3 45.8 7.5 0.0 0.0 3.3 0.0 3.6 *

＜テキスト/Textbook＞

テキストは使わず，ノート講義を行う．

＜参考文献/Reference Book＞

D. Jungnickel , Graphs，Networks and Algorithms ,  Foruth Ed. .   (Springer, 2013) .  ISBN:978-3-642-32277-8  650ページあるが，記述は丁寧で日本語の類書よりは読みやすい． 

 

繁野麻衣子  『ネットワーク最適化とアルゴリズム－シリーズ応用最適化4－』初版 (朝倉書店、2010年10月)ISBN:978-2-254-11789-9 日本語で書かれた数少ない教科書の一つ．アルゴリズム中心である．日本語だからといって読み易いわけではない． 
 

 
お問合せは同志社大学 各学部・研究科事務室まで
 
Copyright(C) 2020 Doshisha University All Rights Reserved.　無断転載を禁止します。