概要:
既に学習したプログラミング言語の基礎的な文法を基に,アルゴリズムとデータ構造に関する概念・諸定義を学習する.また演習を通じて学習したアルゴリズムとデータ構造を実現する.
授業の進め方・方法:
授業は講義形式と演習形式を混合した形式で実施される。また各週のテーマ従った演習を授業で提示する。
注意点:
学習内容には抽象度の高い概念が含まれる。これらの概念を定着させ,実現するために,演習内容に習熟するよう留意すること。また,アルゴリズムの内容とデータ構造を正しく理解するために,積極的にそれらを用いて習熟するよう留意すること。
自学自習として,各回の授業内容,達成項目及び教科書内容を確認しておくこと。学習内容に含まれる概念を理解するために,教科書等に掲載されている例題を基に十分復習すること。理解を確実にするため,各回の授業内容に関連する例題や練習問題を実行し解くこと。
|
|
週 |
授業内容 |
週ごとの到達目標 |
後期 |
3rdQ |
1週 |
文字列の照合(パターンマッチング) |
文字列の照合(単純な方法)のシーケンスを描ける。BoyerMoore法による文字列の照合のシーケンスを描ける。BoyerMoore法を用いた文字列照合プログラムを作成できる。
|
2週 |
ハッシュ |
ハッシュの演習問題を解くことができる。ハッシュを使った探索プログラムを作成できる。
|
3週 |
再帰呼び出し |
順列の全並びを生成するアルゴリズム(再帰呼び出し使用)のシーケンスを描ける。巡回セールスマン問題のプログラムを作成できる。
|
4週 |
クイックソート |
クイックソートのアルゴリズムのシーケンスを描ける。クイックソートのプログラムを作成できる。
|
5週 |
スタック,キュー |
スタックとキューの基本的なデータ構造の概念と操作を説明することができる。
|
6週 |
リスト |
リスト構造の概念を理解しリストの挿入と削除のプログラムを作成することができる。
|
7週 |
双方向リスト |
双方向リストの概念を理解し要素の操作のプログラムが作成できる。
|
8週 |
中間試験 |
中間試験の問題を解くことができる.
|
4thQ |
9週 |
逆ポーランド記法,パージング |
式を逆ポーランド記法の式に変換し,パージングにより式の値を求めるプログラムを作成することができる。
|
10週 |
2分探索木(配列表現,動的表現,再帰的表現) |
木構造の概念を理解し説明することができる。
|
11週 |
2分探索木(走査) |
2分探索木のノードを走査するアルゴリズムを理解できる。
|
12週 |
ヒープ・ヒープソート |
ヒープソートのアルゴリ ズムを理解し,そのプログラムを作成できる。
|
13週 |
グラフ,グラフの探索 |
グラフの概念と探索のアルゴリズムを理解し,そのプログラムを 作成することができる。
|
14週 |
Eulerの一筆書き |
一筆書き経路を求めるアルゴリズムを理解し,プログラムを作成できる。
|
15週 |
最短絡問題 |
最短絡問題のダイクストラ法を理解し,そのプログラムを作成できる。
|
16週 |
|
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | 後1,後2,後3,後4,後5,後8 |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | 後1,後2,後3,後4,後5,後8 |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | 後1,後2,後3,後4,後5,後8 |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | 後1,後2,後3,後4,後5,後8 |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 3 | 後1,後2,後3,後4,後5,後8 |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 3 | 後2,後5,後14 |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 3 | 後6,後7,後8,後9,後10,後11,後12,後13,後14,後15,後16 |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 3 | 後6,後7,後8,後9,後10,後11,後12,後13,後14,後15,後16 |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 3 | 後6,後7,後8,後9,後10,後11,後12,後13,後14,後15,後16 |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 3 | 後6,後7,後8,後9,後10,後11,後12,後13,後14,後15,後16 |