‘Toán
rời rạc và khoa học máy tính đã đi vào trung tâm của toán học’
PGS Phan
Thị Hà Dương
06/11/2021 07:00 GMT+7
Nhà toán học giành giải Abel năm 2021 - 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.
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, ....
"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 ....
No comments:
Post a Comment