理工学研究科Graduate School of Science and Engineering
PRI500X3（情報学基礎 / Principles of informatics 500）離散アルゴリズム特論１Discrete Algorithms (Ⅰ)
李 磊Lilei LILEI
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YB000 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 月2/Mon.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 応用情報工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This lecture will include the following topics : Overview of the system, Properties of the system, Discrete structures, Combinational counting, Graph theory, (0,1) matrix, Non-negative matrix, M matrix, LCP, Toeplitz matrix, Circulant matrix, Circulant matrix, etc. The goal is learning foundation of discrete algorithms and efficient program technology. Linear algebra and matrix theory is needed for preparation using about 4 hours outside of the class. Grading criteria is based on the score of final report document, 60% or more completeness is needed for pass.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
授業のテーマは下記の通りである。システムの概要、システムの性質、離散構造、組み合わせ計数、グラフの理論、(0,1) 行列、非負行列、M行列、線形相補性問題、Toeplitz 行列、巡回行列、Vandermonde 行列、まとめ。
到達目標Goal
離散アルゴリズムの基礎内容を理解でき、柔軟なアルゴリズム設計能力を身につけてもらう。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」に関連
授業で使用する言語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]：グラフの理論（1）
道と閉路、オイラーグラフ、ハミルトングラフ
第6回[対面/face to face]：グラフの理論（2）
木の性質、木の数え上げ、応用
第7回[対面/face to face]：(0,1) 行列
(0,1) 行列の性質、応用
第8回[対面/face to face]：非負行列
非負行列の理論、性質
第9回[対面/face to face]：M行列
M行列の性質、判別法
第10回[対面/face to face]：線形相補性問題
線形相補性問題、性質、解法
第11回[対面/face to face]：Toeplitz 行列
Toeplitz 行列の定義、性質、高速アルゴリズム
第12回[対面/face to face]：巡回行列
巡回行列の性質、畳み込み
第13回[対面/face to face]：Vandermonde 行列
Vandermonde 行列の性質、数式処理への応用
第14回[対面/face to face]：まとめ
まとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】線形代数、行列理論に関係する内容を復習すること
テキスト（教科書）Textbooks
随時に資料配布する。
参考書References
特になし
成績評価の方法と基準Grading criteria
授業での学習状況や参加度も考慮し、期末のレポートの成績で評価する。6割以上の得点を合格基準とする。
学生の意見等からの気づきChanges following student comments
実用の例題及び演習を充実させる。
学生が準備すべき機器他Equipment student needs to prepare
液晶プロジェクター等を利用する。
その他の重要事項Others
特になし。