| 教授 | 平川豊 |  |
データ構造とアルゴリズム１ |
Data Structure and Algorithms 1 |
開講部 | 工学部 |
開講学科 | 情報工学科 |
開講学年 | 2年次 |
開講時期 | 前期 |
単位数 | 2 |
単位区分 | 必修 |
系列区分 | 専門 |
講義区分 | 講義 |
| 教授 | 平川豊 | |
| 1. | 問題解決のための様々なデータ構造と、それを取り扱う基本的なアルゴリズムを通して、アルゴリズムの設計や解析をするための標準的な技法を修得する。 |
| 2. | アルゴリズムを新たに考案するなどの応用力・実践力を養う。 |
| 3. | C言語を用いて実用的なアルゴリズムをプログラミングする能力を身につける。 |
| 1. | アルゴリズムの重要性 導入：アルゴリズム概論，アルゴリズムの記述，効率，最適性 |
| 2. | 探索問題1 ２，３回では，基本的なアルゴリズムである探索問題（データ集合が固定の静的探索問題）を題材に，アルゴリズム設計と効率改善の基本技法について学ぶ。また，効率の解析を通して，オーダ記法についても学ぶ。 ・探索問題とは？，逐次探索の効率，順序関係を利用した探索 |
| 3. | 探索問題2 ・m-ブロック法，2分探索法 |
| 4. | 探索問題2 ・ハッシュ法 |
| 5. | 基本データ構造1 問題を解く手順を記述するのがアルゴリズムであるが，データ記憶形式であるデータ構造の設計は計算の効率に大きく影響を与える。５〜７回では基本的で重要なデータ構造について学習する。 ・配列と連結リスト構造，2分探索に対するデータ構造 |
| 6. | 基本データ構造2 ・スタックー，キュー |
| 7. | 基本データ構造3 ・ヒープ |
| 8. | 中間試験 １ー７回までの講義内容の理解度を確認する中間試験を実施する。 |
| 9. | 動的探索問題1 ２，３回で学習した静的探索問題と，基本データ構造をベースに，データ集合が不変でなくデータの挿入や削除も許す動的な探索問題について学習する。 ・2分探索木 |
| 10. | 動的探索問題2 ・平衡2分探索木 |
| 11. | データの整列1 データをある規則にしたがって整列させて蓄えること（ソーティング）は計算の効率化にとって非常に重要であり，多数のアルゴリズムが提案されている。ここではアルゴリズムの比較の観点からいくつかのソーティングアルゴリズムについて学習する。 ・バブルソート，セレクションソート，インサーションソート |
| 12. | データの整列2 ・シェルソート，ヒープソート |
| 13. | データの整列3 ・クイックソート，マージソート，ソート問題の計算複雑度 |
| 14. | 演習により総復習を行う |
| 15. | 期末試験 １ー１５回までの講義内容全体の理解度を確認する期末試験を実施する。 出題は全体の内容をバランス良く網羅し，総合的な理解度を評価することを目的とする。 |
| ・ | 火曜日12:00-13:00 |