理工学部Faculty of Science and Engineering
MAT200XG（数学 / Mathematics 200）離散解析Discrete Analysis
金沢 誠Makoto KANAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2021 |
| 授業コードClass code | H9015 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 木5/Thu.5 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
創生科学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
From the discrete structures (DS) area of the standard computer science curriculum (J07-CS), the course covers the following topics:
DS1: functions, relations, and sets
DS2: logic
DS3: graphs
DS4: proof methods
DS5: counting and discrete probability
DS6: automata and regular expressions
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
カリキュラム標準コンピュータ科学J07-CSのうち，離散構造(DS)エリアから次のトピックをカバーする。
DS1: 関数，関係，集合
DS2: 論理
DS3: グラフ
DS4: 証明技法
DS5: 数え上げと離散確率の基礎
DS6: オートマトンと正規表現
到達目標Goal
・真理表から命題論理式を構成できる．
・鳩の巣原理と包含と排除の原理を応用できる．
・有限の確率空間で事象の確率や確率変数の期待値が計算できる．
・可算無限集合と非可算無限集合の区別が理解できる．
・簡単な言語に対して有限オートマトンと正規表現を書くことができる．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
板書を中心とした講義と定期的な課題による。授業の冒頭部分で提出された課題の正答と，実際の間違いの例について解説する。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
※各回の授業形態は予定です。教員の指示に従ってください。
1：命題論理
命題論理式，恒真性，充足可能性，標準形，論理回路
2：関係の閉包
2項関係の分類，2項関係の推移的閉包と反射的推移的閉包
3：同値関係と合同関係
同値関係と分割，商集合，合同関係，整数剰余環
4：数え上げ
全単射の性質，有限集合の要素の個数，順列と組み合わせ，鳩の巣原理とその応用
5：組み合わせ論的証明，包含と排除の原理
組み合わせ論的証明，包含と排除の原理，全射の個数，完全順列の個数
6：離散確率
有限の確率空間，事象の独立性，条件付き確率，ベイズの定理
7：確率変数と期待値
確率変数，期待値，分散
8：グラフと木
グラフに関する基本概念，木，全域木，根付き木，木の巡回戦略
9：無限集合の濃度
可算集合，対角線論法，非可算集合
10：リスト
リスト，リストに関する帰納法と再帰的定義
11：文字列と言語，正規演算と正規表現
文字列，辞書順序，文字列集合，正規演算，正規表現
12：有限オートマトンとパターンマッチング
有限オートマトン，有限オートマトンによる文字列マッチング
13：非決定性有限オートマトン
非決定性有限オートマトンと決定性有限オートマトンの等価性
14：有限オートマトンと正規表現の等価性
正規表現から非決定性有限オートマトンへの変換，決定性有限オートマトンから正規表現への変換
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】授業内で示される演習問題を解く．講義ノートを読んで復習する．
テキスト（教科書）Textbooks
教科書は使用しない．配布する講義ノートを使用する．
参考書References
特に指定しない．
成績評価の方法と基準Grading criteria
期末試験(70％)と宿題(30%)の成績による。
学生の意見等からの気づきChanges following student comments
課題の解答を解説する．
その他の重要事項Others
事前に履修すべき科目：離散構造