#1 - Khai mở

Hầu hết bạn trẻ nào học tin chắc hẳn cũng đã có thời gian miệt mài ôn luyện toán thời còn học cấp hai để thi vào trường chuyên cấp ba. Dĩ nhiên bài tập đầu tiên để làm quen với ngôn ngữ lập trình không phải là quay lui, tham lam hay quy hoạch động, mà là giải toán. Trong quá trình học tin, thoạt đầu bạn sẽ nghĩ rằng các bài tập liên quan đến toán là những bài tập đơn giản, thứ phực tạp hơn là những cấu trúc dữ liệu như interval tree, v.v... Trong bài thi quốc gia, các yếu tố toán học hầu hết vẫn còn ở dạng khá sơ khai. Vì thế, tầm quan trọng của toán học thường bị một số lập trình viên xem nhẹ hơn mức cần thiết.

Thế nhưng nhìn vào những cá nhân tiêu biểu nhất trong lập trình thi đấu của Việt Nam, bạn có bao giờ tự hỏi về điểm chung giữa họ, và chợt giật mình nhận ra hầu hết họ đều đã từng tham gia các kì thi olympic toán học hoặc đã từng học chuyên toán không?

Bạn có thể nghĩ rằng mình có lợi thế học tin trong 3 năm cấp ba. Nhưng khi lên đại học, hãy nhìn vào những người đã từng học chuyên toán, họ sẽ san bằng lợi thế của bạn trong thời gian không hề dài.

Vậy tại sao nền tảng toán học lại đóng vai trò quan trọng như vậy trong lập trình thi đấu?

Tôi đã có thời gian ở cùng phòng kí túc xá với một người từng thi IMO và rút ra được một số điều cốt lõi:

- Thứ nhất, hầu hết các thuật toán đều được sinh ra từ những kết quả toán học quan trọng. Những luồng, cặp ghép, khớp cầu, đường đi ngắn nhất, bao hàm loại trừ, BIT, v.v... không phải bỗng dưng mà sinh ra. Chúng đều mang nặng dấu ấn của toán rời rạc. Bản thân từ “algorithm” được dịch là “thuật toán”, chẳng ai gọi nó là “thuật tin” cả. Càng làm những bài tin khó, bạn sẽ càng nhận ra yếu toán là một thiệt thòi không hề nhỏ.

- Thứ hai, xét về góc độ ôn luyện, thì lượng kiến thức mà một người đi thi IMO phải học vượt xa so với người thi IOI. Bài tập của chuyên toán vừa đòi hỏi khả năng nhạy bén cao, vừa đòi hỏi một nền tảng kiến thức khổng lồ. Trong tin có khái niệm cắn test, nhưng trong toán điều này ít xảy ra. Vậy nên khi chuyển từ toán sang tin, người học toán sẽ có ưu thế vượt trội về kiến thức.

- Thứ ba là sự chăm chỉ và kỉ luật. Đừng nghĩ rằng bạn có thể đạt đến đỉnh cao chỉ dựa vào trí thông minh. Người học toán thực sự là một trong những kiểu người chăm chỉ nhất. Học toán cũng chính là một cách để rèn luyện sự chăm chỉ, khả năng tích hợp các kiến thức với nhau.

Kí ức thuật toán số đầu tiên sẽ dành để nói về những kiến thức toán học cơ bản nhất được sử dụng rộng rãi trong các bài tập lập trình.

1, Sàng số nguyên tố Eratosthenes và kiểm tra số nguyên tố:

+ Sàng số nguyên tố nhỏ hơn N: https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes

+ Kiểm tra số nguyên tố: nếu x không chia hết cho bất kì số nguyên tố nào trong khoảng từ 1 đến thì x là số nguyên tố.

2, Ước chung lớn nhất (gcd), số ước của một s:

Độ phức tạp .

Số ước của một số x với

trong đó

là các số nguyên tố khác nhau, sẽ bằng

3, Định lý Fermat nhỏ, tổ hợp chập k của n: dùng trong các bài toán đếm

+ Định lý Fermat nhỏ: p là số nguyên tố, với a<p ta có:

+ Tổ hợp chập k của n:

Với p là số nguyên tố, ta có:

trong đó:

4, Nguyên lí bao hàm loại trừ: dùng trong các bài toán đếm

Để cho đơn giản, giả sử trong một lớp có n môn học:

Số học sinh giỏi môn i là

Số học sinh giỏi cả môn i và môn j là

Số học sinh giỏi cả 3 môn i, j, k là

...

Vậy số học sinh giỏi ít nhất 1 môn là

5, Dãy Fibonacci: một bài tập cơ bản trong quy hoạch động và nhân ma trận

6, Phương trình đường thẳng, khoảng cách giữa hai điểm, khoảng cách giữa điểm và đường thẳng...

7, Quy nạp toán học: dùng trong chứng minh các thuật toán tham lam, quy hoạch động

“Nếu đúng

và đúng nếu đúng

thì đúng với mọi n.”

Trên đây là những kiến thức cơ bản của toán học dùng trong lập trình. Những thứ cao siêu hơn xin được bàn đến trong những số tiếp theo. Lời kết cho số lần này là: “Hãy học toán thật vững càng sớm càng tốt ngay khi có thể!”. (Tất nhiên bạn có thể nói rằng việc lập trình từ trước đến giờ của bạn chẳng cần tí toán học nào, mà chỉ cần biết cách dùng ngôn ngữ lập trình. Tuy nhiên nếu sau này bạn không giỏi toán, thì mãi mãi bạn cũng chỉ là một thợ code mà thôi.)

TĨNH LẶNG

Tái bút: Chuyên mục mới “Kí ức thuật toán” sẽ lên sóng Free Contest 2-4 lần một tháng, kể từ ngày 6/12/2017. “Kí ức thuật toán” viết về những giải thuật thường gặp trong lập trình theo một cách hoàn toàn riêng biệt, mong rằng sẽ mang đến cho bạn cảm nhận mới mẻ về những điều tưởng chừng khô khan như những dòng code mà bạn viết hàng ngày. Rất mong nhận được những ý kiến đóng góp của các bạn để chuyên mục ngày một hoàn thiện hơn!

Số tiếp theo: {Kí ức thuật toán #2} “Mình đã quá lạc hậu rồi ư?”