| 授業の目標と概要 |
多様化，複雑化する問題に対して，効率的な計算手法である様々なアルゴリズムが考案されている．
本科目の目標を以下に示す．
・基本的な計算量の概念とアルゴリズムの評価法を習得する．
・離散最適化問題クラスについての知識を習得する．
・スケージュリングアルゴリズム，最適化アルゴリズム，意思決定アルゴリズムなどの発展型アルゴリズムを用いての離散最適化問題の問題解決力を習得する．
・並列計算機モデルの概念と並列アルゴリズムの構築法を習得する．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・基本的な逐次計算機アーキティクチャの原理，OSの知識を必須とする．
・初等的な離散数学の知識を要する．
・グラフ理論の知識があればなおよい．
・関数機能付き電卓を必要とする．
|
| 到達目標 |
・逐次，並列アルゴリムズの解析と評価を行える．
・NP完全問題について問題の困難さ，帰着の概念を理解できる．
・離散最適化問題の解決アプローチを理解し，アルゴリズムを利用して最適解を導出できる．
・並列計算機モデルの概念を理解し，並列アルゴリズムを構築法を構築できる．
|
| 成績評価方法 |
最終評価：定期試験の評価とする．
合否判定：最終評価（または，再試験の素点）≧60％を合格とする．
|
| テキスト・参考書 |
参考書：並列分散処理入門 渋沢進 培風館
参考書：分散アルゴリズム 亀田恒彦 近代科学社
参考書：アルゴリズムとデータ構造 平田富夫 森北出版
自習用：アルゴリズム論 浅野哲夫 オーム社
|
| メッセージ |
グラフ理論の知識があればなおよい．
講義はプロジェクターを用いて行う．
|
| 授業の内容 |
授業項目 | 授業項目ごとの達成目標 |
1. 代表的な逐次アルゴリズム(2)
2. 逐次アルゴリズムの計算量解析(4)
3. 問題のクラスPとNP(2)
4. 最適スケジューリングアルゴリズム(6)
|
1. 代表的な逐次アルゴリズムの原理が理解できる．
2. オーダ記号によるアルゴリズム評価法,計算量解析ができる．
3. 問題のクラスと帰着について理解できる．
4. スケジューリングアルゴリズムについて理解・応用できる．
|
| 後期中間試験 |
実施しない
|
5. 離散最適化アルゴリズム・最大化問題(4)
6. 離散最適化アルゴリズム・最小化問題(4)
7. 意志決定アルゴリズム(4)
8. 並列アルゴリズム(4)
|
5. 離散最適化アルゴリズム（最大化問題）について理解・応用できる．
6. 離散最適化アルゴリズム（最小化問題）について理解・応用できる．
7. 意志決定アルゴリズムについて理解・応用できる．
8. 並列アルゴリズムを設計，評価できる．
|
| 後期期末試験 |
実施する
|