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

Chia sẻ: Chu Quang Chien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

286
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ông 2. 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 Numberical 3. 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 Monte Gi 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à: ½