2020年度学院等開講科目情報理工学院数理・計算科学系数理・計算科学コース

アルゴリズム論

開講元: 数理・計算科学コース
担当教員: 伊東利哉
授業形態: 講義 (ZOOM)
メディア利用科目: -
曜日・時限 (講義室): 火3-4 (Zoom) / 金3-4 (Zoom)
クラス: -
科目コード: MCS.T405
単位数: 200
開講時期: 2020年度
開講クォーター: 3Q
シラバス更新日: 2025年7月10日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

問題に応じたアルゴリズムの設計と解析手法について述べる．そのため，導入として，計算モデル，計算量クラス，多項式時間還元と計算量クラスの完全問題を概観する．一方，計算量を尺度とした効率に加え，アルゴリズムから得られる出力の良好度(精度や誤り率など)を尺度として，様々な問題に対するアルゴリズムを設計するとともに，その良好度の理論解析を行う．具体的には，効率的なアルゴリズムとして代表的な乱択アルゴリズム，部分情報から良好な出力を探索するオンライン・アルゴリズム，特殊な構造(独立性の一般概念)を有する問題群に対する貪欲アルゴリズムを示し，それらの理論解析を行う．

到達目標

本講義を履修することにより，以下の能力を習得する．
1) 問題に応じたアルゴリズムの設計と解析手法．
2) 計算量(時間計算量や領域計算量など)を尺度としたアルゴリズムの評価方法
3) 出力の良好度(精度や誤り率など)を尺度としたアルゴリズムの評価方法

キーワード

計算量，乱択アルゴリズム，オンライン・アルゴリズム，近似アルゴリズム，代数的手法，確率的手法

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

数回の講義ごとに，その授業内容の復習のために演習問題を宿題(締切はその次の講義)を出します．次の講義では，その内容の解説を行います．

授業計画・課題

	授業計画	課題
第1回	計算モデル: チューリング機械	計算モデルの基本概念
第2回	計算量クラスと多項式時間還元	計算量の定義，非決定性計算
第3回	NP完全	代表的なNP完全な問題
第4回	[1] 乱択アルゴリズム: 系列の同一性判定 [2] 乱択アルゴリズム: 行列積の同一性判定	[1] 多変数多項式の零点と次数の関係 [2] 非零ベクトルの直行性
第5回	乱択アルゴリズム: 最大カット	期待値の線形性の応用
第6回	非乱択化: 最大カット	2限定独立の応用
第7回	[1] オンライン・アルゴリズム: 仕事割り当て [2] オンライン・アルゴリズム: キャッシング	代表的なオンラインアルゴリズム
第8回	貪欲アルゴリズム: 最小全域木	代表的な貪欲アルゴリズムの例
第9回	貪欲アルゴリズム: 一般化(マトロイド)	貪欲アルゴリズムの特徴付け
第10回	近似アルゴリズムの概要と近似クラス	近似率，近似可能性
第11回	距離空間における巡回セールスマン問題	最小全域木とオイラー閉路の応用
第12回	最大ナップザック問題	多項式時間近似スキーム
第13回	近似困難性	近似クラス真の包含関係
第14回	代数的手法: 集合族/確率的手法: 最大独立集合	代表的な代数的手法と確率的手法の例

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

講義資料はOCW-iで公開あるいは講義中に配布する．

参考書、講義資料等

1. Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010
2. Stasys Jukna, External Combinatorics, Springer, 2001.
3. Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge Univ. Press, 1998.
4. Noga Alon and Joel H. Spencer, The Probabilistic Method, 3rd eds, Wiley, 2008.

成績評価の方法及び基準

数回の講義ごとに出題する宿題に対するレポート（計3回程度）により評価する．

履修の条件・注意事項

履修条件は特に設けないが，アルゴリズムに関する基礎知識が必要である．

連絡先 (メール、電話番号) ※”[at]”を”@”(半角)に変換してください。

伊東利哉 titoh[at]c.titech.ac.jp

オフィスアワー

メールで事前予約すること