計算量理論

• 九州大学理学部　平成31年度前期月曜二限

• ムードル（課題提出用）
• 質問などはこちらのメールアドレスにどうぞ

更新履歴

• ［8月7日］採点済答案をムードルで返却しました。
• ［8月5日］本日の期末試験の採点結果をムードルに載せました。但し気象状況のため、8月6日（火）に予定していたウエスト二号館956室前での答案返却は中止します。返却方法は後日追記します。
• ［7月22日］第十二回資料を掲載。
• ［6月30日］第十一回資料を掲載。7月8日は休講です。
• ［6月24日］第十回資料を掲載。
• ［6月16日］第九回資料を掲載。
• ［6月10日］第八回資料を掲載。
• ［6月2日］第七回資料を掲載。中間試験の日（6月10日）は黒板発表はやりません（6月3日分の必須課題は16日までにやって下さい）。
• ［5月27日］第六回資料を掲載。
• ［5月20日］第五回資料を掲載。中間試験は6月10日に行います。
• ［5月13日］第四回資料を掲載。
• ［4月22日］第三回資料を掲載。
• ［4月15日］第二回資料を掲載。
• ［4月8日］ウェブ頁を開設。第一回資料を掲載。

概要

計算機がもつ情報処理の能力と限界についての理論を扱う。つまり問題を解くためにどのような仕組やどれほどの資源を要するか、またそれによって測られる「問題の困難さ」がどのような構造をなすかを論ずる。計算理論はこのような興味から、今日のような電子計算機のまだ現れない1930年代に数学者や論理学者による考察から始まり、計算機技術の発達や普及とともに発展して来た。本講義はこのように理論的な面白さと実際的意義を併せ持った計算量理論への入門として、以下の事柄を中心に解説する。

• 機械的な処理とは（アルゴリズムとプログラム）
• 計算機構とその限界（有限状態機械、チューリング機械）
• 計算資源（時間、空間）とその量（対数、多項式、指数）
• P≠NP予想とは（発見と検証）
• 計算量の比較と分類（帰着と完全問題）

教科書

なし。配布資料を用いる。

参考書

ここを見て下さい。

試験

中間試験と期末試験を行う。

講義予定と資料

演習問題はムードルにあります。ここにあるものと大体同じですが、少し更新しているのでムードルにあるものを使って下さい（講義の進行とともにちょっとづつ書換えるので、毎週課題をやる前にムードルからダウンロードして下さい）。

在室時間

→こちら

講義の進め方

講義

スライド等で説明をする。

演習

課題（問）を配布する。演習は答案の提出と黒板での発表からなる。この演習による得点は随時ウェブ頁に掲げるので確認せよ。

提出

三人以内の連名で提出できる。相手は問ごとに異なってよい。提出は問単位で一度限りとし、再び提出されたものは無効。例えば或る問の（1）まで提出したら（2）以降は諦めたものとして扱う。提出先はムードルに設ける。

急病などの特別な事情による場合を除き、締切（必須の問は次回講義の前日まで、それ以外は8月6日（火）（下記の「平日二日以内の遅延」を含めて8日（木）））に遅れた答案は無効。そのような事情のときは書面での説明と証拠を要するが、学期全体で二度まで（同日締切の問のみ纏めて一度と数える）に限りそれぞれ平日二日以内の遅延を無審査で認める（三度目の遅延は三回分の証拠を提出しない限り認めない）。配布資料以外のもの（書籍、論文、ウェブ頁、友人など）を参考にした場合は漏れなく記すこと。

配点は問ごとに指定する。但し黒板発表された日以後に提出された答案は得点を三割減じ、後述のようにこれを発表者に与える。

演習の資料中（のうち既に講義で扱った部分）に誤りがあったとき、一箇所につき最初に指摘した者に1点を与える。

発表

対象は前回までに出題された範囲のみ。同じ問に希望者が同時に複数あるときは過去の発表得点が少い者を優先し、同じならば乱択する。一度黒板で正解された問はその後発表できない。発表の際は簡潔に効果的な説明ができるよう準備せよ。配点Xの問の発表がX分間を超えた場合、打ち切ることがある。

黒板で正解を発表した者には、提出による得点とは別に、その問の満点相当の得点を加える。更に以後（当日を含む）に提出された他学生のその問に対する得点の三割を発表者に与える。これら発表による得点は、答案提出時の連名にかかわらず、発表した本人にのみ与える。

試験

中間試験と期末試験を行う。重みは1対2である。いずれも平均点が5割以上6割以下になることを想定した内容である。平均点が5割に満たなかったときは5割になるよう得点を調整する。

補足・注意

• 得点表に出る名前（初期値は姓、随時変更可能）を変えたい人はムードルのハンドル名提出欄に書いておいて下さい。
• 三割献上は時刻は考慮せず発表当日提出分から適用。自力で正解しても前日（通常は日曜）までに出さないと発表者に三割吸い取られます。

補足

講義全般について