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

• 担当教官
  • 安藤和敏 (静岡大学工学部)
• 試験について
• 教科書と参考書
  
  • [教科書]
    • 藤重悟: グラフ・ネットワーク・組合せ論. 共立出版, 2002年. [著者によるサポートのページ]
  • [参考書]
    • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver: Combinatorial Optimization. John Wiley & Sons, 1997.
    • 浅野孝夫, 今井浩: 計算とアルゴリズム . オーム社, 2000年.
    • R. セジウィック: アルゴリズムC (全3巻) . 近代科学社, 1996年.
• 講義内容
  • 第01回 [2006.04.10] ガイダンス
  • 第02回 [2006.04.17] 最大フロー問題とFord-Fulkersonのアルゴリズム
    ハンドアウト (PDF)
    [宿題] 以下のネットワークの最大フローを求めよ.
  • 第03回 [2006.04.24] 最小カット問題
    ハンドアウト (PDF)
    [レポート課題] 以下のネットワークの最大フローと最小カットを求めよ.
  • 第04回 [2006.05.01] 全ての最小カットを見付ける (1)
    テキスト: 補題2.8, 補題2.9, 定理2.8
    [宿題] 上の図で表現されるネットワークの全ての最小カットを求めよ.
  • 第05回 [2006.05.08] 全ての最小カットを見付ける (2)
    [レポート課題] PDF.
  • 第06回 [2006.05.15] 2.4.1 最大マッチング・最小被覆定理
    ハンドアウト (PDF)
    [レポート課題] あり.
  • 第07回 [2006.05.22] 2.4.2 ダルメジ-メンデルゾーン分解
  • 第08回 [2006.05.29] 中間試験(持ち込み不可)
  • 第09回 [2006.06.05] 最短路問題I ハンドアウト (PDF)
    [レポート課題] あり.
  • 第10回 [2006.06.12] 最短路問題II ハンドアウト (PDF)
    [レポート課題] あり.
  • 第11回 [2006.06.19] 最短路問題III ハンドアウト (PDF)
    [レポート課題] あり.
  • 第12回 [2006.06.26] 最短路問題IV ハンドアウト (PDF)
    [レポート課題] あり.
  • 第13回 [2006.07.03] 最小費用フロー問題 ハンドアウト (PDF)
    [レポート課題] あり.
  • 第14回 [2006.07.10] 最小費用フロー問題 ハンドアウト (PDF)
    [レポート課題] あり.
  • 第15回 [2006.07.24] 期末試験(持ち込み不可)