アルゴリズム論

科目基礎情報

学校 有明工業高等専門学校 開講年度 平成31年度 (2019年度)
授業科目 アルゴリズム論
科目番号 0030 科目区分 専門 / 選択
授業形態 授業 単位の種別と単位数 学修単位: 2
開設学科 生産情報システム工学専攻 対象学年 専1
開設期 前期 週時間数 1
教科書/教材 アルゴリズムとデータ構造;石畑 清/岩波書店
担当教員 菅沼 明

到達目標

1. アルゴリズムの計算量について説明できる
2. 手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できる
3. 最適化問題の解法として分枝限定法、動的計画法を説明できる
4. 近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できる

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1アルゴリズムの計算量について根拠を示して説明できる。アルゴリズムの計算量について説明できる。アルゴリズムの計算量について説明できない。
評価項目2手間のかかる問題を解く手法として、深さ優先探索・幅優先探索を利用して探索プログラムを作成できる。手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できる。手間のかかる問題を解く手法として、深さ優先探索・幅優先探索の手順を説明できない。
評価項目3最適化問題の解法として分枝限定法、動的計画法を説明でき、ナップザック問題に適用して解を求めることができる。最適化問題の解法として分枝限定法、動的計画法を説明できる。最適化問題の解法として分枝限定法、動的計画法を説明できない。
評価項目4近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明でき、最適化問題の巡回セールスマン問題に適用して解を求めることができる。近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できる。近似アルゴリズムについて、単純貪欲法、挿入法、局所探索法を説明できない。

学科の到達目標項目との関係

学習・教育到達度目標 B-2

教育方法等

概要:
 本授業の目標は、アルゴリズムに関する事柄について理解を深めることである。この目標を達成するために、具体的に次のことを行う。
 エレガントでかつ高速なアルゴリズムが知られていない問題に関して、アルゴリズムの計算量やNP完全問題などの問題の分類について学ぶ。厳密解を求めるのが困難な問題に対しては、妥当な計算時間で近似解を得るための近似アルゴリズムとして、貪欲法や局所探索法などの解法を理解する。最適化問題である巡回セールスマン問題を例にとり、近似アルゴリズムの適用について理解する。
 最後に、各種アルゴリズムに関する英文を読み輪講形式で発表する。適切な発表資料を作成し、理解されやすい発表を目指して準備を行う。
授業の進め方と授業内容・方法:
 講義を中心とし、適宜、講義内容に関する課題を出題する。また、深さ優先探索や幅優先探索で問題を解くプログラムを作成させる。授業時間外に演習を行う時間およびレポート作成時間が必要となる。さらに、アルゴリズムに関する英文を読むための時間、発表準備の時間、発表資料の作成時間が必要となる。
注意点:
 C言語のプログラミングに関する知識を有することが望ましい。

授業計画

授業内容・方法 週ごとの到達目標
前期
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困難問題を理解できる。
9週 分枝限定法(ナップザック問題) ナップザック問題はどのようなものか理解できる。
分枝限定法とはどのような手法であるかを理解できる。
分枝限定法を用いてナップザック問題を解くことができる。
10週 動的計画法(ナップザック問題) 動的計画法とはどのようなものか理解できる。
動的計画法を用いてナップザック問題を解くことができる。
11週 巡回セールスマン問題 巡回セールスマン問題はどのようなものか理解できる。
巡回セールスマン問題を単純貪欲法、挿入法、局所探索法で解けることを理解できる。
12週 輪講のプレゼンテーション アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
13週 輪講のプレゼンテーション アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
14週 輪講のプレゼンテーション アルゴリズムに関して英語で書かれた本を読み、わかりやすく説明できる。
15週 期末試験
16週 テスト返却と解説

評価割合

試験発表相互評価態度ポートフォリオその他合計
総合評価割合601500250100
基礎的能力0000000
専門的能力601500250100
分野横断的能力0000000