離散システム論 [2003年度前期]

• 試験について
• 担当教官
  • 安藤和敏 (静岡大学工学部)
• 教科書と参考書
  
  • [教科書]
    • 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回 [2003.04.14] 1.1 Two problems (1. 問題とは何か?; 2. アルゴリズムとは何か?)
    レジュメ (PDF)
  • 第2回 [2003.04.28] 1.2 Measuring running times (アルゴリズムの計算量の評価)
    レジュメ (PDF)
  • 第3回 [2003.05.12] 2.1 Minimum spanning trees (グラフの諸概念)
    レジュメ (PDF)
  • 第4回 [2003.05.19] 2.1 Minimum spanning trees (補題 2.1--定理 2.3)
  • 第5回 [2003.05.26] 2.1 Minimum spanning trees (定理 2.4--定理 2.6)
  • 第6回 [2003.06.02] 2.1 Minimum spanning trees (1. Prim のアルゴリズムの復習; 2. Prim のアルゴリズムの計算量)
    レジュメ (PDF)
  • 第7回 [2003.06.16] 2.1 Minimum spanning trees (1. Kruskal のアルゴリズムの復習; 2. Union-Find; 3. Kruskal のアルゴリズムの計算量)
  • 第8回 [2003.06.23] 2.2 Shortest paths
  • 第9回 [2003.06.30] 2.2 Shortest paths (Ford's Algorithm)
  • 第10回 [2003.07.07] 2.2 Shortest paths (Validity of Ford's Algorithm)
  • 第11回 [2003.07.14] 2.2 Shortest paths (Refinement of Ford's Algorithm, Ford-Bellman Algorithm)
  • 第12回 [2003.07.18] 2.2 Shortest paths (Acyclic Digraphs, Nonnegative Costs)
  • 第13回 [2003.09.18] 試験