授業科目名	アルゴリズムとデータ構造II
時間割番号	TCS209
担当教員名	岩沼　宏治
開講学期・曜日・時限	後期・火・III	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Ｉに引き続いて学ぶ．具体的には，情報処理学会J07およびIEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>コンピュータ理工学科向け 記号 コンピテンシー（能力・資質）   CS-A 専門 5.時代の変化に対応できるよう、最新の技術動向を考慮して、自律的・継続的に学習できる。 ○ CS-B 6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。 6a.解決すべき問題を形式化することができる。 ◎ CS-C 6b.要求、時間、費用、資源等の制約条件を考慮した上で、複数の解が存在するような複雑な問題の中から適切な解を見つけ出すことができ ○
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 CS 1 アルゴリズムを設計するための代表的な汎用手法を理解し，応用できること CS-B 2 幾つかの先進的なアルゴリズム理論について理解し説明できること CS-C 3 現実社会における先端的例としてのデータマイニングについて理解し説明できること CS-A
＜成績評価の方法＞
目標No 割合 評価の観点 1 60% 総合的な理解度と応用力を評価する 2 30% 理解度を評価する 3 10% 理解度を氷解する 合計 100%
＜授業の方法＞
オンデマンド型講義資料を用いた事前学習と講義当日のライブ型遠隔授業を組み合わせた講義を行う ・適宜，自主勉強用の演習問題を配布する． ・成績評価は複数回の定期試験，小テストとレポートにより行う．
＜受講に際して・学生へのメッセージ＞
離散数学，アルゴリズムとデータ構造Ｉ，プログラミング基礎，プログラミング応用,　計算機アーキテクチャアI及びII　が関連知識，前提知識である．
＜テキスト＞
岩沼宏冶，美濃英俊，鍋島英知，山本泰生, データ構造とアルゴリズム（電子情報通信レクチャーシリーズB－８）, コロナ社, ISBN:9784339018233
＜参考書＞
R.セジウィック著、野下、星、佐藤、田口訳, アルゴリズムＣ＋＋, 近代科学社, ISBN:4764902222 杉原厚吉, データ構造とアルゴリズム, 共立出版, ISBN:4320120345 杉原、茨木、浅野、山下編,, アルゴリズム工学　－計算困難問題への挑戦ー, 共立出版, ISBN:4320120124 岩間 一雄, アルゴリズム・サイエンス:出口からの超入門, 共立出版, ISBN:4320121686 茨木 俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191
＜授業計画の概要＞
1 タイトル ガイダンスと序論 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？について考察する 2 タイトル 計算問題の本質的な難しさ：計算量理論の入り口 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 完全2分木の大きさと比較に基づくソート法の時間計算量の下界について学ぶ 3 タイトル 時間計算量の空間的克服 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 バケットソート、計数ソート，基底ソート 4 タイトル はじめての計算量理論 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 計算複雑さと無限階層，PとNP問題クラス，完全問題 5 タイトル 簡単な最適化問題 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 資源配分問題、連続ナップザック問題 6 タイトル 分岐限定法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 ０－１ナップザック問題と連続ナップザック問題，Min-Max木とαーβ分枝限定法 7 タイトル 前半のまとめと中間評価その１ 事前学習 事後学習 これまでの講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 8 タイトル 動的計画法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 部分和問題、０－１ナップザック問題 9 タイトル 分割統治法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 簡易型マスター定理，長大数の乗算、点集合の凸包 10 タイトル 近似アルゴリズムその１ 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 ヒューリスティックに基づく手法 11 タイトル 中盤のまとめと中間評価その２ 事前学習 事後学習 これまでの講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 12 タイトル 近似アルゴリズムその２ 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 誤差や制度を保証するアルゴリズム 13 タイトル 巨大データへの挑戦：データマイニングの基礎 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 頻出アイテム集合，Apriori原理，相関ルールマイニング 14 タイトル オンライン近似計算 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 ストリーム頻出アイテムマイニング．近似計算 15 タイトル 期末のまとめと総合評価 事前学習 事後学習 これまでの全ての講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜備考＞
オフィスアワー：月曜４時限目