算法高级教程2.4LasVegasalgorithm.pptVIP

* PollardRho(n) never prints an incorrect answer, any number it prints is a nontrivial divisor of n. PollardRho(n) may not print anything at all, though; there is no guarantee that it will produce any results. We shall see, however, that there is good reason to expect PollardRho(n) to print a factor q of n after Θ(q1/2), iterations of the while loop. Thus, if n is composite, we can expect this procedure to discover enough divisors to factor n completely after approximately n1/4 updates, since every prime factor q of n except possibly the largest one is less than n1/2. * We begin our analysis of the behavior of this procedure by studying how long it takes a random sequence modulo n to repeat a value. Since Zn ={1,2,…,n-1} is finite, and since each value xi in the sequence depends only on the previous value xi-1, the sequence eventually repeats itself. Once we reach an xi such that xi = xj for some j i, we are in a cycle, since xi+1 = xj+1, xi+2 = xj+2, and so on. * The reason for the name rho heuristic is that, as the following Figure shows, the sequence x1, x2, ..., xj-1 can be drawn as the tail of the rho, and the cycle xj, xj+1, ..., xi as the body of the rho. * Figure (a) * Figure (b) * Homework Exercises: Page 50 1,2 Experiments: Exercises 4(score 10) Exercises 6 Problem Satisfiability(SAT) Problem Given clauses C1, C2, . . ., Cn in CNF over Boolean variables x1, x2, . . . xm, namely CNF=C1 ∧ C2, ∧ . . ., ∧ Cn each clause Ci : xi1∨ xi2∨. . . ∨ xij∨… ∨ xik while xij is a literal that is xm or ?xm, and the literals in each clause is different. The SAT problem asks whether a given CNF is satisfiable * Possible paper 1）利用回溯算法和Las vegas算法求解0/1背包问题（10分） 2）利用单纯性算法求解0/1背包问题的解，再对解取整，确定部分物品，然后再利用回溯算法来求解（可写论文） * Las Vegas Algorithms * Summary Introduction n Queens Problems Factorizing Large Integers * A Las Vegas algorithm is a type of randomized algorithm that uses a random value to make randomized choices and never produces an incorrect answer.