理工学部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
事前に履修すべき科目:離散構造