授業科目名	アルゴリズムとデータ構造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 タイトル 計算量理論の入り口：比較に基づくソート法の時間計算量の下限 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 比較に基づくソート法の時間計算量の下界を通して，計算問題の持つ本質的な難しさについて学ぶ 3 タイトル 時間計算量の空間的克服 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 空間を有効に利用するソート法（バケットソート、計数ソート，基底ソート）を学び，大規模メモリを持つ現代的コンピュータ上で有効なアルゴリズム技法を理解する． 4 タイトル はじめての計算量理論 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 計算複雑さと無限階層，PとNP問題クラス，完全問題などを学び，問題の持つ本質的な計算論的難しさと現代的暗号理論への応用などの技術動向について理解する． 5 タイトル 簡単な最適化問題 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 資源配分問題、連続ナップザック問題 6 タイトル 分岐限定法：AIにおける分枝限定法，緩和法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 ０－１ナップザック問題と緩和法，Min-Max木とαーβ分枝限定法 7 タイトル 前半のまとめと中間評価その１ 事前学習 事後学習 これまでの講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 8 タイトル 動的計画法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 部分和問題、０－１ナップザック問題を題材にして，空間的資源を有効に利用するアルゴリズム技法である動的計画法を学ぶ． 9 タイトル 分割統治法 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 簡易型マスター定理，長大数の乗算、点集合の凸包 10 タイトル 近似アルゴリズムその１ 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 人工知能など高速計算が非常に難しい問題を解くために，1960～1980年代前半に盛んに研究されてきたヒューリスティックに基づく近似計算法について学ぶ 11 タイトル 中盤のまとめと中間評価その２ 事前学習 事後学習 これまでの講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 12 タイトル 近似アルゴリズムその２ 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 NP困難問題なと効果的な計算が非常に難しい問題を高速に解くために，1990年度後半から盛んに研究されてきた計算誤差精度が保証される近似アルゴリズムについてその基本を学ぶ． 13 タイトル 巨大データへの挑戦：データマイニングの基礎 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 データマイニング分野を立ち上げた相関ルールマイニング技術の初歩について学ぶ． 14 タイトル ストリームマイニング：オンライン近似計算 事前学習 事後学習 事前配布の講義資料の予習と講義の小テスト 授業内容 高速大容量のストリームデータを高速計算するための離散データマイニング技術の基礎を学ぶ 15 タイトル 期末のまとめと総合評価 事前学習 事後学習 これまでの全ての講義資料の復習 授業内容 これまでの授業のまとめと試験問題の出題意図の解説 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜備考＞
オフィスアワー：月曜４時限目