アルゴリズム論第二

今回は使用しません ★★その他の項目の遠隔授業情報を参照すること★★

コンピュータ技術, 情報通信技術の進歩とともに,
ハードウエアを動かすためのソフトウエア/アルゴリズムの
理論の重要性が認識されている. 画像データの圧縮技術や
情報を安全に送信するための暗号化技術, DNA 配列に
符号化されている遺伝情報の解析など, 非常に広範な分野で
アルゴリズムの理論が研究され, 実用化されている.

本講義では, アルゴリズム論における基礎的な問題を題材として,
効率の良いアルゴリズムを設計するための理論・技術を学ぶ.
より具体的には, 以下を達成目標とする.

1) 講義で取り扱う各基礎問題に対するアルゴリズムの動作と
正当性およびその計算量の解析結果を理解する.
2) 講義で紹介する貪欲算法や動的計画法に代表される
アルゴリズムの設計手法の原理を理解する.

プログラミング通論, アルゴリズム論第一

特になし

資料を配付する.

(a) 授業内容

できるだけ多くのトピックを選んで,
応用上役に立つアルゴリズムの設計手法について講義する.

第1回:グラフアルゴリズム(1):最小全域木問題等
第2回:グラフアルゴリズム(2):最短経路問題等
第3回:動的計画法の適用例(1):オートマトンから正則表現への変換
第4回:動的計画法の適用例(2):文脈自由文法の認識問題
第5回:動的計画法の適用例(3):文脈自由文法の認識問題における再帰構造の導出
第6回:動的計画法の適用例(4):隠れマルコフモデルとは
第7回:動的計画法の適用例(5):隠れマルコフモデルの認識問題
第8回;動的計画法の適用例(6):隠れマルコフモデルの認識アルゴリズム
第9回:動的計画法の適用例(7):近似文字列照合問題
第10回:KMPアルゴリズムにおける失敗関数の計算
第11回:KMPアルゴリズムにおけるオートマトンの構成アルゴリズム
第12回:その他のアルゴリズム
第13回:NP完全・NP困難性とは
第14回:NP困難問題に対する分枝限定法の理論
第15回:その他のアルゴリズム + 期末試験

(b)授業の進め方

講義では, 各問題の背景と動機を説明した後,
アルゴリズムを導入し, その正当性の
証明と計算量の解析を与える.

予習・復習は十分に行い,
できればアルゴリズムの実装などもして欲しい。

(a) 成績評価方法

試験の成績(100%) (期末試験以外に試験を実施することもある)

(b) 評価基準

達成目標で述べた1)と2)の達成度が一定の水準以上であれば合格とする.

適宜相談に応じるが, メールなどで事前にアポイントを取ること.

紹介したアルゴリズムを単に実装できるようになるだけでなく,
計算効率を上げるためにどのような工夫がされているか,
なぜ正しく動くのかを「理解」してほしい.

特になし