検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
データ構造
| 科目名 | データ構造 | ||||
|---|---|---|---|---|---|
| 教員名 | 谷聖一 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業概要 | データ構造の基礎を実践的に学ぶ |
|---|---|
| 授業のねらい・到達目標 | 効率の良いプログラムを作るには，良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある． 本講義では，リスト，スタック，キュー，木構造，ハッシュといった基本的なデータ構造の概念を理解するとともにC言語（あるいは C++）で実装できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています. |
| 授業の方法 | 講義形式の説明と計算機を使った実習を織り交ぜて行う． 本授業の事前・事後学習は，各２時間の学習を目安とする. |
| 履修条件 | 「実践プログラミング２」の内容を理解していることを前提に講義を進める． |
| 授業計画 | |
|---|---|
| 1 |
再帰呼び出し復習 2分探索木復習 【事前学習】「実践プログラミング２」の内容をあらかじめ復習しておく 【事後学習】再帰呼出し・2分探索木に関するプログラミング課題に取り組む |
| 2 |
2分探索木のトラバース復習 【事前学習】2分探索木のトラバーサルについて復習しておく 【事後学習】2分探索木に関するプログラミング課題に取り組む |
| 3 |
平衡木の概念 【事前学習】平衡木について事前に確認する 【事後学習】平衡機の概念に関する課題に取り組む |
| 4 |
平衡木の実装 【事前学習】平衡木の実装について事前に確認する 【事後学習】平衡木に関するプログラミング課題に取り組む |
| 5 |
ヒープ木の概念と実装 【事前学習】ヒープ木について事前に確認する 【事後学習】ヒープ木に関するプログラミング課題に取り組む |
| 6 |
小テストと解説 (1) [筆記] 木構造に関して復習・解説を行い授業の理解を深める 【事前学習】第1回〜第5回の内容について復習しておく 【事後学習】小テストの内容について復習する |
| 7 |
スタックとキュー 【事前学習】スタックとキューについて事前に確認する 【事後学習】スタックとキューに関するプログラミング課題に取り組む |
| 8 |
スタックとキューの探索への応用 ：幅優先探索 【事前学習】幅優先探索について事前に確認する 【事後学習】幅優先探索に関するプログラミング課題に取り組む |
| 9 |
スタックとキューの探索への応用 ：深さ優先探索 【事前学習】深さ優先探索について事前に確認する 【事後学習】深さ優先探索に関するプログラミング課題に取り組む |
| 10 |
再帰呼び出しと深さ優先探索 【事前学習】再帰呼出しを用いた深さ優先探索について事前に確認する 【事後学習】再帰呼出しを用いた深さ優先探索に関するプログラミング課題に取り組む |
| 11 |
ハッシュ関数 内部ハッシュ法 【事前学習】ハッシュ関数・内部ハッシュについて事前に確認する 【事後学習】内部ハッシュに関するプログラミング課題に取り組む |
| 12 |
外部ハッシュ法 【事前学習】外部ハッシュについて事前に確認する 【事後学習】外部ハッシュの時間計算量解析に関する課題に取り組む |
| 13 |
小テストと解説（2) [筆記] スタック・キュー・探索・ハッシュ法に関して復習・解説を行い授業の理解を深める 【事前学習】スタック・キュー・探索・ハッシュ法について復習しておく 【事後学習】小テスト (2) の内容について復習する |
| 14 |
木・探索に関するまとめ（これまでの復習・解説を行い授業の理解を深める） 【事前学習】第1回〜第13回の内容について復習しておくこと 【事後学習】木・探索に関するプログラミング課題に取り組む |
| 15 |
小テストと解説 (3) [実技] これまでの復習・解説を行い授業の理解を深める 【事前学習】この講義に関連して行ったプログラミングについて復習しておく 【事後学習】小テスト (3) の内容について復習する |
| その他 | |
|---|---|
| 教科書 | 森元 逞（著） 『Cをさらに理解しながら学ぶデータ構造とアルゴリズム』 共立出版 2007年 |
| 参考書 | 紀平 拓男・春日 伸弥（著） 『プログラミングの宝箱 アルゴリズムとデータ構造』 ソフトバンククリエイティブ 2011年 第2版 |
| 成績評価の方法及び基準 | 授業内テスト(100%) 授業内テストは，３回の小テスト等を合わせて評価する．詳細は初回の講義で述べる． |
| オフィスアワー | 月曜日 18時〜19時 |