Đại số hiện đại và Khoa học máy tính.

Đại số hiện đại và Khoa học máy tính.

(Nguồn: hailongdao.wordpress.com)

Giữa Toán học và Khoa học máy tính luôn có sự gần gũi. Chẳng hạn như  trong toán ứng dụng phải dùng rất nhiều tính toán nặng bằng máy tính và các ngôn ngữ lập trình đặc thù. Bài viết này muốn đề cập đến một số những liên hệ khác, hiện đại hơn và có vẻ vẫn còn chưa được biết đến rộng rãi với độc giả Việt Nam. Điều thú vị ở đây là những liên hệ này kết nối Khoa học máy tính với những khái niệm khá trừu tượng của Toán cao cấp!

1) Phần mềm phục vụ nghiên cứu trừu tượng:

Gần đây có rất nhiều phần mềm kiểu này được phát triển: Macaulay 2, Cocoa, Magma, SAGE, v.v. Đặc điểm của chúng là cho phép người dùng có thể lập trình với những khái niệm cơ bản của đại số/hình học/số học hiện đại: nhóm, vành, trường, đa tạp đại số. Sự tồn tại của chúng đã đưa đến rất nhiều tiện ích cho các chuyên gia trong những lĩnh vực này. Một ví dụ đơn giản mà tôi cũng hay dùng: nếu như trong nghiên cứu bạn đối mặt với một giả thuyết có vẻ “5 phần đúng, 5 phần sai”. Bạn có thể lập một chương trình đơn giản để kiểm tra giả thuyết này trên vài trăm hay vài nghìn ví dụ ngẫu nhiên. Nếu như tất cả đều đúng thì bạn có thể yên tâm hơn khi tìm cách chứng minh giả thuyết này. Còn nếu sai thì yên tâm đi tìm giả thuyết khác! Ngoài ra các số liệu thu được cũng giúp bạn có thể nhìn ra những giả thuyết chính xác hơn.

Phương pháp này rất được ưa chuộng bởi David Eisenbud, một nhà toán học lý thuyết tên tuổi người Mỹ. Ông này giỏi ở chỗ khi làm quản lý rất nặng (hội trưởng hội toán học Mỹ, viện trưởng viện nghiên cứu Toán ở Berkeley), vẫn làm Toán và còn hăng hơn hồi trẻ! Ông chia sẻ với tôi kinh nghiệm này và nói nó đã giúp ông tiết kiệm nhiều thời gian trong nghiên cứu. Một điều thú vị là ông David còn là người rất biết hưởng thụ cuộc sống, làm việc với ông luôn có những khoảng giải lao hấp dẫn: ăn ngon, leo núi, xem kịch, v.v.

Ông David mải mê lập trình với Macaulay 2!
Ông Eisenbud mải mê lập trình với Macaulay 2 trong vườn nhà!

2) Máy tính hóa chứng minh Toán học:

Đây là mơ ước của khá nhiều nhà Toán học tầm cỡ. Các chứng minh của Toán cao cấp ngày càng phức tạp và dựa trên nhiều tầng các kết quả sẵn có. Làm sao bảo đảm chúng không có lỗ hổng? Một giải pháp là tìm cách mã hóa các bước logic của chứng minh Toán, rồi đưa vào máy tính để kiểm tra độ chính xác. Nói thì nghe đơn giản chứ tất nhiên làm rất khó. Việc đầu tiên là phải xây dựng được một hệ ngôn ngữ đủ để mô tả các hệ thống logic trong chứng minh toán học. Để làm điều này thì trước tiên người làm phải là những nhà toán học hàng đầu, có thể nhìn bao quát các chứng minh rất đa dạng và tìm được điểm chung của chúng ở tầm cơ bản nhất. Ngay cả với điều kiện đủ đó, nói chung phần lớn vẫn nghi ngờ việc này có thể được hiện thực hóa trong một tương lai gần. Trong sự nghi ngờ này cũng có nỗi lo mơ hồ rằng các nhà Toán học đang tự giết mình trong sự đam mê theo đuổi chân lý, nếu như có ngày họ để máy tính thay thế mình!

Một vài ví dụ gần đây: Voevodskyunivalent foundations. Công trình này  sử dụng lý thuyết đồng luân cao cấp, một công cụ ngày càng có tầm ảnh hưởng lớn trong tô pô và hình học đại số.  Ngoài ra cũng rất nên kể đến việc  Gowers dạy máy tính viết chứng minh đơn giản (hai ông Voevodsky và Gowers đều được giải thưởng Fields),  Thomas Halesnỗ lực kiểm tra chứng minh giả thuyết Kepler. Mỗi ví dụ này đều rất thú vị và có thể làm cơ sở để viết được một bài báo dài.

3) Lý thuyết độ phức tạp và hình học đại số:

Để hiểu vấn đề này có thể dùng một ví dụ rất đơn giản chứ không phức tạp!  Xét biểu thức x^2-y^2. Ai đã học cấp 2 đều biết nó có thể viết được dưới dạng (x+y)(x-y). Nếu dùng cách đầu để tính toán thì ta mất 2 phép nhân và 1 phép cộng/trừ. Nếu dùng cách sau thì mất 1 phép nhân nhưng 2 phép cộng/trừ. Sự khác nhau là ở chỗ làm phép nhân tốn kém bộ nhớ máy tính hơn cộng/trừ rất nhiều, nhất là cho các số lớn. Vì vậy vấn đề đặt ra là làm thế nào để hiểu chính xác độ phức tạp của các biểu thức toán học, hay rộng ra là các thuật toán.

Lý thuyết này phát triển rất mạnh những năm gần đây. Đến mức, để đo độ phức tạp của thuật toán người ta phải lập ra cả một vườn bách thú phân loại các cường độ phức tạp khác nhau (complexity zoo)! Có lẽ nhiều người đã nghe nói đến giả thuyết “P và NP” nổi tiếng, một trong những bài toán triệu đô. Hiểu nôm na, bài toán này hỏi xem hai con thú trông khác nhau trong cái vườn thú ở trên thật ra có cùng nhóm không? Đến nay nó  vẫn có vẻ ngoài tầm với, mặc dù cứ vài năm lại có người công bố đã hoặc sắp giải được! Một chuyên gia hàng đầu về lĩnh vực này là Scott Aaronson. Anh này còn có một blog cực kỳ nerdy (có lẽ tiếng Việt dịch là đầu to mắt cận) về nhiều chủ đề thú vị, như làm thế nào chống lại cơn cuồng nộ bầy đàn trên mạng, mà anh đã từng là nạn nhân khi dám bình luận về chủ đề phụ nữ trên blog của mình (-:

Năm vừa rồi tôi tình cờ tham gia một hội thảo về liên hệ giữa ngành này vàHình học đại số.  Một điều lý thú  học được trong hội thảo là một hướng tấn công độc đáo cho vấn đề  “P và NP”.  Đó là tìm cách nghiên cứu độ phức tạp của permanent của các ma trận (hình như tiếng Việt gọi là vĩnh thức, tương tự như  định thức nhưng chỉ dùng dấu cộng giữa các số hạng). Tất nhiên là triển vọng thắng lợi của tiếp cận này vẫn rất mờ mịt, nhưng như thường lệ với các bài toán quan trọng, nó gợi ra những câu hỏi lý thuyết thuần túy rất thú vị.  Ví dụ, liệu chúng ta có thể viết được permanent của một ma trận dưới dạng định thức của một ma trận khác hay không?  (bổ xung: vừa đúng lúc có bài của GS Ngô Quang Hưng về vĩnh thức, có đề cập đến vấn đề này, cảm ơn bạn Phan Dương Hiệu đã cho link!)

Permanent
Một bài giảng về permanent và lý thuyết độ phức tạp.

4) Lý thuyết mật mã và đường cong elliptic:

Đây lại là một liên hệ mới nghe thì rất kỳ lạ nhưng thật ra không đến nỗi khó hiểu. Việc mã hóa thông tin công khai hiển nhiên có tầm quan trọng cực lớn với đời sống hiện đại, ngay cả với mỗi lần bạn gửi email. Trong một bài giảng cho đại chúng gần đây (đối tượng là các cựu sinh viên già có đóng góp cho trường), tôi có so sánh việc mã hóa với làm xúc xích: bạn muốn đảm bảo rằng người lạ có ăn xúc xích và nhìn được vào máy sản xuất của  bạn vẫn không thể nói được bạn dùng loại thịt gì!  Vấn đề tế nhị ở đây là làm sao người nhà bạn vẫn phân biệt được nguồn gốc thịt!

Và đây là thời điểm các phương trình đại số vào cuộc: chúng chính là những máy nghiền thịt hiệu quả nhất. Chẳng hạn xét đa thức f(x) = 4x^3-3x, coi như một cái máy. Bạn có thể nhét miếng thịt x=2 vào máy, để ra miếng xúc xích f(2) = 26. Việc này rất dễ. Tuy nhiên nếu chỉ nhìn vào miếng xúc xích 26, và cái máy f(x), thì đoán được giá trị của x khó hơn nhiều.

Một đường cong elliptic được biểu diễn bởi một phương trình bậc 3 với 2 ẩn số, chẳng hạn y^2=x^3-x-1. Chúng rất nổi tiếng vì nhiều nguyên nhân, trong đó có thể kể đến vai trò quan trọng trong lời giải bài toán Fermat, một công trình thuộc loại vĩ đại nhất của thế kỷ 20. Câu hỏi  là tại sao các đường cong elliptic lại liên quan đến mã hóa? Câu trả lời ngắn gọn là việc giải phương trình, ngay cả phương trình đơn giản, trên những đường cong này có độ phức tạp cao, ngay cả khi bạn rất giỏi Toán và sở hữu một chiếc máy tính mạnh hơn tất cả các loại máy hiện thời.  Vì thế chúng là những máy làm xúc xích rất hiệu quả!

Chúng ta có thể hiểu một phần tại sao giải toán trên những môi trường “lạ” lại khó hơn thông qua một ví dụ đời thường: cái đồng hồ. Khi làm toán trên đồng hồ chúng ta chỉ dùng những số từ 1 đến 12. Nhưng phải nhớ rằng 12=0, vì sau 12 tiếng cái đồng hồ lại trở lại vị trí cũ! Hãy thử giải phương trình rất tầm thường 2x=2 trên môi trường này. Ngoài nghiệm hiển nhiên x=1, chúng ta còn có nghiệm x=7 nữa (vì 2\times 7=14=12+2=2). Thật vậy, nếu bắt đầu từ 7 giờ, cộng thêm 7 tiếng nữa kim của đồng hồ bạn sẽ dừng ở số 2!

Giải toán trên đồng hồ khó hơn giải toán bình thường!
Giải toán trên đường cong đồng hồ khó hơn giải toán bình thường!

5) Tóm tắt:

Bài viết cố gắng giới thiệu vài liên hệ thú vị giữa đại số hiện đại và khoa học máy tính mà tác giả có điều kiện quan sát. Dĩ nhiên còn khá nhiều chủ đề hấp dẫn, như  việc mô phỏng logic bằng lý thuyết phạm trù (của một đồng nghiệp trẻ người Úc) mà bài viết ngắn này không đủ không gian để mô tả.

Logic và lý thuyết phạm trù!
Logic và lý thuyết phạm trù!

————–&&—————

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: