情報科学部Faculty of Computer and Information Sciences
PRI210KA-CS-161（情報学基礎 / Principles of informatics 200）データ構造とアルゴリズム（再）Data Structures and Algorithms
首藤 裕一Yuichi SUDO
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | J8026-R |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 月1/Mon.1 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | 2～4 |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | ABクラス（※学び直し科目。受講方法は履修ガイド参照。） |
| 他学部公開科目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)
When you write a "good" program, you must learn and make use of standard and well-established techniques. In the course, you will learn algorithm --- well-established techniques for programming. More concretely, you will learn popular algorithms (such as sorting) and learn how to evaluate the computational complexity of algorithms. You will also learn data structures for implementing algorithms with programming languages.
Students will be expected to study the topic given in the class around four hours in each week. Your overall grade in the class will be decided based on the following:
Term-end examination: 100%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
高度なプログラミングには、用途にあった「定石」を使いことなすことが不可欠である。この講義では、その「定石」であるアルゴリズムをつかいこなす第一歩を学ぶ。具体的には、様々な分野の代表的なアルゴリズムを紹介し、プログラム化する方法を学ぶ。アルゴリズムが用途にあうかどうかを判断する最も重要な基準の一つである計算量についても学ぶ。また、アルゴリズムをプログラム化するために不可欠なデータ構造についても学ぶ。
到達目標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]：ガイダンス
アルゴリズムとは何か，データ構造とは何かを理解する．
2[対面/face to face]：挿入ソートと実行時間評価
基本的なソートアルゴリズムである挿入ソートを学ぶとともに、実行時間の解析を行う。
3[対面/face to face]：漸近的表記
アルゴリズムの計算量解析に頻用される関数の漸近的表記（ランダウの記号）を学ぶ。
4[対面/face to face]：マージソート
マージソートを学ぶとともに、実行時間の解析を行う。
5[対面/face to face]：ヒープソート
ヒープソートを学ぶとともに、実行時間の解析を行う。
6[対面/face to face]：クイックソート
クイックソートを学ぶとともに、実行時間の解析を行う。
7[対面/face to face]：4種類のソートの実装
これまでに学んだ4種類の整列アルゴリズムを実装し，実行時間を比較する。
8[対面/face to face]：スタック・キュー
基本的なデータ構造であるスタック、キューを学ぶ。
9[対面/face to face]：優先度付きキュー・連結リスト
基本的なデータ構造である優先度付きキューと連結リストを学ぶ．
10[対面/face to face]：辞書1
重要なデータ構造のひとつである辞書の概念を理解する。
11[対面/face to face]：辞書2
辞書を実現する手法としてチェイン法およびオープンアドレス指定法を学ぶ。
12[対面/face to face]：グラフの表現
グラフを表現するための色々なデータ構造を理解する。
13[対面/face to face]：単一始点最短路問題
グラフに関する代表的アルゴリズムである単一最短路問題とベルマン・フォード法，ダイクストラ法について学ぶ。
14[対面/face to face]：ダイクストラ法のプログラミング
ダイクストラ法の実装を通してグラフアルゴリズムへの理解を深める。
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
本授業の復習等の授業時間外学習は、各週につき4時間を標準とする。
テキスト（教科書）Textbooks
書名: アルゴリズムイントロダクション 第1巻 基礎・ソートと順序統計量・データ構造・数学的基礎 第4版
著者: Thomas H. Cormen他
翻訳：浅野他
出版社: 近代科学者
出版年: 令和5年
参考書References
書名: アルゴリズムとデータ構造
著者: 大槻兼資・秋葉拓哉
出版社: 講談社
出版年: 令和2年
成績評価の方法と基準Grading criteria
定期試験(100%)。ただし，授業における平常点を一部加味する場合もある。
学生の意見等からの気づきChanges following student comments
板書時には極力教室前方の電気をつけるように留意する。
学生が準備すべき機器他Equipment student needs to prepare
演習にはノートPCを利用する。