[Chia sẻ] Một bài tập Toán Tin có gì?

Nhiều bạn đồng nghiệp ngoài ngành không rõ môn Tin học ở các trường chuyên đang học gì và cũng khá nhầm lẫn với việc học lập trình Toán Tin với cái món Tin học văn phòng. Bởi vậy nên nhân trưa muộn thứ 7 viết một bài nhỏ về một bài tập Toán Tin đang dạy cho các bạn khối 10 chuyên Tin.

Hiện đang dạy cho các bạn về Số học thuật toán. Một bài tập khá hay về số chính phương như sau. Phát biểu của bài tập thì trông thật đơn giản: “Tìm số chính phương lớn nhất tạo bởi tích của các số nguyên phân biệt từ 1 đến n với n cỡ 10^7”.

Ví dụ như từ 1 đến 7 ta có thể lấy các số: 1, 2, 3, 4, 6 tạo nên số 144 là số chính phương.

Vậy nhưng khi n đủ lớn cỡ 10^7 thì để giải bài tập này ta cần những kiến thức nào để xử lý?

1. Sàng nguyên tố Eratosthenes

Học giả Eratosthenes ở thế kỷ III TCN đã đưa ra phương pháp tìm các số nguyên tố trên tấm lá cọ của mình. Ông có lẽ cũng không tưởng tượng được lũ con cháu của mình phát minh ra cái công cụ máy tính để dùng giải thuật của ông để tối ưu cho việc liên tục kiểm tra một số có nguyên tố hay không? Sàng nguyên tố sẽ giúp việc kiểm tra các số nguyên tố với thời gian khá tối ưu.

2. Công thức Legendre

Legendre là một nhà toán học người Pháp, ông nổi tiếng với những công trình liên quan đến số học, đại số, thống kê, giải tích. Một trong các công trình nổi tiếng của ông chính là công thức Legendre. Công thức này cho ta số mũ đúng của số nguyên tố p trong phân tích n! ra thừa số nguyên tố. Ảnh về định lý và chứng minh của nó ở dưới.

3. Phép nhân nhanh bằng chia để trị

Hình như phép nhân này được người Ấn độ đưa ra. Để tính a^n thì các bác ấy đưa về việc tính a^(n/2) và cứ vậy chia nhỏ để mức tính a^0 = 1. Có lần thấy cô giáo nào dạy online có hướng dẫn cách nhân này và còn pr rằng phép nhân cô Hằng (cô Hiền gì đó). Với cách nhân này, tốc độ tính toán trong máy tính cải tiến một cách vượt bậc từ độ phức tạp O(n) xuống O(logn). Ta có thể tưởng tượng tuổi vũ trụ hiện tại là cỡ 10^18 giây. Phép log cơ số 2 có thể đưa 10^18 về một con số cỡ 64 lệnh.

4. Định lý Fermat nhỏ

Kết quả của bài toán thường rất lớn nên nếu muốn biểu diễn hết thì phải xây dựng kiểu dữ liệu số nguyên lớn. Tuy nhiên để đảm bảo về mặt tốc độ thực thi thì các yêu cầu thường sẽ chia lấy dư cho một số nguyên nào đó như là (10^9 + 7). Để đảm bảo việc lấy nghịch đảo modulo (a/b chia lấy dư cho mod) thì ta phải sử dụng định lý Fermat nhỏ:

“Nếu p là một số nguyên tố thì a^p – a sẽ chia hết cho p”.

Định lý này sẽ cho phép ta lấy được nghịch đảo modulo trong trường hợp mod là một số nguyên tố.

5. Kiến thức lập trình.

Hiển nhiên Toán Tin thì phải lập trình rồi. Ở đây cần được trang bị các kiến thức về biến số, vòng lặp, cấu trúc dữ liệu, bộ nhớ, tốc độ xử lý của máy tính….Cái này nói thì ngắn nhưng để có được skill này cũng phải luyện hằng tháng hằng năm.

Sau khi có được giải thuật thì cần hoàn thiện bài toán bằng các dòng lệnh. Nói cách khác là phải dạy cho máy tính giải được bài toán bằng ngôn ngữ của máy tính. Cái mà cứ thấy mấy chú gõ lóc ca lóc cóc suốt ngày suốt đêm. Có chú thì code thật, có chú thì chơi game liên minh – nói chung cũng khó phân biệt nếu không rành máy tính.

6. Test thử chương trình

Sau khi code xong thì đến giai đoạn test thử. Thông thường thì thử các test nhỏ có thể tính được bằng tay. Sau đó có thể viết những đoạn code kiểu thô sơ tạo ra những test vừa và kiểm tra lại. Nói chung công đoạn này rất mệt vì có những sai sót không lường trước được trong tính toán như tràn số, thực hiện các phép toán không đúng thứ tự, kiểu dữ liệu…

Hiện tại các thầy dạy món này có xây dựng được những hệ thống chấm điểm chuẩn để học sinh có thể test chương trình của mình. Nó cũng giảm được nhiều khó khăn cho người dạy và người học.

Tuy nhiên khi đi thi lại chấm offline nên nhiều chú không biết mình đã sai ở đâu cả – thuật toán sai, code sai, nhầm lẫn tiểu tiết….

Vậy kết luận rằng: Bản chất việc học Toán Tin là học Toán trên máy tính. Học được Toán Tin thì ắt hẳn phải rất cứng về Toán. Hơn thế nữa, các kỹ năng máy tính phải ở mức thượng thừa, phải tinh thông về các ngôn ngữ lập trình, phải nắm vững khoa học máy tính.

Hiển nhiên để phát triển con người thì còn cần thể thao, văn nghệ, khả năng giao tiếp, sự linh hoạt trong cuộc sống, tư duy phản biện nữa nhưng thông thạo Toán Tin cũng là một kỹ năng nên có của các chàng trai trẻ! Thực ra có nhiều cô giỏi lắm luôn ấy nhưng code nhiều sợ đầu to mắt cận nên cũng không khuyến khích phụ nữ tham chiến món này nhiều quá!

Chúc cả nhà cuối tuần vui vẻ khỏe khoắn!