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