  シラバス参照
|
| 科目一覧へ戻る | 2019/01/02 現在 |
| 科目名（和文） ／Course |
データ構造とアルゴリズム |
|---|---|
| 科目名（英文） ／Course |
Data Structures and Algorithms |
| 時間割コード ／Registration Code |
21140601 |
| 学部（研究科） ／Faculty |
情報工学部 |
| 学科（専攻） ／Department |
情報通信工学科 |
| 担当教員（○：代表教員）
／Principle Instructor （○） and Instructors |
○小野 孝男 |
| オフィスアワー ／Office Hour |
小野 孝男(火曜日 ５限, 2608室) |
| 開講年度 ／Year of the Course |
2018年度 |
| 開講期間 ／Term |
前期 |
| 対象学生 ／Eligible Students |
2年 |
| 単位数 ／Credits |
2.0 |
| 更新日 ／Date of renewal |
2018/03/16 |
|---|---|
| 使用言語 ／Language of Instruction |
日本語 |
| オムニバス ／Omnibus |
該当なし |
| 授業概略と目的 ／Cource Description and Objectives |
コンピュータープログラムを作成するにあたり, 「処理の方法」である「アルゴリズム」と「データの保持方法」である「データ構造」は, 密接な関係があるとともに非常に重要でもある. そこで, 本講義ではそれらの評価尺度の 1つである計算量を理解するとともに基本的なアルゴリズム?データ構造の考え方と設計方針を理解することを目的とする. |
| 履修に必要な知識?能力?キーワード ／Prerequisites and Keywords |
アルゴリズムやデータ構造をプログラムから完全に切り離して考えてもあまり意味はない. したがって, 多少なりともプログラムを設計した経験があるとよい. また, アルゴリズムやデータ構造の理論は「プログラム」をしやに入れているため, 書いてあることを変に曲解せず「そのまま」理解することも必要である. キーワード: アルゴリズム, データ構造, 再帰 |
| 履修上の注意 ／Notes |
実際にプログラムを作ったときの経験を振り返るとよいだろう. また, 一部の内容については同時期に開講される「プログラミング言語II」でも触れるので, あわせて受講することで「抽象的なアルゴリズム?データ構造」と「実際の C言語での実装」の両方が理解できると思う. |
| 教科書 ／Textbook(s) |
なし. 毎回資料を配布する. |
| 参考文献等 ／References |
近藤嘉雪, 「定本 Cプログラマのためのアルゴリズムとデータ構造」 その他, 書名に「アルゴリズム」や「データ構造」という単語が入っている書籍は多い. そのようなものを参照することで, 多面的な理解ができると思う. |
| 自主学習ガイド ／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework |
アルゴリズムやデータ構造を「形」で覚えたとしてもあまり意味はない. 具体的な問題に対して実際にプログラムを作成しその動作を見ていくことで, 実際の「動作」が理解できるだろう. |
| 資格等に関する事項 ／Attention Relating to Professional License |
|
| 備考 ／Notes |
| No. | 単元（授業回数） ／Unit (Lesson Number) |
単元タイトルと概要 ／Unit Title and Unit Description |
時間外学習 ／Preparation and Review |
配布資料 ／Handouts |
|---|---|---|---|---|
| 1 | 1 | [アルゴリズムと計算量] 「アルゴリズム」の定義を知り, その評価指標としての「計算量」の概念を理解する. |
講義内容を当日配布する | |
| 2 | 2 | [配列の探索] たくさんのデータを持つ配列から特定のデータを見つけるアルゴリズムを考えることにより, 1つの問題に対して複数のアルゴリズムが考えられることを理解する. |
講義内容を当日配布する | |
| 3 | 3 | [計算量] 計算量を記述する方法を学ぶび, 実際のアルゴリズムに対して計算量を求める. |
講義内容を当日配布する | |
| 4 | 4 | [リスト] 簡単なデータ構造であるリストの概念を理解し, その実装としての配列と線形リストの特徴について学ぶ. |
講義内容を当日配布する | |
| 5 | 5 | [二分探索木] 格納するデータが順序構造を持つことを前提に, 単純なリストよりも効率よくデータを探索することのできる二分探索木について理解する. |
講義内容を当日配布する | |
| 6 | 6 | [ハッシュ] 離散的なデータをより効率的に探索するデータ構造であるハッシュについて理解する. |
講義内容を当日配布する | |
| 7 | 7 | [ソート(1)] データを一定の順序に入れ替えるソートアルゴリズムを分類し, 比較に基づくそーとアルゴリズムの理論的限界を学ぶ. |
講義内容を当日配布する | |
| 8 | 8 | [ソート(2)] 実際によく用いられるそーとアルゴリズムの 1つであるクイックソートとその性能を紹介する. |
講義内容を当日配布する | |
| 9 | 9 | [ソート(3)] 理論的には高速に実行できるヒープソートとマージソートについて, その考え方と基本的なアルゴリズムを紹介する. |
講義内容を当日配布する | |
| 10 | 10 | [グラフ] 実際の問題ではグラフという構造を用いることも多い. そこでグラフの概念とデータとしての表現方法を紹介する. |
講義内容を当日配布する | |
| 11 | 11 | [最短経路問題] グラフ上の 2点間の最短経路を見つけるアルゴリズムを紹介する. |
講義内容を当日配布する | |
| 12 | 12 | [最小全域木問題] グラフによってあらわされる「もの同士の関係」から, 「もの同士の関連の強さ」を導き出す手法の 1つである最小全域木問題を取り上げ, 特殊なデータ構造を紹介する. |
講義内容を当日配布する | |
| 13 | 13 | [文字列探索] 日常的に使われる「文字列探索」に対して基本的なアルゴリズムから工夫した手法までを紹介する. |
講義内容を当日配布する | |
| 14 | 14 | [問題の分類] 実際に現れる問題は, 簡単なものから難しいものまでさまざまである. そこで, 系sな量によって問題を文分割する. |
講義内容を当日配布する | |
| 15 | 15 | [まとめ] 講義全体のまとめを行う. |
講義内容を当日配布する | |
| 16 | 16 | [期末試験] 筆記試験を実施する. |
| No. |
到達目標 ／Learning Goal |
知識?理解 ／Knowledge & Undestanding |
技能?表現 ／Skills & Expressions |
思考?判断 ／Thoughts & Decisions |
伝達?コミュニケーション ／Communication |
協働 ／Cooperative Attitude |
||
|---|---|---|---|---|---|---|---|---|
| 1 | アルゴリズムの表現方法を学ぶ. | ○ | ○ | ○ | ||||
| 2 | アルゴリズムの解析について理解する. | ○ | ○ | ○ | ||||
| 3 | データ構造とそれを操作するアルゴリズムの構造を理解する. | ○ | ○ |
| No. |
到達目標 ／Learning Goal |
定期試験 ／Exam. |
中間レポート1 | 中間レポート2 | |||
|---|---|---|---|---|---|---|---|
| 1 | アルゴリズムの表現方法を学ぶ. | ○ | ○ | ○ | |||
| 2 | アルゴリズムの解析について理解する. | ○ | ○ | ○ | |||
| 3 | データ構造とそれを操作するアルゴリズムの構造を理解する. | ○ | ○ | ||||
|
評価割合（％） ／Allocation of Marks |
70 | 15 | 15 | ||||