|
授業科目名
|
担当教官
|
|||||
|
アルゴリズムとデータ構造
|
岩沼 宏治
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263610 | 2 | Ｇ | 2 | 前期 | 月 | I |
| ［概要と目標］ | ||||||
| コンピュータを専攻するものにとって、全く自明かつ最も基本的な事実として、 アルゴリズム無くして、コンピュータ無し がある。本講義では、コンピュータ関連項目の中で最も中心的な課題であるアルゴリズムについて「プログラミング I，II，同演習」の後を受けて、より進んだ話題について講義を行う． |
||||||
| ［必要知識・準備］ | ||||||
| プログラミング I, II，計算機アーキテクチャをしっかり復習されたい．またＣ言語の知識とプログラミング技術が必須である． | ||||||
| ［評価基準］ | ||||||
| 評価は、中間筆記試験と期末筆記試験を総合して行う．また講義の進行あわせて適宜レポートを課す． | ||||||
| ［教科書］ | ||||||
| ［参考書］ | ||||||
|
|
||||||
| ［講義項目］ | ||||||
| １． 序論： コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？ ２． ヒープソート： 選択ソートの改良，完全2分木の埋め込みによるヒープの実現 ３． 比較によるソート法の時間計算量の下界（本質的に必要な計算量）とその空間的克服：バケットソート、基底ソート ４． 文字列照合： 素朴なアルゴリズムとBoyer-Moore法 ５． 簡単な最適化問題： 資源配分問題、連続ナップザック問題 ６． グラフの問題：最小全域木，クラスカルのアルゴリズム，プリムのアルゴリズム，最短経路問題，ダイクストラのアルゴリズム ７． 中間試験 ８． 計算不可能性原理、計算量の無限階層、ＮＰ完全問題 ９． 分割統治法： 長大数の乗算、点集合の凸包 １０． 動的計画法： 部分和問題、０−１ナップザック問題 １１． 分岐限定法： ０−１ナップザック問題 １２． 近似解法： 貪欲算法、ランダム法、局所探索法、緩和法 １３． 進んだ話題： 分散アルゴリズム，確率的アルゴリズム １４． 期末試験 |
||||||