| 日付 | 講義内容 | 講義メモ |
第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 |