2025年度 (最新) 学院等開講科目 情報理工学院 情報工学系
データ構造とアルゴリズム
- 開講元
- 情報工学系
- 担当教員
- 小池 英樹
- 授業形態
- 講義 (対面型)
- メディア利用科目
- -
- 曜日・時限
(講義室) - 火5-6 (W9-324(W933)) / 金5-6 (W9-324(W933))
- クラス
- -
- 科目コード
- CSC.T271
- 単位数
- 200
- 開講時期
- 2025年度
- 開講クォーター
- 4Q
- シラバス更新日
- 2025年4月2日
- 使用言語
- 日本語
シラバス
授業の目的（ねらい）、概要
本講義では，アルゴリズムとデータ構造の基本を学ぶ．前半では基本的なデータ構造とそのデータ構造を操作するアルゴリズム，後半ではより高度なアルゴリズムについて学ぶ．
到達目標
本講義を履修することにより以下を修得する．
(1) 計算機科学の基礎となるデータ構造とアルゴリズムに関する知識
(2) 上のデータ構造とアルゴリズムのCによる実装
(3) 各アルゴリズムの効率に関する知識
キーワード
リスト，スタック，木，２分木，グラフ，ソート，分割統治法，動的計画法，文字列照合
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
授業の進め方
各講義の後，ホームワーク課題が与えられる．課題では講義で学んだアルゴリズムとデータ構造をCプログラムとして実装する．
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | イントロダクション |
アルゴリズムとはなにかについて学ぶを学ぶ |
| 第2回 | 抽象データ型，計算効率 |
抽象データ型、計算効率について学ぶ |
| 第3回 | 基本的なデータ構造：リスト，スタック，待ち行列 |
リスト、スタック、待ち行列について学ぶ |
| 第4回 | 基本的なデータ構造：グラフ，木と２分木 |
グラフ、木、2分木を理解する |
| 第5回 | 基本的なデータ構造：辞書とハッシュ |
辞書とハッシュについて学ぶ |
| 第6回 | 順序付き集合の処理：ヒープ，２分探索木，平衡探索木 |
順序付き集合について学ぶ |
| 第7回 | 中間試験 |
|
| 第8回 | 整列のアルゴリズム：バブルソート，挿入ソート，選択ソート |
整列アルゴリズムを学ぶ |
| 第9回 | 整列のアルゴリズム：ヒープソート、マージソート、クイックソート |
整列アルゴリズムを学ぶ |
| 第10回 | グラフアルゴリズム: グラフのデータ構造，深さ優先探索，幅優先探索 |
グラフアルゴリズムについて学ぶ |
| 第11回 | グラフアルゴリズム：最短経路（Dijkstra, Floyd-Warshall)，最小全域木(Kruskal, Prim) |
グラフアルゴリズムについて学ぶ |
| 第12回 | 文字列の照合 |
文字列照合のアルゴリズムについて知る |
| 第13回 | 高度な問題に対するアルゴリズム |
高度な問題に対するアルゴリズムを学ぶ |
| 第14回 | 期末試験 |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
資料を講義中に配布
参考書、講義資料等
茨木俊秀：「Ｃによるアルゴリズムとデータ構造」，オーム社，ISBN 978-4-274-21604-6
セジウィック：「アルゴリズムC 第1〜4部 -基礎・データ構造・整列・探索」，近代科学社，ISBN 978-4764905603
成績評価の方法及び基準
中間テスト (30%)
プログラミング課題 or レポート (40%)
期末試験 (30%)
関連する科目
- GRE.C101 ： 情報基礎学第一
- GRE.C102 ： 情報基礎学第二
- CSC.T243 ： 手続き型プログラミング基礎
- CSC.T253 ： 手続き型プログラミング発展
- LAS.I121 ： コンピュータサイエンス第一
- LAS.I122 ： コンピュータサイエンス第二
履修の条件・注意事項
履修条件は特に設けないが，関連する科目を履修していることが望ましい．
その他
新型コロナ感染対策として履修人数制限が必要な場合には、情報工学系の学生を優先することがあります.