CÁC THUẬT TOÁN XÁC SUẤT (PROBABILISTIC)

Tham khảo tài liệu các thuật toán xác suất (probabilistic), công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
CÁC THUẬT TOÁN XÁC SUẤT (PROBABILISTIC) CÁC THU T TOÁN TO XÁC SU T SU (PROBABILISTIC) Numberical probabilistic algorithms Numberical Gi i thi u: - Thu t toán xác su t v s dùng tính toán 1 k t qu g n úng c a v n toán h c (K t qu g n chính xác nh t v i k t qu th c t ).1. Buffon’s Needle: - G ch nh ng ư ng th ng có kho ng cách D u nhau trên b ng - Có 355 que tăm có chi u dài L=1/2 D. - Tung nh ng que này lên b ng, thì bao nhiêu que s rơi vào gi a 2 ư ng th ng? Numberical probabilistic algorithms Numberical Gi i quy t bài toán:- S que s rơi vào gi a 2 ư ng th ng 0 355- Gi s que rơi vuông góc v i ư ng th ng: s có ½ kh năng que rơi vào gi a 2 ư ng th ng- N u que rơi song song v i ư ng th ng thì xác su t rơi ra ngoài là r t nh M i que có 1/pi kh năng rơi vào 2 ư ng th ng- Bài toán Buffon’s Needle tính ra ư c là 113 que (355/pi) s rơi vào gi a 2 ư ng th ng Numberical probabilistic algorithms Numberical K t lu n :- T bài toán Buffon’s needle có th ư c dùng tính pi = n/k ( n- s que ném ban u, k – s que rơi vào gi a 2 ư ng th ng) Cách gi i quy t khác:- Cho 1 hình vuông có c nh là 2R ch a 1 hình tròn có bán kính là R.- Ném phi tiêu ng u nhiên vào trong hình vuông. m xem có bao nhiêu phi tiêu rơi vào hình tròn Numberical probabilistic algorithms Numberical ST=pi*R2 Di n tích hình tròn: SV=(2R)2 Di n tích hình vuông: T l : ST/SV = pi/4 Hay nói cách khác: pi = 4*c/s (c- s phi tiêu rơi vào hình tròn, s- s phi tiêu ư c ném) T k thu t này có th ư c ng d ng tính di n tích nh ng hình không quy t c:- Cho 1 hình b t kì A, và 1 hình vuông bao trùm ngoài hình A.- Ném ng u nhiên phi tiêu vào hình vuông Numberical probabilistic algorithms Numberical Tính t l : T = phi tiêu rơi vào A / t ng phi tiêu ư c ném. T = Di n tích A/Di n tích hình vuông2. Monte Carlo Intergration: - Cho 1 hàm f liên t c vùng dư i ư ng cong c a f chính là tích phân c a hàm (Tích phân xem như di n tích S dư i ư ng cong y =f(x) v i x ch y t a b) Numberical probabilistic algorithms Numberical- Tuy nhiên có nh ng hàm r t khó ho c không th l y tích phân C n s d ng n k thu t Monte Carlo:- Cho 1 hàm y=f(x) b t kì- V 1 hình vuông bao b c o n f(x) c n tính tích phân- Ném ng u nhiên phi tiêu vào trong hình vuông, và m bao nhiêu phi tiêu rơi vào dư i ư ng cong Di n tích dư i ư ng cong x p x = S phi tiêu dư i ư ng cong/s phi tiêu ném Numberical probabilistic algorithms Numberical Gi i thu t:float Integrate (f, n ) // n- s phi tiêu ư c ném{ int hits=0; for (int i =1;i Numberical probabilistic algorithms Numberical3. Probabilistic Counting: - t cư c: Ch n ng u nhiên ít nh t 2 ngư i trong 25 ngư i, sao cho 2 ngư i này có cùng sinh nh t. - Có N!/(N-k)! Cách ch n k khác nhau t t p N có th t - Có Nk cách khác nhau ch n k n u có s l p l i Cơ h i th ng cư c: 1- 365!/(340!*36525) = 56,9% Th c t cơ h i chi n th ng có th cao hơn, vì ngày sinh nh t này không tính n năm Monte Carlo Algorithms MonteGi i thi u:- Thu t toán Monte Carlo s tr v 1 k t qu , và tính chính xác c a k t qu s tăng d n theo nh ng l n ch y c a thu t toán.- Th nh tho ng thu t toán này cũng ưa ra k t qu sai.- Thu t toán Monte Carlo tr v k t qu p có chính xác là: ½