| 授業科目名（和文） ［Course］ |
データ構造とアルゴリズム |
| 授業科目名（英文） ［Course］ |
Data Structures and Algorithms |
| 学部（研究科） ［Faculty］ |
情報工学部 |
| 学科（専攻） ［Department］ |
情報通信工学科 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○小野 孝男 自室番号（2608）、電子メール（onotakao**c.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
前期 2単位 |
| 対象学生 ［Eligible students］ |
情報工学部情報通信工学科 2年次生 |
| 授業概略と目標 ［Course description and Objects］ |
プログラムを作成するうえで，「処理の方法」であるアルゴリズムと「処理するデータの保持方法」であるデータ構造は非常に重要である．そこで，本講義では基本的なアルゴリズムやデータ構造の設計方法を理解し，これらの評価手法の 1つとして「計算量」の概念を学ぶことを目的とする． |
| 到達目標 ［Learning Goal］ |
1. 計算量，計算の複雑さの考え方を理解する． 2. 基本的なデータ構造である配列や連結リスト，スタックなどを理解する． 3. 配列や文字列の探索，整列，経路探索の手法と計算量を理解する． |
| 履修上の注意 ［Notes］ |
1年次で「プログラミング言語I」や「情報通信工学演習」など，ソフトウエアに関する講義?演習を履修していることが望ましい． また，重要な事項についてはC における実装を「プログラミング言語II」でも扱っているので，そちらも併せて履修することでより理解が深まると思われる． |
| 授業計画とスケジュール ［Course schedule］ |
1. アルゴリズムと計算量 ?「アルゴリズム」の定義を知り，「計算量」の概念を理解する． 2. 配列の探索 ?配列から目的のデータを見つける手法として線形探索，二分探索とハッシュについて学ぶ． 3. 計算量 ?計算量を記述する記法について学び，二分探索を対象として具体的に計算量の求め方を知る． 4. リスト ?簡単なデータ構造として「リスト」の概念を紹介し，その実現方法である配列および連結リストを学ぶ． 5. 二分探索木 ?順序構造を持つデータに対し，連結リストよりも効率的に操作できるデータ構造である二分探索木について学ぶ. 6. ハッシュ ?離散的なデータに対し，その値から効率的に存在するかどうかを調べる手法として「ハッシュ」を知る． 7. ソート (1) ?ソートアルゴリズムの分類方法を紹介し，比較に基づくソートによる理論的な効率の限界を理解する．また，簡単なソートアルゴリズムを知る． 8. ソート (2): クイックソート ?効率的なソートアルゴリズムの 1つであるクイックソートの考え方を紹介し，その計算量の求め方を示す． 9. ソート (3)：ヒープソートとマージソート ?クイックソートは一般に高速であるが，運が悪いと処理に非常に時間がかかってしまうことがある．これに対し，平均的に効率的なアルゴリズムであるヒープソートとマージソートを紹介する． 10. グラフ ?「グラフ」というデータ構造は「もの」と「もの」の関係を表す 1つの手法として用いられる．そこで今回はまずグラフをデータとして保持する方法を紹介し，次にグラフに存在する全頂点を列挙する方法を示す． 11. 最短経路問題 ?グラフの応用として最短経路問題を取り上げ，そのアルゴリズムとして Dijkstra法と Warshall-Floyd法を紹介する． 12. 最小全域木問題 ?「もの」同士の関連性をグラフで表し，その最小全域木を求めると「もの」を関連性によって分類することが可能である．そこで，最小全域木を求めるアルゴリズムとそこで用いられる特殊なデータ構造を紹介する． 13. 文字列の探索 ?長い文字列の中から特定のパターンを見つける「文字列探索」アルゴリズムを紹介する． 14. 計算量による問題の分類 ?我々が直面する問題には，簡単なものもあれば難しいものも存在する．ここでは計算量によって問題の「難しさ」が分類できることを示す． 15. まとめ ?これまでの講義の内容を簡単にまとめる． |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
期末試験 (70 %)，レポート (30 %) および受講態度により総合的に評価する． |
| 教科書 ［Textbook］ |
教科書：なし．毎回講義の際に資料を配布する． 参考書： ?近藤嘉雪，”定本 Ｃプログラマのためのアルゴリズムとデータ構造”，ソフトバンククリエイティブ，1998 その他，書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．自分の好みに合ったものを見つけて学習して欲しい． |
| 自主学習ガイド及び キーワード ［Self learning］ |
?指示された課題を解いてくること． ?単に講義を聴くだけでは表面的な理解にとどまってしまうおそれがあるので，Cやpython, Perlなどを用いて実際にプログラムを作成すること． キーワード：データ構造，アルゴリズム，計算量，再帰 |
| 開講年度 ［Year of the course］ |
28 |
| 資格等に関する事項 | 基本情報技術者，応用情報技術者のアルゴリズム部分の内容を含む |