本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

実際の授業をいくつか文書におこしてみました。先生方の仮想講義を体験してみてください。情報科学科の講義は90分授業です。午前中の講義は10時15分から、午後の講義は13時から始まります。14時45分からの講義がある曜日もあります。

計算量理論 | 今井 浩
開講時間:火曜2限 | 1
シラバス
TM、計算量、NP 完全、近似アルゴリズム。
概要
計算量理論の授業では、ある問題をコンピュータで解くことがどれだけ難しいのかということを議論していく。この議論の中で、いくつかの問題が「同じくらい難しい問題のグループ」に分けられること、そしてそれらに対するいくつかのアプローチを紹介する。
授業の内容について
計算量理論では、問題を計算することの難しさに関することを学びます。つまりは、コンピュータでその問題を解くのが、簡単なのか、難しいのかだとか、解くのにどれくらいの時間かかるのか、というようなことについて学びます。

例えば、「n個の数字を小さい順に並べる」というようなソートの問題を考えて見ます。こうしたソートのアルゴリズムにはいろいろなものが考え出されており、(2年生冬学期必修の「アルゴリズムとデータ構造」で習います)バブルソート、挿入ソートだったら、O(n^2)時間かかるだとか、クイックソート、ヒープソートだったら、O(nlogn)時間かかるということがわかっています。上記にあげた中では、O(nlogn)時間が最も短いということになりますが、今度は果たしてそれがベストな解かということが問題になってきます。つまり、「どういうアルゴリズムを考えてもソートはO(nlogn)時間以下では計算できない」ということを確かめていく(つまり、その問題の難しさを決定していく)のが、計算量理論の問題のひとつです。

※O(N)時間というのは計算量がオーダーNの時間であることを意味し、問題を解くのにNの定数倍の関数で抑えられる計算時間がかかることを意味します。 ()内は問題サイズn(ソートの問題ならば、並べ替える数字の個数が問題のサイズになります。)の関数によって表されます。

そして、この「O(N)時間以下では計算できない」という計算時間のオーダーによって、問題の難しさが定義され、その難しさによって問題が分類されます。この分類は大きく、「決定不能」「決定可能」に分けられ、決定可能なものの中では「指数時間」(サイズnの問題を解くのにO(M^n)時間かかる)と「多項式時間」(サイズnの問題を解くのにO(n^M)時間かかる)に分けることができます。講義の中では、この「指数時間」の問題と「多項式時間」の問題について詳しく扱っていきます。

この指数時間の問題は、問題サイズが大きくなると「指数爆発」(爆発的な関数値の増加。指数関数のグラフを思い出してみてください。)を起こしてしまいます。そのため、問題サイズの大きい指数時間の問題を解くには、何十万、何百万以上もの時間が必要になるため、指数時間の問題は実際には「解けない」問題になってしまいます。そこで、指数時間の問題(解けない)と多項式時間の問題(解ける)を区別していくことが、問題の難しさを考える上で大事になってきます。

こうした問題の計算時間は、Turing Machine(以下TM)(既出ですか?説明必要?)を用いて定義されます。そして、TMを用いて多項式時間で計算できる問題クラス(=「多項式時間の問題」)を「P」と表現します。情報科学に関連する話題の中で、時折耳にするであろう「NP」「NP完全」という言葉は、こういった問題クラスの名前です。 NP、NP完全の具体的な定義や、その意義については、授業のなかでメイントピックとして詳しく扱っていきますので、お楽しみに!

この授業の軸になる計算時間の定義はTMによって行われるので、TMの復習や、また、グラフ理論との関連も深いので、3年夏学期必修の「離散数学」の復習もしておくと理解が楽になると思います。

「情報科学演習2」(3年冬学期 必修)では、この計算量理論と、連続系アルゴリズムの講義に関する演習を行います。この演習によって、計算量理論の講義の理解を深めることができます。


授業の進行
授業は板書で進んでいくので、しっかりノートをとることが大切です。先生いわく、板書のスピードで説明できる量がちょうど良い授業内容の量なんだとか?また、口頭での説明も詳しく行ってくれるので、その説明をしっかり聞いて、必要に応じてメモを取るとよいでしょう。

授業はじめのお話は、授業内容には関係ありませんが、きちんと聞いておくとためになります。
試験について
授業に加えて演習までしっかり消化しておくと良いと思います。重要な概念を理解しているかということはもちろんのこと、問題のNP完全性を示せ、というようなものや、問題に対する多項式時間のアルゴリズムを与えよ、といったものが出題されます。
参考書
参考書として、以下の本が挙げられています。中身が英語なので読むのは楽ではありませんが、内容はわかりやすい、と思います。

Computers and Intractability: A Guide to the Theory of Np-Completeness
Michael R. Garey and David S. Johnson \\
W H Freeman & Co (Sd) (1979/06)