到達目標
１. アルゴリズムの計算量について説明できる
２. 手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できる
３. 最適化問題の解法として分枝限定法、動的計画法を説明できる
４. 近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | アルゴリズムの計算量について根拠を示して説明できる。 | アルゴリズムの計算量について説明できる。 | アルゴリズムの計算量について説明できない。 |
| 評価項目2 | 手間のかかる問題を解く手法として、深さ優先探索・幅優先探索を利用して探索プログラムを作成できる。 | 手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できる。 | 手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できない。 |
| 評価項目3 | 最適化問題の解法として分枝限定法、動的計画法を説明でき、ナップザック問題に適用して解を求めることができる。 | 最適化問題の解法として分枝限定法、動的計画法を説明できる。 | 最適化問題の解法として分枝限定法、動的計画法を説明できない。 |
| 評価項目4 | 近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明でき、最適化問題の巡回セールスマン問題に適用して解を求めることができる。 | 近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できる。 | 近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できない。 |
学科の到達目標項目との関係
学習・教育到達度目標 B-2
説明
閉じる
学習・教育到達度目標 B-2
説明
閉じる
教育方法等
概要:
本授業の目標は、アルゴリズムに関する事柄について理解を深めることである。この目標を達成するために、具体的に次のことを行う。
エレガントでかつ高速なアルゴリズムが知られていない問題に関して、基本的にはしらみつぶしの方法で解くことになることを理解する。しらみつぶしで解を求める場合でも、つぶしていく順序などによって解に到達する計算量が異なることを理解する。計算量を表す記法についても学ぶ。
解を求めることが難しい問題に関して、NP困難問題やNP完全問題などの問題の分類について学ぶ。このような厳密解を求めるのが困難な問題に対しては、妥当な計算時間で近似解を得るための近似アルゴリズムが使われることを学ぶ。この近似アルゴリズムとして、貪欲法や局所探索法などの解法を理解する。最適化問題である巡回セールスマン問題を例にとり、近似アルゴリズムの適用について理解する。
最後に、アルゴリズムに関する英文を読み輪講形式で発表する。適切な発表資料を作成し、理解されやすい発表を目指して準備を行う。
この科目はSDGsの目標のうち、「4.質の高い教育をみんなに」と「9.産業と技術革新の基盤をつくろう」に関連する。
授業の進め方・方法:
講義を中心とし、適宜、講義内容に関する課題を出題する。また、深さ優先探索や幅優先探索で問題を解くプログラムを作成する。授業時間外に演習を行う時間およびレポート作成時間が必要となる。さらに、アルゴリズムに関する英文を読むための時間、発表準備の時間、発表資料の作成時間が必要となる。
注意点:
C言語のプログラミングに関する知識を有することが望ましい。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス、アルゴリズムの基本的事項 |
アルゴリズムの計算量について理解できる。
O記法を理解できる。
|
| 2週 |
深さ優先探索（nクィーン問題） |
nクィーン問題はどのようなものか理解できる。
nクィーン問題の解の絞り込みについて理解できる。
|
| 3週 |
深さ優先探索（nクィーン問題） |
nクィーン問題を深さ優先探索で解くアルゴリズムを理解できる。
|
| 4週 |
幅優先探索（8パズル問題） |
8パズル問題はどのようなものか理解できる。
8パズル問題のような問題は深さ優先探索では解けないことを理解できる。
|
| 5週 |
幅優先探索（8パズル問題） |
8パズル問題を幅優先探索で解くアルゴリズムを理解できる。
|
| 6週 |
ゲームの木の探索 |
ゲームの木とはどのようなものか理解できる。
単純なゲームを例に挙げ、ゲームの木をプログラムで探索することができる。
|
| 7週 |
ゲームの木の探索 |
単純なゲームを例に挙げ、ゲームの木をプログラムで探索することができる。
|
| 8週 |
クラスPとNP |
クラスPやクラスNPの意味を理解できる。
NP完全問題、NP困難問題を理解できる。
|
| 2ndQ |
| 9週 |
分枝限定法（ナップザック問題） |
ナップザック問題はどのようなものか理解できる。
分枝限定法とはどのような手法であるかを理解できる。
分枝限定法を用いてナップザック問題を解くことができる。
|
| 10週 |
動的計画法（ナップザック問題） |
動的計画法とはどのようなものか理解できる。
動的計画法を用いてナップザック問題を解くことができる。
|
| 11週 |
巡回セールスマン問題 |
巡回セールスマン問題はどのようなものか理解できる。
巡回セールスマン問題を単純貪欲法、挿入法、局所探索法で解けることを理解できる。
|
| 12週 |
輪講のプレゼンテーション |
アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
|
| 13週 |
輪講のプレゼンテーション |
アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
|
| 14週 |
輪講のプレゼンテーション |
アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
|
| 15週 |
期末試験 |
|
| 16週 |
テスト返却と解説 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 60 | 15 | 0 | 0 | 25 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 60 | 15 | 0 | 0 | 25 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |