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

• 担当教官
  • 安藤和敏 (静岡大学工学部)
• レポート課題について
• 教科書と参考書
  
  • [教科書]
    • V.V. ヴァジラーニ: 近似アルゴリズム. シュプリンガー・フェアラーク, 2002年.
  • [参考書]
    • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver: Combinatorial Optimization. John Wiley & Sons, 1997.
    • 浅野孝夫, 今井浩: 計算とアルゴリズム . オーム社, 2000年.
    • 茨木俊秀: Cによるアルゴリズムとデータ構造 . 昭晃社, 1999年.
    • R. セジウィック: アルゴリズムC (全3巻) . 近代科学社, 1996年.
• 講義内容
  • 第1回 [2004.04.12] (安藤) ガイダンス
  • 第2回 [2004.04.19] (安藤) 第1章 はじめに
  • 第3回 [2004.04.26] (白川) 第2章 集合カバー 2.1 グリーディーアルゴリズム
  • 第4回 [2004.05.10] (白川) 第2章 集合カバー 2.2 層別化
  • 第5回 [2004.05.17] (白川) 第2章 集合カバー 2.2 層別化
  • 第6回 [2004.05.24] (岡田) 第3章 シュタイナー木とTSP 3.1 メトリックシュタイナー木
  • 第7回 [2004.05.31] (岡田) 第3章 シュタイナー木とTSP 3.2 メトリックTSP
  • 第8回 [2004.06.07] (山崎) 第4章 多分割カットと k-カット 4.1 多分割カット問題
  • 第9回 [2004.06.14] (山崎) 第4章 多分割カットと k-カット 4.2 最小k-カット問題,
    (土田) 第5章 k-センター 5.1 パラメトリック刈取り法のメトリックk-センター問題への適用
  • 第10回 [2004.06.21] (土田) 第5章 k-センター 5.1 パラメトリック刈取り法のメトリックk-センター問題への適用
  • 第11回 [2004.06.28] (土田) 第5章 k-センター 5.2 重み付き版
  • 第12回 [2004.07.05] (水越) 第2章 集合カバー 2.3 最短拡大ストリング問題への応用
  • 第13回 [2004.07.12] (水越) 第2章 集合カバー 2.3 最短拡大ストリング問題への応用
  • 第14回 [2004.07.16] (水越) 第7章 最短拡大ストリング 7.1 近似率4のアルゴリズム