GE7 1801

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

Data Structures and Algorithms

学期曜時限

2学期　水曜日　1・2時限

教室

7A201

3・4年

2単位

担当教員

森継　修一

オフィスアワーと研究室

火18:00～19:30　214

授業概要

知識情報システム構築の基礎となる基本的なデータ構造とアルゴリズムについて解説する。
コンピュータ科学の立場から、既修の数学的知識を活用して、効率的アルゴリズムの設計・解析･評価を行うことを目指す。

学習・教育目標

1. 基本的なアルゴリズムとデータ構造を理解する。
2. 与えられたアルゴリズムに即したプログラミングができるようになる。
3. コンピュータ科学におけるレポートのまとめ方を身に付ける。

授業計画

1. アルゴリズムの計算量

　　　計算量の定義とアルゴリズムの評価・高速アルゴリズムの設計法

1. 探索アルゴリズム

　　　２分探索木・平衡木・Ｂ木・ハッシュ法など。

1. 整列アルゴリズム

　　　特に２次記憶上のデータのソートについて。

1. グラフのアルゴリズム

　　　オイラーグラフ／通路／回路・２部グラフにおけるマッチング・ネットワーク

1. 多項式のアルゴリズム

　　　多項式乗算の高速化・FFTの利用

成績評価の方法

複数回のレポートの総合点による。
（試験でないからといって単位が保証されているわけではない。）

教材・教科書・参考書等

参考書：『岩波講座ソフトウェア科学3　アルゴリズムとデータ構造』石畑清，岩波書店(1989)
参考書：『岩波講座情報科学11　データ管理算法』渋谷政昭・山本毅雄，岩波書店(1983)
参考書：『アルゴリズム＋データ構造＝プログラム』Niklaus Wirth，日本コンピュータ協会(1979)

履修要件
前提知識，他科目との関連等

「情報数学」「基礎数学A」「基礎数学B」「プログラミング演習I」「プログラミング演習II」の単位をすべて取得済みの者に限る。

授業外の学習内容・方法

その日の授業内容に関連する課題を毎週示す。すべての提出を義務付けるものではないが、単位が認定されるためには、規定回数以上のレポートで合格点を取る必要がある。

備考
講義のホームページ等