授業科目名	アルゴリズムとデータ構造II
時間割番号	UCS252
担当教員名	岩沼　宏治
開講学期・曜日・時限	後期・火・III	単位数	2
＜対象学生＞
工学科２年次以上
＜授業の目的＞
情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Ｉに引き続いて学ぶ．具体的には，情報処理学会J07およびIEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>工学科向け 記号 コンピテンシー（能力・資質） 説明   工-A 専門 ②専門的知識 専門分野の基礎的知識を体系的に理解して説明 ◎ 工-B ⑥自律的かつ継続的学修能力 時代変化に対応しつつ自律的継続的な学修で社会的課題解決に貢献 ○ 工-C ⑦理解力･判断力 自然現象や社会的事象を理解・分析 ○ 工-D ⑧論理的思考力 問題や課題を論理的思考で解決 ○ 工-E ⑨創造的思考力・デザイン 総合的な知見･専門知識･学科学的修経験による創造的思考で課題解決 ○
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 工学 1 アルゴリズムとデータ構造に関する基礎的知識を体系的に説明できること 工-A 2 アルゴリズムとデータ構造に関する基礎的な課題を論理的思考で解決できること 工-D 3 アルゴリズムとデータ構造に関する応用的な課題を総合的な知識と思考で解決できること 工-E 4 アルゴリズムとデータ構造に関係した工学的事象を理解・分析できること 工-C 5 アルゴリズムとデータ構造に関して自律的かつ継続的な学習ができること 工-B
＜成績評価の方法＞
目標No 割合 評価の観点 1 15% 中間・期末の複数回の試験により基礎的知識の理解度を評価する 2 30% 中間・期末の複数回の試験により基礎的問題のな論理的な解決能力を評価する 3 30% 中間・期末の複数回の試験により応用問題に対する総合的な解決能力を評価する 4 5% 中間・期末の複数回の試験により本講義内容に関連する工学的事象の理解度を評価する 5 20% 毎回の小テストおよびレポートにより評価する 合計 100%
＜授業の方法＞
講義は面接授業を基本として，小テスト（オンライン型）を毎回行う．必要に応じてライブ型講義も実施する ・Moodle上に講義資料と復習用動画資料を公開し，オンデマンド型授業の長所を取り入れる． ・試験対策その他のための演習問題もMoodle上で配布する． ・成績評価は複数回の試験と小テスト，およびレポートにより行う．
＜受講に際して・学生へのメッセージ＞
離散数学，アルゴリズムとデータ構造Ｉ，プログラミング基礎，プログラミング応用,　計算機アーキテクチャアI及びII，線形代数学が関連知識，前提知識である．
＜テキスト＞
電子情報通信学会編 ; 岩沼宏治 [ほか] 共著, データ構造とアルゴリズム, Array, ISBN:9784339018233, (2018年出版 電子情報通信レクチャーシリーズ / 電子情報通信学会編, B-8)
＜参考書＞
R. セジウィック著 ; 野下浩平 [ほか] 共訳, アルゴリズムC++, Array, ISBN:4764902222, (1994年出版) 杉原厚吉著, データ構造とアルゴリズム, Array, ISBN:4320120345, (2001年出版) 杉原厚吉 [ほか] 編, アルゴリズム工学 : 計算困難問題への挑戦, Array, ISBN:4320120124, (2001年出版) 岩間一雄著, アルゴリズム・サイエンス : 出口からの超入門, Array, ISBN:4320121686, (2006年出版 アルゴリズム・サイエンスシリーズ / 杉原厚吉 [ほか] 編, 2 ; 超入門編) 茨木俊秀著, アルゴリズムとデータ構造, Array, ISBN:4785601191, (1989年出版 21世紀を指向した電子・通信・情報カリキュラムシリーズ, B-4)
＜授業計画の概要＞
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 タイトル 事前学習 事後学習 授業内容
＜前年度授業に対する改善要望等への対応＞
アンケート結果確認中
＜備考＞
(未登録)