到達目標
(1) 計算可能性理論について理解する．(定期試験と課題)
(2) 計算量理論について理解する．（定期試験と課題）
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 到達目標(1)の評価指標 | 計算可能性理論について，他者に説明できるレベルで理解している． | 計算可能性理論について，講義で取り上げた例題を解くことができる． | 計算可能性理論について，基本的な概念の定義や用語の定義を述べることができない． |
| 到達目標(2)の評価指標 | 計算量理論について，他者に説明できるレベルで理解している． | 計算量理論について，講義で取り上げた例題を解くことができる． | 計算量理論について，基本的な概念の定義や用語の定義を述べることができない． |
学科の到達目標項目との関係
学習・教育目標 (B2)
説明
閉じる
JABEE 1.2(c)
説明
閉じる
JABEE 1.2(d)(1)
説明
閉じる
JABEE 1.2(g)
説明
閉じる
教育方法等
概要:
本講義では，コンピュータプログラムで解ける問題とはどのような問題か，また効率的な解法が存在する問題とはどのような問題かという根本的な問いについて考察する．
(科目情報)
教育プログラム 第2学年 ◎科目
授業の進め方・方法:
原則として毎回，授業内容の理解を問う課題を課すので，授業を良く聞いて理解に努めること．
(参考図書)
[1] MacCormick, J.，計算できるもの，計算できないもの，オライリー・ジャパン．
[2] シプサ, M.，計算理論の基礎，共立出版．
[3] 川添愛，白と黒のとびら，東京大学出版会．
(事前学習)
参考図書 [1] の該当箇所を読んでおくことが望ましい．
注意点:
(履修上の注意)
配布プリントを整理するためのクリアファイル(A4サイズ)を用意すること．
(自学上の注意)
参考図書の必要箇所を参照して予習・復習を行うこと．授業内容は [1] に基づく．
評価
(総合評価)
総合評価 = 定期試験 × 0.7 + 課題 × 0.3
(再試験について)
前期末試験終了後の適切な時期に実施する．受験資格者については試験解説時にアナウンスする．
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
イントロダクション (計算不能問題 / なぜ計算理論を学ぶのか / コンピュータプログラムとは何か 他) |
授業の概要を理解する
|
| 2週 |
不可能なPythonプログラム (背理法 / 他のプログラムを解析するプログラム / 完璧なバグ検出プログラムは存在しない 他) |
計算不能問題について理解する
|
| 3週 |
計算問題とは何か (計算問題の定義 / 問題を「解く」ことの形式的な定義 / 言語の認識と判定 他 ) |
計算問題の定義を理解する
|
| 4週 |
チューリングマシン：最も単純なコンピュータ (チューリングマシンの定義 / 古典的コンピュータは量子コンピュータをシミュレートできる / 全ての既知のコンピュータはチューリング等価である 他) |
チューリングマシンの概要について理解する
|
| 5週 |
万能コンピュータプログラム (万能Pythonプログラム / 万能チューリングマシン / 他のプログラムを書き換えるプログラム 他) |
万能チューリングマシンについて理解する
|
| 6週 |
還元：問題が難しいことを証明する方法 (やさしいことを示すための還元 / 難しいことを示すための還元 / 計算不能問題の多さ 他 ) |
還元について理解する
|
| 7週 |
非決定性：手品か現実か (非決定性Pythonプログラム / 計算木 / 非決定性チューリングマシン 他) |
非決定性について理解する
|
| 8週 |
有限オートマトン：限られた資源による計算 (決定性有限オートマトン (DFA) / 非決定性有限オートマトン (NFA) / 正規表現 他) |
有限オートマトンと正規表現について理解する
|
| 2ndQ |
| 9週 |
前期中間試験 |
到達目標(1)
|
| 10週 |
前期中間試験の解答と解説・計算量理論：効率が重視されるとき (ビッグオー記法 / プログラムの実行時間 / 計算量クラス 他) |
計算量理論の概要について理解する
|
| 11週 |
クラスPolyとクラスExpo：もっとも根本的な2つの計算量クラス (クラスPolyとクラスExpoの定義 / HaltEx問題 / 入力の不合理な符号化方法は計算量に影響を与える 他) |
クラスPolyとクラスExpoについて理解する
|
| 12週 |
クラスPolyとクラスNPoly：簡単に検証できる難しい問題 (多項式時間検証器 / 計算量クラスPolyCheck / 計算量クラス NPoly 他) |
クラスPolyCheckとクラスNPolyについて理解する
|
| 13週 |
多項式時間写像還元：XはYと同じくらい易しいことの証明 (多項式時間写像還元の定義 / ハミルトン閉路での多項式時間還元の例 / 3つの充足可能性問題 (CircuitSat, Sat, 3-Sat) ほか) |
多項式時間写像還元について理解する
|
| 14週 |
NP完全性：最も難しい問題の難しさの程度は同じである (P≠NP問題 / NP完全性 / P=NPならどうなるか 他) |
NP完全性について理解する
|
| 15週 |
前期期末試験 |
到達目標(2)
|
| 16週 |
前期期末試験の解答と解説 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前3,前4,前5,前6,前7,前8 |
| オートマトンの概念について説明できる。 | 4 | 前8 |
| コンパイラの役割と仕組みについて説明できる。 | 4 | 前1 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前3,前4,前5,前6,前7,前8 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前8 |
評価割合
| 試験 | 課題 | 合計 |
| 総合評価割合 | 70 | 30 | 100 |
| 専門的能力 | 70 | 30 | 100 |