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

  [ GB11931 ]
Data Structures and Algorithms
対象:2学年 開設学期:春ABC 曜日・時限:月3・4 単位数:3単位
担当教員:北川博之、天笠俊之、長谷部浩二

概要

ソフトウェアを書く上で基本となるデータ構造とアルゴリズムの考え方について学ぶ。線形構造、木構造、グラフ構造、データ整列、データ探索について学習する。

学習・教育目標

プログラミング技術の基本となるデータ構造とアルゴリズムを理解する。

キーワード

リスト、木、グラフ、整列、探索

Keywords

list, tree, graph, sorting, and search

時間割

授業計画
第1週
1.アルゴリズムとデータ構造の基本概念
アルゴリズムの正しさ、アルゴリズムの評価、データ構造
第2〜3週
2.基本的なデータ構造
配列, リンク配置, 連結リスト, スタック, キュー, 木構造
第4週
3.集合とハッシュ
集合の表現方法と集合に対する操作, 辞書とハッシュ法
第5〜6週
4.全順序集合
ヒープ, 2分探索木, AVL木
第7〜8週
5.整列
単純な整列アルゴリズム, ヒープソート, クイックソート, マージソート
第9週
第8週目までの復習及び中間試験
第10〜11週
6.グラフアルゴリズム
隣接行列,隣接リスト,深さ優先探索,幅優先探索, Dijkstra法
第12〜13週
7.文字列照合
 単純照合法,KMP法, BM法
第14週
8.アルゴリズムの設計手法
分割統治法,グリーディ法, 動的計画法
第15週
第14週目までの復習及び期末試験

教材

教科書:「アルゴリズムとデータ構造」(原隆浩, 水田智史, 大川剛直著)共立出版

参考書籍

「Cで学ぶデータ構造とアルゴリズム」(西原清一著)オーム社

予備知識・前提条件

JavaまたはC言語による簡単なプログラミングの経験があること。

成績評価

成績評価は、中間試験、学期末試験および講義時間中に行われる何回かの小テストの成績を、中間・学期末試験80%、小テスト20%の割合で考慮して行う。

教員メールアドレス

北川博之:kitagawa, 天笠俊之:amagasa, 長谷部浩二:hasebe
のあとに(AT)cs.tsukuba.ac.jp

TF・TA

TA:草村優太、高橋知克、菅野健太、三浦大地(コンピュータサイエンス専攻)

オフィスアワー

水 12:00-13:30 総B903(北川)
特に定めないので、事前にメール等でアポイントを取ること(天笠)