Luận văn Chứng minh Định lýWeierstrass theo Phương pháp Xác suất

Phương pháp xác suất phát triển mạnh gần đây và trở thành một trong những công cụ được dùng hữu hiệu và rộng rãi để ứng dụng cho tổ hợp. Một trong những lý do chính trong sự phát triển nhanh này là vai trò quan trọng của sự ngẫu nhiên trong Lý thuyết Khoa học Máy tính, lĩnh vực mà gần đây là động lực của nhiều bài toán tổ hợp hấp dẫn. Sự tác động qua lại giữa Toán Rời rạc và Khoa học Máy tính yêu cầu một mảng giải thuật trong tìm tòi về Phương pháp Xác suất trong Tổ hợp và một số vấn đề bước đầu được trình bày trong tài liệu này. Tài liệu vì vậy bao gồm sự nghiên cứu các phương pháp cơ bản cũng như các phương pháp hiện đại ứng dụng trong đó kèm theo một số ý tưởng về giải thuật. Xin nói ngay rằng chúng ta sẽ chủ yếu tìm hiểu về phương pháp cơ bản mà thôi. Phương pháp xác suất cơ bản có thể được mô tả như sau: Nhằm chứng minh sự tồn tại của những cấu trúc tổ hợp với những tính chất chắc chắn nào đó, chúng ta xây dựng một không gian xác suất hợp lý cho cấu trúc đó và chỉ ra rằng những tính chất mong muốn tồn tại với xác suất dương. Phương pháp này được khởi nguồn bởi Paul Erdos, người đóng góp rất nhiều cho sự phát triển của nó trong năm mươi năm qua. Và dường như hợp lý khi gọi nó là "Phương pháp Erdos". Những đóng góp của ông không chỉ đo bằng số các kết quả sâu sắc trong chủ đề này, mà còn bởi nhiều bài toán và dự đoán thú vị điều đòi hỏi nhiều tâm huyết nghiên cứu trong lĩnh vực này