離散システム論 [2010年度前期] (終了)

• シラバス (HTML)
• 担当教官
  • 安藤和敏 (静岡大学工学部)
• 試験と成績の評価について (2010.08.19 更新)
• テキスト
  • V. フバータル: 「線形計画法(上)」 啓学出版, 1986年.
  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver: Combinatorial Optimization . John Wiley & Sons, 1997.
• 参考書
  • 藤重悟: グラフ・ネットワーク・組合せ論. 共立出版, 2002年. [著者によるサポートのページ]
• 講義内容
  • 第01回 [2010.04.09] ガイダンス.
  • 第02回 [2010.04.16] 線形計画法(第1章 p. 3--8)
  • 第03回 [2010.04.23] 線形計画法(第2章 p.17--22くらいまで)
  • 第04回 [2010.05.07] 線形計画法(第2章 p.23--29)
  • 第05回 [2010.05.14] 線形計画法(第3章 p.34--40, p.49)
  • 第06回 [2010.05.21] 線形計画法(第3章 p.49-54)
  • 第07回 [2010.05.28] 線形計画法(第5章 p.69-73双対定理の直前まで)
  • 第08回 [2010.06.04] 線形計画法(第5章 p.73-79)
  • 第09回 [2010.06.11] 中間試験
  • 第10回 [2010.06.18] 試験問題の解説, 相補性定理の復習, 一般的な双対定理と相補性
  • 第11回 [2010.06.25] 最大フロー問題 (フローとカット)
  • 第12回 [2010.07.02] 最大フロー問題 (最大フロー最小カット定理の証明, 最小カットと線形計画法)
  • 第13回 [2010.07.09] 最短路問題 (可能ポテンシャルとフォードのアルゴリズム)
  • 第14回 [2010.07.16] 最小費用フロー問題(プライマルアルゴリズム, 相補性条件)
  • 第15回 [2010.07.23] 最小費用フロー問題(最適性の条件)
  • 期末試験 [2010.07.30]
• 課題 (提出先はシステム棟5Fエレベータホールのレポート提出Box)
  • 課題1 (提出期限 2010.04.22)
    テキスト第1章章末(p.11-12)の問題1.1, 問題1.2, 問題1.4.
    ただし1.1については, 標準形でない問題を標準形に直しなさい.
  • 課題2 (提出期限 2010.04.30; 17:00)
    テキスト第2章の章末(p.33)の問題2.1.
  • 課題3 (提出期限 2010.05.28; 17:00)
    テキスト第3章の章末(p.56)の問題3.9.
  • 課題4 (提出期限 2010.06.02; 17:00)
    テキスト第2章の章末(p.33)の問題2.1a,b,cの双対問題を示せ. (提出期限が少し早いので注意.簡単な問題なので.)
  • 課題5 (提出期限 2010.06.24; 17:00) PDF
  • 課題6 (提出期限 2010.07.08; 17:00) PDF