到達目標
1. 有限オートマトン，プッシュダウンオートマトンについて理解し設計することができる
2. チューリング機械について理解し設計することができる
3. オートマトンと形式言語との関係について説明することができる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | ＮＦＡをＤＦＡに変換することでその等価性を理解することができる | 簡単な言語をオートマトンで表現することができる | 簡単な言語をオートマトンで表現することができない |
| 評価項目2 | 計算機械としてチューリング機械を設計することができる | 簡単な言語を非決定チューリング機械を用いて設計することができる | 簡単な言語を非決定チューリング機械を用いて設計することができない |
| 評価項目3 | 言語の階層構造を理解し，正規言語ではない言語の存在を証明することができる | 正規文法，文脈自由文法および文脈依存文法の定義を理解することができる | 正規文法，文脈自由文法および文脈依存文法の定義を理解することができない |
学科の到達目標項目との関係
教育方法等
概要:
情報科学分野におけるオートマトンと形式言語ついて学習する．オートマトンは計算機のモデルであり，機械が計算することとは何か，またその計算能力についての理論を与えるための道具である。一方，形式言語は自然言語やプログラミング言語のモデルである。オートマトンと形式文法との関係およびその階層構造について説明でき，チューリング機械等の計算モデルの原理を理解することを到達レベルとする．
授業の進め方・方法:
集合の写像や関係の概念をよく理解しておくこと．関連科目は「アルゴリズムとデータ構造」，「情報数学」，「プログラミング言語論」である．これら科目との連携を意識しながら履修すること．
注意点:
評価方法： 中テスト（B）および期末試験（B）, 計2回の平均点とする
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス
オートマトンとは |
オートマトンの概念を理解し，その歴史と役割について説明することができる
|
| 2週 |
有限オートマトン
・決定性有限オートマトンと状態遷移図 |
決定性有限オートマトンの形式的定義を理解し，状態遷移図によっていくつかの言語を表現することができる．
|
| 3週 |
有限オートマトン
・最簡形の決定性有限オートマトン |
同じ言語を表す複数のDFAが存在することを理解し，唯一の最簡形を構築することができる．
|
| 4週 |
有限オートマトン
・非決定性有限オートマトン |
決定性FAと非決定性FAの違いについて説明することができ，NFAとDFAが等価であることを,
NFA / DFA変換を求めることで説明することができる．
|
| 5週 |
演習 |
FAシミュレータを利用しDFA，NFAを設計することができる
|
| 6週 |
プッシュダウンオートマトン (PDA）
・決定性PDA |
プッシュダウンスタックや決定性PDAの概念を理解し，いくつかの言語について，状態遷移図で示すことができる
|
| 7週 |
プッシュダウンオートマトン (PDA）
・非決定性PDA |
DPDAとNPDAが生成する言語のクラスが異なることを説明することができる
ある言語についてPDAを設計することができる
・DPDAとNPDAが生成する言語のクラスが異なることを説明することができる
|
| 8週 |
中テスト |
|
| 2ndQ |
| 9週 |
答案返却
チューリング機械 (TM) |
間違った問題の正答を求めることができる
チューリング機械の概念と原理を説明することができる
|
| 10週 |
・決定性チューリング機械 (TM) |
間違った問題の正答を求めることができる
決定性チューリング機械で単純なアルゴリズムを実装することができる
|
| 11週 |
演習 |
TMシミュレータを利用しチューリング機械を設計することができる
|
| 12週 |
形式言語
・正規文法と文脈自由文法 |
形式言語の階層を理解し，正規文法および文脈自由文法で言語の生成について説明することができる
|
| 13週 |
形式言語
・正規表現 |
正規表現の定義を理解し，FAや正規文法を正規表現で表すことができる
|
| 14週 |
形式言語
・正規言語ではない言語の証明 |
ポンプの補題を用いて，ある言語が正規言語ではないことを証明することができる
|
| 15週 |
期末試験 |
|
| 16週 |
答案返却・解答解説 |
間違った問題の正答を求めることができる
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | 前1 |
| 主要な計算モデルを説明できる。 | 4 | 前1 |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 2 | |
| システムプログラム | 形式言語の概念について説明できる。 | 4 | 前2 |
| オートマトンの概念について説明できる。 | 4 | 前1,前3 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前12 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前2 |
| 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 3 | |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 3 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 100 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 |