科目ナンバー

SE-IG2-8A32

履修条件・関連科目等

「数理情報学１」の履修が望ましい。

授業で使用する言語

日本語

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

授業の概要

アルゴリズムは目的を達成するための計算手順のことである。アルゴリズムの良し悪しによって情報システム全体の効率が大きく変わることから、効率の良いアルゴリズムを設計する能力は情報技術者にとって必要不可欠な技術である。本授業では、効率の良いアルゴリズムを設計するための代表的な手法について学ぶ。目的に応じて適切なアルゴリズムを与えることができるようになることを目指す。

科目目的

効率的なアルゴリズムを設計する際に必要となる考え方や思考力を身につけること。

到達目標

授業で解説する貪欲法、分割統治法、動的計画法などの代表的なアルゴリズム設計手法について理解し、未知の問題に対しても適切なアルゴリズムを設計することができるようになること。

授業計画と内容

第1回　貪欲法1：区間スケジューリング
第2回　貪欲法2：最大遅延最小化スケジューリング
第3回　貪欲法3：最小全域木問題
第4回　貪欲法4：ハフマン符号
第5回　分割統治法1：マージソート、漸化式の解析
第6回　分割統治法2： 反転数の数え上げ
第7回　分割統治法3：選択アルゴリズム
第8回　分割統治法4：Strassenの行列積アルゴリズム
第9回　動的計画法1：重み付き区間スケジューリング
第10回　動的計画法2：ナップサック問題
第11回　動的計画法3：連鎖行列積　
第12回　動的計画法4: 最短路問題に対するベルマン・フォード法
第13回　その他のアルゴリズム
第14回　まとめ

授業時間外の学修の内容

指定したテキストやレジュメを事前に読み込むこと／授業終了後の課題提出

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

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

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

成績評価の方法・基準

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

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

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

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

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

実施しない

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

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

その他

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

manabaの小テスト機能を用いて復習のための演習問題を出題する。

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

いいえ

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

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

テキスト・参考文献等

テキスト・授業資料をmanabaに掲載する。

参考書：
Kleinberg and E. Tardos 著（浅野孝夫、他、訳）：アルゴリズムデザイン（共立出版）
T.コルメン、C.ライザーソン、R.リベスト、C.シュタイン 著（浅野哲夫、他、訳）：アルゴリズムイントロダクション、第1巻 数学的基礎とデータ構造（近代科学社）
T.コルメン、C.ライザーソン、R.リベスト、C.シュタイン 著（浅野哲夫、他、訳）：アルゴリズムイントロダクション、第2巻 アルゴリズムの設計と解析手法（近代科学社）

その他特記事項

参考URL

https://researchmap.jp/takuro_fukunaga/