トップ > カリキュラム > 時間割 > シラバス一覧 > GC12401 データ構造とアルゴリズム

シラバス

GC12401

データ構造とアルゴリズム Data Structures and Algorithms

標準履修年次: 2年専門基礎・必修 ・2 単位
春学期AB  木曜日  5・6時限  7A105
担当教員: 古瀬 一隆・乾 孝司

概要

計算機ソフトウェアを書く上で基本となるデータ構造とアルゴリズムの考え方について主に理論的な面を学ぶ。本科目とペアとなっている「データ構造とアルゴリズム実習」では本授業で学んだことを実際にプログラムすることによって実践的に本科目の内容を理解する。

学習・教育目標

以下の概念などを理解する。
  • データ構造とアルゴリズムの関係
  • アルゴリズムの複雑さ(漸近計算量)に関する基本的な概念
  • 線形構造と木構造
  • データ整列の基本アルゴリズム
  • データ探索の基本アルゴリズム

授業計画

講義内容
第 1 週 イントロダクション
データ構造とアルゴリズムとは、擬似コード、アルゴリズムの複雑さ
第 2 週 線形構造と再帰
配列、線形リスト、キュー、スタック、再帰とスタック
第 3 週 木構造
木の定義と用語,木のデータ構造、木の走査
第 4 週 データ整列I
選択整列法、バブル整列法などの初等的なデータ整列法、クイックソート
第 5 週 データ整列II
基数整列法、マージソート、ヒープソート
第 6 週 データ探索I
線形探索、二分探索、二分探索木
第 7 週 データ探索II
平衡木、ハッシュ法
第 8 週 グラフ構造I
グラフの定義と用語、グラフのデータ構造、グラフの探索
第 9 週 グラフ構造II
連結性、最短路問題
第 10 週 その他のアルゴリズム
文字列照合、さまざまなアルゴリズム

教材・参考書等

教科書:「アルゴリズムC 第1巻 基礎・整列」, R.セジウィック著(野下他訳),近代科学社, 2800円+税, 1996.
参考書:「アルゴリズムC 第2巻 探索・文字列・計算幾何」, R.セジウィック著(野下他訳),近代科学社, 3200円+税, 1996.
(ただし、参考書も購入予定で意欲のある者には上記の教科書+参考書の代わりに以下の本を教科書として薦める。
「アルゴリズムC・新版」, R.セジウィック著(野下他訳),近代科学社, 6800円+税, 2004.
「データ構造とアルゴリズム実習」の第1回目の授業のときにこれらの本の違いは説明する。)

成績評価

学期末試験を主に成績を決定する。講義に出席することが成績評価の前提となるのできちんと出席すること。

授業外の学習

「データ構造とアルゴリズム」および「同実習」を学修するために必要な総時間は 135時間(45×3)である。 授業時間が60時間(1.5×10×4)あるので、予習・復習・ 宿題やレポートに授業時間外でかける時間は 少なくとも75時間は必要である。予習・復習・実習への時間配分にバランスを取ること。

予備知識・前提条件

基本的な計算機およびプログラミング(C言語)の知識・スキルが必要である。

教員連絡先・オフィスアワー

教員一覧ページ を参照。