到達目標
(1) 有限オートマトンと正規言語について理解する．(定期試験と小テスト)
(2) プッシュダウンオートマトンと文脈自由言語について理解する．（定期試験と小テスト）
(3) Turing機械と計算可能性について理解する．（定期試験と小テスト）
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| (1) 有限オートマトンと正規言語について理解する． | 有限オートマトンと正規言語について，他者に説明できるレベルで理解している． | 有限オートマトンと正規言語について，講義で取り上げた例題を解くことができる． | 有限オートマトンと正規言語について，基本的な概念の定義や用語の定義を述べることができない． |
| (2) プッシュダウンオートマトンと文脈自由言語について理解する． | プッシュダウンオートマトンと文脈自由言語について，他者に説明できるレベルで理解している． | プッシュダウンオートマトンと文脈自由言語について，講義で取り上げた例題を解くことができる． | プッシュダウンオートマトンと文脈自由言語について，基本的な概念の定義や用語の定義を述べることができない． |
| (3) Turing機械と計算可能性について理解する． | Turing機械と計算可能性について，他者に説明できるレベルで理解している． | Turing機械と計算可能性について，講義で取り上げた例題を解くことができる． | Turing機械と計算可能性について，基本的な概念の定義や用語の定義を述べることができない． |
学科の到達目標項目との関係
学習・教育目標 (B2)
説明
閉じる
JABEE 1(2)(g)
説明
閉じる
JABEE 2.1(1)②
説明
閉じる
教育方法等
概要:
本講義では，記号処理を行う機械と，そのような機械によって処理される言語の関係について学ぶ．ここで学ぶ数学的概念はプログラミング言語の設計やコンパイラの構成を行う際の理論的基盤となる．
(科目情報)
教育プログラム 第2学年 ◎科目
授業の進め方・方法:
原則として毎回，授業内容の理解を問う小テストを実施するので，授業を良く聞いて理解に努めること．
(参考図書)
[1] Sipser, M., Introduction to the Theory of Computation, PWS Pub. Co.
[2] シプサ，M., 計算理論の基礎，共立出版．
[3] ホップクロフト, J. 他，オートマトン 言語理論 計算論 I [第2版]，サイエンス社．
[4] ホップクロフト, J. 他，オートマトン 言語理論 計算論 II [第2版]，サイエンス社．
[5] 川添愛，白と黒のとびら，東京大学出版会．
[6] Stuart, T., アンダースタンディング コンピュテーション，オライリー・ジャパン．
(事前学習)
参考図書 [1, 2] の該当箇所を読んでおくことが望ましい．
注意点:
(履修上の注意)
配布プリントを整理するためのクリアファイル(A4サイズ)を用意すること．
(自学上の注意)
参考図書の必要箇所を参照して予習・復習を行うこと．授業内容は [1] に基づく．[2] は [1] の邦訳．[3][4] はこの分野の標準的な教科書の一つ．[5] は形式言語理論を学べるファンタジー小説．[6] はプログラミング (Ruby) を通して実践的に形式言語理論と計算理論を学べる本．
評価
(総合評価)
総合評価 = 定期試験 × 0.7 + 課題 × 0.3
(再試験について)
前期末試験終了後の適切な時期に実施する．受験資格者については試験解説時にアナウンスする．
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
イントロダクション |
予備知識を確認する．(無向グラフ / 木 / 有向グラフ / アルファベット / 文字列)
|
| 2週 |
有限オートマトンと正規言語 |
有限オートマトンと正規言語について理解する．(有限オートマトン / 正規言語)
|
| 3週 |
正規演算 |
正規演算について理解する．(有限オートマトンの設計 / 正規演算)
|
| 4週 |
非決定性有限オートマトン |
非決定性有限オートマトンについて理解する．(非決定性有限オートマトン / 有限オートマトンの等価性)
|
| 5週 |
正規表現 |
正規表現について理解する．(正規表現 / 正規言語と正規表現)
|
| 6週 |
非正規言語 |
非正規言語について理解する．(非正規言語 / 反復補題 / 抽斗論法)
|
| 7週 |
プッシュダウンオートマトン |
プッシュダウンオートマトンについて理解する．(プッシュダウンオートマトン / 文脈自由文法)
|
| 8週 |
復習と応用演習 |
|
| 2ndQ |
| 9週 |
前期中間試験 |
|
| 10週 |
前期中間試験の解答と解説 |
|
| 11週 |
文脈自由言語 |
文脈自由言語について理解する．(文脈自由言語 / Chomsky標準形 / 文脈自由言語とプッシュダウンオートマトン / 非文脈自由言語 / 文脈自由言語の反復補題)
|
| 12週 |
Turing機械 |
Turing機械について理解する．(Turing機械 / Turing認識可能 / Turing決定可能)
|
| 13週 |
決定可能言語 |
決定可能性について理解する．(決定可能言語 / DFAの受理問題 / DFAの空性問題 / 文脈自由文法の生成問題 / 文脈自由言語の決定可能性 / Turing機械の受理問題 / 停止問題)
|
| 14週 |
Turing認識可能性 |
Turing認識可能性について理解する．(濃度 / 可算集合 / 非可算集合 / Turing認識不能言語)
|
| 15週 |
前期期末試験 |
|
| 16週 |
前期期末試験の解答と解説 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前11,前12,前13,前14,前15,前16 |
| オートマトンの概念について説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前11,前12 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前11,前12,前13,前14,前15,前16 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前2,前3,前4,前5,前8 |
評価割合
| 試験 | 小テスト | 合計 |
| 総合評価割合 | 70 | 30 | 100 |
| 専門的能力 | 70 | 30 | 100 |