http://www.graco.c.u-tokyo.ac.jp/~kawamura/teaching/enshu2/

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

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

日程と締切

配布A締切B締切C締切内容
第一回PDF10月10日10月10日10月17日11月7日漸近記法、計算資源の評価
第二回PDF10月24日10月24日10月31日11月21日問題と算法、時間限定
第三回PDF11月7日11月7日11月14日12月5日空間限定、帰着
第四回PDF11月21日11月21日11月28日12月19日非決定性と乱択
第五回PDF12月5日12月5日12月12日1月16日完全問題
第六回PDF12月19日12月19日1月8日1月16日最適化と近似
第七回PDFウェブ配布なし1月13日1月23日神託と相対化
第八回PDF1月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は提出し、学期中に少くとも一度は発表をすること。

補足・注意

リンク

更新履歴