授業科目名	アルゴリズムとデータ構造II
時間割番号	TCS209
担当教員名	岩沼　宏治
開講学期・曜日・時限	後期・火・III	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Ｉに引き続いて学ぶ．具体的には，情報処理学会J07およびIEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部(～2023年度入学生)>コンピュータ理工学科向け 記号 コンピテンシー（能力・資質）   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%
＜授業の方法＞
講義は面接授業を基本として，小テスト（オンライン型）を毎回行う． ・Moodle上に講義資料と復習用動画資料を公開し，オンデマンド型授業の長所を取り入れる． ・試験対策その他のための演習問題もMoodle上で配布する． ・成績評価は複数回の試験と小テスト，およびレポートにより行う．
＜受講に際して・学生へのメッセージ＞
離散数学，アルゴリズムとデータ構造Ｉ，プログラミング基礎，プログラミング応用,　計算機アーキテクチャア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木に対するαーβ分枝限定法，および0-1ナップザック問題を例とした緩和法を学ぶ． 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 タイトル 事前学習 事後学習 授業内容
＜前年度授業に対する改善要望等への対応＞
前年度の授業アンケートにおいて，講義内容の周辺事項の解説について賛否両方の意見が寄せられた．今年度は試行として，周辺事項を少し減らし，講義での口頭説明の分量の削減を試みる予定である．その他は前年度と同様に実施する予定である．
＜備考＞
オフィスアワー：月曜４時限目