情報科学部Faculty of Computer and Information Sciences
PRI310KA-CS-261（情報学基礎 / Principles of informatics 300）アルゴリズムの設計と解析Design and Analysis of Algorithm
首藤 裕一Yuichi SUDO
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | J8039 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 水4/Wed.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | 3～4 |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）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 | |
| 選択・必修Optional/Compulsory | |
| カテゴリー（2022年度以降入学者）Category (2022~) | |
| カテゴリー（2021年度以前入学者）Category (~2021) |
専門教育科目 専門科目 学科専門科目 |
| カテゴリーCategory |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Mastering the basics of data structures and algorithms is a prerequisite for a deep understanding of computer science. In this course, students will learn basic design techniques of algorithms and well-known algorithms that every student of computer science should know, assuming that they have already mastered the basic concepts of algorithms and computational complexity in "Data Structures and Algorithms 1," a course of the spring semester.
Students will be expected to study the topic given in the class for four hours each week. Your overall grade in the class will be decided based on the following:
Term-end examination: 90%, short reports and in-class contribution: 10%
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
データ構造とアルゴリズムの基礎を身につけることは計算機科学を深く理解するための必要条件である。本講では、春学期開講の「データ構造とアルゴリズム1」でアルゴリズムや計算量に関する基本的な概念を習得していることを前提として、アルゴリズムの基本的な設計技法や、計算機科学を学ぶ者なら誰もが知っておくべき著名なアルゴリズム群を学ぶ。
到達目標Goal
計算機科学を学ぶ上で必須となるデータ構造とアルゴリズムの基礎を理解するとともに、典型的なアルゴリズム設計技法を習得する。
授業で使用する言語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.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：ガイダンス・振り返り
本授業のガイダンスを行うとともに、「データ構造とアルゴリズム1」の内容を振り返る。
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]：素集合データ構造
有用なデータ構造である素集合データ構造（Union-Find）を学ぶ。
8[対面/face to face]：演習（素集合データ構造）
例題を通して素集合データ構造の活用を学ぶ。
9[対面/face to face]：最小全域木構成
素集合データ構造の典型的な活用例として最小全域木構成アルゴリズムを学ぶ。
10[対面/face to face]：演習（最小全域木構成）
例題を通して最小全域木構成に慣れ親しむ。
11[対面/face to face]：平衡二分探索木（1）
有用なデータ構造である平衡二分探索木について学ぶ。
12[対面/face to face]：平衡二分探索木（2）
有用なデータ構造である平衡二分探索木について学ぶ。
13[対面/face to face]：最大流問題
最大流問題と関連する諸問題について学ぶ。
14[対面/face to face]：振り返り
本授業で学んだことを振り返り、アルゴリズムへの理解を定着させる。
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
復習等の授業時間外学習は各週につき4時間を標準とする。
テキスト（教科書）Textbooks
書名: アルゴリズムとデータ構造
著者: 大槻兼資・秋葉拓哉
出版社: 講談社
出版年: 令和2年
参考書References
特になし
成績評価の方法と基準Grading criteria
定期試験（90%）、および、課題の提出状況や講義への貢献などの平常点（10%）で評価。
学生の意見等からの気づきChanges following student comments
板書時には極力教室前方の電気をつけるように留意する。
学生が準備すべき機器他Equipment student needs to prepare
演習にはノートPCを利用する。