| ■授業内容と方法 |
|
前半は，グラフ・ネットワーク分野の代表的なアルゴリズムを説明する．これらはネットワーク設計，経路決定等，実世界の問題に適用される．後半は，組合せ最適化のための代表的なアルゴリズムである，分枝限定法，ラグランジュ緩和，動的計画法，およびヒューリスティックス手法について解説する．講義の合間に，課題のプログラムに関する議論を取り入れてる．
|
| ■達成目標 |
○グラフ・ネットワーク分野のアルゴリズムを理解する．またNP完全性，近似解法等の基本概念，及び分枝限定法，動的計画法等のアルゴリズムの基本戦略を理解する（専門性）
○グラフ・ネットワーク分野、または、組合せ最適化のアルゴリズムをプログラムとして実装し実行できる（実践性)
○新たな問題に対するアルゴリズムを設計できる（創造性）
|
| ■評価基準と評価方法 |
|
達成目標に到達したかどうかを課題(20%)，中間試験(40%)，期末試験(40%)によって評価する．専門性は主として試験，実践性は課題，創造性は試験及び課題によって評価する．全ての達成目標に到達したものについて，総合点60%以上のものをD，70%以上をC，80%以上をB，90%以上をAとする．課題の提出がない場合には，実践性が評価できないので筆記試験が満点でも単位は与えない．
|
| ■履修条件 |
|
アルゴリズムとデータ構造，プログラミング1,2
|
| ■授業計画 |
1. グラフ・アルゴリズム・計算量(1)
2. グラフ・アルゴリズム・計算量(2)
3. 線形計画法と双対問題
4. ネットワーク理論(最短路問題)
5. ネットワーク理論(最大流問題)
6. ネットワーク理論(最小費用流問題)
7. 演習
8. 中間試験
9. 分枝限定法
10. ラグランジュ緩和
11. 動的計画法
12. 主・双対法
13. ヒューリスティックス(1)
14. ヒューリスティックス(2)
15. 演習
|
| ■事前・事後学習 |
|
|
| ■教科書 |
ISBN |
|
久保幹雄，組合せ最適化とアルゴリズム，共立出版
|
4320016475 |
|
| ■参考書 |
ISBN |
|
|
| ■備考(メッセージ) |
|
|
| ■オフィスアワー |
|
月曜日の２時限目．ただし在室中は対応可能．事前にメール連絡があると確実．
|
| ■メールアドレス |
morikazu＠ie.u-ryukyu.ac.jp
|
| ■URL |
|
http://www.ie.u-ryukyu.ac.jp/~morikazu/Class/Algorithm2.html
|