基礎情報演習２Ａ

「データ構造とアルゴリズム２」の授業において学習する各種アルゴリズムとデータ構造を演習により、具体的に体得する。具体的な例題を通して、アルゴリズム手法の内容を理解し、計算量を評価し、実際に応用できる能力を養う。

達成目標

1.	基本的なデータ整列アルゴリズムを用いてデータ整列を行うことができる（授業計画の1〜2）。
2.	基本的なグラフアルゴリズムを用いてグラフ上での探索問題を解くことができる（授業計画の3〜8）。
3.	代表的ないくつかの文字列照合アルゴリズムを用いて文字列照合を行うことができる（授業計画の9）。
4.	アルゴリズムの設計手法により代表的な問題を解くことができる（授業計画の10〜14）。

授業計画

1.	ソートI：バブルソート，セレクションソート，インサーションソート，シェルソート
2.	ソートII：ヒープソート，クイックソート
3.	幅優先探索
4.	深さ優先探索
5.	最短経路問題(I)：ダイクストラ法
6.	最短経路問題(II)：ダイクストラ法（続き）
7.	最大流問題(I)
8.	最大流問題(II)（続き）
9.	文字列照合問題：力まかせ法，ボイヤー・ムーア法
10.	再帰：ユークリッドの互除法
11.	動的計画法：フィボナッチ数列
12.	ナップサック問題(I)：
13.	ナップサック問題(II)：動的計画法を用いた解法
14.	グリーディ法：硬貨の交換問題，最小全域木問題
15.	期末試験

評価方法と基準

毎回の出席と課題提出60%（14回），小テスト20%（4回程度），期末試験20%(1回）による。計100点満点で採点し、60点以上を合格とする。

教科書・参考書

浅野哲夫，和田幸一，増澤利光「アルゴリズム論」IT　Text　情報処理学会編，オーム社。この教科書は毎回必ず持参すること。

履修前の準備

「データ構造とアルゴリズム１」および「基礎情報演習１A」を履修し、その内容を理解しておくことが望ましい。また、「データ構造とアルゴリズム２」を同時に履修することを強く推奨する。

オフィスアワー

・	講義、演習中以外ならば、いつでも研究室へどうぞ（ただし、豊洲校舎）。または、後期水曜日12:10-13:00大宮校舎4号館2階講師控室にて。