理工学部Faculty of Science and Engineering
MAT200XG（数学 / Mathematics 200）離散解析Discrete Analysis
鮏川 矩義Noriyoshi SUKEGAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | H9015 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 木3/Thu.3 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 小東館-E103 |
| 配当年次Grade | 2年 |
| 単位数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)
This course introduces basic analysis techniques of discrete mathematics, such as counting methods, graph theory, generating functions and recursive relations, algorithm design and analysis, and discrete probabilities. The goal of this course is to acquire the ability to analyze the structure of discrete events using data and algorithms
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
数え上げ、グラフ理論、母関数と再帰関係式、アルゴリズムの設計と解析、離散確率など、離散数学の基本的な解析の技法について学ぶ。離散的な事象の構造をデータとアルゴリズムによって解析できるようになる
到達目標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]：準備（１）
集合、関係、関数
2[対面/face to face]：準備（２）
証明技法、アルゴリズム、計算量
3[対面/face to face]：数え上げ
積法則、和法則、鳩ノ巣原理、包除原理
4[対面/face to face]：グラフ（１）
定義と基本的な用語
5[対面/face to face]：グラフ（２）
連結グラフ、強連結有向グラフ
6[対面/face to face]：グラフ（３）
木、全域木
7[対面/face to face]：グラフ（４）
平面グラフ、グラフの彩色
8[対面/face to face]：母関数（１）
母関数の定義、数え上げ問題への応用
9[対面/face to face]：母関数（２）
再帰関係式とその解法
10[対面/face to face]：アルゴリズム（１）
再帰法、分割統治法
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
事前に履修すべき科目：離散構造