現実に直面する組合せ最適化問題には、実用的な時間で最適解を求められそうにないものが多いことが知られている。本講義では、そのような計算困難問題に対する現実的なアルゴリズムの設計手法を学習する。根幹をなすNP完全性と理論計算機科学で近年多くの成果が発表されているアルゴリズム設計手法について解説する。本講義では、さまざまなアルゴリズム設計手法を、具体的なアルゴリズムとその性能解析とともに解説する。これにより、現実に直面する問題に対して、計算困難さを見積もり、さまざまなアプローチでアルゴリズムを設計できるようになることを目指す。表示可能なデータがありません。クラスPについて学習する。クラスPを定義したうえで、クラスPに含まれる問題をいくつか解説する。アルゴリズム設計手法の一つである貪欲法について解説する。クラスNPについて学習する。NP困難、NP完全の概念を解説する。組合せ最適化問題がNP完全である場合、全ての入力インスタンスに対して、多項式時間で、最適解を出力するアルゴリズムが存在しそうにないことを解説する。NP完全問題に対する現実的なアプローチとして、制限された入力インスタンスに対して、多項式時間で、最適解を出力するアルゴリズムの設計手法を学ぶ。擬多項式時間アルゴリズム、固定パラメータアルゴリズムについて解説する。NP完全問題に対する現実的なアプローチとして、全ての入力インスタンスに対して、比較的小さい指数時間で、最適解を出力するアルゴリズムの設計手法を学ぶ。用いた指数時間アルゴリズム設計手法について解説する。NP完全問題に対する現実的なアプローチとして、全ての入力インスタンスに対して、多項式時間で、近似解を出力するアルゴリズム(近似アルゴリズム)の設計手法を学ぶ。TSPを例として、近似アルゴリズムの設計手法と近似困難性について解説する。第5回に引き続き、近似アルゴリズムの設計手法について解説する。線形計画問題を用いた近似アルゴリズム設計手法、PTAS、FPTASについて解説する。乱数を用いたアルゴリズム(乱択アルゴリズム)の設計手法について解説する。乱択アルゴリズムの分類を解説したうえで、乱択クイックソート、乱択素数判定アルゴリズムなど、基礎的かつ重要な乱択アルゴリズムについて解説する。講義のまとめを行ない、試験によって受講者の習熟度を判定する。L3(IS)テキスト・参考書テキスト特に指定しない。本ページで資料を配布する。履修条件アルゴリズムとデータ構造、グラフ理論に関する基礎知識があることが望ましい。・試験(60%)およびレポート(40%)により評価する。・アルゴリズム設計手法の理解、基礎知識の習得を基準とする。