授業科目名				担当教員
アルゴリズムとデータ構造II				岩沼　宏治
時間割番号	単位数	コース	履修年次	期別	曜日	時限
TCS209	2	CS,F	2	後期	火	III
［概要］
情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Ｉに引き続いて学ぶ．具体的には，情報処理学会J07および<BR>IEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる
［具体的な達成目標］
1.　アルゴリズムを設計するための代表的な汎用手法を理解し，応用力を養う。<BR>2.　幾つかの先進的なアルゴリズム理論について理解を深める<BR>3.　現実社会における例として，巨大データを扱うデータマイニングを取り上げ，上述の理論と技術の適用実例について学ぶ
［必要知識・準備］
離散数学，アルゴリズムとデータ構造Ｉ，プログラミング基礎，プログラミング応用,<BR>計算機アーキテクチャアI及びII
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：期末期  40  % 講義の理解度を評価する  2 試験：中間期  40  % 講義の理解度を評価する  3 小テスト／レポート  20  % 講義の理解度を評価する
［教科書］
(未登録)
［参考書］
R.セジウィック著、野下、星、佐藤、田口訳, アルゴリズムＣ＋＋, 近代科学社, ISBN:4764902222 Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining, Addison-Wesley Companion, ISBN:0321321367 杉原、茨木、浅野、山下編,, アルゴリズム工学　−計算困難問題への挑戦ー, 共立出版, ISBN:4320120124 岩間 一雄, アルゴリズム・サイエンス:出口からの超入門, 共立出版, ISBN:4320121686 茨木 俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191
［講義項目］
第1回　序論：コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？<BR>第2回　完全2分木の大きさと比較に基づくソート法の時間計算量の下界<BR>第3回　時間計算量の空間的克服：バケットソート、基底ソート<BR>第4回　簡単な最適化問題：　資源配分問題、連続ナップザック問題<BR>第5回　分割統治法：　長大数の乗算、点集合の凸包<BR>第6回 動的計画法：　部分和問題、０−１ナップザック問題<BR>第7回　分岐限定法と緩和手法：　０−１ナップザック問題と連続ナップザック問題<BR>第8回　ヒューリスティック型近似アルゴリズム：貪欲算法、局所探索法、焼きなまし法<BR>第9回　演習<BR>第10回　中間評価（総括とまとめ）<BR>第11回 データマイニング：入門<BR>第12回 データマイニング：Aprioriアルゴリズム<BR>第13回 データマイニング：オンライン法と近似アルゴリズム<BR>第14回 演習<BR>第15回 総合評価（総括とまとめ）
［教育方法］
講義の概要資料をPowerPointを利用して電子的に作成し，ホームページから配布する<BR>・適宜，自主勉強用の演習問題を配布する．<BR>・中間試験の答案用紙の採点結果を返却する予定である．これにより自己の実力の確認を行なってもらいたい．
［JABEEプログラムの学習・教育目標との対応］
(未登録)
［その他］
オフィスアワー：月曜４時限目