検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
データ構造
| 令和元年度以前入学者 | データ構造 | ||||
|---|---|---|---|---|---|
| 平成２８年度以前入学者 | データ構造 | ||||
| 教員名 | 大澤正彦 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業の形態 | オンデマンド型（Powerpointによる録画授業配信）と課題研究型（Blackboardによる資料配信）を組み合わせる。 BlackboardのコースID：水曜2限→20213031 |
|---|---|
| 授業概要 | データ構造の基礎を実践的に学ぶ |
| 授業のねらい・到達目標 | 効率の良いプログラムを作るには，良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある． 本講義では，リスト，スタック，キュー，木構造，ハッシュといった基本的なデータ構造の概念を理解するとともにC言語（あるいは C++）で実装できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している. |
| 授業の方法 | 授業の形式：【 講義 】 Blackboardを通じて、オンデマンド教材を配布する。 受講生はその教材を視聴し、学修すること。 また、課題を解き、期日まで（特に指定がない場合は翌週の講義まで）に所定の方法で提出すること。課題の回答は翌週までに提供するので、復習すること。 また、Blackboardの掲示板機能を通して「質問」と「議論」の機会を提供する。 |
| 履修条件 | 「実践プログラミング２」の内容を理解していることを前提に講義を進める． |
| 授業計画 | |
|---|---|
| 1 |
【オンデマンド型】 再帰呼び出し復習と2分探索木復習
【事前学習】「実践プログラミング２」の内容をあらかじめ復習しておく （2時間） 【事後学習】再帰呼出し・2分探索木に関するプログラミング課題に取り組む （2時間） |
| 2 |
【オンデマンド型】 2分探索木のトラバース復習
【事前学習】2分探索木のトラバーサルについて復習しておく （2時間） 【事後学習】2分探索木に関するプログラミング課題に取り組む （2時間） |
| 3 |
【オンデマンド型】 平衡木の概念
【事前学習】平衡木について事前に確認する （2時間） 【事後学習】平衡機の概念に関する課題に取り組む （2時間） |
| 4 |
【オンデマンド型】 平衡木の実装
【事前学習】平衡木の実装について事前に確認する （2時間） 【事後学習】平衡木に関するプログラミング課題に取り組む （2時間） |
| 5 |
【オンデマンド型】 ヒープ木の概念と実装
【事前学習】ヒープ木について事前に確認する （2時間） 【事後学習】ヒープ木に関するプログラミング課題に取り組む （2時間） |
| 6 |
【課題研究型】 木の実践的なプログラミング
【事前学習】第1回〜第5回の内容について復習しておく （2時間） 【事後学習】木構造に関するプログラミング課題に取り組む （2時間） |
| 7 |
【オンデマンド型】 再帰呼び出しによる深さ優先探索
【事前学習】再帰呼出しを用いた深さ優先探索について事前に確認する （2時間） 【事後学習】再帰呼出しを用いた深さ優先探索に関するプログラミング課題に取り組む （2時間） |
| 8 |
【オンデマンド型】 スタックとキューの探索への応用 ：幅優先探索
【事前学習】幅優先探索について事前に確認する （2時間） 【事後学習】幅優先探索に関するプログラミング課題に取り組む （2時間） |
| 9 |
【オンデマンド型】 スタックとキューの探索への応用 ：深さ優先探索
【事前学習】深さ優先探索について事前に確認する （2時間） 【事後学習】深さ優先探索に関するプログラミング課題に取り組む （2時間） |
| 10 |
【課題研究型】 探索の実践的なプログラミング
【事前学習】第7回〜第9回の内容について復習しておく （2時間） 【事後学習】探索に関するプログラミング課題に取り組む （2時間） |
| 11 |
【オンデマンド型】 ハッシュ関数: 内部ハッシュ法
【事前学習】ハッシュ関数・内部ハッシュについて事前に確認する （2時間） 【事後学習】内部ハッシュに関するプログラミング課題に取り組む （2時間） |
| 12 |
【オンデマンド型】 ハッシュ関数: 外部ハッシュ法
【事前学習】外部ハッシュについて事前に確認する （2時間） 【事後学習】外部ハッシュの時間計算量解析に関する課題に取り組む （2時間） |
| 13 |
【課題研究型】 ハッシュの実践的なプログラミング
【事前学習】第11回〜第12回の内容について復習しておく （2時間） 【事後学習】ハッシュに関するプログラミング課題に取り組む （2時間） |
| 14 |
【課題研究型】 これまでの総復習1: 木構造
【事前学習】第1回〜第13回の内容について復習しておくこと （2時間） 【事後学習】総合的なプログラミング課題に取り組む （2時間） |
| 15 |
【課題研究型】 これまでの総復習2: 探索
【事前学習】第1回〜第13回の内容について復習しておくこと （2時間） 【事後学習】総合的なプログラミング課題に取り組む （2時間） |
| その他 | |
|---|---|
| 教科書 | 森元 逞（著） 『Cをさらに理解しながら学ぶデータ構造とアルゴリズム』 共立出版 2007年 |
| 参考書 | 紀平 拓男・春日 伸弥（著） 『プログラミングの宝箱 アルゴリズムとデータ構造』 ソフトバンククリエイティブ 2011年 第2版 |
| 成績評価の方法及び基準 | レポート:オンデマンド教材に関連するプログラミング課題とそのレポートによって評価する(40%)、授業参画度:毎回の講義ごとに実施する小テストの成績によって評価する(60%) |
| オフィスアワー | 随時受け付ける。授業時に伝えるメールアドレスにてアポイントを取ること。 |