到達目標
・オートマトン理論や形式言語理論の基礎を理解する。
・計算可能性や計算複雑性についての理論を理解し、各種問題について、その計算可能性や計算複雑性を論ずることができるようになる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
オートマトン理論、
形式言語理論 | 与えられた言語が有限オートマトンやプッシュダウンオートマトンで認識可能か否かを判断できる。 | 有限オートマトンやプッシュダウンオートマトンに関する定義や定理を理解している。 | 有限オートマトンやプッシュダウンオートマトンに関する定義や定理を理解していない。 |
計算可能性 | 与えられた言語がチューリング機械で判定可能か否かを判断できる。 | チューリング機械に関する定義や定理を理解している。 | チューリング機械に関する定義や定理を理解していない。 |
計算複雑性 | 与えられた言語が属する計算量のクラスを判断できる。 | 時間計算量や領域計算量に関する定義や定理を理解している。 | 時間計算量や領域計算量に関する定義や定理を理解していない。 |
学科の到達目標項目との関係
JABEE基準 (d-1)
説明
閉じる
JABEE基準 (d-2a)
説明
閉じる
システム創成工学教育プログラム学習・教育目標 B-2
説明
閉じる
システム創成工学教育プログラム学習・教育目標 D-1
説明
閉じる
教育方法等
概要:
計算理論の基礎を学習する。
授業の進め方・方法:
計算機を用いて各種問題を解くにあたり、その問題は計算機を用いて解くことができるか、あるいは、解くためには
どのくらいの計算量やメモリ量を必要とするか、といったことを検討するために必要な理論について学習する。
注意点:
【参考書】
「計算理論の基礎 [原著第2版] 1. オートマトンと言語」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸
・植田広樹・藤岡淳・渡辺治訳、共立出版
「計算理論の基礎 [原著第2版] 2. 計算可能性の理論」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸
・植田広樹・藤岡淳・渡辺治訳、共立出版
「計算理論の基礎 [原著第2版] 3. 複雑さの理論」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸
・植田広樹・藤岡淳・渡辺治訳、共立出版
「チューリングの計算理論入門」、高岡詠子著、講談社
【関連科目】
情報数学、データ構造とアルゴリズム、計算機言語処理、情報理論、情報セキュリティ
【学習指針】
できる限り講義時間中に理解することを心がけること。疑問点については、質問するなり文献等を調べるなりして、
自ら進んで解決するように努めること。
【事前学習】
事前に配布される講義資料に目を通しておくこと。
【事後展開学習】
各講義終了後速やかに、講義内容において理解できたことと理解できなかったことを整理すること。
理解できなかったことについては、次回の講義までに解決しておくこと。
【評価割合】
試験の成績(100%)で評価する。ただし、本科目への取り組み姿勢に問題がある場合(講義時間中に取り組むべき
演習問題に取り組んでいない、レポート等の課題が未提出、提出物の内容が不十分、など)は減点することがある。
学修単位の履修上の注意
講義時間中に提示する演習問題を自学自習時間に解くこと。演習問題の類似問題を試験で出題し、試験の成績として自学自習内容を評価する。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
オートマトン(1) |
有限オートマトンを理解する。
|
2週 |
オートマトン(2) |
正規表現と正規言語を理解する。
|
3週 |
オートマトン(3) |
文脈自由文法と文脈自由言語を理解する。
|
4週 |
オートマトン(4) |
文脈自由文法の標準形を理解する。
|
5週 |
オートマトン(5) |
プッシュダウンオートマトンを理解する。
|
6週 |
計算可能性(1) |
チューリング機械を理解する。
|
7週 |
計算可能性(2) |
非決定性チューリング機械を理解する。
|
8週 |
計算可能性(3) |
判定可能問題を理解する。
|
2ndQ |
9週 |
計算可能性(4) |
判定不能問題を理解する。
|
10週 |
計算可能性(5) |
帰着を理解する。
|
11週 |
計算複雑性(1) |
時間計算量の基礎を理解する。
|
12週 |
計算複雑性(2) |
クラスPとクラスNPを理解する。
|
13週 |
計算複雑性(3) |
NP完全を理解する。
|
14週 |
計算複雑性(4) |
領域計算量を理解する。
|
15週 |
期末試験 |
授業内容を理解し、正しく解答する。
|
16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 試験 | 合計 |
総合評価割合 | 100 | 100 |
専門的能力 | 100 | 100 |