| 授業の目標と概要 |
・多様化，複雑化する問題に対して，効率的な計算手法である様々な
アルゴリズムが考案されている．本科目では，基本的な計算量の概念
から，再帰アルゴリズム，確率的アルゴリズム，遺伝的アルゴリズ
ム，並列アルゴリズムなどの発展型アルゴリズムの構築法とそれらの
評価についての知識の習得を目的とする．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・基本的な逐次計算機アーキティクチャの原理，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. 並列アルゴリズムを設計，評価できる．
|
| 後期期末試験 |
実施する
|