• 内容
  • 平面グラフ、2部グラフ、Eulerグラフ
  • 最大流・最小カット定理、2部マッチング、Mengerの定理
  • 線形計画法、単体法、双対定理、相補性条件
    • 線形計画単体法説明資料 (pdf file)
  • ネットワークフロー
  • パーフェクトグラフ、区間グラフ
  • マトロイド
  • 参考書 Christos H. Papadimitriou and Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Dover Publication, Unabridged Version, 1998.
  • 参考書　 藤重悟: グラフ・ネットワーク・組合せ論. 工系数学講座, 共立出版, 2002.

• 内容: Turing機械, NP完全性, 近似アルゴリズム, 計算量クラス
  • 冬学期配布資料1 (pdf file)
  • 参考書 M. R. Garey and D. S. Johnson: Computer and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.

• テーマ: 先端アルゴリズム入門
  • ランダム化アルゴリズム(グラフ最小カット)
  • 量子情報処理の必要性
  • 量子暗号
  • 量子アルゴリズム
  • 参考資料 (pdf)

• テーマ：新計算モデルとしての量子非局所性
  • 量子情報パワーの源
  • 量子非局所性・量子エンタングルメント
  • 量子対話証明・計算量理論
  • 参考資料 (pdf)

• 講義テーマ:
  • Randomized Algorithms
    参考書 R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
    Number Theory and Algebras, Algebraic Techniques, hashing, distributed algorithms

• with Tetsuo Shibuya, Francois Le Gall

Last updated 2011-06-11