到達目標
アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができる.
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができる.
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる.
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができる | アルゴリズムの概念を理解し,自ら工夫してプログラムを作りあげることができる. | アルゴリズムの概念を理解し,具体的に手順を示すとプログラムを作ることができる | アルゴリズムの概念を理解していない.または,簡単なアルゴリズムを実現するプログラムが自力で書くことができない. |
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができる | アルゴリズムの計算量を数式で理論的に展開し,複数のアルゴリズムの比較を行うことができる. | 幾つかのアルゴリズムに関して計算量の議論を理解し,それによってアルゴリズムの比較が可能であることを理解している. | 計算量の概念が理解できない.または,計算量の議論の内容を理解することができない. |
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる. | 様々なデータ構造を自ら理解し,それらのデータ構造を用いた簡単なプログラムを自力で作ることができる. | 与えられたデータ構造を理解し,それらを用いた簡単なプログラムを詳細な解説を見ながら作ることができる. | 与えられたデータ構造を理解することができない.または,基本的なデータ構造を用いた簡単なプログラムを作ることができない. |
学科の到達目標項目との関係
教育方法等
概要:
基礎事項として,ポインタおよび再帰について学習する。次にデータの表現方法や効率の良いアルゴリズムの実装能力を身につけるため,基本的かつ代表的なアルゴリズムとデータ構造について学習する.
授業の進め方・方法:
原則として,毎回の授業で課題の説明を行い,残りの時間はプログラムを作成する演習時間とする.ただし,計算量の解説などの一部の項目では,座学中心の授業を行う.
注意点:
原則として授業の後半でC言語によるプログラミング演習を行なう.課題が授業時間内に終わらないことも予想されるので,自宅にプログラム開発環境を構築することが望ましい.また本科目の単位を修得するためには,全ての課題を期限内に提出することが必要条件となるので注意すること.
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
後期 |
3rdQ |
1週 |
線形探索と二分探索 計算時間の比較と考察 |
線形・二分探索のアルゴリズムを理解・実装し,適切な条件下で各手法の計算時間を測定・比較できる.
|
2週 |
文字列検索(1) 力まかせ法とKMP法 |
力まかせ法・KMP法のアルゴリズムを理解し実装できる.
|
3週 |
文字列検索(2) BM法 |
BM法のアルゴリズムを理解し実装できる.
|
4週 |
ポインタを用いた文字列処理 |
C言語におけるポインタの概念を理解し,文字列処理に応用することができる.
|
5週 |
ポインタを用いた線形リストの実現 |
線形リストの概念を理解しリスト構造を応用した簡単なデータ処理機能を実装できる.
|
6週 |
ハッシュ関数を利用した検索 |
ハッシュ法のアルゴリズムを理解し実装できる.
|
7週 |
木構造の表現法 木構造を用いた検索 |
木構造の概念を理解し木構造を応用した簡単なデータ処理機能を実装できる.
|
8週 |
グラフ構造を用いた経路探索(1) 深さ優先探索 |
深さ優先探索のアルゴリズムを理解し実装できる.
|
4thQ |
9週 |
グラフ構造を用いた経路探索(2) 幅優先探索 |
幅優先探索のアルゴリズムを理解し実装できる.
|
10週 |
グラフ構造を用いた経路探索(3) ダイクストラ法 |
ダイクストラ法のアルゴリズムを理解し実装できる.
|
11週 |
グラフ構造を用いた経路探索(4) フロイド法 |
フロイド法のアルゴリズムを理解し実装できる.
|
12週 |
動的計画法 |
動的計画法のアルゴリズムを理解し実装できる.
|
13週 |
基本情報技術者試験・応用情報技術者試験における「アルゴリズムとデータ構造」 |
基本・応用情報技術者試験の内容および各試験における出題と当該演習との関連性を理解できる.
|
14週 |
後期課題の総まとめ |
後期すべての課題について復習し未提出課題の提出を完了する.
|
15週 |
定期試験 |
|
16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 1 | |
ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 1 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
評価割合
| 試験 | 課題 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
総合評価割合 | 70 | 30 | 0 | 0 | 0 | 0 | 100 |
基礎的能力 | 20 | 5 | 0 | 0 | 0 | 0 | 25 |
専門的能力 | 50 | 25 | 0 | 0 | 0 | 0 | 75 |
分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |