計算量理論 演習問題

計算量演習.pdf

計算量理論を学ぶための演習問題です。東大での講義演習、京大での集中講義で使ったものをもとに、独習できるよう少し説明を加えたので公開します。通常の教科書よりも簡素な説明ですが、自力で解き進めることで要点をむしろ短時間で深く理解できることを目指しています。

計算量理論とは

問題を計算機で解く困難さについて理解することを目指す理論です。実際の算法(アルゴリズム)設計の指針として役立つ知識であるとともに、困難さそのもののなす構造の解明を目指して活溌に理論研究がなされている分野でもあります。

この演習では片方の立場に偏せず、どちらの興味をもつ人にとっても基礎となる共通部分を扱っています。(もう少し詳しくいうと、1~4節が本当の基礎的な共通部分で、5節、6節は若干それぞれ理論側、応用側の話といえます。まだ5~6節が貧弱なので、そのうち拡充したい。)

予備知識・解答など

高校数学のほかには予備知識は特に要らない積り。でも簡単なプログラミングの経験などがあった方が読み易いかもしれません。

解答はありませんがメールで質問を頂ければ答えます(どこの学生さんでも遠慮なくどうぞ)。随時改訂していますので、細かい誤りの御指摘から、「ここがわからなかった」「○○についての説明は?」など、御意見・御感想を頂ければ幸いです。

他の資料など

良い参考書はありますか?

こちらを見て下さい