質問はこちらのメールアドレスへどうぞ(→質問・回答集)
配布 | A締切 | B締切 | C締切 | 内容 | ||
第一回 | 10月10日 | 10月10日 | 10月17日 | 11月7日 | 漸近記法、計算資源の評価 | |
第二回 | 10月24日 | 10月24日 | 10月31日 | 11月21日 | 問題と算法、時間限定 | |
第三回 | 11月7日 | 11月7日 | 11月14日 | 12月5日 | 空間限定、帰着 | |
第四回 | 11月21日 | 11月21日 | 11月28日 | 12月19日 | 非決定性と乱択 | |
第五回 | 12月5日 | 12月5日 | 12月12日 | 1月16日 | 完全問題 | |
第六回 | 12月19日 | 12月19日 | 1月8日 | 1月16日 | 最適化と近似 | |
第七回 | ウェブ配布 | なし | 1月13日 | 1月23日 | 神託と相対化 | |
第八回 | 1月16日 | その場で | 1月20日 | まとめ |
12月22日(月)一限(発表の済んでいない人のみ)
七回程度に分けて課題(問)を配布する。問にはABCの三種がある。前回までの内容を参照する問もあるので配布資料は計算量理論の講義ノートとともに毎回持参せよ。演習は答案の提出と黒板での発表からなる。
三人以内の連名で提出できる。相手は問ごとに異なってよい。提出は問単位で一度限りとし、再び提出されたものは無効。例えば或る問の(1)まで提出したら(2)以降は諦めたものとして扱う。締切は原則としてAが配布当日、Bが次週末、Cは数週間後の指定する日。詳しくは上の表の通り。提出先は七号館一階事務室前のレポート箱、又は演習当日に手渡し。ホチキス等で綴じず、所定の用紙(又は同じ情報を紙面上部に記載)の片面のみを使う。一問が二枚以上に及ぶときは繫がりがわかるように書く。採点の都合上A、B、Cで紙を分けること。
レポート箱への提出日の判定は事務室印による。急病など已むを得ざる事情による場合を除き、締切に遅れた答案は無効。そのような事情のときは書面での説明と証拠を要するが、学期全体で二度まで(同日締切の問のみ纏めて一度と数える)に限りそれぞれ平日二日以内の遅延を無審査で認める(三度目の遅延は三回分の証拠を提出しない限り認めない)。配布資料と講義ノート以外のもの(書籍、論文、ウェブ頁、友人など)を参考にした場合は漏れなく記すこと。これを怠ることは剽窃(盗作)にあたるから厳正に対処する。
満点はAが一問8点、Bは10点、Cは問ごとに指定。但し黒板発表された日以後に提出されたCは得点を三割減じ、後述のようにこれを発表者に与える。
対象は前回までに配布したBまたはCのみ。同じ問に希望者が同時に複数あるときは過去の発表得点が少い者を優先し、同じならば乱択する。一度黒板で正解された問はその後発表できない。発表の際は簡潔に効果的な説明ができるよう準備せよ。配点Xの問の発表がX分間を超えた場合、打ち切ることがある。
黒板で正解を発表した者には、提出による得点とは別に、その問の満点相当の得点を加える。更にCについては以後(当日を含む)に提出された他学生のその問に対する得点の三割を発表者に与える。これら発表による得点は、答案提出時の連名にかかわらず、発表した本人にのみ与える。
以上の提出・発表による得点は随時このウェブ頁に掲げるので確認せよ。この合計得点に次を満す或る単調非減少函数を掛けたものを計算量演習の評点(満点50)とする。なお以下の「○割」は問の個数でなく配点における割合である。
但し全員AとBは提出し、学期中に少くとも一度は発表をすること。