【授業概要】
・テーマ
各種のデータ構造とそれらに関連する基本的なアルゴリズムを学ぶ. データ構造とアルゴリズムは,プログラムを作る上で必ず学ばなければならない基礎の一つであり,少しでも本格的な良いプログラムを作ろうと思えば,データ構造とアルゴリズムに関する知識が欠かせない.このようなプログラミングの基礎となる,基本的な種々のデータ構造とそれらに関連する基本的なアルゴリズムを解説する.
・到達目標
(a)各種のデータ構造(線形構造、木構造、グラフ構造)を理解する (b)基本的な探索法(縦型探索法、横型探索法)を理解する (c)文字列照合の代表的なアルゴリズム(KMP法)を理解する (d)グラフの最短路問題の代表的なアルゴリズム(ダイクストラ法)を理解する (e)解探索の代表的なアルゴリズム(Aアルゴリズム)を理解する (f)データ整列の代表的なアルゴリズム(ヒープソート法,クイックソート法)を理解する (g)データ探索の代表的なアルゴリズム(ハッシュ法)を理解する
・キーワード
線形構造,木構造,グラフ構造,スタックと待ち行列,文字列照合,グラフの最短路問題,解の探索,データ整列,データ探索
【科目の位置付け】
本授業の基礎となる科目:計算機基礎 本授業と関連が深い科目:プログラミング言語,データベース論,プログラミング演習,計算機工学演習 情報科学科の学習・教育目標の(B)情報基礎力に対応する.
【授業計画】
・授業の方法
講義形式で行う.毎回授業終了前の15分~20分間でその時間内に学んだことの演習を行う.
・日程
第 1週 ガイダンス,データ構造とアルゴリズムの基礎 第 2週 線形構造 第 3週 スタックと待ち行列,基本的な探索法 第 4-5週 文字列照合(KMP法など) 第 6週 木構造 第 7週 グラフ構造 第 8週 中間試験と解説 第 9週 グラフの最短路問題(ダイクストラ法など) 第10週 解の探索(Aアルゴリズムなど) 第11-12週 データ整列(ヒープソート法,クイックソート法など) 第13-14週 データ探索(表探索,木構造探索) 第15週 定期試験と解説 なお、学生の理解度などに応じて講義内容を修正することもある
【学習の方法】
・受講のあり方
欠席や遅刻をすると授業内容が分からなくなるので必ず遅刻せずに出席すること. 私語など他の受講生の迷惑となる行為は行わないこと.受け身にならず積極的な受講を期待する.
・授業時間外学習へのアドバイス
予習として,テキストの該当箇所を前もって読んでくるとともに疑問点などをノートに書きだしてくる. 復習として,演習問題をもう一度解いてみるとともに講義で出てきたアルゴリズムを実際にC言語を用いてプログラミングするのが望ましい.
【成績の評価】
・基準
総合点で60点以上を合格とする.
・方法
中間試験(50点),定期試験(50点)の配点で評価する.
【テキスト・参考書】
自作のテキストを生協で販売するので1回目の講義前に購入すること. 参考書 1. 斎藤信男・西原清一、データ構造とアルゴリズム、コロナ社、2800円(1998) 2. 西原清一、Cで学ぶデータ構造とアルゴリズム、オーム社、2600円(2008) 3. 広瀬貞樹、あるごりずむ、近代科学社、2400円(2006)
【その他】
・オフィス・アワー
毎週月曜日 16:00~17:30、相談場所:工学部8号館 8-301号室
|