Toán học và thuật toán

Hồi năm 1992, khi tôi đang làm cộng tác viên ở ICTP (Trung tâm vật lý quốc tế, Italia) thì gặp phải một vấn đề không có lời giải như sau: Tôi được CIMPA (trung tâm toán quốc tế của Pháp) mời sang Nice dự một trường hè về đúng chuyên ngành của tôi. Khi đến Lãnh Sự Quán Pháp xin visa (thời đó chưa có khối Shenghen) thì họ giở nguyên tắc đòi phải có công hàm từ ĐSQ của Việt Nam vì hộ chiếu của tôi là hộ chiếu công vụ (thời đó ai đi nước tư bản cũng được cấp hộ chiếu công vụ). Khi đến ĐSQ Việt Nam ở Roma xin công hàm thì họ đòi phải có giấy công tác từ cơ quan chủ quản ở trong nước. Hỏi về trong nước để xin giấy công tác thì không ai cho, vì tôi chẳng thuộc ai quản lý. Thế là tôi trở thành nạn nhân của một bộ các luật lệ mâu thuẫn, không thể xin visa đi Pháp. Nhưng cuối cùng tôi đã tìm được một thuật toán để giải quyết vấn đề tưởng chừng không có lời giải này, và đã sang Pháp dự trường hè CIMPA một cách hoàn toàn hợp pháp. Bạn đọc tò mò muốn biết thuật toán của tôi thế nào, thì xem đến cuối bài sẽ rõ.

Trong cuộc sống và trong công việc, chúng ta hay gặp phải những tình huống lạ, những tình huống mà chúng ta mới gặp lần đầu, chưa biết trước cách giải quyết. Những tình huống đó gây khó khăn cho chúng ta, đòi hỏi chúng ta phải suy nghĩ về những vấn đề lạ. Nhưng đồng thời đó cũng chính là cơ hội cho chúng ta vươn lên và khám phá được những cái mới, còn những công việc lặp đi lặp lại đã có máy móc dần dần làm thay cho con người.

Để giải quyết một vấn đề mà chúng ta gặp phải, chúng ta cần tìm ra một cách giải, hay có thể gọi là một thuật toán để đi đến lời giải. Trong các môn học ở nhà trường, thì môn toán chính là môn tốt nhất để dạy và học về cách tiếp cận thuật toán đối với các vấn đề. Nếu như qua việc học toán mà học sinh hiểu được bản chất các thuật toán quan trọng nhất để áp dụng trong các tình huống khác nhau trong cuộc sống và công việc, thì có thể coi đây là sự thành công của bản thân môn toán trong giáo dục. Rất tiếc rằng, điều này còn rất lâu mới trở thành hiện thực. Vào thời điểm hiện tại, trên thế giới, khía cạnh thuật toán vẫn còn ít được quan tâm tới trong việc dạy và học toán.

Một ví dụ điển hình cho khẳng định trên chính là kỳ thi toán olympic IMO 2014 vừa qua. Đề bài của IMO 2014 không hề rắm rối phức tạp, đặc biệt nếu so với đề thi HSG của Việt Nam. Và chỉ cần kiến thức toán PTCS chứ cũng không cần đến kiên thức PTTH để có thể hiểu đề bài và lời giải của toàn bộ đề thi. Thế nhưng, điểm thi năm nay tương đối thấp so với các năm khác, nên chỉ cần được 29/42 điểm (tức là chỉ cần làm được 4/6 bài và viết được một hai ý gì đó cho 2 bài còn lại) là được huy chương vàng. Một số bài năm nay khó, không phải là vì chúng phức tạp, mà là vì chúng lạ, khiến cho các thí sinh ngỡ ngàng không biết làm thế nào. Tôi sẽ lấy bài số 5 và bài số 6 của IMO 2014 làm ví dụ, chính là hai bài mà đoàn Việt Nam được ít điểm.

Bài số 5 như sau: Có một đống đồng xu có tổng mệnh giá nhỏ hơn hoặc bằng 99,5, sao cho mệnh giá của đồng xu nào cũng có dạng 1/n với n là số tự nhiên (các đồng xu khác nhau có thể có mệnh giá khác nhau). CMR chia được đống đồng xu thành không quá 100 túi sao cho tổng mệnh giá của mỗi túi không vượt quá 1.

Làm sao để tiếp cận một bài toán “lạ hoắc” như trên, với giả sử là bạn không “trúng tủ”, chưa từng làm một bài rất tương tự như thế? Một số phương pháp tiếp cận chung gồm 4 bước sau (lặp di lặp lại nếu cần thiết): quan sát, suy luận, tính toán, kiểm tra. (Bốn bước này không phải do tôi nghĩ ra, mà là đã được đúc kết từ lâu, và được trình bày rất hay trong quyển sách “3 ngày ở nước Tí Hon” cho học sinh cấp 2  mà tôi gần đây có dịch lại sang tiếng Việt, do Sputnik Education đang xuất bản).  Trong các bước quan sát và lý luận có việc quan sát các tương quan trong bài toán, làm thử các trường hợp riêng, dựa vào các trường hợp riêng để đưa ra các giả thuyết liên quan rồi xét các giả thuyết đó, biến đổi để đơn giản hóa bài toán, đưa về các dạng bài toán quen thuộc hơn hay dễ giải hơn. Nhiều khi, tổng quát hóa cũng chính là một cách để đơn giản hóa. Nếu là vấn đề lớn, phức tạp, thì phải chia để trị, tức là làm sao chia nó ra thành các bước nhỏ hơn, giải quyết từng bước đó dễ dàng hơn là giải quyết toàn bộ vấn đề.

Có một anh bạn của tôi, là chuyên gia máy tính, có nói với tôi một câu từ cách đây hơn 20 năm mà đến bây giờ tôi vẫn rất tâm đắc: khi được giao một nhiệm vụ lập trình, lập trình viên nào mà ngồi vào hì hụi viết chương trình ngay thì là lập trình viên tồi. Lập trình viên tốt trước khi viết chương trình thì phải quan sát, suy nghĩ đã. Trong toán hay trong nhiều lĩnh vực khác cũng vậy, trước khi “bổ củi” cần quan sát và suy luận để hình dung vấn đề.

Trong trường hợp bài toán số 5 trên, thì có thể quan sát ngay là số 99,5 gần với số 100. Từ đó ta có giả thuyết là nếu thay 99,5 và 100 bởi N -1/2 và N trong đó N là số tự nhiên bất kỳ thì vẫn đúng. Nếu như bài toán chỉ đúng khi N = 100 chứ không đúng với N khác, khi đó thì bài toán chắc là khá phức tạp, nhưng đây là đề thi để học sinh có thể làm trong vòng một vài tiếng, không quá phức tạp được, nên giả thuyết là bài toán đúng với N bất kỳ là giả thuyết tương đối khả dĩ. Việc thay 100 bằng N tùy ý này cho phép chúng ta giả sử là không có đồng xu nào có mệnh giá 1. Thật vậy, nếu có m đồng có mệnh giá 1 thì cho các đồng đó vào m túi, còn lại N = 1 -100 túi và số tiền <= 99,5 – m = N – 1/2.

Một bước lý luận thông dụng quan trọng là: ta cứ thử giải quyết vấn đề một cách “ngây thơ” nhất, để xem nó tắc ở chỗ nào, khó ở chỗ nào. Ở đây có nghĩa là, ta cứ thử bỏ dần tiền vào 100 túi, cho đến bao giờ bỏ được hết hoặc bị tắc không bỏ được nữa thì thôi. Nhưng khi nào thì có thể bị tắc? Đó là khi còn 1 đồng tiền mà cứ bỏ vào túi nào cũng khiến cho mệnh giá của túi đó vượt quá 1. Vì có N túi mà tiền <= N – 1/2, nên có túi có tiền <= (N -1/2)/N = 1 – 1/2N. Điều đó có nghĩa là, nếu có đồng tiền còn lại không bỏ được vào túi nào, thì mệnh giá của nó phải > 1/2N. Cách giải quyết “ngây thơ” này cho ta quan sát sau, làm đơn giản vấn đề:  ta có thể giả sử tất cả các đồng tiền có mệnh giá > 1/2N, chứ không cần quan tâm đến các đồng tiền có mệnh giá <= 1/2N nữa (các đồng có mệnh giá <= 1/2N luôn có thể bỏ vào, sau khi đã giải quyết các đồng có mệnh giá > 1/2N)

Một bước lý luận thông dụng quan trọng khác là: làm sao đơn giản hóa bài toán, đưa về những trường hợp đơn giản nhất có thể (gọi là phương pháp reduction trong toán). Ở đây, có thể hiểu là có ít xu thì đơn giản, càng có nhiều xu thì phức tạp hơn. Như vậy, ta có thể tìm cách làm giảm số đồng xu. Có 1 cách hiển nhiên là: nếu có thể đối 2 hay nhiều đồng xu trong đống lấy 1 đồng xu khác (có mệnh giá bằng tổng mệnh giá của các đồng kia), thì ta đơn giản hóa được đống đồng xu: nếu giải được sau khi đã đổi, thì sau khi giải xong ta có thể đổi lại để có lời giải cho đống đồng xu ban đầu. Cứ đổi xu để đơn giản hóa như vậy, ta đưa được bài toán về trường hợp mà không còn đổi xu được nữa.

Đến đây, bài toán đã đơn giản hóa đi đáng kể, vì ta chỉ còn cần xét trường hợp sau: tổng mệnh giá <= N -1/2, không có đồng xu nào có mệnh giá bằng 1, không có một nhóm các đồng xu nào có thể đổi thành 1 đồng xu khác, và không có đồng xu nào có mệnh giá <1/2N. Tất cả các trường hợp còn lại đều suy giản về được trường hợp này. Bây giờ lại quan sát tiếp xem trường hợp cuối cùng này ra sao.
Ta sẽ quan sát thấy là với mọi số tự nhiên k thì không có quá 1 đồng xu có mệnh giá 1/2k và không có quá (2k-2) đồng xu có mệnh giá 1/(2k-1) (vì sao thế?). Từ đó có cách xếp xu vào túi như sau: túi k chứa các đồng xu mệnh giá 1/(2k-1) và 1/2k, với k =1, …, N. (Bạn đọc hãy tự kiểm tra rằng cách này OK).

Tôi viết lời giải cho bài số 5 phía trên khá dài dòng để giải thích quá trình suy nghĩ dẫn đến lời giải mà bản thân tôi sử dụng khi thử làm bài đó, còn tất nhiên khi viết thành lời giải “tròn trịa” thì có thể viết ngắn hơn nhiều. Nhìn từ quan điểm thuật toán, bài số 5 này thật ra khá đơn giản, vì chỉ sau vài bước lược giản hóa dễ thấy là đã đưa về được trường hợp chia được ngay thành các túi. Bạn nào học về lập trình máy tính chắc sẽ nghĩ ngay được cách viết chương trình chia xu dựa trên các bước phía trên. Rất tiếc là đoàn VN chỉ có 2 bạn giả được bài này.

Bài số 6 của IMO 2014 thì còn lạ hơn bài số 5 nữa, và không có bạn VN nào giải được, tuy có một bạn được 3/7 điểm. Các đoàn khác cũng “rụng” gần hết bài này. Đề bài có thể phát biểu như sau: Giả sử có n đường thẳng trên mặt phẳng, sao cho không có 2 đường nào song song và không có 3 đường nào đồng qui. CMR có thể tô ít nhất \sqrt{n} đường bằng màu xanh, sao cho không có miền bị chặn nào trên mặt phẳng có biên toàn là màu xanh.

Con số \sqrt{n} trong đề bài có lẽ là con số gây hoang mang, bởi thoạt nhìn chẳng biết nó từ đâu ra. Số các điểm cắt nhau thì là n(n-1)/2, còn số các miền bị chặn thì là (n-1)(n-2)/2, tức là đều so được với n^2, chứ chẳng có cái gì trên mặt phẳng có số lượng dạng \sqrt{n}.  Những hoang mang như vậy có thể ảnh hưởng xấu đến tâm lý, khiến việc tìm lời giải trở nên khó khăn hơn. Bỏ qua các hoang mang, ta cứ thử làm một thuật toán “ngây thơ” để giải quyết vấn đề tô màu, xem nó sẽ gặp khó khăn bế tắc ở đâu. Thuật toán ngây thơ đó là: đầu tiên ta tô một đường bất kỳ màu xanh. Sau đó cứ còn tô được thêm đường màu xanh (sao cho không có miền bị chặn nào trên mặt phẳng có biên toàn là màu xanh) thì tô tiếp, còn đến lúc không tô được thêm nữa thì dừng lại. Gọi số đường tô được lúc dừng lại là k. Nếu thuật toán đơn giản này mà OK, thì tức là ta có k^2 >= n. Như vậy, nếu ta chứng minh dược k^2 >= n thì OK.

Một phương pháp chứng minh thông dụng là dùng phản chứng. Tức là ta sẽ chứng minh rằng, nếu đã tô được k đường, và n > k2, thì còn tô thêm được đường nữa. Để chứng minh điều đó, chỉ cần CMR số đường cấm không vượt quá k^2 – k = k(k-1).  Đường cấm tức là đường mà nếu tô nó thì sẽ có miền bị chặn với biên toàn màu xanh. Bây giờ lại vận dụng nhận xét sau: số điểm nút xanh (= giao điểm của các đường xanh) là k(k-1)/2, nên nếu ta làm sao thiết lập quan hệ được giữa các đường cấm và các nút xanh, kiểu “đương cấm nào cũng cho bởi nút xanh, và mỗi nút xanh không cho quá 2 đường xanh” thì là OK. Ý tưởng là như vậy. Đi vào cụ thể hơn, thì quan hệ sẽ là: mỗi đường cấm ứng với ít nhất 2 đoạn cấm (1 đoạn cấm là một đoạn màu xanh đi từ 1 nút xanh đến đường cấm), còn từ mỗi nút xanh chỉ đi ra được nhiều nhất là 4 đoạn cấm thôi. Và lời giải đến đây gần như là kết thúc (bạn đọc có thể tự viết lại lời giải hoàn chỉnh, sẽ không quá 1 trang giấy).

Đấy là chuyện thi toán quốc tế. Quay lại chuyện dạy toán và học toán “bình thường”. Năm nay, tôi có dạy toán cho một lớp đại học năm thứ nhất chuyên ngành tin học, thay cho một đồng nghiệp nghỉ đẻ. Một số bạn sinh viên phàn nàn với tôi là chương trình toán chán quá, chẳng thấy liên quan gì đến tin học. Mà đúng thế thật, tôi đọc chương trình cũng thấy chán. Nhưng tôi chỉ là “lính đánh thuê” chứ không soạn chương trình nên không thay đổi được nó.
Cái mà tôi cố gắng làm để “bù trừ” lại là giải thích thêm cho các sinh viên những khái niệm mà họ học chính là các thuật toán có ý nghĩa ra sao. Ví dụ như, công thức nội suy Lagrange chính là thuật toán để vẽ đường cong “đơn giản nhất, đẹp mắt nhất” đi qua một số điểm cho trước, và khi người ta thiết kế ô tô, tàu bay thì thay vì vẽ toàn bộ các điểm người ta chỉ cần vẽ ít điểm thôi rồi nội suy ra các điểm còn lại theo kiểu công thức đó. Hay như chuỗi Taylor để làm gì? Nó cũng chính là thuật toán cho phép chúng ta tính xấp xỉ một cách rất chính xác các giá trị của các hàm phức tạp, v.v. Ví dụ như, ta có thể tính nhẩm bằng tay các số như e, sin(1), v.v. với độ chính xác rất cao mà không cần máy tính (máy tính nó cũng dùng các thuật toán như ta tính nhẩm thôi), v.v. Khi học sinh sinh viên (đặc biệt là sinh viên tin học) được giải thích ý nghĩa thuật toán của các khái niệm toán học, thì họ cũng phấn khởi lên nhiều. Đối với sinh viên sinh vật, hóa học, v.v.  thì có thể cần dạy hơi khác đi, với nhiều minh họa ứng dụng toán học trong ngành của họ hơn, ví dụ như tại sao lại dùng hàm lũy thừa khi khảo sát dân số, v.v. Cuối cùng thì toán học vẫn là một tổng hợp các công cụ để mô hình hóa và các thuật toán đề giải quyết các vấn đề nảy sinh trong mọi lĩnh vực, chứ không phải là một mớ khái niệm từ trên trời rơi xuống và xa vời thực tế.

Thế còn thuật toán để giải quyết vấn đề visa thì sao? Với hộ chiếu công vụ, thì tôi không thể đi Pháp. Như vậy tôi phải thay hộ chiếu. Không ai tự nhiên lại cho thay hộ chiếu, như vậy tôi phải mất hộ chiếu. Thế là một hôm đẹp trời, tôi ra đồn cảnh sát Italia báo mất ví có hộ chiếu trong đó. (Không ai phải chứng minh chuyện mình bị móc mất hộ chiếu với cảnh sát, vì làm sao có thể chứng minh được điều đó, chỉ chứng minh được là mình có hộ chiếu nếu chưa mất thôi). Với chứng nhận mất hộ chiếu của cảnh sát, tôi lên ĐSQ VN làm hộ chiếu khác, và ở đó, khác với ở VN, người ta chỉ cấp hộ chiếu phổ thông chứ không cấp hộ chiếu công vụ cho loại không phải cán bộ nhà nước như tôi :)

Print Friendly

2 comments to Toán học và thuật toán

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.