Toán học - Khẩu Bazooka Trong Chiến Trường Lập Trình

Toán học - Khẩu Bazooka Trong Chiến Trường Lập Trình

Toán là một trụ cột không thể thiếu trong lập trình. Trên thực tế, toán là một nền tảng vững chắc cho rất nhiều ngành trong công nghệ thông tin, đặc biệt là ngành Machine Learning nổi trội ngày nay.

Tuy nhiên, một sự thật đáng buồn là không nhiều người coi trọng nó, thậm chí ít người hơn nữa mặc định sử dụng toán mà không hiểu bản chất, lí do của nó. Hôm nay chúng ta sẽ đào sâu một chút vào chủ đề ít được chú trọng này nhé!

1. Những ứng dụng nổi bật của toán học trong lập trình

Trước tiên chúng ta sẽ tìm hiểu toán giúp tiết kiệm thời gian như thế nào trong những problem cơ bản nhé!

Xét một bài kinh điển sau: Tính tổng các số từ 1 đến 1 tỉ.

Nếu bạn chưa biết về công thức nổi tiếng n * (n + 1) / 2 thì có lẽ bạn sẽ phải chạy loop như sau:

// pseudocode
sum = 0
for (i from 1 to 1000000000):
    sum = sum + i

Kết quả là:

500000000500000000
Time taken by program is: 3.222866s

Nhưng khi chúng ta dùng công thức trên, kết quả là:

500000000500000000
Time taken by program is: 0.000598s

2 cách làm trên đều cho cùng một kết quả, nhưng rõ ràng bạn không cần phải đợi đến 3 giây nếu bạn sử dụng công thức toán học đơn giản nọ. Hơn nữa, hãy tưởng tượng rằng, nếu cần phải tính tổng đến 10 tỉ, nếu bạn dùng loop thì sẽ phải tốn đến nửa phút, đến 100 tỉ thì sẽ mất 5 phút ... cứ như vậy thì chỉ cần tính đến 1.5 * 1027  (tức là 15 trăm triệu tỉ tỉ) thì sẽ mất khoảng 13.8 tỉ năm, đúng tuổi của vũ trụ hiện tại!!

Vậy chúng ta đã tiết kiệm thời gian giải một bài toán, từ khoảng thời gian vũ trụ mất để phát triển đến ngày nay, xuống còn dưới 1 giây!

Ngoài ra chúng ta còn một số problem khác mà ý tưởng về toán tưởng chừng như không rõ ràng như:

Có bao nhiêu số có 7 chữ số và các chữ số đều khác nhau?

Một lần nữa, ý tưởng đầu tiên nảy ra trong đầu bạn có lẽ là kiểm tra tất cả các số có 7 chữ số và đếm. Và một lần nữa, loop tốn khá nhiều thời gian:

544320
Time taken by program is: 1.540760s

Tuy nhiên, nếu bạn chịu khó phân tích một cách "toán" một chút, bạn sẽ tìm ra công thức thú vị sau:

count = 9 * 9 * 8 * 7 * 6 * 5 * 4

Và sự khác biệt có thể được nhận thấy một cách rõ rệt:

544320
Time taken by program is: 0.000042s

Cùng một kết quả, nhưng thời gian thực hiện thì chênh lệch một trời một vực, vì nếu bạn biết những máy tính ngày nay thực hiện những phép toán nhanh thần tốc đến mức nào thì giờ bạn sẽ công nhận rằng, 0.1 giây là một cách biệt rất rất lớn, chứ chưa nói đến cả 1 giây!

Tất nhiên, toán học không chỉ có ứng dụng tiết kiệm cho chúng ta hàng ngàn, hàng triệu giây trong lập trình. Nhiều phân ngành khác nhau trong Computer Science áp dụng rất nhiều ở những mảng khác nhau trong toán học thuần. Một số ví dụ tiêu biểu về những mảng toán học hữu dụng nhất trong CS có thể kể đến như:

  • Toán nhị phân: Cái này thì có lẽ mình không cần phải nói nhiều, cả thế giới lập trình có thể sẽ "tuyệt chủng" nếu thiếu mảng này!
  • Ma trận và Biến đổi Fourier: Image Processing - Xử lí hình ảnh
  • Lý thuyết đồ thị: Networking
  • Thống kê: Nền tảng của Data Science - khoa học dữ liệu
  • Suy luận Bayes, lý luận toán học: Machine Learning, AI
  • Lý thuyết trò chơi: Hữu ích trong những problem cơ bản cũng như trong thị trường chứng khoán, hoạt động tình báo

2. Làm thế nào để kiểm soát "khẩu bazooka" này?

Như vậy, một lần nữa, chúng ta không thể phủ nhận rằng, trong "chiến trường" lập trình khắc nghiệt hiện nay, thành thạo về toán thì sẽ giống như bạn sử dụng thành thạo cả một khẩu bazooka hạng nặng trong một đấu trường chỉ đầy những tay "súng lục", "súng trường".

Vậy làm thế nào ta có thể kiểm soát và sử dụng thành thạo "khẩu bazooka" này?

Cá nhân mình xuất thân từ "gia đình" toán học và dần trở thành một "bán" lập trình viên. Những lập trình viên mình biết đi theo con đường ngược lại: Làm việc với tin học trước, sau đó mới bắt đầu "vắt chân lên cổ" để học toán. Bạn có lẽ thuộc số đông đó, và bạn có thể cũng đang chật vật với khẩu bazooka nọ, rất "OP" nhưng không biết làm cách nào mà sử dụng nó.

Nói cho công bằng, mỗi người có cách học tập, cách tiếp cận, cách thích nghi khác nhau. Chính vì vậy mà toán vừa là niềm vui đối với hàng triệu học sinh, vừa là cơn ác mộng của hàng triệu học sinh khác ở khắp nơi. Nếu bạn không "trị" nó đúng cách của bạn, không những bạn không thể thưởng thức những vẻ đẹp của nó, bạn có thể sẽ còn phải mất nhiều tháng năm cuộc đời vì môn học "khó nhai" này đấy!

Tuy nhiên, không có cái gai nào mà không nhổ được cả. Theo quan điểm của mình, muốn sử dụng "khẩu bazooka" ấy, trước tiên bạn cần phải "hiểu" cách sử dụng nó và cách nó hoạt động, vì sao nó lại hoạt động như vậy. Đối với một bài toán cũng như vậy. Để thạo nó, bạn nên "chứng minh" nó trước, hiểu được vì sao nó lại ra kết quả như vậy.

Bạn có thể biết công thức tổng từ 1 đến n, nhưng bạn có biết vì sao nó lại ra được công thức nhẹ nhàng mà tinh tế như vậy không?

Thực ra cách chứng minh công thức ấy cũng không có gì quá cao siêu:

// n chẵn
  1 + 2 + ... + n
= (1 + n) + (2 + n - 1) + ... + [(n / 2 - 1) + (n / 2 + 2)] + [(n / 2) + (n / 2 + 1)]
= (n + 1) + (n + 1) + ... + (n + 1) // n / 2 lần
= (n + 1) * (n / 2)
// n lẻ
  1 + 2 + ... + n
= (1 + 2 + ... + n - 1) + n
= [(n - 1) * n / 2] + n // Áp dụng công thức trên, vì n - 1 chẵn
= n * (n + 1) / 2

Vậy thì ta sẽ được gì trong việc cố gắng chứng minh những công thức như vậy?

Thứ nhất, bạn phần nào rèn luyện được tư duy để làm việc với những vấn đề tương tự. Thứ hai, những công thức như trên chính là một mảnh ghép quan trọng để chứng minh những công thức khó nhằn hơn nữa, như "tổng các bình phương từ 1 đến n", "tổng các lập phương từ 1 đến n"... Đây chính là nền tảng của cách xử lí "một vấn đề lớn" bằng cách chia thành "những vấn đề nhỏ". Thứ ba và trên hết, nếu bạn không hiểu cách khẩu bazooka của bạn vận hành, bạn sẽ không thể khai thác được hết tiềm năng, sức mạnh tiềm ẩn được cất giấu bên trong nó.

Mặt khác, chứng minh một bài toán, một công thức có đôi nét giống như khi bạn đang gỡ một cái thắt nút rất khó. Đôi khi bạn sẽ nản lòng, nhụt chí vì nhiều trở ngại. Nhưng một khi bạn đã thành công gỡ được nó, bạn sẽ phấn chấn lên và có tinh thần để gỡ thêm vài cái thắt nút khó hơn nữa. Vì khi đó bạn đã được thử thách đến giới hạn của mình, gỡ được cái thắt nút đầu tiên sẽ khiến bạn tưởng chừng như bạn đã phá vỡ giới hạn đó, và bạn sẽ có động lực phá vỡ nó thêm nhiều lần nữa.

Tạm kết

Như vậy, đó là những ứng dụng của toán học trong lập trình, từ đơn giản cho đến cao siêu, những lí do bạn nên đặc biệt coi trọng sức mạnh của "khẩu bazooka" này, và một cách tiếp cận để thành thạo nó. Có thể nó không phải là cách dễ dàng nhất, cách tối ưu nhất, nhưng nó cũng không phải là đơn giản với bất kì ai. Hãy nhớ rằng, cái khó ở đây của toán chúng ta đều đang đương đầu chính là cái khó mà bất kì người tài giỏi nào cũng đều phải trải qua, chỉ là họ đã tìm được cách để "chiến đấu" với nó. Hy vọng các bạn sẽ sớm tìm được cách của riêng bạn!

Để giúp các bạn và cùng các bạn "chiến đấu", trong những bài sắp tới, mình sẽ chia sẻ về những cách khác nhau toán học được sử dụng trong lập trình như thế nào, bắt đầu từ những problem cơ bản hay được dùng để luyện tập hàng ngày. Hy vọng các bạn sẽ ủng hộ và đón xem nhé!