検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
データ構造
| 令和２年度以降入学者 | データ構造 | ||||
|---|---|---|---|---|---|
| 令和元年度以前入学者 | データ構造 | ||||
| 教員名 | 谷聖一 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 対面形式で実施する．（もし遠隔形式で実施する場合は，同時双方向型授業（Zoom）とする．） Blackboard コースID: 20221446 |
|---|---|
| 授業概要 | データ構造の基礎を実践的に学ぶ |
| 授業のねらい・到達目標 | 効率の良いプログラムを作るには，良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある． 本講義では，リスト，スタック，キュー，木構造，ハッシュといった基本的なデータ構造の概念を理解するとともに Python あるいは C言語/C++ で実装できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している. なお，新カリキュラム（令和2年度以降入学者対象）では，この科目は文理学部（学士(理学)）のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している。 ・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる.(A-3-3) ・問題を分析し，複数の解決策を提示した上で，問題を解決することができる.(A-4-3) ・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる.(A-5-3) |
| 授業の方法 | 授業の形式：【講義】 ・基本的に Blackboard, Google Classroom, OneDrive, Google Drive, Google Chat でコミュニケーション行う． ・事前学習・事後学習の一環として，C言語/C++, Ruby, あるい Python を用いたアルゴリズムの実現と性能評価実験を課題として出題する． ・課題の一部は自己評価・相互評価を行う場合がある．レポートには，総評することでフィードバックを行う． 対面参加できない学生の要件は学部の方針に従う． 学部が定める要件を満たし，オンライン参加が認められた場合の受講方法： ・授業時間帯にZoomにて授業に参加する． |
| 履修条件 | 「実践プログラミング２」の内容を理解していることを前提に講義を進める． また，文理学部教育用アカウント (stu アカウント) と NU-Apps G アカウントを適切に使い分けられることを前提とする． |
| 授業計画 | |
|---|---|
| 1 |
再帰呼び出し復習と2分探索復習
【事前学習】「実践プログラミング２」の内容をあらかじめ復習しておく （2時間） 【事後学習】再帰呼出し・2分探索に関するプログラミング課題に取り組む （2時間） |
| 2 |
2分探索木の実装復習
【事前学習】2分探索木の実装について復習しておく （2時間） 【事後学習】2分探索木に関するプログラミング課題に取り組む （2時間） |
| 3 |
2分探索木のトラバース復習
【事前学習】2分探索木のトラバーサルについて復習しておく （2時間） 【事後学習】2分探索木のトラバーサルに関するプログラミング課題に取り組む （2時間） |
| 4 |
平衡木の概念
【事前学習】平衡木について事前に確認する （2時間） 【事後学習】平衡機の概念に関する課題に取り組む （2時間） |
| 5 |
平衡木の実装 (AVL 木の場合)
【事前学習】平衡木の実装について事前に確認する （2時間） 【事後学習】平衡木に関するプログラミング課題に取り組む （2時間） |
| 6 |
ヒープ木の概念と実装
【事前学習】ヒープ木について事前に確認する （2時間） 【事後学習】ヒープ木に関するプログラミング課題に取り組む （2時間） |
| 7 |
工夫したヒープ木の実装
【事前学習】工夫したヒープ木の実装について事前に確認する （2時間） 【事後学習】木構造に関するプログラミング課題に取り組む （2時間） |
| 8 |
小テスト (1) スタックとキューの探索への応用 ：幅優先探索 【事前学習】幅優先探索について事前に確認する （2時間） 【事後学習】幅優先探索に関するプログラミング課題に取り組む （2時間） |
| 9 |
スタックとキューの探索への応用 ：深さ優先探索
【事前学習】深さ優先探索について事前に確認する （2時間） 【事後学習】幅優先探索に関するプログラミング課題に取り組む （2時間） |
| 10 |
再帰呼び出しによる深さ優先探索
【事前学習】再帰呼出しを用いた深さ優先探索について事前に確認する （2時間） 【事後学習】再帰呼出しを用いた深さ優先探索に関するプログラミング課題に取り組む （2時間） |
| 11 |
探索の実践的なプログラミング
【事前学習】第8回〜第10回の内容について復習しておくこと （2時間） 【事後学習】木の探索に関するプログラミング課題に取り組む （2時間） |
| 12 |
ハッシュ関数と内部ハッシュ法
【事前学習】ハッシュ関数と内部ハッシュについて事前に確認する （2時間） 【事後学習】内部ハッシュに関するプログラミング課題に取り組む （2時間） |
| 13 |
外部ハッシュ法
【事前学習】外部ハッシュについて事前に確認する （2時間） 【事後学習】外部ハッシュに関する課題に取り組む （2時間） |
| 14 |
外部ハッシュの計算量
【事前学習】第12回・第13回の内容について復習しておくこと （2時間） 【事後学習】ハッシュに関する課題に取り組む （2時間） |
| 15 |
まとめと小テスト (2)
【事前学習】第1回〜第14回の内容について復習しておくこと （2時間） 【事後学習】総合的なプログラミング課題に取り組む （2時間） |
| その他 | |
|---|---|
| 教科書 | 大槻 兼資 著 『問題解決力を鍛える!アルゴリズムとデータ構造 （KS情報科学専門書）』 講談社 2020年 |
| 参考書 | 平田富夫 『アルゴリズムとデータ構造』 2016年 第3版 米田 優峻 著 『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』 技術評論社 2021年 第1版 茨木 俊秀 『Cによるアルゴリズムとデータ構造(改訂2版) 』 オーム社 2019年 第2版 |
| 成績評価の方法及び基準 | 授業内テスト(40%)、授業参画度(60%) ・授業内テストは2回実施する．詳細は1回目の授業時に説明する． ・授業内テストは対面で実施する．（対面でのテストを受験できない事情がある場合は，1対1あるいは少人数での面接テスト・オンラインテスト・レポートの組み合わせでテストに代えるなどの配慮を行う．） ・6回前後の事前学習あるいは事後学習の一環として課題提出を課す．この評価が授業参画度の中核をなす． ・基本的対面出席者も Zoom 参加者も Blackboard, Google Classroom, OneDrive, Google Drive, Google Chat でコミュニケーション行う． |
| オフィスアワー | 随時受け付ける．Google Chat にてアポイントを取ること． |