tailieunhanh - Lý thuyết Xác suất cơ bản: các tiên đề, có điều kiện xác suất, các biến ngẫu nhiên, phân phối

That’s not good: may goes same path and produces the same bug as in the first. | I . Basic probability axioms conditional probability random variables distributions .. 2010 Van Nguye ịíJ_j_i Probability for CS 1 Application Verifying Polynomial Identities-HiMiHiHi t ht Computers can make mistakes Incorrect programming Hardware failures - sometimes use randomness to check output Example we want to check a program that multiplies together monomials x 1 x-2 x 3 x-4 x 5 x-6 x6-7x3 25 In general check if F x G X One way is Write another program to re-compute the coefficients That s not good may goes same path and produces the same bug as in the first 2010 Van Nguyen Probability for CS 2 How to use randomness Assume the max degree of F G is d. Use this algorithm Pick a uniform random number from 1 2 3 . 100d Check if F r G r then output equivalent otherwise nonequivalent Note this is much faster than the previous way - O d vs. O d2 One-sided error non-equivalent always true equivalent can be wrong How it can be wrong If accidentally picked up a root of F x -G x 0 This can occur with probability at most 1 100 2010 Van Nguyen Probability for CS