1. |
授業の概要(ねらい)・ディプロマポリシーとの関連 |
|
様々なデータ構造と、それを取り扱う基本的なアルゴリズムの理解を通して、(1)アルゴリズムの設計や解析をするための基本的な手法を修得します。さらに(2)その基本手法を応用できる能力を養うことを目標とします。(1)が必須で(2)の入り口までが、この授業の到達目標です。具体的な学習内容は次の通りです。アルゴリズムとその計算量(時間計算量、領域計算量など)、基本的なデータ構造(リスト、スタック、キュー、木など)、アルゴリズムの設計技法(再帰法、動的計画法、バックトラック法など)、探索アルゴリズム、ソーティングアルゴリズム、グラフアルゴリズム、パターン照合など。
ディプロマポリシー2(DP2)に関する知識、技法、態度を修得します。
|
2. |
授業の到達目標 |
|
授業の到達目標は次の4つです。
(a)基本的なデータ構造を理解し、適切に使うことができる。
(b)基本的なアルゴリズムを理解し、適切に使うことができる。
(c)計算量を用いてアルゴリズムの良し悪しが評価できる。
(d)問題に対して、適切なアルゴリズムとデータ構造を選択できる。
|
3. |
成績評価の方法および基準・フィードバック方法 |
|
2回のレポートの合格を前提に、科目修得試験の結果で評価します。レポートに赤を入れて返却することでフィードバックをします。
|
4. |
教科書・参考書 |
|
荒井正之著:“Javaアプレットによるデータ構造とアルゴリズム”、共立出版、2008、ISBN978-4-320-12201-7。
|
5. |
準備学修の内容・必要な時間 |
|
授業は教科書に沿って進めますので、教科書の該当部分を精読して、その授業回のキーワードとなる概念を必ず確認してから授業に臨んでください。(1.5時間) 復習として、テキストの該当部分の章末にある演習問題を必ず解いてください。(1.5時間)
|
6. |
その他履修上の注意事項 |
|
テキストを読むだけではなく、自分のコンピュータにEclipseとJDKをインストールし、実際にプログラムを作って、学習内容を1つ1つ確認しましょう。
|
7. |
授業内容 |
|
【第1回】 | データ構造とアルゴリズムと—データ構造の違いとアルゴリズムの効率 | 【第2回】 | 計算—時間計算量と領域計算量 | 【第3回】 | 基本的なデータ構造(1)—配列 | 【第4回】 | 基本的なデータ構造(2)—クラス | 【第5回】 | 基本的なデータ構造(3)—リスト | 【第6回】 | 基本的なデータ構造(4)—Javaにおけるデータ型,スタック | 【第7回】 | 基本的なデータ構造(5)—木構造 | 【第8回】 | 基本的なデータ構造(6)—平衡木 | 【第9回】 | 基本的なデータ構造(7)—平衡木 | 【第10回】 | 基本的なデータ構造(8)—ヒープ | 【第11回】 | 探索アルゴリズム(1)—線形探索、二分探索、深さ優先探索 | 【第12回】 | 探索アルゴリズム(2)—広がり優先探索、バックトラック法、ハッシュ法 | 【第13回】 | 文字列探索―クヌース・モリス・プラット法、ボイヤー・ムーア法、再帰 | 【第14回】 | ソートアルゴリズム—単純選択ソート、バブルソート、クイックソートなど | 【第15回】 | まとめと科目修得試験 |
|