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

2020年度


11655104 

△応用数学Ⅰ
Applied Mathematics I
2単位/Unit  秋学期/Fall  京田辺/Kyotanabe  講義/Lecture

  渡邊　芳英

＜概要/Course Content Summary＞

離散数理で学んだグラフ理論の基礎を前提として，グラフ上のネットワーク理論の基礎事項を講義するとともに，ネットワーク上の様々な最適化問題の数学的な構造と解法アルゴリズムについて講義する．取り扱う問題は，最短経路問題，最大流問題，最小費用流問題などである．これらの問題は組み合わせ最適化問題の重要な例であり，その意味ではこの講義は別に開設される「数理計画法」の離散版を担っているともいえる．さらに，最短経路問題との関連で注目され盛んに研究されているMin-Plus線形代数（トロピカル線形代数）の初歩についても講義する．　

＜到達目標/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） Min-Plus代数入門　
  		（授業時間外の学習/ Assignments） 復習を行う 
（実施回/ Week） 14  （内容/ Contents） Min-Plus代数と最短経路問題  （授業時間外の学習/ Assignments） 復習を行う 
（実施回/ Week） 15  （内容/ Contents） 総括  （授業時間外の学習/ Assignments） 出来なかった問題をもう一度考えてみること 

＜成績評価基準/Evaluation Criteria＞

平常点  20%  オンライン授業への積極的な参加を評価 
中間評価レポート  40%  最短経路問題に対する様々な解法アルゴリズムを理解して，具体的な問題に適用できるかを問う． 
期末菱化レポート  40%  最大流問題およびその解法アルゴリズムについて理解し，具体的な問題で適用できるか，またMin-Plus行列と最短経路問題の関連を理解しているかを問う 

 

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

    

登録者数

成績評価（%)

評点
平均値

備考
A B C D F 他
38 36.8 36.8 13.2 0.0 13.2 0.0 2.8

＜テキスト/Textbook＞

テキストは指定しない．eclassでプリントを配布する

＜参考文献/Reference Book＞

Dieter Jungnickel , Graph， Networks and Algorithms :  Algorithms and Computation in Math. Vol.5 ,  Fourth Ed. .   (Springer-Berlin-Heidelberg-Newyork , 2013) .  ISBN:978-3-642-32277-8  600ppの大著で，英語ですが，記述は丁寧で意外と読みやすい本です． 

 

繁野麻衣子  『ネットワーク最適化とアルゴリズム－シリーズ応用最適化4－』初版 (朝倉書店、2010年10月)ISBN:978-4-254-11789-9 日本語で専門家により書かれた比較的新しい教科書．アルゴリズム中心 
 

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