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