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