情報領域演習第三(2クラス)

Google Classroom を使用します (クラスコード: 未定)

効率のよいアルゴリズムを設計する上で重要となるデータ構造について詳しく学習し, 実際にプログラミングを行うことで理解を深める.

基礎プログラミングおよび演習, プログラミング通論, 情報領域演習第一, 情報領域演習第二

なし

演習問題の入手方法は講義内で指示する.
また, 教科書は指定しないが, 以下の書籍を参考に自習するとよい.
R. セジウィック著/野下浩平, 星守, 佐藤創, 田口東 共訳: アルゴリズムC・新版─基礎・データ構造・整列・探索, 近代科学社, 2004年.
T. コルメン, R. リベスト, C. シュタイン, C. ライザーソン/浅野哲夫ほか訳: アルゴリズムイントロダクション第3版. 総合版 (分冊版もあり), 近代科学社, 2013年.

リスト, スタック, キューなどの線形構造や集合・辞書を表すより進んだデータ構造としてハッシュ表や木構造の性質と操作の方法を理解し, 実際にプログラムを記述することで学習を進めるとともに, 基本的なアルゴリズムについても学習する. 主な学習内容は以下の通り.

1. C 言語プログラミングの復習(1) 基礎事項の復習
2. C 言語プログラミングの復習(2) 再帰関数、文字列処理
3. C 言語プログラミングの復習(3) 構造体
4. C 言語プログラミングの復習(4) ポインタ、スタックやキューの実装と応用
5. リストに対する基本操作
6. リストの応用
7. 基本的な探索と整列
8. 効率のよい整列(1)
9. 効率のよい整列(2)
10. 二分探索とハッシュ法
11. 基本的な木構造とその操作
12. 平衡木(1)
13. 平衡木(2)
14. グラフ構造に対する基本操作
15. グラフの応用

ただし、本演習のカバーする範囲の新たな課題を導入することもある。

前学期の「プログラミング通論」と同学期に並行して実施される「アルゴリズム論第一」の講義内容を十分に理解しておくこと. また, 理解を深めるために参考図書などによる自主的な学習を推奨する.

評価方法: 課題, レポートの内容を通じて評価する.
評価基準: 各回の課題を締切までに必ず提出すること. これまで学習したデータ構造やアルゴリズムの特徴を理解し, 与えられた問題に対して適切なデータ構造やアルゴリズムを選択できることが必要となる. 15 回を通した全問題の 60% に正当すれば合格できる(ただし無断欠席や他者の回答の盗用などによる大きなペナルティがある場合は, その限りではない).

授業終了後, もしくは, 予めメールでアポイントをとること.

本講義の目的はプログラミングを通じて, データ構造やアルゴリズムへの理解を深めることです. 完成したプログラムを単に書き写すのではなく, 自分で考えながら手を動かしてプログラミングに必要な技術を習得してください. 単にネットの情報を流用したり, 他所に教えてもらうだけでは力はつきません.

なし