tailieunhanh - Lecture Algorithm design - Chapter 8: Intractability I
Lecture Algorithm design - Chapter 8 include all of the following: Poly-time reductions, packing and covering problems, constraint satisfaction problems, sequencing problems, partitioning problems, graph coloring, numerical problems. | Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http wayne kleinberg-tardos 8. Intractability I poly-time reductions packing and covering problems constraint satisfaction problems sequencing problems partitioning problems graph coloring numerical problems Last updated on Sep 8 2013 6 40 AM Section 8. Intractability I poly-time reductions Algorithm design patterns and antipatterns Algorithm design patterns. Greedy. Divide and conquer. Dynamic programming. Duality. Reductions. Local search. Randomization. Algorithm design antipatterns. NP-completeness. O nk algorithm unlikely. PSPACE-completeness. O nk certification algorithm unlikely. Undecidability. No algorithm possible.
đang nạp các trang xem trước