概要:
この科目では、代表的なデータ構造、アルゴリズムの基礎知識、アルゴリズムの設計技法を学ぶ。データ構造はデータの集まりとデータ間の結合関係を表現したものである。アルゴリズムは問題を解くための計算の手続きで、その手続きで計算すれば有限時間内に必ず答えを出して計算が終了するようなものをいう。データ構造とアルゴリズムは言わばプログラムの素であり、効率のよいプログラムを作成するために不可欠な知識である。
授業の進め方・方法:
講義形式
注意点:
本科目は、授業で保証する学習時間と、予習・復習及び課題レポート作成に必要な標準的な自己学習時間の総計が、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週 |
期末試験
|
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 基礎的能力 | 工学基礎 | 情報リテラシー | 情報リテラシー | 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。 | 4 | 後1 |
| 与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。 | 4 | 後6,後7,後9 |
| 任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。 | 4 | 後2,後3,後5,後6,後11,後13 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | 後1 |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | 後6,後7,後9,後15 |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | 後1 |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | 後1 |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | 後1 |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | 後10,後11,後12,後13,後14 |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | 後2 |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 後2 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | 後3,後4,後5 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | 後3,後4,後5 |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | 後10,後11,後12 |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | 後11,後12 |
| 分野横断的能力 | 総合的な学習経験と創造的思考力 | 総合的な学習経験と創造的思考力 | 総合的な学習経験と創造的思考力 | 要求に適合したシステム、構成要素、工程等の設計に取り組むことができる。 | 3 | 後6,後7,後9,後15 |