理工学研究科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 | YB001 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月3/Mon.3 |
| 科目種別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 : Computers and computational model, Computational complexity and stability, Graph searching, Evaluation of the network structure, Coding algorithms, Integer algorithms, FFT, FPT, Simple GA and its application, Softcomputing, etc. The goal is learning applications of discrete algorithms and efficient program technology. C or C++ Programming Language is needed for preparation using about 4 hours outside of the class. Grading criteria is based on the final report document, 60% or more completeness is needed for pass.
授業で使用する言語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」「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]：暗号アルゴリズム
整数論基礎と基本的暗号アルゴリズム
第6回[対面/face to face]：整数アルゴリズム
整数乗算の高速アルゴリズム、多項式計算との関連性
第7回[対面/face to face]：高速フーリエ変換
FFT、巡回たたみこみ、数論変換
第8回[対面/face to face]：高速多項式アルゴリズム
多項式の乗算、除算
第9回[対面/face to face]：遺伝的アルゴリズム基礎
遺伝的アルゴリズムの基本原理、手順
第10回[対面/face to face]：遺伝的アルゴリズム応用（1）
パターンマッチング
第11回[対面/face to face]：遺伝的アルゴリズム応用（2）
ニューラルネットワークの構造決定
第12回[対面/face to face]：遺伝的アルゴリズム応用（3）
人工生命へのアプローチ
第13回[対面/face to face]：ソフトコンピューティング
ファジー、ニューロコンピューティングの基礎
第14回[対面/face to face]：まとめ
まとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】CまたはC++プログラミング言語を復習すること
テキスト（教科書）Textbooks
随時に資料配布する。
参考書References
特になし
成績評価の方法と基準Grading criteria
授業での学習状況や参加度も考慮し、期末のレポートの成績で評価する。6割以上の得点を合格基準とする。
学生の意見等からの気づきChanges following student comments
演習問題も充実する。
学生が準備すべき機器他Equipment student needs to prepare
液晶プロジェクター等を利用する。
その他の重要事項Others
特になし。