授業科目名	アルゴリズムとデータ構造I演習
時間割番号	UCS207
担当教員名	朱　臻陽
開講学期・曜日・時限	前期・木・III	単位数	1
＜対象学生＞
工学科２年次以上
＜授業の目的＞
本科目では，講義「アルゴリズムとデータ構造I」で学ぶ内容をもとに，コンピュータを用いた演習を行うことを通して，重要かつ具体的なアルゴリズムやデータ構造およびアルゴリズムに関する一般的な技術の理解を深める．基礎的なデータ構造である木構造とハッシュ表とグラフについては，表現法及び探索法を学ぶ．さらに，最小全域木問題、最短経路問題、トポロジカルソート、文字列照合アルゴリズムの実装方法を学ぶ．また，C++言語を用いて実際にアルゴリズムやデータ構造を実装する能力を身に付ける．
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>工学科向け 記号 コンピテンシー（能力・資質） 説明   工-A 専門 ②専門的知識 専門分野の基礎的知識を体系的に理解して説明 ◎ 工-B ⑦理解力･判断力 自然現象や社会的事象を理解・分析 ○ 工-C ⑧論理的思考力 問題や課題を論理的思考で解決 ○ 工-D ⑨創造的思考力・デザイン 総合的な知見･専門知識･学科学的修経験による創造的思考で課題解決 ○
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 工学 1 二分木，ハッシュ表，グラフおよび文字列照合に関する専門知識を持ち，これらの手法について説明ができる． 工-A 2 各手法の利点と欠点を理解し，特定の問題に適した手法を選択できる． 工-B 3 データ構造およびアルゴリズムを実装する際に発生する問題を論理的に分析し，適切に解決へ導くことができる． 工-C 4 解決すべき実問題に向けてデータ構造とアルゴリズムを組み合わせ，自らソリューションを生み出すことができる． 工-D
＜成績評価の方法＞
目標No 割合 評価の観点 1 70% レポート，試験により評価する 2 10% レポート，試験により評価する 3 10% レポート，試験により評価する 4 10% レポート，試験により評価する 合計 100%
＜授業の方法＞
「プログラミング基礎」および「同演習」並びに「プログラミング応用」および「同演習」を履修済みで (単位取得が望ましい)，C++言語の基本的知識とプログラミング技術を修得していること．履修にあたっては，上記の先行科目で学習した内容を必ず復習しておくこと．
＜受講に際して・学生へのメッセージ＞
科目「プログラミング基礎演習」および「プログラミング応用演習」を履修済みで，C++言語の基本的知識とプログラミング技術を習得済みであること．
＜テキスト＞
電子情報通信学会編 ; 岩沼宏治 [ほか] 共著, データ構造とアルゴリズム, コロナ社, ISBN:4339018236, (2018年出版 電子情報通信レクチャーシリーズ / 電子情報通信学会編, B-8)
＜参考書＞
高橋麻奈著, やさしいC++ 第5版, SBクリエイティブ, ISBN:4797392592, (2017年出版) 渡部有隆著, プログラミングコンテスト攻略のためのアルゴリズムとデータ構造, マイナビ, ISBN:9784839952952, (2015年出版) T.コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳, 基礎・ソート・データ構造・数学 1 第3版, 近代科学社, ISBN:9784764904064, (2012年出版 世界標準MIT教科書, . アルゴリズムイントロダクション)
＜授業計画の概要＞
1 タイトル プログラミング応用の復習 事前学習 事後学習 講義中またはCNSの掲示により指示する 授業内容 リダイレクト，再帰関数・再帰呼び出しの復習，二分探索の復習 2 タイトル 二分木の基礎 事前学習 事後学習 講義中またはCNSの掲示により指示する 授業内容 二分探索木における要素の追加・探索・削除 3 タイトル 二分木の応用(1) 平衡木 事前学習 事後学習 講義中またはCNSの掲示により指示する 授業内容 AVL木におけるデータの追加・削除 4 タイトル 二分木の応用(2) プライオリティキュー 事前学習 事後学習 講義中またはCNSの掲示により指示する 授業内容 コマンドライン引数，プライオリティキューの実装，ヒープソート 5 タイトル 中間評価(1) 事前学習 事後学習 講義中またはCNSの掲示により指示する 授業内容 中間テスト(1) 6 タイトル 標準テンプレートライブラリの利用 事前学習 事後学習 講義中または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」との連携を重視する．