アルゴリズム特論

Advanced Lecture for Algorithms

ー

コース応用科目データ科学コース

情報科学研究科

1年

KIIMD5MCA1

2.0単位

講義 (Lecture)

2024年度後期

玉置 卓、照山 順一、宮崎 修一

情報科学研究科

日本語

目標9

随時質問を受け付ける。質問がある場合は、事前に教員にメール等で連絡を取るのが望ましい。

shuichi@gsis.u-hyogo.ac.jp
tamak@gsis.u-hyogo.ac.jp
junichi.teruyama@gsis.u-hyogo.ac.jp

ー

2◎／1〇

ー

ー

講義目的
1. アルゴリズムの基本的な設計技法 (分割統治法、局所探索法、貪欲法、動的計画法など) を習得する。
2. NP完全性のような計算困難性を示すための技法を習得する。
3. 計算困難問題に対するアルゴリズムの設計技法 (近似アルゴリズム、オンラインアルゴリズム、乱択アルゴリズム、固定パラメータ容易性など) を習得する。

到達目標
「講義目的」で述べた3つの内容を理解したうえで、それを他人に説明できるようになる。また、それを応用して自分でアルゴリズムを設計できるようになる。

講義内容
アルゴリズムの基本的な設計技法、計算困難性を示すための技法、計算困難問題に対するアルゴリズムの設計技法について解説する。

授業計画
1. アルゴリズムの基礎
2. グラフの基礎
3. 基本的なアルゴリズム: 動的計画法
4. 基本的なアルゴリズム: 分割統治法
5. 基本的なアルゴリズム: 局所探索法
6. 基本的なアルゴリズム: 貪欲法
7. 問題の複雑さ
8. 近似アルゴリズム
9. オンラインアルゴリズム
10. ここまでの理解度の確認
11. 省領域アルゴリズム
12. 乱択アルゴリズム
13. 固定パラメータ容易性
14. 量子計算の基礎
15. 量子アルゴリズム

※生成系AI の取扱いについて
レポート，小論文，学位論文等については、学生本人が作成することを前提としているため、生成系AIのみを用いて作成することはできません。

教科書は指定せず、講義資料を配布する。

授業中に紹介する。

事前学習
配布された資料に目を通し、理解できない場所を明確にしておく。講義中に出された問題を解いておく。目安は毎回2時間程度。

事後学習
配布資料やノートを見直しながら、授業内容が理解できているかを確認する。また、理解できていない部分の理解に努める。目安は毎回2時間程度。

講義内で随時出題される問題を解き発表するとともに、それに疑問を持った学生や教員からの質問への対応することで、コミュニケーション能力を養う。

基準
講義目的で述べた内容を理解し、それを応用できる者については、講義目的・到達目標に記載する能力の到達度に基づき、S（90点以上）、Ａ（80 点以上）、B（70 点以上）、C（60 点以上）による成績評価のうえ、単位を付与する。

方法
中間試験と期末レポートによる。それぞれを60点満点とし
min｛100, 中間試験の素点+期末レポートの素点｝
を成績とする。それに加え、受講態度（積極的な発言等）を含めて総合的に評価する。

講義の中で出題した問題はその日、あるいは翌週に解答を示す。
中間試験や期末試験の内容に質問があるものは、教員室などで随時質問を受け付ける。

該当しない

講義の進度により内容を変更することがある