(1)計算量の概念を説明できる。(2)様々なデータ構造を用いた探索の計算量について説明できる。(3)様々な整列のアルゴリズムとその計算量について説明できる。
概要:
第2学期開講
様々な整列とデータ構造を用いた探索のアルゴリズムと,その計算量について学び,ソフトウェア設計に活かせるようになることを目標とする。
授業の進め方・方法:
配布プリントに基づいて授業を進める.C言語の基本的な文法知識が必須である.C言語の教科書を携帯することを助言する.各項目ごとにプログラミングの演習課題を課す.演習課題を行うことにより知識の定着を図る.データ構造・アルゴリズムを理解するためには,図や模式図等を用い,その状況や動作を説明できることが重要である.
注意点:
データ構造とアルゴリズムは,プログラムを作成する際には是非とも習得すべき学問である.なぜなら,プログラムはデータ構造とアルゴリズムから構成されているからである.より良いプログラムは,データ構造とアルゴリズムを同時に考慮することにより作成される.データ構造とアルゴリズムを理解すると,より良いプログラムを作成する能力が身に付く.また,プログラミング能力を伸ばすためにも必須である.
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
計算量 |
基本的なアルゴリズムとフローチャートについて理解できる。
|
2週 |
基本的なデータ構造 |
線形リスト,二分木,ハッシュテーブル等の基本的なデータ構造について理解できる。
|
3週 |
線形リスト |
線形リストの構造とそれを用いた線形探索のアルゴリズムと計算量について理解する。
|
4週 |
線形リスト演習 |
線形リストを用いた線形探索を用いたソフトウェアを設計できる。
|
5週 |
二分木 |
二分木を用いた線形探索のアルゴリズムと計算量について理解する。
|
6週 |
二分木演習 |
二分木の構造とそれを用いた線形探索を用いたソフトウェアを設計できる。
|
7週 |
ハッシュ表 |
ハッシュ表を用いた線形探索のアルゴリズムと計算量について理解する。
|
8週 |
ハッシュ表演習 |
ハッシュ表の構造とそれを用いた線形探索を用いたソフトウェアを設計できる。
|
2ndQ |
9週 |
中間まとめ |
|
10週 |
基本的な整列のアルゴリズム |
バブルソート,挿入ソート,クィックソート等の基本的な整列アルゴリズムについて理解できる。
|
11週 |
バブルソート |
バブルソートのアルゴリズムと計算量について理解する。
|
12週 |
挿入ソート |
挿入ソートのアルゴリズムと計算量について理解する。
|
13週 |
クィックソート |
クィックソートのアルゴリズムと計算量について理解する。
|
14週 |
アルゴリズムとデータ構造を意識したプログラム設計 |
同一の問題に対し,様々なアルゴリズムとデータ構造を用いてソフトウェアを設計できる。
|
15週 |
定期試験 |
|
16週 |
まとめ |
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
基礎的能力 | 工学基礎 | 情報リテラシー | 情報リテラシー | 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。 | 4 | |
与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。 | 4 | |
任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。 | 4 | |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |