- 学部・研究科
Faculty/Graduate School - 総情
- 時間割コード
Course Code - 70605
- 科目名
Course title
サブテーマ
Subtitle - アルゴリズム解析・設計
＜C＞ - 授業形態/単位
Term/Credits - クラス
Class -
- 春/2
- 担任者名
Instructor - 仲川 勇二
- 曜限
Day/Period - 木3
- 授業概要
Course Description
到達目標
Course Objectives -
言語 / Language
日本語(Japanese)
授業概要 / Course Description
プログラムは、コンピュータを制御するための一連の命令（手順）とデータの集まりからなっている。有限回の処理で終わる一連の手順をアルゴリズムと呼ぶ。基本的なアルゴリズムとしては、データを整列するためのソートアルゴリズム、整列されたデータからある項目を探索するためのサーチアルゴリズム等がある。本講義では、基本的なアルゴリズムとそのアルゴリズムが使用する計算時間について講究する。また、プログラムの中で、大量のデータを取り扱う場合、そのデータ構造の設計がよくないと、その後のデータの取り扱いがかなり煩雑になる。よいデータ構造を設計するための基礎となるように、基本的なデータ構造についても言及する。
到達目標 / Course Objectives
基本的なアルゴリズムの解析と設計が理解できる。
- 授業計画
Course Content -
授業計画 / Course Content
１ アルゴリズムと計算量
２ 基本的なデータ構造
（1）抽象データ型
（2）リスト
（3）スタック
３ ソートアルゴリズムと解析
（1）O(n＾2)ソートアルゴリズム
（2）O(n log n)ソートアルゴリズム１
（3）O(n log n)ソートアルゴリズム２
（4）O(n)ソートアルゴリズム１
（5）O(n)ソートアルゴリズム２
４ サーチアルゴリズムと解析
（1）二分探索法
（2）ハッシュ法
（3）RACサーチ
５ アルゴリズムの実現例(1) 例１
(2) 例２
６ アルゴリズムの設計授業時間外学習 / Expected work outside of class
数学の知識が必要です。微分積分について復習することが望ましい。
- 成績評価の方法・基準
Grading Policies /
Evaluation Criteria -
方法 / Grading Policies
定期試験を行わず、平常試験(小テスト・レポート等)で総合評価する。小テスト(ほぼ100％）、レポート等の評価を考慮することがある。
基準 / Evaluation Criteria
基本的なアルゴリズムの解析と設計が理解できているかで評価する。
- 教科書
Textbooks
プリント資料
-
参考書
References エイホ・ホップクロフト・ウルマン 『データ構造とアルゴリズム』 （培風館） ヴィルト 『アルゴリズムとデータ構造』 （近代科学社） アズムーデ 『抽象データ型とアルゴリズム』 （サイエンス社） セジウィック 『アルゴリズム第1巻〜第3巻』 （近代科学社） ゴネット 『アルゴリズムとデータ構造ハンドブック』 （啓学出版） 茨木 『アルゴリズムとデータ構造』 （昭晃堂）
- 備考
Other Comments 微分積分、ベクトル、行列等の数学的基礎知識を前提として講義する。