授業科目名
  データ構造とアルゴリズム
   Data Structures and Algorithms
時間割番号
1605
担当教員名
  櫻井　祐子
実務経験
反映科目
学科・年次
  工学部 情報工学科
  工学部 創造工学教育課程
  2年次
科目区分
  専門教育科目
単位数
2
時間割
  前期 水曜3-4限
授業形態
講義
授業実施方法
  ☑ 対面【一部遠隔の場合あり】
  ☐ 全て遠隔【全授業（テストを除く）をオンデマンドで実施（全オンデマンド型）】
  ☐ 全て遠隔【同時双方向で実施】
  ☐ 全て遠隔【オンデマンド及び同時双方向で実施】
  ☐ 1/2遠隔【全授業のうち、1/2以上を遠隔（オンデマンド又は同時双方向）】

・「全て遠隔」又は「1/2遠隔」に✓のある科目は、遠隔授業の上限単位数60単位に算定されます。
・大学院には遠隔授業における上限単位数はありません。
ディプロマ・ポリシーとの対応
☐ 1. 人間，文化，社会を理解し，それらを技術的観点から考察する能力と技術を新しい生活につなぐ強い使命感・責任感，高い倫理観
☑ 2. 現象の理解・操作のための数理的基礎知識と科学的素養
☐ 3. 国内外の人々と対話できるコミュニケーション力と論理的思考力
☑ 4. （高度工学教育課程のみ）基幹となる専門分野の基盤的な知識・技術とこれによって課題を解決する能力，新たな知識・技術を習得する能力
☑ 4. （創造工学教育課程のみ）基幹となる専門分野の基礎知識と他の分野の知識・技術を関連づけ多面的に見ることで新たな価値を創出する能力
授業の目的・達成目標

目的

効率のよいプログラムを書くためには,データ構造とアルゴリズムに関する知識が不可欠である．この授業では,さまざまな処理を効率的に行うための基本的なデータ構造およびアルゴリズムの解析法と設計法を修得することを目的とする．

達成度目標

  1. アルゴリズムの定義を理解し，その重要性を説明できる．
  2. アルゴリズムの効率性の評価尺度としての漸近的記法を理解，利用することができる．
  3. 探索問題が何であるかを理解し，線形探索，2分探索が説明できる．
  4. リスト，キュー，スタック，ヒープを理解し，その実現法を説明できる．
  5. 木構造に基づく各種データ構造を理解し，その実現法，利点を説明できる．
  6. 基本的な整列アルゴリズムを理解し，その効率を説明できる．
  7. グラフに対する表現法を理解し，隣接リスト，隣接行列を説明できる．
  8. グラフに対する基本的な探索アルゴリズムを理解，利用することができる．
  9. グラフの最短経路問題を理解し，ダイクストラ法を説明できる．
  10. 再帰法，分割統治法を理解し，それらの適用例を説明できる．
  11. グリーディ法を理解し，その適用例を説明できる．
  12. 動的計画法を理解し，その適用例を説明できる．
  13. 計算困難性の基本を理解し，説明できる．
授業計画
  1. アルゴリズムの重要性と効率性の評価尺度
  2. 探索問題(線形探索・二分探索)
  3. 基本的なデータ構造(１)(配列，リスト，キュー，スタック)
  4. 基本的なデータ構造(２)(二分探索木，平衡二分木，B-木)
  5. データの整列(１)（バブルソート，挿入ソート，ヒープソート(1)）
  6. データの整列(２)（ヒープソート(2)，マージソート，クイックソート）
  7. アルゴリズムの設計法（再帰，動的計画法，分割統治法）
  8. 中間試験・講評
  9. グラフアルゴリズム(１)（グラフの表現、探索）
  10. グラフアルゴリズム(２)（幅優先，深さ優先探索の応用）
  11. グラフアルゴリズム(３)（ダイクストラ法）
  12. グラフアルゴリズム(４)（MST）
  13. 近似アルゴリズム（TSP，2-Opt法，焼きなまし法，分枝限定法）
  14. 計算困難性（NP）
  15. 期末試験・講評

注意: 授業実施状況に応じて，中間試験を総合演習などに代える可能性があります．

成績評価の方法

試験，授業ごとのレポートにより判断する．
試験 : レポート = 7:3 の割合で評価する．

成績評価の基準
秀　 達成目標を超えた成果を上げている　100点～90点
優　 達成目標に十分達している　　　　　89点～80点
良　 達成目標に達している　　　　　　　79点～70点
可　 達成目標に概ね達している　　　　　69点～60点
不可 達成目標に達していない　　　　　　59点以下

原則，レポートの提出率が80%以上の場合に上記の基準により評価する．

事前・事後学修等の指示及び履修にあたっての注意事項

「情報数学Ｉ」全般の知識，および「情報数学Ⅱ」における一部の数学的知識を必要とする．

事前学修：moodle上の授業資料及び教科書による予習（120分）
事後学修：授業後に実施するレポート課題を中心に，受講日のうちに授業内容について教科書の演習問題や授業資料等で復習（120分）

教科書