計算機がもつ情報処理の能力と限界についての理論を扱う。つまり問題を解くためにどのような仕組やどれほどの資源を要するか、またそれによって測られる「問題の困難さ」がどのような構造をなすかを論ずる。計算理論はこのような興味から、今日のような電子計算機のまだ現れない1930年代に数学者や論理学者による考察から始まり、計算機技術の発達や普及とともに発展して来た。本講義はこのように理論的な面白さと実際的意義を併せ持った計算量理論への入門として、以下の事柄を中心に解説する。
なし。配布資料を用いる。
ここを見て下さい。
中間試験と期末試験を行う。
演習問題はムードルにあります。ここにあるものと大体同じですが、少し更新しているのでムードルにあるものを使って下さい(講義の進行とともにちょっとづつ書換えるので、毎週課題をやる前にムードルからダウンロードして下さい)。
回 | 月日 | スライド | 内容 |
---|---|---|---|
一 | 4月8日 | 概要 | |
二 | 4月15日 | 問題と機械(1) | |
三 | 4月22日 | 問題と機械(2) | |
四 | 5月13日 | 時間限定 | |
五 | 5月20日 | 計算状況と模倣 | |
六 | 5月27日 | 空間限定 | |
七 | 6月3日 | 非決定性と乱択(1) | |
八 | 6月10日 | 中間試験+非決定性と乱択(2) | |
九 | 6月17日 | 帰着 | |
十 | 6月24日 | 困難性(1) | |
十一 | 7月1日 | 困難性(2) | |
7月8日 | (休講) | ||
十二 | 7月22日 | 最適化と近似 | |
十三 | 7月29日 | まとめ、演習の残り | |
8月5日 | 期末試験 |
スライド等で説明をする。
課題(問)を配布する。演習は答案の提出と黒板での発表からなる。この演習による得点は随時ウェブ頁に掲げるので確認せよ。
三人以内の連名で提出できる。相手は問ごとに異なってよい。提出は問単位で一度限りとし、再び提出されたものは無効。例えば或る問の(1)まで提出したら(2)以降は諦めたものとして扱う。提出先はムードルに設ける。
急病などの特別な事情による場合を除き、締切(必須の問は次回講義の前日まで、それ以外は8月6日(火)(下記の「平日二日以内の遅延」を含めて8日(木)))に遅れた答案は無効。そのような事情のときは書面での説明と証拠を要するが、学期全体で二度まで(同日締切の問のみ纏めて一度と数える)に限りそれぞれ平日二日以内の遅延を無審査で認める(三度目の遅延は三回分の証拠を提出しない限り認めない)。配布資料以外のもの(書籍、論文、ウェブ頁、友人など)を参考にした場合は漏れなく記すこと。
配点は問ごとに指定する。但し黒板発表された日以後に提出された答案は得点を三割減じ、後述のようにこれを発表者に与える。
演習の資料中(のうち既に講義で扱った部分)に誤りがあったとき、一箇所につき最初に指摘した者に1点を与える。
対象は前回までに出題された範囲のみ。同じ問に希望者が同時に複数あるときは過去の発表得点が少い者を優先し、同じならば乱択する。一度黒板で正解された問はその後発表できない。発表の際は簡潔に効果的な説明ができるよう準備せよ。配点Xの問の発表がX分間を超えた場合、打ち切ることがある。
黒板で正解を発表した者には、提出による得点とは別に、その問の満点相当の得点を加える。更に以後(当日を含む)に提出された他学生のその問に対する得点の三割を発表者に与える。これら発表による得点は、答案提出時の連名にかかわらず、発表した本人にのみ与える。
中間試験と期末試験を行う。重みは1対2である。いずれも平均点が5割以上6割以下になることを想定した内容である。平均点が5割に満たなかったときは5割になるよう得点を調整する。
出席はとりますか。
とりません。
答案は手書きであるべきか。提出方法の指定はあるか。
手書きであってもなくても構わない。但し提出はムードルで。メール等による提出は不可。
ハンドル名は途中で変えられるか。
はい、ムードルにハンドル名指定用の記入欄があるので、そこに新しいのを出すと上書きされます。
発表は、単に答を黒板に書けばよいのか。
他学生に向けて(河村に向けてではない)、わかりやすく説明せよ。
課題がかなりたくさん出るようですが、全部やる必要あるんですか。
そういう積りではない。全部やるのは多分無理。但し必答問題を指定することがあるので、それは次週までにやって下さい。
他の資料を見たり、受講者どうしで相談しても構わないか。
構わない。その場合は答案に適切に記すこと。
○○学科の者ですが、履修できますか。
それを決めるのは○○学科であるはずなので、そちらで規則を調べたり問合せたりして下さい。
初回(4月8日)に行けなかったが、履修できるか。
どうぞ。但しムードルにある演習の問A.1を提出して下さい。
必須問を出せなかったことがあるんですが、どうなりますか。
必須の問は次週に解説することがあるので、以後は(上述の二日遅延枠を除き)提出できなくなります。それ以外の減点などは特にありません。