計算量理論

得点表

更新履歴

概要

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

教科書

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

参考書

ここを見て下さい。

試験

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

講義予定と資料

月日スライド内容
4月9日PDF概要(1)/形式言語理論の復習
4月16日PDF概要(2)/計算可能性理論の復習
4月23日PDF資源の限定と上下界
5月7日PDF時間限定(1)
5月14日PDF時間限定(2)
5月21日PDF計算状況と模倣
5月28日PDF空間限定[中間試験範囲ココマデ]
6月4日PDF非決定性と乱択(1)
6月11日PDF中間試験
6月18日PDF非決定性と乱択(2)
十一6月25日PDF帰着と困難性(1)
十二7月2日PDF帰着と困難性(2)
(休講)7月9日
十三7月12日PDF最適化と近似[期末試験範囲ココマデ]
十四7月23日PDF雑談、演習の残り
7月30日結果PDF期末試験

必答

次の問は全員(次回講義の前日までに)提出せよ。

在室時間

→こちら

講義の進め方

講義

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

演習

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

提出

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

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

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

演習の資料中に誤りがあったとき、一箇所につき最初に指摘した者に1点を与える。

発表

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

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

試験

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

補足・注意

補足

講義全般について

出席はとりますか。

とりません。[4月9日追記]

演習と試験の比率は。

第一回スライドに追記しました。[4月9日追記]

答案は手書きであるべきか。提出方法の指定はあるか。

手書きであってもなくても構わない。但し提出はムードルで。メール等による提出は不可。

ハンドル名は途中で変えられるか。

はい、ムードルにハンドル名指定用の記入欄があるので、そこに新しいのを出すと上書きされます。

発表は、単に答を黒板に書けばよいのか。

他学生に向けて(河村に向けてではない)、わかりやすく説明せよ。

課題がかなりたくさん出るようですが、全部やる必要あるんですか。

そういう積りではない。全部やるのは多分無理。但し必答問題を指定することがあるので、それは次週までにやって下さい。

他の資料を見たり、受講者どうしで相談しても構わないか。

構わない。その場合は答案に適切に記すこと。

○○学科の者ですが、履修できますか。

それを決めるのは○○学科であるはずなので、そちらで規則を調べたり問合せたりして下さい。

初回(4月9日)に行けなかったが、履修できるか。

どうぞ。但しムードルにある演習の問0.1(第一~二回資料の末尾の問6.1)を提出して下さい。