到達目標
1.有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。
2.正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。
3.下降型および上昇型の構文解析法を説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を正確かつ詳細に説明できる。 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できる。 | 有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンおよび チューリングマシンについて、その機構と動作を説明できない。 |
| 評価項目2 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について正確かつ詳細に説明できる。 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できる。 | 正規文法、文脈自由文法、文脈依存文法および句構造文法について説明できない。 |
| 評価項目3 | 下降型および上昇型の構文解析法を正確かつ詳細に説明できる。 | 下降型および上昇型の構文解析法を説明できる。 | 下降型および上昇型の構文解析法を説明できない。 |
学科の到達目標項目との関係
教育方法等
概要:
形式言語とオートマトンは、計算機科学を形成する基礎理論であり、情報工学の重要科目として、現 在、Webマイニングやコンパイラ・文書解析に利用されている。 本授業では、オートマトン、すなわち計算機械の数学的モデルに関して、各種モデルとその計算能力 を学習し、オートマトンと緊密な関係にある形式言語に関して、形式文法による言語の生成能力につ いて学習する。また、応用例として、プログラミング言語の正規表現や構文解析法を学習する。
授業の進め方・方法:
教科書に沿った講義を行う。オートマトンが受理する言語および文法により生成される言語に関する 演習問題をできるだけ多く扱い理解を深める。また、応用例として、プログラミング言語に用いられ る正規表現や構文解析の演習を行う。 予習または復習による自学自習の機会に自ら演習問題に取り組むことを推奨する。
注意点:
本科目は学修単位科目であるので、授業時間以外での学修が必要であり、これを課題として課す。
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
オートマトンと形式言語とは |
オートマトンと形式言語の概要を説明できる。
|
| 2週 |
決定性有限状態オートマトンと受理言語 |
決定性有限状態オートマトンとその受理言語を説明できる。
|
| 3週 |
非決定性有限状態オートマトンと受理言語 |
非決定性有限状態オートマトンとその受理言語を説明できる。
|
| 4週 |
正規表現 |
正規表現を説明できる。
|
| 5週 |
状態数最小のオートマトン |
任意のオートマトンを状態数最小のオートマトンに変形できる。
|
| 6週 |
ポンプの補題 |
ポンプの補題を説明できる。
|
| 7週 |
正規文法と正規言語 |
正規文法と正規言語を説明できる。
|
| 8週 |
決定性プッシュダウンオートマトンと受理言語 |
決定性プッシュダウンオートマトンとその受理言語を説明できる。
|
| 2ndQ |
| 9週 |
非決定性プッシュダウンオートマトンと受理言語 |
非決定性プッシュダウンオートマトンとその受理言語を説明できる。
|
| 10週 |
文脈自由文法と文脈自由言語 |
文脈自由文法と文脈自由言語を説明できる。
|
| 11週 |
構文解析 |
構文解析法を説明できる。
|
| 12週 |
チューリングマシン |
チューリングマシンを説明できる。
|
| 13週 |
線形拘束オートマトン |
線形拘束オートマトンを説明できる。
|
| 14週 |
文脈依存文法と文脈依存言語 |
文脈依存文法と文脈依存言語を説明できる。
|
| 15週 |
句構造文法と句構造言語 |
句構造文法と句構造言語を説明できる。
|
| 16週 |
定期試験 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 2 | |
| オートマトンの概念について説明できる。 | 2 | |
評価割合
| 試験 | レポート | 合計 |
| 総合評価割合 | 80 | 20 | 100 |
| 専門的能力 | 80 | 20 | 100 |