山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名 アルゴリズムとデータ構造II
時間割番号 TCS209
担当教員名 岩沼 宏治
開講学期・曜日・時限 後期・火・III 単位数 2
<対象学生>
(未登録)
<授業の目的>
情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を、アルゴリズムとデータ構造Iに引き続いて学ぶ.具体的には,情報処理学会J07およびIEEE/ACMのモデルカリキュラムCC2008の内容をカバー題材を取り上げる
<本授業科目による獲得・涵養が特に期待されるコンピテンシー>(能力・資質)
工学部(~2023年度入学生)>コンピュータ理工学科向け
記号コンピテンシー(能力・資質) 
CS-A専門5.時代の変化に対応できるよう、最新の技術動向を考慮して、自律的・継続的に学習できる。
CS-B6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。6a.解決すべき問題を形式化することができる。
CS-C6b.要求、時間、費用、資源等の制約条件を考慮した上で、複数の解が存在するような複雑な問題の中から適切な解を見つけ出すことができ
<到達目標>  到達目標とは
目標NO説明コンピテンシーとの対応
CS
1アルゴリズムを設計するための代表的な汎用手法を理解し,応用できることCS-B
2幾つかの先進的なアルゴリズム理論について理解し説明できることCS-C
3現実社会における先端的例としてのデータマイニングについて理解し説明できることCS-A
<成績評価の方法>
目標No割合評価の観点
160%総合的な理解度と応用力を評価する
230%理解度を評価する
310%理解度を評価する
合計100% 
<授業の方法>
講義は面接授業を基本として,小テスト(オンライン型)を毎回行う.
・Moodle上に講義資料と復習用動画資料を公開し,オンデマンド型授業の長所を取り入れる.
・試験対策その他のための演習問題もMoodle上で配布する.
・成績評価は複数回の試験と小テスト,およびレポートにより行う.
<受講に際して・学生へのメッセージ>
離散数学,アルゴリズムとデータ構造I,プログラミング基礎,プログラミング応用, 計算機アーキテクチャアI及びII,線形代数学が関連知識,前提知識である.
<テキスト>
  1. 岩沼宏冶,美濃英俊,鍋島英知,山本泰生, データ構造とアルゴリズム(電子情報通信レクチャーシリーズB-8), コロナ社, ISBN:9784339018233
<参考書>
  1. R.セジウィック著、野下、星、佐藤、田口訳, アルゴリズムC++, 近代科学社, ISBN:4764902222
  2. 杉原厚吉, データ構造とアルゴリズム, 共立出版, ISBN:4320120345
  3. 杉原、茨木、浅野、山下編,, アルゴリズム工学 -計算困難問題への挑戦ー, 共立出版, ISBN:4320120124
  4. 岩間 一雄, アルゴリズム・サイエンス:出口からの超入門, 共立出版, ISBN:4320121686
  5. 茨木 俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191
<授業計画の概要>
1タイトルガイダンスと序論
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか?について考察する
2タイトル計算量理論の入り口:比較に基づくソート法の時間計算量の下限
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容比較に基づくソート法の時間計算量の下界を通して,計算問題の持つ本質的な難しさについて学ぶ
3タイトル時間計算量の空間的克服
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容空間を有効に利用するソート法(バケットソート、計数ソート,基底ソート)を学び,大規模メモリを持つ現代的コンピュータ上で有効なアルゴリズム技法を理解する.
4タイトルはじめての計算量理論
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容計算複雑さと無限階層,PとNP問題クラス,完全問題などを学び,問題の持つ本質的な計算論的難しさと現代的暗号理論への応用などの技術動向について理解する.
5タイトル簡単な最適化問題
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容資源配分問題を例とする増分法、連続ナップザック問題を例とする貪欲法について学ぶ
6タイトル分岐限定法:AIにおける分枝限定法,緩和法
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容離散最適化問題において重要な探索木の探索の効率化技法として,人工知能分野で多用されるMin-Max木に対するαーβ分枝限定法,および0-1ナップザック問題を例とした緩和法を学ぶ.
7タイトル前半のまとめと中間評価その1
事前学習
事後学習
これまでの講義資料の復習
授業内容これまでの授業のまとめと試験問題の出題意図の解説
8タイトル動的計画法
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容部分和問題、0-1ナップザック問題を題材にして,空間的資源を有効に利用するアルゴリズム技法である動的計画法を学ぶ.
9タイトル分割統治法
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容分割統治法の理論的枠組みを示す簡易型マスター定理を紹介し,巨大データの高速処理を実現する例として,長大数の高速乗算、点集合の凸包計算について学ぶ
10タイトル近似アルゴリズムその1
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容人工知能など高速計算が非常に難しい問題を解くために,1960~1980年代前半に盛んに研究されてきたヒューリスティックに基づく近似計算法について学ぶ
11タイトル中盤のまとめと中間評価その2
事前学習
事後学習
これまでの講義資料の復習
授業内容これまでの授業のまとめと試験問題の出題意図の解説
12タイトル近似アルゴリズムその2
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容NP困難問題なと効果的な計算が非常に難しい問題を高速に解くために,1990年度後半から盛んに研究されてきた計算誤差精度が保証される近似アルゴリズムについてその基本を学ぶ.
13タイトル巨大データへの挑戦:データマイニングの基礎
事前学習
事後学習
事前配布の講義資料の予習と講義の小テスト
授業内容データマイニング分野を立ち上げた相関ルールマイニング技術の初歩について学ぶ.
14タイトルストリームマイニング:オンライン近似計算
事前学習
事後学習
事前配布の講義資料の予習と講義後の小テスト
授業内容高速大容量のストリームデータを高速計算するための離散データマイニング技術の基礎を学ぶ
15タイトル期末のまとめと総合評価
事前学習
事後学習
これまでの全ての講義資料の復習
授業内容これまでの授業のまとめと試験問題の出題意図の解説
<前年度授業に対する改善要望等への対応>
前年度の授業アンケートにおいて,講義内容の周辺事項の解説について賛否両方の意見が寄せられた.今年度は試行として,周辺事項を少し減らし,講義での口頭説明の分量の削減を試みる予定である.その他は前年度と同様に実施する予定である.
<備考>
オフィスアワー:月曜4時限目