到達目標
オートマトン・言語理論，計算の理論・計算の複雑さ，代数系・整数論・有限体，暗号・符号理論に関して，それらの基本的事項を理解し，工学上の応用問題を解決するための数学的知識と計算技術を習得すること．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 離散数学の基本的な概念に関する問題を解くことができる． | 離散数学の基本的な概念を説明できる． | 離散数学の基本的な概念を説明できない． |
| 評価項目2 | 離散数学に関するアルゴリズムを実装することができる． | 離散数学に関する知識をアルゴリズムに利用することができる． | 離散数学に関する知識をアルゴリズムに利用することができない． |
| 評価項目3 | オートマトン・言語理論に関する問題を解くことができる． | オートマトン・言語理論の概念について説明できる． | オートマトン・言語理論の概念について説明できない． |
学科の到達目標項目との関係
教育方法等
概要:
オートマトンは，現実の機械を抽象化したものとして，計算というものを理論的に考察する場合の基礎である．このような抽象化された機械を用いて，計算が不可能な問題が存在することを示す．計算が可能な場合においても，その計算量の程度についても考察する．また，オートマトンは，文字の並びとしての語，そして，語の集まりである言語を定めるものとして，コンパイラなどの分野で重要である．さらに，集合，写像，関係，代数系などに関して，これらを応用と関連付けて学ぶと，興味深い分野であることを示す．
授業の進め方・方法:
・すべての授業内容は，学習・教育到達目標(B)<基礎>およびJABEE基準1(2)(c)に対応する．
・授業は講義・輪講形式で行う．講義中は集中して聴講する．
・「授業計画」における各週の「到達目標」はこの授業で習得する「知識・能力」に相当するものとする．
注意点:
＜到達目標の評価方法と基準＞下記授業計画の「到達目標」を網羅した問題を２回の中間試験，２回の定期試験で出題し，目標の達成度を評価する．各到達目標に関する重みは同じである．評価結果が100点法で60点以上の場合に目標の達成とする．
＜学業成績の評価方法および評価基準＞前期中間・前期末・後期中間・学年末の，計４回の試験結果の平均点を最終評価とする．再試験は実施しない．
＜単位修得要件＞学業成績で60点以上を取得すること．
＜あらかじめ要求される基礎知識の範囲＞指数・対数・三角関数，数列と級数，微分と積分，順列と組合せ，線形代数の基本事項について理解していること．とくに，本教科の学習には「線形代数Ⅰ」「線形代数Ⅱ」の理解と習得が必要である．
＜自己学習＞授業で保証する学習時間と，予習・復習（中間試験，定期試験のための学習も含む）及びレポート作成に必要な標準的な学習時間の総計が，90時間に相当する学習内容である．
＜注意事項＞オートマトン・言語理論，計算の理論・計算の複雑さ，代数系・整数論・有限体，暗号・符号理論は，情報工学のさまざまな分野で利用されており，技術者にとって重要な数学の一分野である．基本的な例題と演習問題に取り組み，内容を十分理解することが大切である．本教科は，後に学習する「代数学特論」（専攻科）に強く関連する教科である．
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
集合
双対性
|
＜集合と写像＞
1. 集合と濃度に関する問題を解くことができる．
|
| 2週 |
関数
関数の合成
|
＜集合と写像＞
2. 写像に関する問題を解くことができる．
|
| 3週 |
順列・組合せ
多項定理
|
＜集合と写像＞
3. 代数的構造に関する問題を解くことができる．
4. 関係，類別と同値類に関する問題を解くことができる．
|
| 4週 |
基数法
論理代数
|
＜集合と写像＞
5. 証明の方法に関する問題を解くことができる．
＜代数的構造＞
10.群・環・体についての問題を解くことができる．
|
| 5週 |
条件文と双条件文
ブール代数
|
＜代数的構造＞
11.剰余環についての問題を解くことができる．
12.多項式環についての問題を解くことができる．
|
| 6週 |
論理ゲートと論理回路
カルノー図
|
＜代数的構造＞
13.Galois体（有限体）についての問題を解くことができる．
＜計算の理論・計算の複雑さ＞
8. 計算機械とその言語に関する問題を解くことができる．
|
| 7週 |
述語論理
束縛変数と自由変数
|
＜計算の理論・計算の複雑さ＞
9. 計算不可能な問題に関する問題を解くことができる．
10. 計算量と計算の複雑さに関する問題を解くことができる．
11. NP完全問題に関する問題を解くことができる．
|
| 8週 |
中間試験
|
これまでに学習した内容を説明し，諸量を求めることができる．
|
| 2ndQ |
| 9週 |
グラフの概念と基礎知識
いろいろなグラフ
|
＜グラフ理論＞
6. グラフ構造の基本に関する問題を解くことができる．
|
| 10週 |
二つの古典的問題
結婚の問題とラテン方陣
|
＜グラフ理論＞
7. オイラー閉路に関する問題を解くことができる．
|
| 11週 |
木
有向グラフ
|
＜グラフ理論＞
8. 木構造の基本に関する問題を解くことができる．
|
| 12週 |
ネットワークプランニング
アルファベットと言語
|
＜グラフ理論＞
9. ネットワークフローに関する問題を解くことができる．
＜オートマトン・言語理論＞
1. 集合，写像等に関する問題を解くことができる．
|
| 13週 |
有限状態機械
有限オートマトン
|
＜オートマトン・言語理論＞
2. 有限オートマトンに関する問題を解くことができる．
3. プッシュダウンオートマトンに関する問題を解くことができる．
|
| 14週 |
文脈自由文法
プッシュダウンオートマトン
|
＜オートマトン・言語理論＞
4. チューリング機械に関する問題を解くことができる．
5. 線形拘束オートマトンに関する問題を解くことができる．
|
| 15週 |
チューリング機械
オートマトンと言語
|
＜オートマトン・言語理論＞
6. オートマトンと形式言語の関係に関する問題を解くことができる．
7. 言語とその階層構造に関する問題を解くことができる．
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | |
| ブール代数に関する基本的な概念を説明できる。 | 4 | |
| 論理代数と述語論理に関する基本的な概念を説明できる。 | 4 | |
| 離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 4 | |
評価割合
| 試験 | 課題 | 相互評価 | 態度 | 発表 | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 配点 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |