到達目標
[1] アルゴリズムの計算量の解析技法を習得すること
[2] 基本的なデータ構造とそれらに対する操作を理解すること
[3] アルゴリズムの基本設計技法を習得すること
[4] 基本的なソーティングアルゴリズムとそれらの時間計算量を把握すること
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | アルゴリズムの計算量と問題の下界を解析することができる | アルゴリズムの計算量を解析することができる | アルゴリズムの計算量を解析することができない |
| 評価項目2 | 基本的なデータ構造を理解し、それらを的確に使うことができる | 基本的なデータ構造を理解し、それらを使うことができる | 基本的なデータ構造を理解できず、それらを使うこともできない |
| 評価項目3 | アルゴリズムの基本設計技法を的確に使うことができる | アルゴリズムの基本設計技法を使うことができる | アルゴリズムの基本設計技法を使うことができない |
| 評価項目4 | 基本的なソーティングアルゴリズムとそれらの時間計算量を的確に説明することができる | 基本的なソーティングアルゴリズムとそれらの時間計算量を説明することができる | 基本的なソーティングアルゴリズムを説明できず、それらの時間計算量も説明できない |
学科の到達目標項目との関係
学習・教育目標 (D)
説明
閉じる
学習・教育目標 (F)
説明
閉じる
学習・教育目標 (G)
説明
閉じる
教育方法等
概要:
この科目では、代表的なデータ構造、アルゴリズムの基礎知識、アルゴリズムの設計技法を学ぶ。データ構造はデータの集まりとデータ間の結合関係を表現したものである。アルゴリズムは問題を解くための計算の手続きで、その手続きで計算すれば有限時間内に必ず答えを出して計算が終了するようなものをいう。データ構造とアルゴリズムは言わばプログラムの素であり、効率のよいプログラムを作成するために不可欠な知識である。
授業の進め方・方法:
講義
注意点:
本科目は、授業で保証する学習時間と、予習・復習及び課題レポート作成に必要な標準的な自己学習時間の総計が、90時間に相当する学習内容である。考える力を養うこと。eラーニングシステムで当該週の小テストとプログラミング課題が出される。学修単位の科目であるので、期限内に小テストと課題それぞれについて2/3以上をクリア・提出することが必須要件である。
合格の対象としない欠席条件(割合) 1/3以上の欠課
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
アルゴリズムと計算量
|
問題と問題例の違いを説明し、問題を解くアルゴリズムとは何かを説明できる。オーダ表記を用いてアルゴリズムの計算量を解析できる。
|
| 2週 |
列を表すデータ構造 1/2
|
配列とリストについて、プログラムで実現する方法を説明できる。各データ構造に対して基本操作に要する時間計算量を解析できる。
|
| 3週 |
列を表すデータ構造 2/2
|
スタックとキューについて、プログラムで実現する方法を説明できる。各データ構造の性質と基本操作に要する時間計算量を解析できる。
|
| 4週 |
グラフと木
|
グラフと木について、プログラムで実現する方法と空間計算量について説明できる。各方法に対し、グラフ(木)の頂点の隣接関係を調べる操作の時間計算量を説明できる。
|
| 5週 |
ヒープ
|
ヒープは部分順序付き木を1次元配列で実現したものである。ヒープを構成するアルゴリズムとデータを挿入・削除するアルゴリズムが書ける。また、それらの時間計算量を解析できる。
|
| 6週 |
再帰法と再帰方程式
|
再帰法を用いてアルゴリズムが書ける。再帰的手続きの時間計算量を解析して得られる再帰方程式を解くことができる。
|
| 7週 |
分割統治法
|
再帰法と組合せて用いられる分割統治法を用いてアルゴリズムが書ける。
|
| 8週 |
中間試験
|
|
| 4thQ |
| 9週 |
動的計画法
|
最適化問題に広く用いられる動的計画法とその計算過程を説明できる。
|
| 10週 |
素朴なソーティングアルゴリズムと決定木 |
単純挿入法、単純選択法、バブルソートのアルゴリズムが書けて、それらの時間計算量を解析できる。また、決定木を用いて、比較によるソーティングにおける比較回数を解析でできる。
|
| 11週 |
最適なソーティングアルゴリズム
|
最悪時間計算量が最適であるマージソートとヒープソートのアルゴリズムが書けて、それらの時間計算量を解析できる。
|
| 12週 |
クイックソートとバケットソート
|
平均時間計算量が最適であるクイックソートのアルゴリズムが書けて、その時間計算量を解析できる。要素同士の比較を行わないバケットソートについて説明できる。
|
| 13週 |
2分探索法と2分探索木
|
データが探索キーの大きさの順に並んでいるとき高速にデータを探索できる2分探索法を説明できる。2分探索の考え方を生かしながら、データの挿入・削除が行える2分探索木についてアルゴリズムが書けて、時間計算量を解析できる。
|
| 14週 |
AVL木、B木、ハッシュ法
|
2分探索木は必ずしも木のバランスが良くなるとは限らない。代表的な平衡木であるAVL木とB木について説明できる。また、データの比較を行わずに集合を表現するハッシュ法について説明できる。
|
| 15週 |
貪欲法
|
グラフの最小全域木を構成する、クルスカルのアルゴリズムとプリムのアルゴリズムを説明できる。また、それらの時間計算量を解析できる。
|
| 16週 |
期末試験
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 試験 | 小テスト | 課題 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 66 | 14 | 20 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 66 | 14 | 20 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |