情報科学部Faculty of Computer and Information Sciences
PRI210KA-CS-261(情報学基礎 / Principles of informatics 200)データ構造とアルゴリズム2Design and Analysis of Algorithm 2
首藤 裕一Yuichi SUDO
授業コードなどClass code etc
学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
添付ファイル名Attached documents | |
年度Year | 2023 |
授業コードClass code | J0516 |
旧授業コードPrevious Class code | |
旧科目名Previous Class title | |
開講時期Term | 秋学期授業/Fall |
曜日・時限Day/Period | 水5/Wed.5 |
科目種別Class Type | |
キャンパスCampus | 小金井 / Koganei |
教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
配当年次Grade | 2~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) |
(1) 受講希望者 (受講検討中の者も含む) は、情報科学部学部Googleフォーム(https://forms.gle/ECvwxVe2NcxmrbTK9)で初回講義前までに希望申請をしてください。(※以下URLのご案内があるGoogleフォームとは異なるのでご注意ください。) (2) 以下のURLと教育開発支援機構事務局の案内に従って、履修希望の申請を行ってください。 https://www.hoseikyoiku.jp/risyu/index.html (3) 履修取消については、ご自身の所属学部の履修取消期間内に必ず同時に履修削除を行ってください。 |
実務経験のある教員による授業科目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
計算機科学を学ぶ上で必須となるデータ構造とアルゴリズムの基礎を理解するとともに、典型的なアルゴリズム設計技法を習得する。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか(該当授業科目と学位授与方針に明示された学習成果との関連)Which item of the diploma policy will be obtained by taking this class?
情報科学部ディプロマポリシーのうち「DP2」と「DP4-1」に関連
授業で使用する言語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]:貪欲法
頻用技法である貪欲法を学ぶ。
6[対面/face to face]:演習(動的計画法・貪欲法)
例題を通して動的計画法・貪欲法に慣れ親しむ。
7[対面/face to face]:素集合データ構造
有用なデータ構造である素集合データ構造(Union-Find)を学ぶ。
8[対面/face to face]:演習(素集合データ構造)
例題を通して素集合データ構造の活用を学ぶ。
9[対面/face to face]:最大流問題
最大流問題と関連する諸問題について学ぶ。
10[対面/face to face]:演習(最大流問題)
例題を通して最大流問題を解くアルゴリズムとその活用に慣れ親しむ。
11[対面/face to face]:平衡二分探索木
有用なデータ構造である平衡二分探索木について学ぶ。
12[対面/face to face]:演習(平衡二分探索木)
例題を通して平衡二分探索木の活用を学ぶ。
13[対面/face to face]:発展的内容(近似アルゴリズムおよびNP困難性)
近似アルゴリズムやNP困難性などの発展的な内容に触れる。
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を利用する。