平成25年度計算量演習(情報科学演習二)

情報科学演習二(0510023、理学部七号館214室、2単位)のうち「計算量理論」の演習です
http://www-imai.is.s.u-tokyo.ac.jp/~kawamura/teaching/enshu2/

答案用紙.pdf

メールでの質問歓迎→kawamura@is.s.u-tokyo.ac.jp

問(配布資料)

配布A締切B締切C締切内容
第一回.pdf10月11日10月11日10月17日11月8日漸近記法、計算資源の評価
第二回.pdf10月25日10月25日10月30日11月22日チューリング機械、時間限定
第三回.pdf11月8日11月8日11月13日12月13日空間限定、回路
第四回.pdf11月22日11月22日11月27日年内非決定性と乱択
第五回.pdf12月13日12月13日12月18日1月10日帰着と完全問題
第六回.pdf12月22日なし1月8日1月24日探索問題と最適化問題(このウェブページでの配布のみ)
第七回.pdf1月10日1月10日1月16日1月31日神託と相対化
第八回.pdf1月24日1月24日の
二限終了時
1月24日まとめ

月曜一限の試問:11月11日(月)、1月15日(水)
月曜一限の質問時間:1月27日(月)

演習の進め方

七回程度に分けて課題(問)を配布する。問にはABCの三種がある。前回までの内容を参照する問もあるので配布資料は計算量理論の講義ノートとともに毎回持参せよ。演習は答案の提出と黒板での発表からなる。

提出

三人以内の連名で提出できる。相手は問ごとに異なってよい。提出は問ごととし一度出したら撤回できない。例えば或る問の(1)まで提出したら(2)以降は諦めたものとして扱う。締切は原則としてAが配布当日、Bが平日三日後、Cは数週間後の指定する日。詳しくは上の表の通り。提出先は七号館一階事務室前のレポート箱、又は演習当日に担当教員へ。ホチキス等で綴じず、所定の用紙(又は同じ情報を紙面上部に記載)の片面のみを使う。一問が二枚以上に及ぶときは繫がりが判るように書く。採点の都合上A、B、Cで紙を分けること。

レポート箱への提出日の判定は事務室印による。急病など已むを得ざる事情による場合を除き、締切に遅れた答案は採点しない。そのような事情のときは書面での説明と証拠を要するが、学期全体で二度まで(同日締切の問のみ纏めて一度と数える)に限りそれぞれ平日二日以内の遅延を無審査で認める(三度目の遅延は三回分の証拠を提出しない限り認めない)。配布資料と講義ノート以外のもの(書籍、論文、ウェブ頁、友人など)を参考にした場合は漏れなく記すこと。これを怠ることは剽窃(盗作)にあたるから厳正に対処する。

満点はAが一問8点、Bは10点、Cは問ごとに指定。但し黒板発表された日以後に提出されたCは得点を半減する。

発表

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

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

評価

この合計得点に次を満す或る単調非減少函数を掛けたものを計算量演習の評点(満点50)とする。

但し全員AとBは提出し、学期中に少くとも一度は発表をすること。

補足