Năm 2021, Giải Abel toán học – giải thưởng dành cho những nhà Toán học xuất chúng trong cả sự nghiệp, trái với thông lệ thường dành cho các chuyên ngành lý thuyết, đã vinh danh hai nhà toán học László Lovász và Avi Wigderson vì những đóng góp của họ trong Toán rời rạc và Tin học và việc đưa chúng trở thành trung tâm của toán học. Vậy hai lĩnh vực dẫu non trẻ này đã có những ý nghĩa gì và sự đóng góp cho toán học nói riêng cũng như cho khoa học công nghệ và ứng dụng nói chung như thế nào?
VietNamNet giới thiệu bài giảng đại chúng của PGS. Phan Thị Hà Dương tại Lễ ra mắt Hai trung tâm Toán học và Vật lý quốc tế dưới sự bảo trợ của Unesco – Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Bài viết này sẽ đề cập đến các công trình tiêu biểu của Lovász.
Lovász được biết đến không chỉ như một nhà khoa học hàn lâm mà còn vì những đóng góp trọng yếu cho cộng đồng toán học cũng như cho xã hội. Ông đã đảm nhiệm vị trí chủ tịch hội toán học thế giới (2007-2010), chủ tịch Viện hàn lâm khoa học Hungary (2014-2020).
 |
| Nhà Toán học László Lovász từng đến Việt Nam năm 2009 |
Ông đã viết những cuốn sách gối đầu giường của nhiều thế hệ và những bài giảng đại chúng của ông đã lan tỏa tình yêu toán học cho đông đảo công chúng Hungary. Chú trọng đào tạo, ông có nhiều học trò xuất sắc trên khắp thế giới, mà giáo sư Vũ Hà Văn là một ví dụ tiêu biểu. Điều đó có lẽ vì ông đã là một thần đồng khi đã đạt với 3 huy chương vàng và 1 huy chương bạc Kỳ thi Toán quốc tế; và đặc biệt đã được ông tổ của ngành toán rời rạc Paul Erdős dẫn dắt vào lý thuyết đồ thị từ thủa trẻ. Nhưng khác với Erdős - người xây dựng và đưa toán rời rạc thành một ngành toán với lý thuyết sâu sắc, Lovász đưa toán rời rạc đến với các ứng dụng, và đặc biệt trong khoa học máy tính lý thuyết lẫn công nghệ thông tin ứng dụng.
Trước hết nói đến Lovász, người ta nghĩ ngay đến thuật toán LLL – mang tên ba nhà khoa học Lenstra – Lenstra - Lovász. Thuật toán ra đời vào năm 1982, và ngay lập tức đã thu hút và tạo tiền đề cho những ngành lý thuyết và các hướng đi mới của tin học.
Thuật toán này là tìm cơ sở rút gọn của một lưới. Vậy lưới là gì? Hãy hình dung trên mặt phẳng ta có hai véctơ (u1, u2), khi đó ta kẻ các đường thẳng dựa theo các vecto này, nó sẽ chia mặt phẳng thành các đường ngang dọc và có các nút giao nhau của các đường thẳng, được gọi là một lưới. Điều thú vị là nếu ta lấy hai véctơ (v1, v2) và làm như vậy cũng nhận được cùng một lưới. Hai véctơ đã chọn được gọi là một cơ sở. Câu hỏi là cơ sở nào sẽ có ứng dụng hơn? Theo lẽ tự nhiên cái đẹp là gì hài hòa, nhỏ và tròn trịa, vì vậy cơ sở đầu tiên sẽ hợp lý hơn, nó được coi là một cơ sở rút gọn đẹp của cơ sở kia.
Bài toán then chốt là: cho trước một lưới, hoặc một cơ sở không đẹp, hãy đi tìm một cơ sở đẹp.
Thế nào là đẹp? Chính cái cách mà ta chọn để diễn tả cái đẹp sẽ quyết định được việc ta có tìm được nó hay không. Đóng góp của Lovász là đã nới rộng điều kiện vể định nghĩa một cơ sở rút gọn đẹp để ta vừa dễ tìm ra nó và cũng vừa có thế ứng dụng nó vào nhiều vấn đề khác.
Ưng dụng ý nghĩa nhất là trong một ngành khoa học giờ đây đang chiếm một vị trí trọng tâm trong Khoa học máy tính và trong chính cuộc sống của chúng ta. Đó là Mật mã. Mọi mặt cuộc sống hiện nay đều liên quan đến vấn đề bảo mật, từ mã số máy tính, thẻ ngân hàng, bí mật dữ liệu, các thông tin gấp truyền đi, vv. Hệ mật mã quen thuộc nhất ta đang dùng là hệ RSA được Ron Rivest, Adi Shamir và Len Adleman đề xuất vào năm 1977 (Shamir đã sang Việt Nam tham dự Hội nghị Asiacrypt năm 2016). Nó dựa trên lý thuyết số và bài toán phân tích một số ra thành các thừa số nguyên tố (ví dụ phân tích 15 thành tích 3*5). Bài toán này thật là sơ khai, vậy nhưng cũng rất khó, cho đến nay chưa có thuật toán nào làm được trong thời gian đa thức. Vì vậy mà RSA an toàn.
Năm 1996, Coppersmith đã xây dựng một thuật toán phá mã RSA trong một số các trường hợp dựa trên thuật toán LLL. Và chính vì vậy rất nhiều hệ mật mã với các điều kiện riêng trước đây đã bị phá mã. Điều đó cho thấy thuật toán LLL đã có một sức mạnh phá mã mạnh mẽ. Cũng năm 1997, một hướng đi hoàn toàn bất ngờ khác đến từ vật lý, Peter Shor đã xây dựng thuật toán thời gian đa thức để giải bài toán phân tích một số ra thừa số nguyên tố trên máy tính lượng tử. Như vậy, trong tương lai nếu có máy tính lượng tử, hệ RSA không còn bảo mật nữa.
Vậy đặt ra vấn đề hãy xây dựng một hệ mật mã không dựa trên bài toán phân tích số của RSA. Năm 1996 Ajtai đã lần đầu tiên đưa ra hệ mật mã dựa trên lý thuyêt lưới. Và người ta tin rẳng hệ mật mã trên lưới sẽ được bảo toàn ngay cả khi có máy tính lượng tử.
Thuật toán LLL đã đóng vai trò quan trọng trong tiến trình này, vậy mà điều rất thú vị là công trình ấy được đăng trên tạp chí toán học Mathematische Annalen chứ không phải tin học. Tháng 5 năm 1982, Lenstra viết thư cho Lovász: Trước nay các nhà toán học thường coi thuật toán và độ phức tạp tính toán là một lĩnh vực của khoa học máy tính. Bằng cách đăng bài báo này ở tạp chí Toán chúng ta sẽ đưa sự quan tâm của toán học đến việc tính độ phức tạp, cần không chỉ tính đúng mà phải tính nhanh, hiệu quả. Và qua đó cho thấy toán học có thể giúp ích cho tin học thế nào.
Công trình thứ hai là bổ đề địa phương của Lovász, mà chính nhờ có nó đã sinh ra một lĩnh vực toán học mới là Phương pháp chứng minh xác suất. Trước đây để chứng minh một điều gì tồn tại hoặc là ta đi tìm chúng, hoặc là phản chứng nếu không tồn tại thì sai. Phương pháp xác suất sẽ khác: nó nói rằng nếu xác suất để điều đó xảy ra là lớn hơn 0 thì điều đó phải xảy ra.
Hãy xét một số sự kiện xấu, mỗi sự kiện có xác suất là p <1, làm thế nào để có thể có 1 sự kiện tốt, không có tính chất xấu nào? Liệu có tồn tại hay không? Nếu những cái xấu này độc lập với nhau, không liên kết với nhau, thì chúng không đủ mạnh, ta vẫn luôn tìm ra cái tốt. Nhưng lỡ như những cái xấu lại liên quan đến nhau thì sao?
Bài toán này đã tồn tại bao nhiêu năm cho đến khi Lovasz, lại một lần nữa, mở rộng điều kiện.
Ông đã chứng minh rằng nếu các sự kiện xấu liên quan đến nhau, nhưng không liên quan nhiều quá, mỗi sự kiện chỉ ảnh hưởng đến một số sự kiện khác thôi thì vẫn có kết quả mong muốn.
Rất nhiều ứng dụng của Bồ đề của Lovasz, đặc biệt trong logic, trong bài toán tô màu đồ thị và đã làm ra đời nhiều cuốn sách cho mỗi dạng ứng dụng.
Cuối cùng ta hãy nhắc đến một số đóng góp của Lovász cho lý thuyết đồ thị, điển hình là 3 công trình sau: hệ động lực Chip Firring Game, Bước đi ngẫu nhiên trên đồ thi, và đồ thị cực lớn với mạng phức tạp. Có thể nói Lovász có một sự nhạy bén và tầm nhìn, mỗi vấn đề ông đặt ra hay ông quan tâm đều trở thành trọng tâm của ngành và đều mở đường cho rất nhiều nghiên cứu và ứng dụng sau đó. Và đặc biệt, ngày nay các mạng phức tạp như mạng Internet, facebook, mạng các đồng tác giả các bài báo, mạng giao thông, vv đều được mô tả như các đồ thị cực lớn. Phương pháp nghiên cứu các mạng này khác và đột phá so với các bài toán cổ điển về đồ thị, Lovász đã nắm bắt được những chủ đề cốt lõi của lý thuyết hoàn toàn mới mẻ này và đã đóng góp những công trình tầm cỡ.
Và điều thú vị nho nhỏ là ông cũng đã đến Việt Nam năm 2009 dự Hội thảo do Viện Toán học tổ chức, khi ông là chủ tịch hội toán học thế giới.
PGS. Phan Thị Hà Dương
PGS.TSKH. Phan Thị Hà Dương: Học Toán ở đại học trong nước
“…Tôi nghĩ nếu như sau này mình đi dạy, trong số hàng chục, hàng trăm học sinh ngồi nghe giảng thế kia, chỉ cần có một đứa nhóc nào có được niềm vui ngập tràn như cô sinh viên là mình đang có thì lúc ấy cũng đáng lắm…”
"Trí tưởng tượng chỉ có thể khoáng đạt khi xuất phát từ sự thật”
“Cần phải có nhiều bộ SGK, vừa là tạo điều kiện để người dùng có thể lựa chọn tham khảo, vừa là động lực thúc đẩy các tác giả cố gắng hết sức để sách được người đọc đánh giá cao…” – PGS Toán học Phan Thị Hà Dương nói.
.svg){kind=icon}
