講義コード
授業番号
授業科目名アルゴリズムとデータ構造
科目名(英題)
講義題目
授業科目区分コア科目(計算機)
開講年度2009
開講学期前期
曜日時限
必修選択選択
単位数2.0
担当教員山下雅史
対象学部等システム情報科学府・情報学専攻
対象学年修士1年
開講地区伊都地区
履修条件特になし
授業概要時代が要請し, 新しくアルゴリズムやデータ構造が開発されてきた 領域に以下のものがある. まず, バイオインフォマティクスやナノ 技術といった応用分野を想定し, 巨大データを扱うための計算パラダイムが提案されてきた. つぎに, セキュリティという重要な応用 分野が出現し, 整数論に基づくアルゴリズムが整備されてきた. そ して最後に, インターネットや並列計算機といった新しい環境を想 定したアルゴリズムが開発されてきた. 本講義では, これらの最新の成果のいくつかを講義する.
全体の教育目標情報科学の社会への影響力は急速に増大している.これに従って, 複雑で巨大な問題を正確かつ高速に解くことが必要になっている. そこで, 時代が要請する高度なアルゴリズムとデータ構造を学生 に習熟させることを目標とする.
個別の学習目標授業計画を参照のこと.
授業計画1: 基本アルゴリズムの復習 (1)
動的計画法, 貪欲アルゴリズム
2: 基本アルゴリズムの復習 (2)
最小全域木アルゴリズム, 最大流アルゴリズム
3: ソーティングネットワーク
4: 行列演算
5: 線形計画法
6: 多項式とFFT
7: 中間試験
8: 整数論的アルゴリズム
9: 文字列アルゴリズム
10: 計算幾何学
11: オンラインアルゴリズム
12: NP完全性
13: 近似アルゴリズム
14: 乱択アルゴリズム
15: まとめ
キーワードアルゴリズム、データ構造
授業の進め方教科書を中心に授業を行います。
テキストIntroduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein
参考書
学習相談教員室(場所は授業中に提示する)で学習相談を行います.希望する者は,事前に電子メールで相談希望日時,相談内容を連絡し,予約して下さい.
試験/成績評価の方法等試験および宿題によって評価する。
その他アルゴリズムのおもしろさを分かってもらえるような講義にしたい.