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



授業科目名 アルゴリズムとデータ構造I演習
時間割番号 TCS208
担当教員名 朱 臻陽
開講学期・曜日・時限 前期・木・IV 単位数 1
<対象学生>
(未登録)
<授業の目的>
本科目では、講義「アルゴリズムとデータ構造I」で学ぶ内容に関して、コンピュータを用いた演習を行うことを通して、重要かつ具体的なアルゴリズムやデータ構造及びアルゴリズムに関する一般的な技術の理解を深める。基礎的なデータ構造である木構造とハッシュ表とグラフについては、表現法及び探索法を学ぶ。さらに、最小全域木問題と最短経路問題とトポロジカルソートと文字列照合プログラムの実装方法を学ぶ。また、C++言語によって実際にアルゴリズムやデータ構造を実装する能力を身に付ける。
<本授業科目による獲得・涵養が特に期待されるコンピテンシー>(能力・資質)
工学部>コンピュータ理工学科向け
記号コンピテンシー(能力・資質) 
CS-A専門6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。
<到達目標>  到達目標とは
目標NO説明コンピテンシーとの対応
CS
1二分木とその応用(平衡木,プライオリティキュー等)に関するアルゴリズムやデータ構造についてプログラムを実装できる.CS-A
2STL,ハッシュ表とその応用に関するアルゴリズムやデータ構造についてプログラムを実装できる.CS-A
3グラフ(最小スパニング木,最短経路,トポロジカルソート等)と文字列照合に関するアルゴリズムやデータ構造についてプログラムを実装できる.CS-A
4プログラミングを通してデータ構造,オブジェクト指向プログラミング,二分探索,貪欲法,再帰と分割統治法などのアルゴリズム手法について説明できる.CS-A
<成績評価の方法>
目標No割合評価の観点
115%プログラミングの中間テストを実施し,達成目標1の到達度を評価する.
215%プログラミングの中間テストを実施し,達成目標2の到達度を評価する.
340%プログラミングの最終テストを実施し,達成目標3の到達度を評価する.
430%講義後ならびに学期末にレポート課題を課し,各達成目標の到達度を評価する.
合計100% 
<授業の方法>
「プログラミング基礎」および「同演習」並びに「プログラミング応用」および「同演習」を履修済みで (単位取得が望ましい),C++言語の基本的知識とプログラミング技術を修得していること.履修にあたっては,上記の先行科目で学習した内容を必ず復習しておくこと.
<受講に際して・学生へのメッセージ>
(未登録)
<テキスト>
  1. 電子情報通信学会編 ; 岩沼宏治 [ほか] 共著, データ構造とアルゴリズム, コロナ社, ISBN:4339018236,
    (2018年出版 電子情報通信レクチャーシリーズ / 電子情報通信学会編, B-8)
<参考書>
  1. 高橋麻奈著, やさしいC++ 第5版, SBクリエイティブ, ISBN:4797392592,
    (2017年出版 「プログラミング基礎」の教科書)

  2. 渡部有隆著, プログラミングコンテスト攻略のためのアルゴリズムとデータ構造, マイナビ, ISBN:9784839952952,
    (2015年出版)

  3. T.コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳, 基礎・ソート・データ構造・数学 1 第3版, 近代科学社, ISBN:9784764904064,
    (2012年出版 世界標準MIT教科書, . アルゴリズムイントロダクション)

  4. Steven S. Skiena, The Algorithm Design Manual 2nd ed, Springer London, ISBN:9781849967204,
    (2010年出版)

  5. Mark A. Weiss, Data structures and problem solving using C++ 2nd ed, Addison-Wesley, ISBN:9780201612509,
    (2000年出版)
<授業計画の概要>
1タイトルプログラミング応用の復習
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容リダイレクト,再帰関数・再帰呼び出しの復習,二分探索の復習
2タイトル二分木の基礎
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容二分探索木における要素の追加・探索・削除
3タイトル二分木の応用(1) 平衡木
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容AVL 木におけるデータの追加・削除
4タイトル二分木の応用(2) プライオリティキュー
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容コマンドライン引数,プライオリティキューの実装,ヒープソート
5タイトル中間評価1
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容中間テスト(1)
6タイトル標準テンプレートライブラリ(STL)の利用
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容STL コンテナ vector, list, map の使い方
7タイトルハッシュ表(1) 分離チェイン法,ハッシュ関数の設計
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容ハッシュ表原理,分離チェイン法を用いたハッシュ表の実装
8タイトルハッシュ表(2) 開番地法,ハッシュ表の拡大
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容ハッシュ表の実装 (開番地法)・代替アドレスの選定
9タイトル中間評価2
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容中間テスト(2)
10タイトルグラフの表現とグラフの探索
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容隣接リストによるグラフのデータ構造の実装,グラフの深さ優先探索アルゴリズム
11タイトル最小スパニング木
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容最小全域木問題のクラスカル法の実装
12タイトル最短経路問題
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容ダイクストラ法によるグラフ最短経路の探索
13タイトルトポロジカルソートとクリティカルパス問題
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容Kahn のトポロジカルソート法の実装
14タイトル文字列照合
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容Boyer-Moore 法の実装
15タイトル最終評価とまとめ
事前学習
事後学習
講義中またはCNSの掲示により指示する
授業内容期末テストとまとめ
<備考>
講義「アルゴリズムとデータ構造I」との連携を重視する.