アルゴリズム特論(99MD013)


授業名アルゴリズム特論(99MD013)授業名（英）
教員名神林　靖
開講年度学期2025年度 後期
曜日時限木曜6限
開講学科大学院 工学研究科 数理情報科学専攻

単位2.0学年修士課程1年
区分専門科目 講義・演習課程選択

概要大学学部で学んだアルゴリズムとデータ構造を踏まえて、アルゴリズムの高度な設計と解析の手法を学ぶ。トピックとしては、計算モデル、整列、データ構造、グラフアルゴリズム、並列アルゴリズム、行列計算、整数論的アルゴリズム、NP完全性、近似アルゴリズム等を取り扱う。必ずしも大学学部でアルゴリズムを履修していることを要求するものではないが、コンピュータアルゴリズムについて常識的な知識はあることを前提とする。
達成目標・現実世界で出会うほとんどのアルゴリズムについて解析できる。　
・与えられた問題について最適なアルゴリズムを発見できる。　
・アルゴリズムの正当性を主張できる。
・NP完全性について議論できる。
学習教育目標
成績評価方法評価方法
試験：50％，演習：50％
評価基準
試験と演習の成績の合計に基づいて，以下のような評価を行う。
S: 90～100点　A: 80～89点　B: 70～79点　C: 60～69点　D: 59点以下　不合格　
再試験は実施しない。
教科書Panos Louridas, "Real-World Algorithms: a Beginer's Guide", MIT Press, 2017.
参考書T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: “Introduction to Algorithms” Fourth Edition, MIT Press, 2022.
履修上の注意十分なプログラミングの経験があることが望ましい。

授業計画【授業計画】
第1回　グラフ表現
第2回　迷路探索（１）
第3回　迷路探索（２）
第4回　符号化
第5回　ハフマン符号
第6回　圧縮
第7回　暗号
第8回　デッフィー・エルマン鍵交換
第9回　高速な冪乗計算
第10回　RSA暗号
第11回　インターネット上の匿名化
第12回　タスクスケジューリング（１）
第13回　タスクスケジューリング（２）
第14回　グラフと探索アルゴリズム
第15回　定期試験
【授業外の課題学習】教科書の事前に指定された範囲を読むこと。課題とされた演習に取り組むこと。前者は180分後者は180分程度を目安とする。　

注意



アクセシビリティ
全てをリセット

背景色 背景色

フォント フォント

フォントカーニング フォントカーニング

文字の大きさ 文字の大きさ

1

画像の可視性 画像の可視性

文字間隔 文字間隔

0

行の高さ 行の高さ

1.2

リンクの強調 リンクの強調

文字の色 文字の色