理工学部Faculty of Science and Engineering
PRI200XE（情報学基礎 / Principles of informatics 200）組み合わせアルゴリズムCombinatorics
李 磊Lilei LILEI
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H6024 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 水5/Wed.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)
This lecture will include the following topics : Discrete set and discrete structure, Basic concept of matrix, Fast algorithm of matrix product, Fast algorithm of matrix inversion, LUP decomposition of matrix, Applications of LUP decompsition, Boolean matrix product, DFT, FFT Algorithm, Convolution, FNT, FPT, Polynomial product, Polynomial division etc. The goal is learning foundation of combination algorithms and efficient program technology. Data structure and Algorithms is needed for preparation using about 4 hours outside of the class. Grading criteria is based on the score of final exam, 60% or more is needed for pass.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
離散集合と離散構造、行列の基礎概念、行列積の高速アルゴリズム、逆行列の高速アルゴリズム、行列のLUP分解、LUP分解の応用、ブール行列の乗算、離散的フーリエ変換、高速フーリエ変換のアルゴリズム、畳込み演算、整数論変換、多項式変換、多項式積の計算、多項式の除算、まとめ。
到達目標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. ）
組み合わせアルゴリズムとはなにか？最適化とは？計算量とは？NP理論とは？探索、ソート、行列と多項式計算の分野で現れる高速アルゴリズムを紹介し、組み合わせ論的思考力強化を狙うアルゴリズムの設計を紹介する。課題等に対し、授業期間中で回答における評価及び解説を行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：離散集合と離散構造
離散集合及び群、環、体等の離散構造
第2回[対面/face to face]：行列の基礎概念
行列の基礎概念を紹介する
第3回[対面/face to face]：行列積の高速アルゴリズム
Strassen の行列乗算アルゴリズム
第4回[対面/face to face]：逆行列の高速アルゴリズム
逆行列の高速アルゴリズムを紹介する
第5回[対面/face to face]：行列のLUP分解
行列のLUP分解のための高速アルゴリズムを紹介する。
第6回[対面/face to face]：LUP分解の応用
行列LUP分解の高速アルゴリズムを利用した応用を紹介する。
第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
A.V.エイホ、J.E.ホップクロフト、J.D.ウルマン共著、アルゴリズムの設計と解析Ⅱ、サイエンス社。
参考書References
必要に応じ、資料を配布する。
成績評価の方法と基準Grading criteria
期末の定期試験の成績で評価する。6割以上の得点を合格基準とする。
学生の意見等からの気づきChanges following student comments
演習問題を真面目に取り込む。
学生が準備すべき機器他Equipment student needs to prepare
液晶プロジェクト等を利用する。
その他の重要事項Others
特になし。