アルゴリズム

1. 序論 1.1 アルゴリズムの記法 1.2 アルゴリズムの正しさの証明 1.3 アルゴリズムの良さを表す尺度 2. 基本データ構造 2.1 配列 2.2 リスト 2.3 2 重連結リスト 2.4 配列とリストの比較 2.5 スタックとキュー：常にO(1)でアクセス可能な使用法 3. 検索 3.1 線形検索 3.2 二分検索 3.3 二分検索木 3.4 平衡木（Balanced Tree） 3.5 B 木 3.6 ハッシュ法 4. 整列 4.1 O(n2)の整列アルゴリズム 4.2 O(n log n)の整列アルゴリズム 4.3 大小比較に基づかない整列アルゴリズム 4.4 ハードウェアソートアルゴリズム 5. 文字列照合 5.1 単純なアルゴリズム 5.2 Knuth Morris Pratt のアルゴリズム 5.3 正規表現とオートマトン 5.4 Boyer-Moore のアルゴリズム 5.5 系列間のマッチング 6. マッチング 6.1 受入側提案の受入保留アルゴリズム 6.2 マッチングの安定性 6.3 学生側提案の受入保留アルゴリズム 6.4 マッチングの最適性 7. グラフのアルゴリズム 7.1 グラフの探索 7.2 最短経路 7.3 最小木（Minimum Spanning Tree） 7.4 最大流（Maximum Flow） 8. ゲームにおける最善手の選択 8.1 ゲームの木とmini-max原理 8.2 α-β法に基づく枝刈り 9. 難しい問題 9.1 問題の難しさ 9.2 NP問題（Non-deterministic Polynomial） 9.3 多項式時間還元可能とNP完全 9.4 近似解法 ----------------------------- 1. Introduction 1.1 Description of algorithms 1.2 Proof of the correctness of algorithms 1.3 Metrics of the goodness of algorithms 2. Basic data structures 2.1 Array 2.2 List 2.3 Doubly-linked list 2.4 Comparison of arrays and lists 2.5 Stack and queue: O(1) accessible usage 3. Lookup 3.1 Linear lookup 3.2 Binary lookup 3.3 Binary lookup tree 3.4 Balanced Tree 3.5 B-tree 3.6 Hash 4. Sort 4.1 O(n2) sorting algorithms 4.2 O(n log n) sorting algorithms 4.3 Sorting algorithms not based on magnitude comparison 4.4 Hardware sorting algorithms 5. String matching 5.1 Simple algorithm 5.2 Knuth Morris Pratt's algorithm 5.3 Regular expression and automaton 5.4 Boyer-Moore's algorithm 5.5 Sequence matching 6. Stable Matching 6.1 Deferred Acceptance Algorithm 6.2 Stability 6.3 Optimality 7. Graph Algorithms 7.1 Graph Search 7.2 Shortest Path 7.3 Minimum Spanning Tree 7.4 Maximum Flow 8. Best move selection in games 8.1 Game tree and mini-max pronciple 8.2 α-β pruning 9. Intractable problems 9.1 Problem classes 9.2 NP(Non-deterministic Polynomial) problems 9.3 Polynominal time reducibility and NP completeness 9.4 Approxinate solutions

中間レポート1回＋期末試験の予定

視野を広げる