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


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

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

授業概要大学学部で学んだアルゴリズムとデータ構造を踏まえて、アルゴリズムの高度な設計と解析の手法を学ぶ。トピックとしては、計算モデル、整列、データ構造、グラフアルゴリズム、並列アルゴリズム、行列計算、整数論的アルゴリズム、NP完全性、近似アルゴリズム等を取り扱う。必ずしも大学学部でアルゴリズムを履修していることを要求するものではないが、コンピュータアルゴリズムについて常識的な知識はあることを前提とする。
達成目標・現実世界で出会うほとんどのアルゴリズムについて解析できる。　
・与えられた問題について最適なアルゴリズムを発見できる。　
・アルゴリズムの正当性を主張できる。
・NP完全性について議論できる。
DPとの関連性DP1：〇
DP2：
DP3：
成績評価方法評価方法
試験：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回　ハフマン符号とLZW圧縮
第5回　共通鍵暗号とデッフィー・エルマン鍵交換
第6回　高速な冪乗計算
第7回　公開鍵暗号とRSA暗号
第8回　これまでのまとめ
第9回　タスクスケジューリング
第10回　ダイクストラのアルゴリズム
第11回　インターネット上の匿名化
第12回　ベルマン・フォードのアルゴリズム
第13回　ページランクのアイデアとハイパーリンク行列
第14回　ショルツ法とフロイド・ワーシャルのアルゴリズム
第15回　まとめとディスカッション
【授業外の課題学習】教科書の事前に指定された範囲を読むこと。課題とされた演習に取り組むこと。前者は180分後者は180分程度を目安とする。　

注意



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

背景色 背景色

フォント フォント

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

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

1

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

文字間隔 文字間隔

0

行の高さ 行の高さ

1.2

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

文字の色 文字の色