到達目標
(1) 有限オートマトンの動作を理解し、説明できる
(2) プッシュダウンオートマトンの動作を理解し、説明できる
(3) 正規文法、文脈自由文法について理解し、説明できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 有限オートマトンについて深く理解しており、特定の言語を受理する有限オートマトンを自分で構成できる | 有限オートマトンについて理解しており、概略を説明できる | 有限オートマトンについて、理解できていない |
| 評価項目2 | プッシュダウンオートマトンについて深く理解しており、特定の言語を受理するプッシュダウンオートマトンを自分で構成できる | プッシュダウンオートマトンについて理解しており、概略を説明できる | プッシュダウンオートマトンについて、理解できていない |
| 評価項目3 | 正規文法、文脈自由文法について深く理解しており、特定の言語を生成する文法を構成できる | 正規文法、文脈自由文法について理解しており、概略を説明できる | 正規文法、文脈自由文法について理解できていない |
学科の到達目標項目との関係
教育方法等
概要:
「計算とは何か」を数学的に論じる際に用いられる数理モデル「オートマトン」について学び、「計算理論」の入学的内容を理解する。
授業の進め方・方法:
授業は教科書「オートマトン・言語理論の基礎」および配布プリント主にし、スライドを併用した講義とする。演習問題を多く取り入れることにより、学習内容の定着と理解度の向上を図る。
注意点:
【成績評価の基準・方法】
技術者が身につけるべき専門知識として、上記の到達目標に対する達成度を試験等において評価する。
成績は試験の素点を80%、平素の学習状況（課題等）を20%の割合で総合的に評価する。
学年末の成績は前学期末の成績とし、前学期末の成績は前期中間の成績も含めて総合的に評価する。
【事前・事後学習】
事前学習として教科書の該当部分をよく読み込むこと。また、事後学習として授業内で取り組んだ演習問題の内容をよく見直すこと。
【履修上の注意】
この科目を履修するにあたり、３年生科目の「アルゴリズムとデータ構造」の内容を十分に理解しておくこと。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
オートマトンとは |
オートマトンと言語理論の概略を理解する
|
| 2週 |
集合と写像 |
オートマトンを学習するうえで必要となる、集合と写像の知識について復習する
|
| 3週 |
有限オートマトン① |
決定性有限オートマトンの動作について理解する
|
| 4週 |
有限オートマトン② |
非決定性有限オートマトンの動作について理解する
|
| 5週 |
有限オートマトン③ |
空動作のある非決定性有限オートマトンの動作について理解する
|
| 6週 |
有限オートマトン④ |
非決定性有限オートマトンから、同じ言語を受理する決定性有限オートマトンを導く方法を理解する
|
| 7週 |
有限オートマトン⑤ |
決定性有限オートマトンの最簡系を導く方法を理解する
|
| 8週 |
有限オートマトン⑥ |
これまでに習った有限オートマトンに関する練習問題を解き、理解を深める
|
| 2ndQ |
| 9週 |
プッシュダウンオートマトン① |
決定性プッシュダウンオートマトンの動作を理解する
|
| 10週 |
プッシュダウンオートマトン② |
非決定性プッシュダウンオートマトンの動作を理解する
|
| 11週 |
プッシュダウンオートマトン③ |
決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの言語識別能力について理解する
|
| 12週 |
オートマトンと形式文法① |
形式文法と形式言語について理解する
|
| 13週 |
オートマトンと形式文法② |
正規文法と有限オートマトンの関係を理解する
|
| 14週 |
オートマトンと形式文法③ |
文脈自由文法とプッシュダウンオートマトンの関係を理解する
|
| 15週 |
総合演習 |
本科目で学習したオートマトン、形式言語に関する演習問題を解くことができる
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前5,前11,前12,前15 |
| オートマトンの概念について説明できる。 | 4 | 前5,前6,前7,前9,前10,前13,前14 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前11,前12,前15 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前13,前14 |
評価割合
| 試験 | 平素の学習状況 | | | | | 合計 |
| 総合評価割合 | 80 | 20 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 50 | 10 | 0 | 0 | 0 | 0 | 60 |
| 専門的能力 | 30 | 10 | 0 | 0 | 0 | 0 | 40 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |