| 科目名 |
アルゴリズム論 |
| 担当教員 |
坂本 明雄 |
| 対象学年 |
1年,2年 |
クラス |
院：専門001 |
| 講義室 |
Ａ１０６ |
開講学期 |
２学期 |
| 曜日・時限 |
月２,木２ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
【 授業の目的 】
アルゴリズムとは，ひとことで言えば問題の解き方のことであり，「算法」と和訳されることもある。この授業の目的は，アルゴリズムに関するいくつかのトピックスを紹介しながら，計算量の概念を理解し，最終的には問題の難しさを表現する“ＮＰ-困難”あるいは“ＮＰ-完全”という考え方を理解することである。
【 授業の進め方 】
数回は講義形式で行うが，各所でいくつかの研究課題を出す。受講生は，いくつかの課題を選んでレポートを提出する。課題発表では，ディスカッションの時間を十分とる。
【 達成目標 】
問題，個別問題，アルゴリズム，時間計算量といった基礎概念を理解し，説明できること
判定問題や最適化問題といった問題のクラス分けの概念を理解し，説明できること
問題の難しさに関するクラス分けである，クラスＰとクラスＮＰの概念を理解し，説明できること
ＮＰ-困難およびＮＰ-完全の概念を理解し，説明できること
|
| 授業の詳細2 |
【 授業計画 】
１・２．アルゴリズムとは何か
アルゴリズムとは何かを考えるには，まず“問題”とは何かを定めなければならない。ここでは，アルゴリズムについて議論していく上で必要な基礎概念を具体例を交えて解説する。
３・４．ユークリッドのアルゴリズム
二つの正整数の最大公約数を求めるユークリッドのアルゴリズムを題材に，アルゴリズムの時間計算量について考える。
５．課題発表
これまでの授業で課された研究課題についての発表会を行い，その内容に関してディスカッションする。
６・７．多項式時間アルゴリズム
時間計算量が問題のサイズの多項式で表現できるアルゴリズムについて，具体例を示しながら解説する。
８・９．判定問題と最適化問題
条件を満たすかどうかをyesまたはnoで答える判定問題と，条件を満たす解集合の中で最適なものを見つける最適化問題について解説する。
10．課題発表
これまでの授業で課された研究課題についての発表会を行い，その内容に関してディスカッションする。
11．クラスＰとクラスＮＰ
問題の二つのクラス，ＰとＮＰについて解説する。クラスＰに属する問題は“易しい”問題である。
12・13．ＮＰ-完全問題
クラスＮＰに属する問題の中でも最も“難しい”問題が“ＮＰ-完全問題”である。これに関連した話題として「Ｐ≠ＮＰ予想」や，メタヒューリスティックなどについても解説する。
14・15．課題発表
これまでの授業で課された研究課題についての発表会を行い，その内容に関してディスカッションする。
|
| 授業の詳細3 |
【 成績評価 】
提出された研究課題のレポート，課題発表時のディスカッション，最終課題レポートを総合的に判断して成績を次のように評価する。ただし，上記３項目中のいずれかで“不可”との評価になった場合，成績評価は“Ｆ(不合格)”とする。
◆AA：上記３項目のすべてで“優秀”との評価が得られた場合
◆Ａ：上記３項目中２項目で“優秀”との評価が得られた場合
◆Ｂ：上記３項目のいずれかで“優秀”との評価が得られた場合
◆Ｃ：上記３項目のすべてで“可”との評価が得られた場合
◇ テキスト
授業で補助テキストを配布する。参考文献についても授業中に示す。
|
| 授業の詳細4 |
|
| 授業の詳細5 |
|
| 授業の詳細6 |
|
| 授業の詳細7 |
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|