96251 アルゴリズム研究
|
選 |
|
秋学期 |
|
2 |
|
1・2 |
|
真野 芳久 |
講義題目 | |
開講キャンパス | 瀬戸キャンパス |
講義内容 | プログラムを作成するための基本的なアルゴリズムとその設計法について概説する。アルゴリズム設計法として貪欲算法、分割統治法、動的計画法、分枝限定法等を紹介する。問題に対して、いくつかのアルゴリズムが考えられるとき、どのアルゴリズムを選択するかを理論的手間の評価である計算複雑度の理論と、実際の手間の評価の双方の話題を、代表的なアルゴリズムを題材にして学ぶ。 |
講義計画 | アルゴリズムに関する基本的な話題(計算量の概念、基本的なアルゴリズム設計法)については学部で学んでいるが、これらの復習を最初に3回程度行なう。 その後、アルゴリズムとデータ構造との密接な関係に焦点を当てつつ、良い計算量のアルゴリズムを与えるデータ構造を抽象データとして議論する。それらには、集合、グラフ、リストなどの基本概念の抽象データ表現方法、B-木、二項ヒープ、互いに素な集合などの高度なデータ構造が含まれる。 |
評価方法 | レポートおよび学期末の定期試験による。 |
テキスト | T.コルメンら著、浅野ら訳:アルゴリズムイントロダクション (第1巻 数学的基礎とデータ構造、 第2巻 アルゴリズムの設計と解析手法、第3巻 精選トピックス)、 近代科学社、1995 |
その他 |