データ構造とはデータのメモリ上での表現であり、アルゴリズムは問題を解くための具体的手順（算法）である。データ構造とアルゴリズムは、情報工学のもっとも重要な分野の一つであり、効率の良いプログラムを書くために必須の知識である。
本講義では、プログラミングの基礎となる基本的な種々のデータ構造やアルゴリズムについて解説する。また本講義では、問題解決のための様々なデータ構造と、それを取り扱う基本的なアルゴリズムを通して、アルゴリズムの設計や解析をするための標準的な技法を修得する。これによりアルゴリズムを新たに考案するなどの応用力・実践力を養うことを目指す。データ構造とアルゴリズムそれ自体は特定のプログラミング言語による実現を目指すものではないが，本講義ではC言語で書かれたプログラムを利用し解説や演習を実施する。
本講義では、プログラミングの基礎となる基本的な種々のデータ構造やアルゴリズムについて解説する。また本講義では、問題解決のための様々なデータ構造と、それを取り扱う基本的なアルゴリズムを通して、アルゴリズムの設計や解析をするための標準的な技法を修得する。これによりアルゴリズムを新たに考案するなどの応用力・実践力を養うことを目指す。データ構造とアルゴリズムそれ自体は特定のプログラミング言語による実現を目指すものではないが，本講義ではC言語で書かれたプログラムを利用し解説や演習を実施する。
- 問題解決のための様々なデータ構造と、それを取り扱う基本的なアルゴリズムを通して、アルゴリズムの設計や解析をするための標準的な技法の概要を解説できる。
- 基本的なアルゴリズムを理解し、それを用いて、基本的な演習問題を解くことができる。
- 様々な課題に対して、それを解くためのアルゴリズムを作成することができる。
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1. | イントロダクション + アルゴリズム概論、アルゴリズムの重要性 + アルゴリズムの記述 + 効率 + 最適性 |
講義内容の復習 | 200minutes |
| 2. | 探索問題1 + 探索問題とは？ + 逐次探索の効率 + 順序関係を利用した探索 + 計算量とオーダ記法 第２、３回では、基本的なアルゴリズムである探索問題（データ集合が固定の静的探索問題）を題材に、アルゴリズム設計と効率改善の基本技法について学ぶ。また，効率の解析を通して，計算量とオーダ記法についても学ぶ。 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 3. | 探索問題2 + m-ブロック法 + 2分探索法 レポート1を出題 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 4. | 探索問題3 + ハッシュ法 基本データ構造1 + 配列 + 連結リスト構造 問題を解く手順を記述するのがアルゴリズムであるが，データ記憶形式であるデータ構造の設計は計算の効率に大きく影響を与える。４〜６回では基本的で重要なデータ構造について学習する。 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 5. | 基本データ構造2 + 2分探索に対するデータ構造 + スタック、キュー + レポート2 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 6. | 基本データ構造3 + ヒープ |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 7. | 中間試験と試験のポイントの解説 | 試験勉強（講義中に取り扱った演習内容をよく確認すること） | 400minutes |
| 8. | 動的探索問題1 + 2分探索木 + レポート3 出題 第2、3回で学習した静的探索問題と基本データ構造をベースに，データ集合が不変でなくデータの挿入や削除も許す動的な探索問題について学習する。 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 9. | 動的探索問題2 + 平衡2分探索木 + 動的ハッシュ |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 10. | ソート1 + バブルソート + セレクションソート + インサーションソート + レポート4 出題 データをある規則にしたがって整列させて蓄えること（ソーティング）は計算の効率化にとって非常に重要であり，多数のアルゴリズムが提案されている。ここではアルゴリズムの比較の観点からいくつかのソーティングアルゴリズムについて学習する。 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 11. | ソート2 + シェルソート + ヒープソート |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 12. | ソート3 + クイックソート + マージソート + ソート問題の計算複雑度 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 13. | 総復習 ここまでに開設したデータ構造とアルゴリズムを振り返って俯瞰する。 |
講義内容の予習 | 100minutes |
| 講義内容や演習内容の復習 | 100minutes | ||
| 14. | 期末試験と試験のポイント解説 | 試験勉強 | 400minutes |
| Total. | - | - | 3200minutes |
| 中間試験 | 期末試験 | レポート | 毎回の小テスト | Total. | |
|---|---|---|---|---|---|
| 1. | 10% | 10% | 10% | 25% | 55% |
| 2. | 5% | 5% | 5% | 14% | 29% |
| 3. | 2% | 2% | 2% | 10% | 16% |
| 4. | 0% | ||||
| Total. | 17% | 17% | 17% | 49% | - |
(1)2回の試験、(2)レポート、(3)毎回の授業内容の理解度を確認する演習課題（scombを利用した小テスト）により総合的・多角的に評価する。
毎回の復習TEST 10点ｘ12（49%）
レポート 10点ｘ４（17%）
中間試験 40点（17％）
期末試験 40点（17%）
基準：毎回の講義を理解し、演習問題に回答できれば80% 毎回の演習の基礎問題のみ回答できれば60%とする。
毎回の復習TEST 10点ｘ12（49%）
レポート 10点ｘ４（17%）
中間試験 40点（17％）
期末試験 40点（17%）
基準：毎回の講義を理解し、演習問題に回答できれば80% 毎回の演習の基礎問題のみ回答できれば60%とする。
| ways of feedback | specific contents about "Other" |
|---|---|
| Feedback in outside of the class (ScombZ, mail, etc.) |
教科書：IT Text アルゴリズム論 浅野哲夫・和田幸一・増澤利光共著，情報処理学会編集（オーム社）
参考書： 問題解決力を鍛える!アルゴリズムとデータ構造 大槻 兼資 （講談社）
参考書： 問題解決力を鍛える!アルゴリズムとデータ構造 大槻 兼資 （講談社）
本講義の内容を基本情報演習1Aにおいて実際にC言語を用いたプログラミング演習によって学習する。そのため，C言語の基本について，「プログラミング入門１および２」を履修し理解していることが望ましい。また，離散数学により問題の数学的な捉え方・解法を学んでいることが望ましい。
- Course that cultivates a basic problem-solving skills
- Course that cultivates a basic self-management skills
- Course that cultivates an ability for utilizing knowledge
| Work experience | Work experience and relevance to the course content if applicable |
|---|---|
| Applicable |
- 4.QUALITY EDUCATION
- 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
Last modified : Sat Sep 09 06:32:09 JST 2023