- 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.[r]
(1)C
CÁÁC THUC THUẬẬT TOT TOÁÁN N
X
XÁÁC C SUSUẤẤTT
(PROBABILISTIC)
(2)Numberical probabilistic algorithms
Numberical probabilistic algorithms
Giới thiệu:
- Thuật toán xác suất số dùng để tính tốn kết gần vấn đề toán học (Kết gần xác với kết thực tế)
1 Buffon’s Needle:
- Gạch đường thẳng có khoảng cách D bảng
- Có 355 que tăm có chiều dài L=1/2 D
(3)Numberical probabilistic algorithms
Numberical probabilistic algorithms
Giải quyết toán:
- Số que rơi vào đường thẳng 0355
- Giả sử que rơi vng góc với đường thẳng: có ½ khả que rơi vào đường thẳng
- Nếu que rơi song song với đường thẳng xác suất rơi ngồi nhỏ
Mỗi que có 1/pi khả để rơi vào đường thẳng
(4)Numberical probabilistic algorithms
Numberical probabilistic algorithms
Kết luận:
- Từ tốn Buffon’s needle dùng để tính pi = n/k ( n- số que ném ban đầu, k – số que rơi vào đường thẳng)
Cách giải quyết khác:
- Cho hình vng có cạnh 2R chứa hình trịn có bán kính R
(5)Numberical probabilistic algorithms
Numberical probabilistic algorithms
Diện tích hình trịn: ST=pi*R2
Diện tích hình vng: SV=(2R)2
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 ném)
Từ kỹ thuật ứng dụng để tính diện tích hình khơng quy tắc:
- Cho hình A, hình vng bao trùm ngồi hình A
(6)Numberical probabilistic algorithms
Numberical probabilistic algorithms
Tính tỉ lệ: T = phi tiêu rơi vào A / tổng phi tiêu ném
T = Diện tích A/Diện tích hình vuông
2 Monte Carlo Intergration:
- Cho hàm f liên tục vùng đường cong f tích phân hàm
(7)Numberical probabilistic algorithms
Numberical probabilistic algorithms
- Tuy nhiên có hàm khó khơng thể lấy tích phân
Cần sử dụng đến kỹ thuật Monte Carlo: - Cho hàm y=f(x)
- Vẽ hình vng 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 hình vng, đếm phi tiêu rơi vào đường cong Diện tích đường cong xấp xỉ = Số phi tiêu