理工学部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 | 2022 |
| 授業コード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
The goals of the course are: to be able to construct a propositional formula from a given truth table; to be able to apply the pigeon-hole principle and the principle of inclusion-exclusion; to be able to calculate probabilities and expectations in finite probability spaces; to understand the distinction between countable and uncountable infinities; to be able to express simple languages in terms of finite automata and regular expressions.
The time required for study outside of the classes will be at least four hours per week.
The course grade will be based on the roughly weekly assignments (30%) and the final exam (70%).
授業で使用する言語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
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：命題論理（1）
命題論理式，命題論理式の解釈，充足可能性，トートロジー，トートロジー的帰結，トートロジー的同値性
2[対面/face to face]：命題論理（2）
真理関数，関数的完全性，選言標準形
3[対面/face to face]：関係の閉包
2項関係の分類，2項関係の推移的閉包と反射的推移的閉包，2項関係の表現と推移的閉包
4[対面/face to face]：同値関係と合同関係
同値関係と分割，商集合，合同関係，整数剰余環
5[対面/face to face]：有限集合の要素の個数
全単射の性質，有限集合の要素の個数の定義，鳩の巣原理，いろいろな集合の要素の個数
6[対面/face to face]：組み合わせ論的証明，包含と排除の原理
組み合わせ論的証明，包含と排除の原理，全射の個数，完全順列の個数
7[対面/face to face]：離散確率
有限の確率空間，事象の独立性，条件付き確率，ベイズの定理
8[対面/face to face]：確率変数と期待値
確率変数，期待値，分散
9[対面/face to face]：無限集合の大きさ（1）
Schröder-Bernsteinの定理，可算無限集合
10[対面/face to face]：無限集合の大きさ（2）
カントールの対角線論法，非可算集合，カントールの3進集合
11[対面/face to face]：文字列と言語
文字列に関する基本概念，文字列の長さに関する帰納法，言語，正規演算
12[対面/face to face]：正規表現
正規表現と正規言語
13[対面/face to face]：有限オートマトンとパターンマッチング
有限オートマトン，決定性有限オートマトンによる文字列マッチング
14[対面/face to face]：有限オートマトンと正規表現の等価性
正規表現から有限オートマトンへの変換，有限オートマトンから正規表現への変換
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】授業内で示される演習問題を解く．講義ノートを読んで復習する．
テキスト（教科書）Textbooks
教科書は使用しない．配布する講義ノートを使用する．
参考書References
特に指定しない．
成績評価の方法と基準Grading criteria
期末試験(70％)と宿題(30%)の成績による。
学生の意見等からの気づきChanges following student comments
課題の解答を解説する．
その他の重要事項Others
事前に履修すべき科目：離散構造