到達目標
アルゴリズムの必要性を理解するため,探索問題やソート問題などなど従来からよく用いられるアルゴリズムの仕組みを学ぶ.
【教育目標】C,D
【学習・教育到達目標】C-2,D-1
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | アルゴリズムを設計できる | アルゴリズムを理解できる | アルゴリズムを理解できない |
学科の到達目標項目との関係
教育方法等
概要:
アルゴリズムの応用や設計ができるよう,探索問題や動的計画法などなど従来からよく用いられるアルゴリズムからアルゴリズムの設計技法を学ぶ.
授業の進め方・方法:
教科書を用いた授業を中心に進める.教科書にサンプルプログラムが記載されているのであらかじめ確認し、プログラムの文法等で理解できない場合は、「プログラミング」などの授業で使用した教科書等で学習しておくこと.学習の理解度を確認するために課題にていくつかのアルゴリズムを実装する.
注意点:
試験結果(80%)、課題(20%)で評価する。詳細は第1回目の授業で告知する。
課題等を課すので自学自習をしてレポート等を提出すること。レポート等の未提出が、必要な自学自習時間数相当分の4分の1以上の場合は低点とする。
各種アルゴリズムの仕組みの理解の程度を評価する。総合成績60点以上を単位修得とする。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
後期 |
3rdQ |
1週 |
ガイダンス |
アルゴリズムの必要性が理解できる
|
2週 |
文字列探索(1) |
単純な文字列探索技法が理解できる
|
3週 |
文字列探索(2) |
複雑な文字列探索技法が理解できる
|
4週 |
文字列探索(3) |
複雑な文字列探索技法が理解できる
|
5週 |
計算量とオーダー記法 |
アルゴリズムの計算量の求め方とオーダー記法が理解できる
|
6週 |
再帰と分割統治法(1) |
再帰アルゴリズムの仕組みが理解できる
|
7週 |
再帰と分割統治法(2) |
分割統治法の仕組みが理解できる
|
8週 |
動的計画法(1) |
動的計画法の仕組みが理解できる
|
4thQ |
9週 |
動的計画法(2) |
動的計画法の応用ができる
|
10週 |
貪欲法 |
貪欲法の仕組みが理解できる
|
11週 |
Union-Find(1) |
Union-Findの仕組みが理解できる
|
12週 |
Union-Find(2) |
Union-Findの応用ができる
|
13週 |
PとNP |
P問題とNP問題が理解できる
|
14週 |
難問対策(1) |
難問の対策例が理解できる
|
15週 |
難問対策(2) |
難問の対策例が理解できる。
|
16週 |
まとめ |
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 3 | |
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 3 | |
情報数学・情報理論 | 離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 4 | |
評価割合
| 試験 | 課題 | 合計 |
総合評価割合 | 80 | 20 | 100 |
総合能力 | 80 | 20 | 100 |