概要:
これまでに開発されている,問題解決のための各種のアルゴリズムと,関連するデータ構造について理解すること.そして,プログラミング上の応用問題において,それらを活用できる能力を養うこと.理論だけでなくコーディングも重視していく.
授業の進め方・方法:
・各週の内容は,電子情報工学科学習・教育到達目標(B)<専門>の項目に相当する.
・授業は講義・輪講形式で行う.講義中は集中して聴講する.
・「授業計画」における各週の「到達目標」はこの授業で習得する「知識・能力」に相当するものとする.
注意点:
<到達目標の評価方法と基準>下記授業計画の「到達目標」を網羅した問題を2回の中間試験,2回の定期試験で出題し,目標の達成度を評価する.各到達目標に関する重みは同じである.合計点の60%の得点で,目標の達成を確認できるレベルの試験を課す.
<学業成績の評価方法および評価基準>前期中間・前期末・後期中間・学年末の4回の試験の平均点による評価を80%,プログラミング課題等に対するレポートの評価を20%として学業成績を評価する.ただし,試験の得点が60点に満たない場合は,補講の受講やレポート提出等の後,再試験により再度評価し,合格点の場合は先の試験の得点を60点と見なす.
<単位修得要件>学業成績で60点以上を取得すること.
<あらかじめ要求される基礎知識の範囲>本教科はプログラミング基礎,マイクロコンピュータ基礎,プログラム設計,オペレーティングシステムの学習が基礎となる教科である.また,数学の基本事項について理解していることも必要である.
<レポート等>授業中に演習(C++プログラミング)を適宜行う.また,プログラミング課題に対するレポート提出を求める.さらに,それ以外に,計算問題等に対するレポート提出を求めることがある.
<備考>データ構造とアルゴリズムに関する理解は,情報工学分野における最も重要な基盤の一つである.具体例で確認・理解すると同時に,数学的な表現を理解できることも必要である.論理的・数学的な思考力を,さらに培っていくことが大切である.本教科は後に学習するソフトウェア工学,人工知能,数値解析の基礎となる教科である.
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
アルゴリズムとは
|
1. 整列のアルゴリズムについて説明できる.
|
2週 |
ソート
|
1. 整列のアルゴリズムについて説明できる.
|
3週 |
サーチ
|
2. 探索のアルゴリズムについて説明できる.
|
4週 |
データ構造とは
|
3. リスト構造の概念と操作を説明でき,実装することができる.
|
5週 |
リスト
|
3. リスト構造の概念と操作を説明でき,実装することができる.
|
6週 |
スタック
|
4. スタック,キューの概念と操作を説明でき,実装することができる.
|
7週 |
キュー
|
4. スタック,キューの概念と操作を説明でき,実装することができる.
|
8週 |
中間試験
|
これまでに学習した内容を説明し,諸量を求めることができる.
|
2ndQ |
9週 |
再帰
|
5. 再帰が問題を解決していく過程を説明できる.
|
10週 |
最大公約数を求める
|
5. 再帰が問題を解決していく過程を説明できる.
|
11週 |
木構造
|
6. 木構造の概念と操作を説明でき,実装することができる.
|
12週 |
2分木
|
6. 木構造の概念と操作を説明でき,実装することができる.
|
13週 |
多分木
|
6. 木構造の概念と操作を説明でき,実装することができる.
|
14週 |
マップ
|
7. ハッシュ法のアルゴリズムについて説明できる.
|
15週 |
ハッシュ
|
7. ハッシュ法のアルゴリズムについて説明できる.
|
16週 |
|
|
後期 |
3rdQ |
1週 |
誤差
|
8. コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる.
|
2週 |
数値計算
|
8. コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる.
|
3週 |
文字列検索
|
9. 文字列検索のアルゴリズムについて説明できる.
|
4週 |
KMP法
|
9. 文字列検索のアルゴリズムについて説明できる.
|
5週 |
BM法
|
9. 文字列検索のアルゴリズムについて説明できる.
|
6週 |
深さ優先探索
|
10. 深さ優先探索,幅優先探索のアルゴリズムについて説明できる.
|
7週 |
幅優先探索
|
10. 深さ優先探索,幅優先探索のアルゴリズムについて説明できる.
|
8週 |
中間試験
|
これまでに学習した内容を説明し,諸量を求めることができる.
|
4thQ |
9週 |
動的計画法
|
11. 動的計画法のアルゴリズムについて説明できる.
|
10週 |
ナップザック問題
|
11. 動的計画法のアルゴリズムについて説明できる.
|
11週 |
最短経路問題
|
11. 動的計画法のアルゴリズムについて説明できる.
|
12週 |
逆ポーランド記法
|
12. 2分探索木のアルゴリズムについて説明できる.
|
13週 |
グラフ構造
|
13. グラフ構造の概念と操作を説明でき,実装することができる.
|
14週 |
重み付きグラフ
|
13. グラフ構造の概念と操作を説明でき,実装することができる.
|
15週 |
ダイクストラ法
|
13. グラフ構造の概念と操作を説明でき,実装することができる.
|
16週 |
|
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |