Giới thiệu toán học
Chương này giới thiệu các kiến thức toán học có thể dùng trong OI．Khoa học máy tính gắn chặt với toán học, và trong lập trình thi đấu đặc biệt nhấn mạnh các mảng rời rạc, cụ thể như số học, tổ hợp, xác suất kỳ vọng, đa thức．Các kiến thức này chú trọng triển khai chương trình và bài toán thực tế, có thể xuất hiện ở hầu hết các dạng bài．
Thực tế, nhiều thuật toán và cấu trúc dữ liệu, cũng như tự động cơ, cũng có thể coi là thuộc phạm trù toán học, nhưng được tách sang các chương như chuỗi để nêu bối cảnh ứng dụng giúp dễ hiểu hơn．Chương này chủ yếu giới thiệu các khái niệm cơ bản, đại số, số học, lý thuyết trò chơi và xác suất, v.v．Vận dụng các kiến thức này có thể giúp tối ưu các thuật toán/cấu trúc dữ liệu khác, ví dụ:
- Dùng đa thức để tối ưu dạng chập của bài ba lô, phục vụ một số bài chuỗi．
- Nhiều bài truy hồi có bối cảnh tổ hợp hoặc xác suất kỳ vọng, có thể tiếp tục dùng hàm sinh để suy luận và giải, cũng như dùng FFT kết hợp chia để trị để tối ưu độ phức tạp．
- Dùng đồng dư và vành để phân tích tổng trọng số của các đường đi không đơn trong đồ thị theo modulo, và dùng DSU có trọng số để duy trì．
Ngoài ra, toán phổ thông là nền tảng của toán cho thi tin học, nắm chắc các khái niệm và tính chất cơ bản trong sách giáo khoa sẽ giúp học tốt chương này．
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply