##master-page:LecturePageTemplate
#format wiki
#language ja
= 講義名 =
アルゴリズム論
== 開講時限・場所 ==
木曜２限　７号館００７号室
== 担当教員 ==
今井浩
== 評価基準 ==
レポート
== 課題 ==
締め切りは7月末。レポートボックスに提出

持ってる分だけ上げます。チラッ -- [[fujima]] <<DateTime(2013-07-26T14:05:22+0900)>>

 * Randomized selection algorithm でパラメータをチューニングしてk番目に小さな数を n + k + sqrt(n) * (log(n))^{O(1)} ステップ (成功確率 > 1 - O(1)) で求めることが出来ることを示せ。
 * 定理「任意のCNF論理式phiに対し、m/2節充足する truth assignment が存在する。(ただしmはphiの節数)」に関する、講義中での確率的な議論を determinize せよ。
 * MAXSATのLP-based randomized rounding の determinized について論ぜよ。
 * SDP (SemiDefinite Programming) の視点から、MAXSATについて議論せよ。(近似比0.878を達成できる！)
 * 3SATに対するMarcov Chain を考えて、解析せよ。
(ここまでで複数個提出せよ。)
 * #DNF の PRAS について論ぜよ。
(ここに2週間の空白。ここ以外にサボってないかは覚えていない。 -- [[fujima]] <<DateTime(2013-07-26T14:05:22+0900)>>)
 * S.Arora B.Barak Computational Complexity - A Modern Approach 2009 で IP = PSPACE を読んで感想を述べよ。
 * #3SATでの dishonest prover が最後まで逃げ切れる例を作れ。 (n = 3,4,5 m = 2,3,4,5 などで。)


----
[[Category5年夏学期授業]]