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