計算量特論 (Advanced Course on Computational Complexity)
(大学院 木曜3-4限(10:20〜11:50,J科大学院講義室(2号館106号室))


講義の概要 :
日常遭遇する様々な情報処理や計算の問題に対して, その本質的な困難さ(〜その問題を解くのに必要とする時間やメモリ量) を明らかにすることを目指す分野である計算量理論 (Computational Complexity Theory)について講義する.
また,授業の前半では,整数計画ソルバを用いたパズルの解法等も行う予定.

教科書:
教科書は用いません.適宜資料を授業中配布/このページに掲載します.

評価 :
2回(予定)出題するレポートによる (試験は行いません).

講義予定 :
下記各参考書の前半部分の内容に 沿いつつ講義する.ただし,関連する話題も適宜取り入れる.
必要なバックグラウンドや,最新のトピック等に関する解説を適宜加える.

ちなみに去年の内容はこちら
日付 講義内容 講義メモ
第1回 4月11日(木) イントロ イントロ
第2回 4月18日(木) 探索問題,決定問題,P,NP, その2と3
第3回 4月25日(木) NP完全,SAT,帰着
第4回 5月9日(木) PとNPとLPとIP,SAT≦IP,IPソルバ,N-Queen資材置き場 アクセス制限で見られない場合にはメールで一報くださいその4
第5回 5月16日(木) 続IP,レポート1出題 その5
第6回 5月23日(木) 続続IP,分枝限定法,平面切除法,MTZ Formulation その6
第7回 5月30日(木) レポート1解説,coNP, MinDNF その7
第8回 6月6日(木) Sigma_2, Pi_2, PH, PSPACE, EXPTIME, オセロチェス倉庫番 その8
第9回 6月13日(木) 回路計算量,Natural Proof その9
第10回 6月20日(木) ストリーミングアルゴリズム,領域計算量 そのA
第11回 6月27日(木) 乱数小噺,Freivals,素数判定 そのB
第12回 7月4日(木) 続乱数,Fermat Test, PRIMES is in Pメイキング,BPPそのC
第13回 7月11日(木) Chernoff Bound, BPP Amplification, k-限定独立,脱乱化 そのD

おすすめ参考書 :
1.M.Sipser 著: Introduction to the Theory of Computation, 3rd Eds.,Thomson (2012)
この分野の定番の教科書.
訳書あり(原著は1冊ですが,訳書は3冊に分かれています.各約3,000円):
計算理論の基礎 [原著第2版] 1.オートマトンと言語 +2.計算可能性の理論+3.複雑さの理論,共立出版,(2008)

2-1. Sanjeev Arora,Boaz Barak 著: Computational Complexity : A Modern Approach (2009)
この講義では,大体1〜7章に相当する部分をカバーの予定.
2-2.Oded Goldreich 著: Computational Complexity : A Conceptual Perspective (2008)
2-3.Avi Wigderson 著: Mathematics and Computation (2018)
この分野の教科書(やや高度).
どれもドラフトが上のリンクから無料でダウンロードできます.

3-1.Automata, Comput, & Complexity (by Scott Aaronson @ UT Austin) の講義資料
3-2.Algorithmic Lower Bounds: Fun with Hardness Proofs (by Erik Demaine @ MIT) の講義ビデオ

基礎とする科目(学部):
離散数学,確率統計,オートマトン理論

関係する科目(大学院):
アルゴリズム論(by 中野先生),計算理論特論 (by 山崎先生)

参考文献:
  • 数理計画法メモ by 宮代先生

    連絡 :
    現在特にありません.


    レポート用 Gurobi のインストール,使い方.超簡易版 (2019.5改)
    注:以下はWindows版です.Linux等の場合はちょっとだけ違うので注意.11番以降は同じです.

    1. アカデミックライセンスのページ(ここ)へ行く.
    2. For University Users へ進む
    3. 以下 Individual Academic Licences の項目に従ってインストールする.
    4. ステップ 1 の Download Gurobi Optimizer をクリック. (Registがまだであれば),Registフォームが出るので Accout Type = Academic にして (重要!), フォームを埋めて Regist する.
    5. ソフト本体 をダウンロード.
    6. ステップ 2 の Free Academic License へ行き,Licence Key を発行.
    7. ダウンロードしたソフト本体 を実行すると勝手にインストールされる.
    8. インストールされたディレクトリの下 (.../gurobi/ なら .../gurobi/win64/bin) (32ビットバージョンなら .../gurobi/win32/bin)に行き, grbgetkey *** を実行. *** は 上で表示されたもの. これで,12ヶ月使用可能な模様.
    (注1:domain 見てるかも知れないので, 大学からやらないといけないかも...)
    (注2:cygwin の terminal 上からだとうまく行かない場合があるようです. そんなときは,DOS窓(コマンドプロンプト)上からトライすると良いかも.)
    9. 再起動しろと言われたらする.
    10. さっきのディレクトリに行き,gurobi.bat を実行すると起動.
    11. 注意いろいろ:CPLEX形式で書いたとき,'+' や '=' の前後にスペース必要な模様. 「係数」と変数の間にもスペース必要.右辺には数字しか書けないので,その他は左辺に移項のこと.
    12. gurobi > m=read("example.lp") で CPLEX 形式読み込み.(シングルクォート,ダブルクォートどちらもOk."m" は好きな名前でOk.その時は以下も併せて変えること)
    13. m.optimize() で計算.
    14. m.printAttr("X") で 非ゼロの値を持ってる変数を出力.
    15. m.write("example.sol")でファイルに結果を出力.拡張子が .sol でないとエラーかも.
    ちなみに,gurobi.log にも結果が出力されていると思われ.
    16. なにかわからないことあれば,まずは,ここ(整数計画法メモ by 宮代先生)を参照すべし.


    最終更新日: 2019.7.10