アルゴリズム
| exacnt algorithms | ・厳密解法 ・厳密解アルゴリズム |
最適解を1つ求める解法 |
| approximation algorithm | 近似解法 | 求められる解の精度に何らかの保証があるもの |
| heuristicn algorithm | 発見的解法 | 良いと思われる解を探索する解法。解の精度に保証は無い |
Exact Exponential Algorithms http://t.co/Xa3MoyTe の輪講をここのところ学生とやっている．指数時間アルゴリズムは結構素朴なアイデアが多いので学生も読んで理解がしやすく，達成感を感じやすい題材という気がする．
— Taisuke Izumi (@taizumi) 2012, 6月 8Exact Exponential Algorithms
厳密指数時間アルゴリズム
http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-16532-0
Today most computer scientists believe that NP-hard problems cannot be solved by polynomial-time algorithms.
From the polynomial-time perspective, all NP-complete problems are equivalent but their exponential-time properties vary widely .
perspective (…な)考え方，見方 property (ものの)特質，特性 vary widely ばらつきが大きい
- Why do some NP-hard problems appear to be easier than others?
- Are there algorithmic techniques for solving hard problems that are significantly faster than the exhaustive, brute-force methods?
The algorithms that address these questions are known as exact exponential algorithms.
appear to （～に）見える；（～と）思われる significantly かなり，著しく，はっきりと exhaustive 徹底的な，余す所のない brute-force 腕力, [しばしば形容詞的に] 力ずくの《プログラムに工夫を凝らさず, 計算機の処理能力をたのむ》 address 〈問題などを〉扱う，処理する
The history of exact exponential algorithms for NP-hard problems dates back to the 1960s.
The two classical examples are Bellman, Held and Karp’s dynamic programming algorithm for the traveling salesman problem and Ryser’s inclusion–exclusion formula for the permanent of a matrix.
inclusion–exclusion(principle) 包除原理 permanent ｎ次の行列式（determinant）はｎ個の項の積のｎ！個の項に適当な符号をつけた和として表される．符号をつけずに全部＋にして加えた式はpermanentと呼ばれる．訳語はないが，強いて訳せば永久式である． http://www.geocities.jp/ikuro_kotaro/koramu/2042_e1.htm
The design and analysis of exact algorithms leads to a better understanding of hard problems and initiates interesting new combinatorial and algorithmic challenges.
initiate 〈…を〉始める，起こす，創始する
The last decade has witnessed a rapid development of the area, with many new algorithmic techniques discovered. This has transformed exact algorithms into a very active research field.
The last decade この10年間(2000-2010)
This book provides an introduction to the area and explains the most common algorithmic techniques, and the text is supported throughout with exercises and detailed notes for further reading.
The book is intended for advanced students and researchers in computer science, operations research, optimization and combinatorics.
optimization 最適化
巡回セールスマン問題入門 ppt file , (September 2000)
by 松井知己（東京大学）
http://homepage2.nifty.com/TOMOMI/POWER-POINT/
http://www.cs.tsukuba.ac.jp/~takahito/Gcourse/part2.pdf
最悪計算量が問題の入力ビット長の多項式では抑えられないアルゴリズムは指数時間アルゴリズム(exponential-time algorithm)とよぶ．つまり，ナップサック問題(2.1)に対する動的計画法は指数時間アルゴリズムである．
