アルゴリズムデザイン
アルゴリズムデザイン
機械的な手順で解決可能な問題を解く際には，それぞれの問題にあった個別のアルゴリズムが必要である．その一方で，アルゴリズムの「設計手法」に着眼すると，それらに共通する統一的な手法がいくつか存在する．本講義では，その代表である分割統治法・貪欲法・動的計画法を学習する．アルゴリズムとデータ構造の授業で学習した多くのアルゴリズムがこれらのいずれかにあたること，及び，現実社会で遭遇する典型的な問題がこれらで解決されるこを，理論的な解析を通じて確認する．
講義スケジュール
はじめに（アルゴリズムの設計手法：ソーティングアルゴリズムを例に）
分割統治法１（整数積）
分割統治法２（行列積）
分割統治法３（最近点対問題）
貪欲法１（最短経路探索問題：ダイクストラ法）
貪欲法２ー１（【実装】優先度付きキュー）
貪欲法２ー２（【実装】ダイクストラ法）
到達度確認テスト（中間）
貪欲法３（最小全域木問題：プリム法）
貪欲法４（最小全域木問題：クラスカル法）
貪欲法５（【実装】クラスカル法と union-find データ構造）
動的計画法１（最短経路探索問題：ベルマン・フォード法）
動的計画法２（ナップサック問題）
動的計画法３（巡回セールスマン問題）
Last Update: 02/September/2021