概要:
データ構造とアルゴリズムIに続き、時間・領域計算量の考え方やソートおよび探索手法を通じて、効率的な問題解決力を養う。ソート・探索アルゴリズムとデータ構造の関係を理解し、最適な手法を選択できる力を身につける。
授業の進め方・方法:
【授業のすすめ方】
授業では代表的な例を教員が解説し、演習問題に取り組むことで理解を深める。
【評価方法】
試験：80%, 課題: 20%
注意点:
オフィスアワーとして水曜日16時20分から17時として設定しているため、理解できない内容があれば質問に来ること。また、オフィスアワー以外の時間であっても事前にOffice Teamsのチャットなどにより連絡しても良いです。
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
ガイダンス |
科目内容の概要を理解し、データ構造とアルゴリズムIで実施した内容の復習を行う。
|
| 2週 |
文字列の探索(1) |
文字列に対する探索について理解できる。Knuth-Morris-Pratt(KMP)アルゴリズムについて理解でき、力まかせのアルゴリズムと比較できる。
|
| 3週 |
文字列の探索(2) |
Knuth–Morris–Pratt（KMP）アルゴリズムのプログラムを作成できる。
|
| 4週 |
文字列の探索(3) |
文字列比較におけるグローバルアラインメントについて理解できる。
|
| 5週 |
文字列の探索(4) |
文字列比較におけるローカルアラインメントについて理解できる。
|
| 6週 |
文字列の探索(5) |
文字列比較におけるアラインメントのプログラムを作成できる。
|
| 7週 |
トライデータ構造 |
文字列検索におけるトライ（Trie）データ構造の仕組みを理解できる
|
| 8週 |
まとめ |
週１から週７の内容について理解を深める
|
| 4thQ |
| 9週 |
整列アルゴリズム(1) |
単純選択方法 、バブルソート方法と挿入ソート方法について理解できる。
|
| 10週 |
整列アルゴリズム(2) |
単純選択、バブルソート、挿入ソートの時間計算量について比較できる。これらの方法のc言語プログラムを実装できる。
|
| 11週 |
整列アルゴリズム(3) |
ヒープソート、クイックソートとマージソートについて理解できる。
|
| 12週 |
整列アルゴリズム(4) |
週１〜週12まで学んだソート方法を比較するC言語プログラムを。実装できる。
|
| 13週 |
整列アルゴリズム(5) |
比較によらないソートについて理解でき、プログラムを実装できる。
|
| 14週 |
整列アルゴリズム(6) |
週 9から週13の内容について理解を深める
|
| 15週 |
総合的課題に取り組む、まとめ |
科目に学習したの内容をまとめて理解できる。
|
| 16週 |
|
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | 後1,後2,後8,後14,後15 |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | 後2,後4,後5,後8,後9,後10,後12,後14,後15 |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | 後2,後8,後10,後11,後12,後13,後14,後15 |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | 後8,後11,後12,後14,後15 |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | 後7,後8,後11,後12,後14,後15 |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | 後8,後11,後12,後13,後14,後15 |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 3 | 後8,後13,後14,後15 |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 3 | 後3,後6,後8,後13,後14,後15 |