Đến nội dung

Hình ảnh

Thuật toán xác suất

- - - - -

  • Please log in to reply
Chủ đề này có 5 trả lời

#1
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Vai trò của thuật toán xác suất.

Đây là bài viết phụ trợ nhanh cho chủ đề ìVấn đề trong tuần”. Các vấn đề đề cập dưới dạng phi hình thức để bạn đọc, nếu chưa quen, (hy vọng tất cả đã quen :delta ) có thể nắm cơ bản vấn đề để thuận lợi hơn cho việc thảo luận "vấn đề trong tuần":
http://www.diendanto...=20

Trong nhiều vấn đề, việc sử dụng các thuật toán đơn định thương gặp bế tắc trong khi đó chỉ cần sử dụng một thuật toán xác suất giản đơn là có thể giải quyết vấn đề : Điều đó có thể hiểu rằng lớp các bài toán giải được bằng máy Turing đơn định với nguồn lực rất lớn có thể không trùm lên lớp các bài toán giải được bằng máy Turing xác suất trong thời gian đa thức. Chính xác thì phải xem xét từng loại máy cụ thể (máy có tương tác hay không), nguồn lực cụ thể,.... Ở đây chúng ta chỉ xem xét vấn đề theo cách "phảng phất" mà thôi :leq

Nói nôm na, máy Turing xác suất có thêm một băng xác suất để thực hiện việc ìtung đồng xu” : phụ thuộc vào kết quả tung xu mà máy sẽ thực hiện kiểu này hay kiểu khác. Kết luận của máy xác suất cũng thường là có độ sai epsilon : kết luận là đúng với khả năng sai là epsilon.

Để thấy sự khác biệt giữa thuật toán xác suất và thuật toán đơn định, ta xét trò chơi sau giữa Badman và cậu con Goodboy (thuật toán xác suất sẽ trình bày dưới đây là một kiểu thuật toán tương tác (iteractive) vì có sự tham gia tương tác của 2 đối tượng) :

Trò chơi:
Badman có 3 hộp, Goodboy có chìa khóa để mở 2 hộp. Vấn đề đặt ra là làm thế nào để Badman có thể biết dù chỉ 1 hộp mà Goodboy có chìa khóa.
Luật chơi giữa hai bố con như sau :

Mỗi lần Badman để vào mỗi hộp 1 số. Goodboy sẽ nhận được 2 số (gọi là a và b) trong 3 hộp mà cậu ta có chìa khóa. Goodboy sẽ phải trả lời cho bố chú theo luật sau :
- Neu a=b thì cậu ta phải trả lời là a.
- Neu a<>b thi cậu ta có thể trả lời là a hoăc b hoăc * ( * có thể là bất kể điều gì như là "bố cuar con là Bad man" :leq ),

Giả thiết là Badman sẽ cho cậu con biết thuật toán mình sẽ sử dụng để hỏi cậu con, còn cậu con thì nhất định muốn giấu bố, không cho bố biết dù chỉ 1 trong 2 chiếc chìa khóa mình có được.

Nếu Badman sử dụng thuật toán đơn định (dù cho có thời gian hỏi vô hạn) thì đành bó tay trước cậu con :
- Nếu Badman để vào 3 hộp các giá trị giống nhau (a,a,a) thì cậu con chắc chắn sẽ trả lời M và tất nhiên đây là một câu hỏi vô nghĩa.
- Nếu Badman để vào 3 hộp các giá trị (a,a,b) (a<>b) thì cậu con có thể trả lời a (vì cậu có thể nhìn được ít nhất 1 hộp có giá trị a) và đây là một câu hỏi vô tác dụng với Badman vì anh ta chẳng thu được thông tin gì : cậu con có chìa khóa của ít nhất 1 trong ai hộp đầu tiên nhưng mình chả cần hỏi vậy cũng biết vì cậu ta có 2 chìa khóa cơ mà !
- Nếu Badman để vào 3 hộp các giá trị khác nhau (a,b,c) thì cậu con có thể trả lời *. Badman lắc đầu, nó có chìa khóa 2 hộp và sẽ nhận giá trị khác nhau nên nó có quyền trả lời như vậy.

Nhưng giờ đây ông bố Badman tuyên bố với cậu con : bố sẽ chơi thuật toán xúc sắc với con, bố sẽ sử dụng con xúc sắc để quyết định câu hỏi chứ bố không tự quyết định theo một qui tắc nhất định như trước nữa.

Cụ thể, đầu tiên bố chọn hai giá trị a, b đặt vào hai hộp đầu tiên. Sau đó bố tung xúc sắc, nếu giá trị là 1, bố sẽ hỏi con (a,b,a), nếu là 2 bố sẽ hỏi (a,b,b), nếu là 3 bố sẽ hỏi (a,b,c). Điều duy nhất bố giấu con (vì chính bố cũng không biết trước) là giá trị của con xúc sắc bố sẽ tung. (trong máy Turing, điều kiện quan trọng là không ai biết được giá trị của băng ngẫu nhiên. Tất nhiên, nếu ta xác định được nó thì đã trở thành máy đơn định rồi).

Giả sử cậu có chìa khóa 2 hộp đầu và nhận giá trị câu hỏi là (a,b,b). Vì ông bố chơi trò xác suất nên cậu sẽ không thể biết là hộp thứ 3 có giá trị a hay b hay c cả. Cậu suy luận :
o Giả sử hộp thứ 3 có giá trị c (tức câu hỏi là (a,b,c)) thì nhất định cậu phải trả lời là *, vì nếu trả lời là a hay b hay c thì đồng nghĩa với việc cậu ta có chìa khóa hộp đấy.
o Giả sử hộp thứ 3 có giá trị a (tức câu hỏi là (a,b,a)) thì nhất định cậu phải trả lời là a, vì nếu trả lời là b hoặc * thì đều chứng tỏ cậu có chìa khóa hộp 2 rồi còn gì.
o Giả sử hộp thứ 3 có giá trị b (tức câu hỏi là (a,b,b)) thì nhất định cậu phải trả lời là b, vì nếu trả lời là a hoặc * thì đều chứng tỏ cậu có chìa khóa hộp 2 rồi còn gì.
Vì cậu biết rằng xác suất 3 trường hợp trên là ngang nhau nên cậu cũng trả lời bừa hoặc a hoặc b hoặc * mà thôi. Nhưng vì ông bố đặt câu hỏi là (a,b,b) nêu nếu cậu trả lời là a hoặc * thì Badman đều có thể kết luận là cậu con có chìa khóa hộp thứ nhất. Xác suất để Badman đưa ra kết luận này là 2/3 và kết luận luôn đúng 100%. Nếu cậu con trả lời là b (xác suất 1/3) thì Badman kể như không biết được thông tin gì và lại chơi tiếp.

Bằng quá trình xem xét kỹ lưỡng và chính xác hơn (coi như bài tập đơn giản), ta có thể thấy rằng Badman có thể tuyên bố với cậu con rằng mình sẽ chọn ngẫu nhiêu 1 trong 4 câu hỏi sau đây để hỏi :
1. (a,a,b)
2. (a,b,a)
3. (a,b,b)
4. (a,b,c)

Và dù cậu con có chơi kiểu gì thì sau 1 câu xác suất ông bố « thắng cuộc » cũng sẽ là 2/3. Và như vậy, sau n câu hỏi Badman sẽ chiến thắng với xác suất sai epsilon = (1/3)^n.

Như vậy, sau n bước Badman sẽ đưa ra câu trả lời với xác suất 1-epsilon và một khi đã trả lời thì câu trả lời là chính xác 100%. Kiểu thuật toán xác suất này được gọi là kiểu Las Vegas

Loại thuật tóan khi kết thức luôn đưa ra câu trả lời nhưng xác suất sai lài epsilon được gọi là thuật toán kiểu Monte Carlo.

(các tên gọi toàn là những trung tâm của các sòng bạc lớn nhất thế giới :leq )

Câu hỏi : Xét trường hợp tổng quát khi có Badman có n hộp và Goodboy có chìa khóa k hộp. Câu hỏi là tìm thuật toán xác suất để Badman có thể phát hiện 1 hộp mà cậu con có chìa khóa.

Câu hỏi tưởng như đơn giản này nhưng mà RC nghĩ mãi chưa ra.

Bài viết đã được chỉnh sửa nội dung bởi RongChoi: 20-04-2005 - 21:17


#2
salida

salida

    Binh nhất

  • Thành viên
  • 34 Bài viết
Hay quá, lần đầu tiên em được nghe cái này.
À, nhưng mà cho em hỏi điều kiện ràng buộc của thuật tóan này là gì vậy ạ?

#3
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

Hay quá, lần đầu tiên em được nghe cái này.
À, nhưng mà cho em hỏi điều kiện ràng buộc của thuật tóan này là gì vậy ạ?

Anh không hiểu ý của Salida lắm, điều kiện mà Salida nói ở đây là gì nhỉ ?
Có phải là kiểu như sau không nhé :
- Với mọi epsilon, tồn tại một thuật toán xác suất trong thời gian đa thức để với xác suất 1-epsilon, Badman có thể đoán được chính xác 1 trong các hộp mà Goodman có chìa khóa. (kiểu thuật toán Las Vegas).
- Với mọi epsilon, tồn tại một thuật toán xác suất trong thời gian đa thức để với xác suất Badman có thể đoán được 1 trong các hộp mà Goodman có chìa khóa với xác suất chính xác là 1-epsilon. (kiểu thuật toán Monte Carlo).
Cheers,
RC

#4
madness

madness

    Trung sĩ

  • Thành viên
  • 137 Bài viết
Ko biết có phải anh đang nói về randomized algorithm ko nhỉ? Trong bài viết ở http://www.cse.buffa...mese/cantor.pdf (cuối trang 13), giáo sư Ngô Quang Hưng dịch là "giải thuật ngẫu nhiên hóa", có lẽ dịch thế này chính xác hơn là "thuật toán xác suất". Nhưng từ "thuật toán xác suất" lại nói lên tính chất của cách tiếp cận vấn đề này hơn, nhất là khi dùng xác suất để đánh giá độ hiệu quả về thời gian cũng như giá trị kỳ vọng mà thuật toán đem lại :Rightarrow

#5
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

Ko biết có phải anh đang nói về randomized algorithm ko nhỉ? Trong bài viết ở http://www.cse.buffa...mese/cantor.pdf (cuối trang 13), giáo sư Ngô Quang Hưng dịch là "giải thuật ngẫu nhiên hóa", có lẽ dịch thế này chính xác hơn là "thuật toán xác suất". Nhưng từ "thuật toán xác suất" lại nói lên tính chất của cách tiếp cận vấn đề này hơn, nhất là khi dùng xác suất để đánh giá độ hiệu quả về thời gian cũng như giá trị kỳ vọng mà thuật toán đem lại :Rightarrow

madness nói ý "một từ chỉ nguyên tắc hoạt động, một từ chỉ phương pháp phân tích" hay phết nhỉ :phi Ko biết có phải vì thế mà sách tây vẫn thường dùng cả hai từ randomized algorithm và probabilistic algorithm?

#6
madness

madness

    Trung sĩ

  • Thành viên
  • 137 Bài viết
mad cũng mới nghe từ probabilistic algorithm, lâu nay chỉ nghe randomized à

Nếu vậy thì có lẽ dùng randomized algorithm và probabilistic analysis (thuật toán ngẫu nhiên hóa và phân tích xác suất) là chính xác hơn cả, vì algorithm nhằm chỉ quá trình hay thủ tục để giải quyết vấn đề, trong quá trình đó ng` ta có dùng phương pháp chọn ngẫu nhiên, chỉ đến khi phân tích thuật toán thì xác suất mới xuất hiện như nhân vật quan trọng nhất :phi

For fun: sau khi googling với key word là "randomized algorithm" cho kết quả với số trang là 40,000 - gấp đôi so với "probabilistic algorithm". Cụm từ đầu được dùng rộng rãi trong các khóa học, cụm từ sau thấy ít xuất hiện trong các khóa, mà thường xuất hiện trong các bài báo --> các bác Tây thích dùng randomized algorithm hơn :Rightarrow

Ng` ta thì đi tìm và phân tích thuật toán, mình lại đi nói chuyện về vấn đề dịch từ :phi

Bài viết đã được chỉnh sửa nội dung bởi madness: 21-04-2005 - 00:23





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh