到達目標
第一階述語論理における証明方法，および，オートマトンに関する基礎知識・作成方法が身についていることを単位認定の基準とする。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 第一階述語論理の基礎を理解し，簡単な論理式の証明ができる | 第一階述語論理の基本概念を理解し，論理式の簡単な証明ができる | 第一階述語論理の基本概念はおおむね理解している。また論理式の証明を，例題を見ながらなら完成できる。 | 第一階述語論理の基本概念を理解していない。また論理式の証明もできない。 |
| 正規表現・決定性有限オートマトン・導出木の概念を理解し，それらを生成することができる | 正規表現，有限オートマトン等の基本概念を理解し，要求する仕様に従って，それらを生成することができる。 | 正規表現，有限オートマトン等の基本概念を理解し，要求する仕様に従って，類似のものを生成することができる。 | 正規表現，有限オートマトン等の基本概念を理解していない。 |
| プッシュダウンオートマトンの概念を理解し，具体的なオートマトンの設計ができる | プッシュダウンオートマトンの概念を理解しており，具体的なオートマトンの設計ができる | プッシュダウンオートマトンの概念を理解しており，例題を見ながら具体的なオートマトンの設計ができる。 | プッシュダウンオートマトンの概念を理解していない。 |
学科の到達目標項目との関係
JABEE (c)
説明
閉じる
JABEE (d)
説明
閉じる
教育方法等
概要:
コンピュータの数学的言語モデルを扱う上で，集合論・言語理論・グラフ理論・論理学・オートマトンなどは，非常に重要な学問である。本科目では，これまで学んできた集合論・言語理論を土台として，コンピュータの言語モデルともいえるオートマトンと，プログラミング言語理論の基礎となる論理学について学習する。
授業の進め方・方法:
座学中心の授業となるため，定理の証明などは詳細な解説を加えながら行い，演習問題は，全学生にやってもらいながら進める。授業の内容を基本とし，関係する数学的基礎概念は，受講者の理解度に応じて解説する。なお、この科目は学修単位科目のため、事前・事後学習として、予習・復習を行うこと。
注意点:
集合・写像・記号論理・グラフ理論・情報数学・離散数学につては，一通り復習しておくこと。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
ガイダンス |
第一階述語論理およびオートマトンの必要性と本授業の内容・目標を理解する。
|
| 2週 |
命題論理 |
命題論理と真理値について復習し，その内容を理解する。
|
| 3週 |
第一階述語論理の基礎 |
第一階述語論理に必要な構成要素と，基本概念について理解する。
|
| 4週 |
第一階述語論理の基礎 |
第一階述語論理における推論規則について理解する。
|
| 5週 |
第一階述語論理における論理式の証明 |
第一階述語論理における証明について理解する。
|
| 6週 |
演習 |
第一階述語論理の証明ができるようになる。
|
| 7週 |
直感主義論理 |
直感主義論理について理解し，その論理における証明ができるようになる。
|
| 8週 |
論理の完全性と健全性 |
第一階述語論理の完全性と健全性について理解する。
|
| 4thQ |
| 9週 |
正規表現と正規言語 |
正規表現およびその必要性について理解する。また形式言語につてい理解する。
|
| 10週 |
文法と導出木 |
形式言語における文法について理解する。また文法の骨子となる導出木について理解する。
|
| 11週 |
正規文法と文脈自由文法 |
文脈自由文法をはじめとする文法のクラスおよびその違いについて理解する。
|
| 12週 |
オートマトン |
決定性有限オートマトン，非決定性有限オートマトンの概念を理解する。
|
| 13週 |
オートマトンの等価性 |
導入したオートマトンが表現できるクラスは全て等価であることを理解する。
|
| 14週 |
正規表現とオートマトンの等価性 |
導入したオートマトンが表現できるクラスと正規表現のそれとが等価であることを理解する。
|
| 15週 |
プッシュダウンオートマトン |
プッシュダウンオートマトンについて理解する。
|
| 16週 |
文脈自由文法とプッシュダウンオートマトン |
プッシュダウンオートマトンと文脈自由文法が表現できるクラスは等価であることを理解する。
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 課題 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 40 | 0 | 0 | 0 | 0 | 0 | 40 |
| 専門的能力 | 40 | 0 | 0 | 0 | 0 | 0 | 40 |
| 分野横断的能力 | 20 | 0 | 0 | 0 | 0 | 0 | 20 |