シラバス参照

授業情報／Course information

科目一覧へ戻る 2019/08/20 現在

授業基本情報
科目名（和文）
／Course		 データ構造とアルゴリズム
科目名（英文）
／Course		 Data Structures and Algorithms
時間割コード
／Registration Code		 21140601
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 情報通信工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○小野　孝男
オフィスアワー
／Office Hour		 小野　孝男(火曜日 ５限)
開講年度
／Year of the Course		 2017年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 2年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2017/04/10
使用言語
／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 [期末試験]
筆記試験を実施する.
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識・理解
／Knowledge & Undestanding		 技能・表現
／Skills & Expressions		 思考・判断
／Thoughts & Decisions		 伝達・コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 アルゴリズムの表現方法を学ぶ. ○ ○ ○
2 アルゴリズムの解析について理解する. ○ ○ ○
3 データ構造とそれを操作するアルゴリズムの構造を理解する. ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 中間レポート1 中間レポート2
1 アルゴリズムの表現方法を学ぶ. ○ ○ ○
2 アルゴリズムの解析について理解する. ○ ○ ○
3 データ構造とそれを操作するアルゴリズムの構造を理解する. ○ ○
評価割合（％）
／Allocation of Marks		 70 15 15

科目一覧へ戻る