NP完全理論を90分で講義

投稿者: | 2010年1月22日
過去の講義で何度も使った、Garey & Johnson: ``Computers and Intractability: A Guide to the Theory of NP-Completeness"

過去の講義で何度も使った、Garey & Johnson: ``Computers and Intractability: A Guide to the Theory of NP-Completeness"

卒業研究でロボットやプログラムを作りましたというのは結構なことだが、大学で情報科学を勉強したというのであれば、NP完全の理論くらいは理解して卒業して欲しい。実際、就職試験の問題としても最もよく出題されているのではないか。私も、毎年限られた時間で、NP完全理論の概要を講義している。

昨日の講義では、NP完全理論の一般論を60分、確率的推論がNP困難問題である証明を30分で説明した。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です