|
授業科目名
|
担当教員
|
|||||||||||||||||||||
|
アルゴリズムとデータ構造II
|
岩沼 宏治
|
|||||||||||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||||||||||
| 263116 | 2 | CS,F過年度生 | 2 | 後期 | 火 | III | ||||||||||||||||
| ［概要］ | ||||||||||||||||||||||
| 情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Ｉに引き続いて学ぶ．具体的には，情報処理学会J07および<BR>IEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる | ||||||||||||||||||||||
| ［具体的な達成目標］ | ||||||||||||||||||||||
| 1. アルゴリズムの設計における汎用理論と技法について理解し，応用力を養う。<BR>2. 問題の持つ本質的な難しさとそれに起因する計算効率化の限界について理解を深める<BR>3. 幾つかの進んだ先進的なアルゴリズムについて学ぶ | ||||||||||||||||||||||
| ［必要知識・準備］ | ||||||||||||||||||||||
| 離散数学，アルゴリズムとデータ構造Ｉ，プログラミング基礎，プログラミング応用 | ||||||||||||||||||||||
| ［評価方法・評価基準］ | ||||||||||||||||||||||
|
||||||||||||||||||||||
| ［教科書］ | ||||||||||||||||||||||
| ［参考書］ | ||||||||||||||||||||||
| ［講義項目］ | ||||||||||||||||||||||
| 第1回 序論：コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？<BR>第2回 完全2分木の大きさと比較に基づくソート法の時間計算量の下界<BR>第3回 時間計算量の空間的克服：バケットソート、基底ソート<BR>第4回 簡単な最適化問題： 資源配分問題、連続ナップザック問題<BR>第5回 分割統治法： 長大数の乗算、点集合の凸包<BR>第6回 動的計画法： 部分和問題、０−１ナップザック問題<BR>第7回 中間評価（総括とまとめ）<BR>第8回 分岐限定法と緩和手法： ０−１ナップザック問題と連続ナップザック問題<BR>第9回 ヒューリスティック型近似アルゴリズム：貪欲算法、局所探索法、焼きなまし法、Ａ＊法<BR>第10回 精度保証型近似アルゴリズム<BR>第11回 確率的アルゴリズム： 素数判定、ＭＡＸＳＡＴ、グラフＫ彩色<BR>第12回 分散アルゴリズムとオンラインアルゴリズム<BR>第13回 データマイニングアルゴリズム：Aprioi法, FP-木、Prefix-Span法<BR>第14回 計算可能性と不可能性および種々の計算量の階層：<BR>第15回 総合評価（総括とまとめ） | ||||||||||||||||||||||
| ［教育方法］ | ||||||||||||||||||||||
| 講義の概要資料をPowerPointを利用して電子的に作成し，ホームページから配布する<BR>• 適宜，自主勉強用の演習問題プリントを配布する．<BR>• 中間試験の答案用紙の採点結果を返却する予定である．これにより自己の実力の確認を行なってもらいたい． | ||||||||||||||||||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||||||||||||||||||
| (未登録) | ||||||||||||||||||||||
| ［その他］ | ||||||||||||||||||||||
| オフィスアワー：月曜４時限目 | ||||||||||||||||||||||