南山大学

 
指定
期間
秋学期
単位
年次
1・2
担当者
吉田 敦
講義題目
開講キャンパス 瀬戸キャンパス 名古屋キャンパス
授業概要 プログラムを評価する基準の1つに性能がある。プログラムの性能を左右するアルゴリズムやデータ構造に関して、計算量などの基本概念、その評価法、良いアルゴリズムの設計法、よくある問題に対する具体的な良いアルゴリズムやデータ構造に関する知識を学ぶ。
学修目標 1.アルゴリズムを評価する基準と方法を説明できる。
2.いくつかのアルゴリズム設計法を知っている。
3.よくある問題に対する良いアルゴリズムに関する基本知識を持っている。
4.良いアルゴリズムを導くいくつかのデータ構造を知っている。
5.基本的な問題に対して良いアルゴリズムを作成し評価することができる。
授業計画 1.アルゴリズムの基礎
2.分割統治法とソーティング(マージソート)
3.ソーティング(ヒープソート)
4.ソーティング(クイックソート)
5.ソーティング(線形時間ソーティングと順序統計量)
6.基本的なデータ構造(ハッシュ表)
7.基本的なデータ構造(2分探索木)
8.設計と解析の手法(動的計画法)
9.設計と解析の手法(貪欲アルゴリズム)
10.設計と解析の手法(ならし解析)
11.高度なデータ構造(B木)
12.高度なデータ構造(2項ヒープ)
13.グラフアルゴリズム(初等的アルゴリズムと最小全域木)
14.グラフアルゴリズム(最短路問題)
15.まとめ
授業時間外の学習(準備学習など) 授業計画を参照して、テキストの該当部分の予習をしておくこと。
評価方法 レポート(100%)による。
テキスト T.コルメンら(著)、浅野ら(訳):アルゴリズムイントロダクション(第1巻改訂2版 数学的基礎とデータ構造、第2巻改訂2版 アルゴリズムの設計と解析手法)、近代科学社、2007。
その他