科目ナンバー

SG-IG5-8C01

履修条件・関連科目等

線形計画法やアルゴリズムに関する基礎知識があることが望ましい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

グラフ（ネットワーク）上の最適化問題など，離散的な構造を持つ計算問題に対するアルゴリズムの設計手法について学習する。特に、NP困難であり多項式時間で厳密に解くことが難しい問題に焦点を当てる。これらの問題に対する近似アルゴリズムや固定パラメータ容易アルゴリズムを学ぶことを通し、数理計画法や乱択、離散数学を利用したアルゴリズムの考え方について学ぶ。

科目目的

離散アルゴリズム設計の考え方を理解し、最新の研究動向を追うための基礎知識を身につける。

到達目標

取り上げたアルゴリズムの仕組みを理解し説明できる。

授業計画と内容

第1回 ネットワークフロー、線形計画法
第2回 線形計画法を用いた近似アルゴリズム設計、頂点被覆問題
第3回 TSP
第4回 集合被覆問題
第5回 シュタイナー森問題
第6回 賞金収集シュタイナー木問題
第7回 頂点重みシュタイナー木問題
第8回 グラフの最大カット
第9回 中間発表
第10回 乗算重み更新法
第11回 固定パラメータ容易アルゴリズム
第12回 カーネル化
第13回 グラフの木分解: 定義
第14回 木分解を利用した厳密アルゴリズム

授業時間外の学修の内容

指定したテキストやレジュメを事前に読み込むこと

授業時間外の学修の内容（その他の内容等）

授業中に出題する演習問題を解くことで理解を確認する。さらに、授業で取り上げた論文や関連論文に目を通すことで、発展的な話題を自習することを勧める。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

プレゼンテーション

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

参考文献
D. Williamson and D. Shmoys 著(浅野孝夫、訳）：「近似アルゴリズムデザイン」(共立出版）。
J. Kleinberg and E. Tados著（浅野孝夫、浅野泰仁、他、訳）：「アルゴリズムデザイン」（共立出版）。
R. Niedermeier: Invitation to Fixed-Parameter Algorithms (Oxford University Press).

その他特記事項

参考URL

https://researchmap.jp/takuro_fukunaga/