chuyên đề quy hoạch động trong bài toán xác suất ôn thi hsa – tsa

Tài liệu gồm 40 trang, được biên soạn bởi nhóm tác giả Team CERAL, hướng dẫn sử dụng phương pháp quy hoạch động trong bài toán xác suất. Tài liệu dành cho học sinh lớp 11 – 12 ôn thi Đánh giá năng lực (HSA – Đại học Quốc gia Hà Nội) và Đánh giá tư duy (TSA – Đại học Bách khoa Hà Nội).

MỤC LỤC:

I. ĐẶT VẤN ĐỀ 4.

1. Một ván cờ bỏ dở năm 1654 4.

2. Từ Huygens, Markov đến Bellman 4.

3. Vì sao chuyên đề này cần cho HSA và TSA? 5.

4. Cấu trúc tài liệu và cách sử dụng 6.

II. CƠ SỞ LÍ THUYẾT 7.

1. Công thức xác suất toàn phần – “động cơ” của mọi hệ thức 7.

2. Hai đặc trưng của một bài toán quy hoạch động 7.

3. Hai cách “cắt” bài toán 8.

4. Hai cách tính: top-down và bottom-up 8.

5. Quy trình bốn bước 8.

6. Từ đếm đến xác suất – kĩ thuật “đếm có trọng số” 9.

7. Nhận diện dạng bài 9.

III. KHỞI ĐỘNG: QUY HOẠCH ĐỘNG TRONG BÀI TOÁN ĐẾM 10.

1. Bài toán leo cầu thang 10.

2. Đường đi trên lưới ô vuông 11.

3. Lưới có điểm cấm 12.

4. Quân hậu trên bàn cờ 12.

5. Đổi tiền và bài toán “giỏ hàng” 13.

6. Bài toán kiểm phiếu (Bertrand, 1887) 13.

IV. CÁC DẠNG TOÁN XÁC SUẤT VÀ VÍ DỤ MINH HOẠ 14.

Dạng 1. Quy hoạch động hai chiều – bài toán chia tiền cược 14.

Dạng 2. Quy hoạch động một chiều theo số bước 16.

Dạng 3. Dãy kết quả có ràng buộc “không liên tiếp” 17.

Dạng 4. Xác suất hấp thụ – bài toán người chơi phá sản 18.

Dạng 5. Quy hoạch động cho kì vọng 19.

Dạng 6. Phân phối của tổng – quy hoạch động “tích chập” 20.

Dạng 7. Tính chẵn – lẻ 21.

Dạng 8. Xích Markov theo thời gian – bảng phân phối 21.

Dạng 9. Đếm có trọng số – lưới thời gian × trạng thái 23.

Dạng 10. Rút không hoàn lại – trạng thái phải “nhớ” những gì đã mất 24.

Tổng kết các mẫu hệ thức 25.

V. ỨNG DỤNG THỰC TẾ 26.

VI. BÀI TẬP LUYỆN TẬP THEO ĐỊNH DẠNG HSA – TSA 31.

A. Câu hỏi trắc nghiệm 4 lựa chọn 31.

B. Câu hỏi điền đáp án 33.

C. Câu hỏi Đúng/Sai 34.

VII. ĐÁP ÁN VÀ HƯỚNG DẪN GIẢI 36.

Bảng đáp án 36.

Hướng dẫn giải 36.

VIII. KẾT LUẬN VÀ LỜI KHUYÊN KHI LÀM BÀI 38.

IX. TÀI LIỆU THAM KHẢO 39.