到達目標
(ア)オートマトンの概念について説明できる。
(イ)形式言語の概念について説明できる。
(ウ)形式言語が制限の多さにしたがって分類されることを説明できる。
(エ)正規表現と有限オートマトンの関係を説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
オートマトン | 有限オートマトン、プッシュダウンオートマトンおよびチューリング機械の概念について説明できる。 | 有限オートマトンの概念について説明できる。 | 有限オートマトンの概念について説明できない。 |
形式言語 | 正規/文脈自由/文脈依存/句構造言語の概念について説明できる。 | 正規言語の概念について説明できる。 | 正規言語の概念について説明できない。 |
オートマトンと形式文法の関係 | 有限オートマトン、プッシュダウンオートマトンおよびチューリング機械と正規/文脈自由/文脈依存/句構造文法の関係について説明できる。 | 有限オートマトンと正規文法の関係について説明できる。 | 有限オートマトンと正規文法の関係について説明できない。 |
学科の到達目標項目との関係
学習・教育到達度目標 A4 現実の問題や未知の問題に対して,問題の本質を数理的に捉え,コンピュータシステムを応用した問題解決方法を多角的視野から検討することができる.
JABEE c 数学及び自然科学に関する知識とそれらを応用する能力
JABEE d 当該分野において必要とされる専門的知識とそれらを応用する能力
本校教育目標 ② 基礎学力
教育方法等
概要:
コンピュータを数学的に取り扱うためのモデルである「オートマトン」、および自然言語やプログラミング言語のモデルである「形式言語」についての基礎理論を学ぶ。
授業の進め方・方法:
座学で行う。自学自習課題として配布プリントもしくは教科書の演習問題を課す。
注意点:
JABEE「情報科学専攻」教育プログラムの選択必修科目である。
選択必修の種別・旧カリ科目名
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
後期 |
3rdQ |
1週 |
オートマトン・言語理論とは(予習:教科書§1.1を読む、復習:第1章演習問題を解く) |
オートマトンおよび形式言語の概念について説明できる。
|
2週 |
集合、写像(予習:教科書§1.2を読む、復習:第1章演習問題を解く) |
集合および写像の概念について説明できる。
|
3週 |
有限オートマトン(1)(予習:教科書§2.1~§2.2を読む、復習:第2章演習問題を解く) |
有限オートマトンを状態遷移図で表すことができる。
|
4週 |
有限オートマトン(2)(予習:教科書§2.3~§2.4を読む、復習:第2章演習問題を解く) |
決定性および非決定性有限オートマトンの概念について説明できる。
|
5週 |
有限オートマトン(3)(予習:教科書§2.5~§2.7を読む、復習:第2章演習問題を解く) |
同じ言語を受理できる決定性および非決定性有限オートマトンがあることを説明できる。
|
6週 |
プッシュダウンオートマトン(1)(予習:教科書§3.1を読む、復習:第3章演習問題を解く) |
プッシュダウンオートマトンの概念について説明できる。
|
7週 |
プッシュダウンオートマトン(2)(予習:教科書§3.2~§3.4を読む、復習:第3章演習問題を解く) |
プッシュダウンオートマトンが受理できる言語について説明できる。
|
8週 |
チューリング機械(予習:教科書§4.1~§4.3を読む、復習:第4章演習問題を解く) |
チューリング機械の概念について説明できる。
|
4thQ |
9週 |
中間試験(予習:教科書§1.1~§4.3を読む、復習:第1~4章演習問題を解く) |
有限オートマトン、プッシュダウンオートマトンおよびチューリング機械の概念について説明できる。
|
10週 |
形式文法と形式言語(1)(予習:教科書§5.1~§5.2を読む、復習:第5章演習問題を解く) |
形式文法および形式言語の概念について説明できる。
|
11週 |
形式文法と形式言語(2)(予習:教科書§5.3~§5.4を読む、復習:第5章演習問題を解く) |
正規/文脈自由/文脈依存/句構造文法および正規/文脈自由/文脈依存/句構造言語の概念について説明できる。
|
12週 |
オートマトンと形式文法(1)(予習:教科書§6.1を読む、復習:第6章演習問題を解く) |
正規文法と有限オートマトンとの関係について説明できる。
|
13週 |
オートマトンと形式文法(2)(予習:教科書§6.2を読む、復習:第6章演習問題を解く) |
有限オートマトン、プッシュダウンオートマトンと正規/文脈自由文法との関係について説明できる。
|
14週 |
オートマトンと形式文法(3)(予習:教科書§6.3~§6.5を読む、復習:第6章演習問題を解く) |
有限オートマトン、プッシュダウンオートマトンおよびチューリング機械と正規/文脈自由/文脈依存/句構造文法との関係について説明できる。
|
15週 |
言語の階層構造(予習:教科書§7.1~§7.4を読む、復習:第7章演習問題を解く) |
正規/文脈自由/文脈依存/句構造言語の性質について説明できる。
|
16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 後1,後10,後11,後12,後13,後14,後15 |
形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 後10,後11,後15 |
オートマトンの概念について説明できる。 | 4 | 後1,後3,後4,後5,後6,後7,後8,後9 |
正規表現と有限オートマトンの関係を説明できる。 | 4 | 後12,後13,後14 |
評価割合
| 中間試験 | 定期試験 | 合計 |
総合評価割合 | 40 | 60 | 100 |
専門的能力 | 40 | 60 | 100 |