アルゴリズム・データ構造および演習

http://www.sw.cei.uec.ac.jp/lectures-j.html

授業の概要
本講義では、コンピュータを使用して問題を解いたり計算したりするために、基本的なデータ構造と効率のよいアルゴリズムについて学ぶ。特に、効率のよいアルゴリズムとそうでないものを実際にプログラミングして、それらの実行時間を比較して計算量の違いを実感する。

主題および達成目標
・効率のよいアルゴリズムと、データ構造の果たす役割について講義する。
・効率のよいアルゴリズムの構成について理解することが本講義の目標である。

コンピュータの基礎知識を内容とする科目、およびプログラミング関係の科目。

コンピュータやプログラムについての知識を前提とし、とくに C や Pascal
のプログラムを理解できることを前提とする。

講義資料を配布する予定である。以下の参考書に授業中に述べるアルゴリズムの
多くが説明されている。
Sara Baase: Computer Algorithms, Introduction to Design and Analysis,
3rd Ed., Addison-Wesley 2000
(サラバース著、岩野他訳:アルゴリズム入門 設計と解析、ピアソンエデュケーション
(第2版の訳本))
A.V.Aho, J.E.Hopcroft, J.D.Ullman: The Design and Analysis of Computer
Algorithms, Addison-Wesley, 1974
(エイホ他著、野崎他訳:アルゴリズムの設計と解析 I,II、サイエンス社)

授業内容:
第1回:スタックとその応用(1)
第2回:スタックとその応用(2)
第3回:リスト構造と木
第4回:関数の大きさと計算量, 漸化式
第5回:分割統治法
第6回:挿入ソート, バブルソート
第7回:クイックソート
第8回:マージソート
第9回:ヒープソート(1)
第10回:ヒープソート(2)
第11回:基数ソート, 最小比較回数のソートアルゴリズム
第12回:最大最小を求めるアルゴリズム
第13回:選択アルゴリズム(1)
第14回:選択アルゴリズム(2)
第15回:文字列マッチングアルゴリズム
定期試験

(b) 授業の進め方:
データ構造の応用と、効率よいアルゴリズムについて講義する。
プロジェクタやパソコンを使用して解説するので、授業に欠席しないように
すること。ときどき演習を実施する。

「アルゴリズム」や「データ構造」という名の書籍は多い。授業内容について
参考書で調べたり、アルゴリズムの内容をプログラム化するのもよいと思う。

(a) 評価方法:
原則として、演習レポート内容と期末試験の成績に基づいて総合評価を行う。
(b) 評価基準:
アルゴリズムに関する基本的な事項について正しく理解していることを
もって合格の最低基準とする。

空いている時間ならいつでも可能ですが、
メールでアポイントメントを取ってください。

効率よいアルゴリズムはコンピュータを使用する上で重要である。効率の
よいアルゴリズムとそうでないものとの比較をして、効率のよさを肌で感じて
ほしい。

特になし