アルゴリズムとデータ構造II
| 科目区分 | 専門教育科目（情報） | 対象学年(以上) | 2年 |
|---|---|---|---|
| 科目名称 | アルゴリズムとデータ構造Ⅱ | 単位数 | 2.00単位 |
| 講義題目 | アルゴリズムとデータ構造II | 曜日・時限 | 月曜2限 |
| 担当教員 | 何 立風 | 開講時期 | 2019年度後期 |
| 到達目標 | ハッシュ法の原理・特徴・実現方法を理解・説明できること。 さまざま文字照合アルゴリズムの原理・特徴・実現方法を理解・説明できること。 さまざまな整列アルゴリズムの原理・特徴・実現方法を理解・説明できること。 グラフのアルゴリズムの原理・実現方法を理解・説明できること。 |
||
| 授業概要 | 表構造においては、ハッシュ法の原理・特徴・実現方法を説明。 文字照合アルゴリズムにおいては、単純なアルゴリズム、KMPアルゴリズム、BMアルゴリズムおよびサークルアルゴリズムを紹介する。グラフのアルゴリズムについては、グラフの表現、グラフの探索、最短経路について解説する。整列アルゴリズムにおいては、まず、整列の基本原理を紹介する。そして、選択による整列（単純法、ヒープソート）、挿入による整列（単純法、シェルソート）、交換による整列（バブルソート、コームソート、クイックソート）およびマージによる整列（マージソート、自然マージソート）に関するそれぞれのアルゴリズムについて解説する。さらに、比較によらない整列方法についても紹介する。また、グラフ構造の特徴、ブラフに関連するアルゴリズムを解説する。 |
||
| 授業計画 | 第1回 表構造の基本 第2回 衝突の解決方法 第3回 文字照合アルゴリズムの基本 第4回 ＫＭＰ法 第5回 簡略ＢＭ法 第6回 ＢＭ法 第7回 整列アルゴリズムの基本 第8回 選択による整列 第9回 挿入による整列 第10回 交換による整列 第11回 マージによる整列 第12回 比較によらない整列 第13回 グラフ構造の基本 第14回 グラフにおける最短路問題 第15回 まとめ 定期試験 |
||
| 授業外学習 | 毎回授業の最初に、前回授業の復習問題と今回授業の予習問題のレポートを提出すること。 | ||
| 履修上の注意 | 関連科目：プログラミングⅠ、プログラミングII、アルゴリズムとデータ構造I 履修条件：「アルゴリズムとデータ構造I」を履修していること。 |
||
| 成績評価の方法 | 評価基準：表構造の原理・実現方法を理解しているか。文字照合の各アルゴリズムを理解しているか。基本的な整列アルゴリズムを理解しているか。文字照合の各アルゴリズムを理解しているか。グラフ構造 評価方法：講義への積極さ・レポート（15％）と試験（85％）で総合的に評価する。 |
||
| 教科書 | 特に指定しない | ||
| 参考書 | (1) 石畑 清：アルゴリズムとデータ構造、岩波書店、ISBN4-00-010343-1 C3355 (2) 近藤 嘉雪：Cプログラマのためのアルゴリズムとデータ構造， ソフトバンクパブリッシング，ISBN4-7973-0495-2 C0055，2700円＋税 (3) 紀平 拓男、春日 伸弥：プログラミングの宝箱 アルゴリズムとデータ構造、 ソフトバンクパブリッシング、ISBN4-7973-2419-8 C0055 |
||