Chủ đề này có 12 trả lời

[namdung]

Trong 367 người bất kỳ thì có ít nhất 2 người có cùng ngày sinh!

Quá đúng, đó là nguyên lý Dirichlet.

Nhưng điều đó đối với dân Toán không có gì là ấn tượng.

Sẽ thật ấn tượng nếu bạn vào một lớp họic khoảng 40-50 học sinh và nói rằng: Trong lớp chúng ta có ít nhất có 2 người có cùng ngày sinh.

Cũng có lúc bạn sai nhưng khả năng bạn đúng là rất cao.

Nghe chừng vô lý nhỉ. Bạn cứ thử tính toán xem xác suất bạn đúng là bao nhiêu (lấy số học sinh bằng 45).

Sau đó chúng ta sẽ tiếp tục với phương pháp Pollard-Rho.

[gadget]

ngày trước em có đọc một nghịch lí trên báo toán học và tuổi trẻ là tại một lễ hội hóa trang có n cặp vợ chồng(n khá lớn),tất nhiên khôgn ai nhận ra nhau;mỗi chàng trai tán tỉnh một gái duy nhất;anh chồng nào cũng chắc mẩm rằng xác suất tán đúng vợ mình là rất thấp nên rất yên tâm;nhưng không ai biết rằng xác suất để có 1 anmh chồng tán tỉnh đúng vợ mình là 1/3
khôgn biết nó có liên quan tới cái mà thầy sắp nói tới không

[iamaguest]

Cau hoi cua bac Namdung rat hay!
Toi thi khong biet gi ve xac suat, tuy nhien toi cho rang khong nen qua cau toan qua. Trong cuoc song va lam toan hay cai gi cung the: Chi can yeu cau voi mot do tin cay nao do thoi. Chang han, khi ta khang dinh trong lop (50 hs) co 2 nguoi cung ngay sinh. Khi do coi nhu viec sinh no cua con nguoi la do tao hoa la chinh, khong chui su chi phoi cua con nguoi (y toi la khong co su chon loc ngay sinh) thi co the coi cac ngay sinh co xac suat nhu nhau. Thi cau tra loi cung dang tin cay roi.
Do vay, xu huong cua cac nha thiet ke cung nhu xay dung chuong trinh, thuat toan cho mot bai toan la: inexact.
Khong biet biet bac namdung co can cau tra loi cho bai toan bac dat ra khong nhi?

[Đông Tà]

Xác suất là 0.941

[gadget]

wrong
edit:mình trêu bạn tí thôi;thực ra bạn nên để ở dạng phân số cho chính xác(kết quả của bạn là làm tròn)

Bài viết đã được chỉnh sửa nội dung bởi gadget: 03-06-2006 - 13:01

[namdung]

Ừ, xác suất đúng có lẽ cao hơn. Mọi người tính kỹ lại xem sao nhé.

Về ý kiến của iamagues, tôi đồng ý là trong cuộc sống, người ta ra quyết định bằng xác suất rất nhiều. Nếu đòi hỏi cái gì cũng chính xác tuyệt đối thì chẳng làm được cái gì. Thuật toán mà tôi muốn trình bày tiếp theo chính là thuật toán xác suất để tìm ước số của một hợp số cho trước.

Ngoài ra, có những thuật toán xác suất để kiểm tra số nguyên tố, các phương pháp kiểm tra xác suất, thống kê xác suất rất thú vị. Trên mạng này có ai rành về vụ này chia sẻ cùng anh em nhé. Mình là dân đại số nên cũng không rành lắm.

[namdung]

ngày trước em có đọc một nghịch lí trên báo toán học và tuổi trẻ là tại một lễ hội hóa trang có n cặp vợ chồng(n khá lớn),tất nhiên khôgn ai nhận ra nhau;mỗi chàng trai tán tỉnh một gái duy nhất;anh chồng nào cũng chắc mẩm rằng xác suất tán đúng vợ mình là rất thấp nên rất yên tâm;nhưng không ai biết rằng xác suất để có 1 anmh chồng tán tỉnh đúng vợ mình là 1/3
khôgn biết nó có liên quan tới cái mà thầy sắp nói tới không

Cái bài của gaget lại dùng đến nguyên lý thêm bớt chứ không phải là thuật toán xác suất như ở đây. Đáp số hình như là 1 - 1/e (với n lớn). Nói chung là khá lớn.

[Đông Tà]

Thế đáp số của anh bạn gadget là bao nhiêu và reasoning như thế nào

[VŨ Thanh Tùng]

Hình như đáp số là thì phải, không biết tính ra số là bao nhiêu.
Hình như có 1 thuật toán cho biết 1 số là nguyên tố đúng với xác suất 3/4, làm K lần thì cho xác xuất đúng là 1-(1/4)^K, nó thuộc lớp thuật toán Monte-Carlo

Bài viết đã được chỉnh sửa nội dung bởi VŨ Thanh Tùng: 30-05-2006 - 19:35

[namdung]

Thực ra chắc các bạn đều làm đúng cả, chỉ sai khác nhau 1 chút thôi. Tôi nghĩ đáp số chính xác là

1 - (365/365)*(364/365)*....(321/365) ~ 0.9409

Như vậy gaget tính đúng rồi đấy.

[Buffon]

Thế cuối cùng pp Pollard-Rho là thế nào í nhỉ, tò mò quá .

[namdung]

Phương pháp Pollard Rho là phương pháp để tìm ước số của một số nguyên dương n bằng phương pháp xác suất.

Ý tưởng chính của phương pháp này nằm ở mệnh đề sau:

Trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?1.177\sqrt{p} số được sinh ngẫu nhiên thì xác suất để có hai số cùng đồng dư mod p là 0.5

Để tìm ước số của n, ta cho phát sinh các số ngẫu nhiên x1, x2, ..., xk, đồng thời tính (xi-xj, n) = p đến khi nào 1 < p < n thì dừng lại.

Bạn có thể tham khảo ở đây để biết thêm chi tiết và cài đặt thử các thuật toán bằng ngôn ngữ mà bạn biết.

Pollard's Rho algorithm

[sunmoon]

Chào các bạn ở diễn đàn toán học, mình mới tham gia nhưng thay dien dan nay hay lam. Minh nghi neu phat bieu rang mot lop co 50 hoc sinh thi co it nhat 2 hoc sinh cung ngay sinh. vay co dung k? cac ban dung toan xac suat tinh thi co ve dung nhung tren thuc te lai khong dung.
neu cac ban dung cac thong ke de xem co bao nhieu lop cua tat ca cac truong trong thanh pho co duoc nhu vay, co nghia la trong 50 hoc sinh deu khong trung ngay sinh nhau.that la kho day.vi de gi xay ra duoc nhu vay, nao la van de tinh canh cac ban, cac ban gioi thi duoc vao mot lop, cac ban ca nha gan truong thi chon cho minh truong gan nha. vay do, de xay ra truong hop khong dung hang thi rat rat la kho, vay cai do sao tinh duoc bang xac suat.do vay ta phai dung thong ke.
du sao thuc te luon phu phang, theo minh nghi la vay.