2025年度 (最新) 学院等開講科目情報理工学院情報工学系

データ構造とアルゴリズム

シラバス

本講義では，アルゴリズムとデータ構造の基本を学ぶ．前半では基本的なデータ構造とそのデータ構造を操作するアルゴリズム，後半ではより高度なアルゴリズムについて学ぶ．

本講義を履修することにより以下を修得する．
(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%)

履修条件は特に設けないが，関連する科目を履修していることが望ましい．

新型コロナ感染対策として履修人数制限が必要な場合には、情報工学系の学生を優先することがあります.