講義名
アルゴリズム論
開講時限・場所
木曜２限 ７号館００７号室
担当教員
今井浩
評価基準
レポート
課題
締め切りは7月末。レポートボックスに提出
持ってる分だけ上げます。チラッ -- fujima 2013-07-26 14:05:22
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 2013-07-26 14:05:22)
- S.Arora B.Barak Computational Complexity - A Modern Approach 2009 で IP = PSPACE を読んで感想を述べよ。
- #3SATでの dishonest prover が最後まで逃げ切れる例を作れ。 (n = 3,4,5 m = 2,3,4,5 などで。)