Chương trình tự tái sinh (2)

Trong phần này ta bàn về nguyên tắc viết các chương trình tự in được bản thân. Ta sẽ làm việc trên một mô hình tổng quát (nhưng hoàn có thể hiện thực được với bất kỳ ngôn ngữ máy tính nào). Giả sử, trong mô hình máy tính này, có một vùng nhớ mà tất cả các chương trình đều lấy input từ đó và ghi ra đó được.

Trước hết, ta có hai quan sát nhỏ:

1. Cho một chuỗi x bất kỳ, ví dụ x = "học như nghịch thủy hành châu", gọi P(x) là chương trình ghi x vào vùng nhớ chung. Có thể có nhiều P(x) khác nhau, ta cứ thống nhất một loại P(x) duy nhất. Bạn có thể nghĩ đến phát biểu

 strcpy(buffer, "Học như nghịch thủy hành châu");

trong ngôn ngữ C chẳng hạn.

2. Cho một chuỗi x bất kỳ trong vùng nhớ, ta có thể dễ dàng viết một đoạn chương trình sẽ ghi P(x) vào vùng nhớ.

Ý tưởng của chương trình tự in bản thân (vào vùng nhớ chung) như sau: chương trình này có hai đoạn, đoạn A và đoạn B, nghĩa là nối A với B thì ta có toàn bộ chương trình.

Đoạn B làm công việc như sau:

1. x = chuỗi các bytes trong vùng nhớ
2. Ghi P(x) vào vùng nhớ
3. Ghi x vào vùng nhớ

Chú ý rằng, sau khi B hoạt động xong thì trong vùng nhớ chung chứa P(x) rồi đến x. Bạn nên tưởng tưởng viết một đoạn chương trình như B trong ngôn ngữ bạn thích.

Đoạn chương trình A thì làm gì? Nó sẽ ghi x vào vùng nhớ cho B đọc và ghi P(x), x. Thế A ghi gì? A ghi ra chính đoạn B ở trên!!!

Vì A ghi B vào vùng nhớ, A = P(B), và x = B. Còn B ghi ra "P(x)x" = "P (B)B" = "AB".

Lần tới ta sẽ hiện thực phương pháp này bằng một ngôn ngữ lập trình nào đó. Có lẽ tôi sẽ thử C và/hoặc Scheme.

More about Chernoff

Chặn Chernoff (Chernoff bound) quả thật là rất hữu dụng trong phương pháp xác suất và các giải thuật ngẫu nhiên hóa. Tôi có một lecture note   tóm tắt vài chặn đơn giản dùng trong phương pháp xác suất, các bạn có thể tìm hiểu thêm.

Tình cờ cách đây vài hôm, đang viết một bài báo về routing trong ad hoc networks thì lòi ra bài toán sau: cho trước một đồ thị G  với degree lớn nhất là d, mỗi cạnh của G tồn tại với xác suất p, tính xác suất xem G liên thông (connected) là bao nhiêu. Tôi hỏi anh Văn thì hóa ra hàm xác suất này có tính concentration rất cao (xem bài báo này của anh Văn và vài đồng nghiệp).  

Chương trình tự tái sinh (1)

Một trong các bài tập rất hay cho người đang học lập trình (bất kể ngôn ngữ nào) là: hãy viết một chương trình in chính nó ra. Chú ý là phải in ra giống hệt, từng giòng từng chữ từng cái xuống hàng. Ở đây ta giả sử có thể viết chương trình bằng một tệp (file) thôi.

Nếu bạn chưa bao giờ nghĩ về các chương trình kiểu này, hãy dành vài chục phút nghĩ trước khi đọc các ví dụ dưới đây. Bạn sẽ thấy bài tập này liên quan mật thiết đến khái niệm "tự tham chiếu", một trong những khái niệm trung tâm trong loạt bài Chung qui chỉ tại Cantor.

Thử xét vài ví dụ sau:

• C/C++:

 main(){char *c="main(){char *c=%c%s%c;printf(c,34,c,34);}";printf(c,34,c,34);}

 

• Java:

 import java.text.*;class a{public static void main(String x[]){char b[]={34};
 char c[]={123};String s[]=new String[3];s[0]="import java.text.*;class a{2}
 public static void main(String x[]){2}char b[]={2}34};char c[]={2}123};
 String s[]=new String[3];s[0]={1}{0}{1};s[1]=new String(b);s[2]=new String(c);
 System.out.println(MessageFormat.format(s[0],s));}}";s[1]=new String(b);s[2]=
 new String(c);System.out.println(MessageFormat.format(s[0],s));}}

 

• Common Lisp:

 ((lambda (x)
 (list x (list (quote quote) x)))
 (quote
 (lambda (x)
 (list x (list (quote quote) x)))))

 

• Perl:

 
 #!/usr/bin/perl
 $_=<<'eof';eval $_; print "#!/usr/bin/perl\n\$_=<<'eof';eval \$_;\n${_}eof\n" eof

Các ví dụ trên tôi lấy ở đây, và ở đây. Lần tới ta sẽ thiết kế một ví dụ cho riêng ta, không cần đi "chôm" về. Các trương trình tự in bản thân còn được gọi là Quine, họ của triết gia Willard van Orman Quine. Có hai câu hỏi liên quan:

1. Có nguyên tắc gì để viết các chương trình lọai này không? Cho một ngôn ngữ mới thì làm thế nào ta viết được một chương trình như vậy?

Các chương trình lọai này có ứng dụng gì không?

Các bài báo kinh điển của KHMT (3)

Một bài báo được trích dẫn rộng rãi trong giới KHMT, xử lý thông tin, machine learning, v.v. là bài báo của Chernoff:

Chernoff, H. (1952). A measure of asymptotic efficiency for tests of an hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493.

Một cách tóm tắt, nếu bạn có n biến ngẫu nhiên độc lập, và cùng hàm phân phối F (independent and identically distributed, or i.i.d.) x_1, x_2,..., x_n, để ước tính giá trị trung bình của hàm phân phối F, chúng ta đều biết rằng chỉ việc lấy tổng của n dữ liệu này cộng lại và chia cho n. Một định lý căn bản và quan trọng bậc nhất của lý thuyết xác suất, law of large numbers, nói rằng, (với những điều kiện thích hợp), khi n đủ lớn thì ước đoán trên của ta sẽ tiến dần đến giá trị trung bình chính xác của F. Đây chính là hiện tượng concentration nổi tiếng trong xác suất.

Tất nhiên mọi ước đoán đều có sai số, và xác suất của sai số đó, còn gọi là tail probability, được chứng minh trong bài báo của Chernoff là exponentially small. Chernoff còn giới thiệu trong bài báo của mình khái niệm Chernoff exponent, chính là rate of the exponential decrease. Khái niệm này vô cùng hữu ích trong hypothesis testing và coding theory, và có vai trò tương tự như khái niệm mutual information và entropy của Shannon vậy. Một bài báo rất nổi tiếng khác với kết quả tương tự như của Chernoff, nhưng tổng quát và chặt hơn nhiều:

Shannon, Gallanger, and Berlekamp (1967). Lower bounds to error probability. Information and Control, 10(1).

Chernoff không phải người đầu tiên, và cũng không phải người cuối cùng nói về hiện tượng concentration trong lý thuyết xác suất, bài báo nổi tiếng của ông chỉ là một kết quả đơn giản nhưng vô cùng hữu ích. Chernoff's bound là một ví dụ đơn giản nhất của cả một mảng nghiên cứu đồ sộ về large deviation theory: Làm sao để ước tính error probability khi chúng ta dùng dữ liệu quan sát được để tính một thống kê cụ thể nào đó (như mean và variance). Nghiên cứu về large deviation theory quan tâm cả đến những dãy biến ngẫu nhiên không độc lập, và mở rộng cả đến những vật thể xác suất vô hạn chiều (như empirical processes).

Tôi hy vọng sẽ có dịp nói thêm (và nghe nhiều hơn ở blog này) về hiện tượng concentration, không chỉ trong lý thuyết xác suất, mà trong cả tự nhiên và cuộc sống của chúng ta nữa. Vì lẽ đó, hiện tượng concentration và large deviation theory chính là nền tảng cơ bản tạo nên nhiều ứng dụng rộng rãi trong khoa học công nghệ nói chung và ngành máy tính, điện tử nói riêng. Xin liệt kê một vài ví dụ chung:

 

• Xây dựng thuật toán ngẫu nhiên (randomized algorithms): Rất nhiều vấn đề mà người ta chưa tìm được deterministic algorithm một cách hiệu quả, nhưng lại có nhiều thuật toán ngẫu nhiên mà có thể giải quyết hiệu quả được vấn đề trong phần lớn các trường hợp. Rất nhiều thuật toán ngẫu nhiên trong ngành KHMT là ứng dụng cụ thể của các thuật toán sampling nổi tiếng, như Monte Carlo và Monte Carlo Markov Chain (bao gồm Gibbs sampling, Metropolis-Hasting sampling,vv...).
• Rất nhiều tính chất thuật toán rất khó được mổ xẻ trong từng trường hợp, nhưng hiện tượng concentration (thường là đúng) nói rằng ta chỉ nên phân tính những tính chất chung (average behavior/properties) là đủ. Điều này làm cho cuộc sống của ta dễ dàng hơn nhiều. (Ví dụ, bạn muốn tìm số cliques trong một graph ngẫu nhiên? Hoặc bạn muốn tìm max cut trong một graph bằng một thuật toán độc đáo? )
• Trong việc học một mô hình từ dữ liệu (Learning a model from empirical data): Nếu càng có nhiều dữ liệu, hiện tượng concentration giúp ta biết rằng, ta sẽ tìm được mô hình càng chính xác. Đây chính là nền tảng của toàn bộ ngành thống kê, machine learning, và nói chung tất cả các ngành khoa học có liên quan đến xây dựng mô hình từ dữ liệu như computational biology, public health, demography, vv...

Lý thuyết thông tin (information theory/coding theory/signal processing):
Shannon cho chúng ta biết rằng nếu dùng code block đủ dài (tương tự như khi có đủ dữ liệu) thì sẽ tồn tại một phương pháp coding/compression hầu như không có lỗi.

Các bài báo kinh điển của KHMT (2)

 

Nối tiếp bài viết về bài báo nổi tiếng của Shannon, tôi muốn nói về một bài báo kinh điển trong thống kê cùng giai đoạn những năm 40, có vai trò đặc biệt đến KHMT, kinh tế, và operations research, và đẻ ra cả một lĩnh vực mới trong thống kê gọi là sequential analysis. Đó là bài báo sau đây của Abraham Wald, vốn là giáo sư đại học Columbia:

Wald, A. (1945). Sequential tests of statistical hypotheses. Annal of Mathematical Statistics. 16, 117-186.

Bài báo này giới thiệu một vấn đề mới mẻ trong một trong những lĩnh vực quan trọng nhất của ngành thống kê, đó là hypothesis testing, và giới thiệu một hướng giải quyết trọn vẹn. Được thai nghén trong thời kỳ chiến tranh thế giới lần thứ 2, có lẽ Wald đã quan tâm đến những vấn đề rất cụ thể trong lĩnh vực signal processing, như radar signal detection, missile detection, và system failure detection. Chẳng hạn chúng ta có một dãy dữ liệu mà radar có thể bắt được. Chúng ta muốn biết đó là một máy bay địch hay ta, để báo động cho quân đội và dân chúng. Ta muốn ra quyết định sớm nhất có thể được, nhưng cũng hạn chế tình huống báo động giả (false alarm, nói là máy bay kẻ thù trong khi đó là máy bay của ta), cũng như hạn chế tối thiểu tình trạng detection failure (không phát hiện được đây là máy bay địch). False alarm còn được gọi là type 1 error, còn detection failure probability được gọi là type 2 error trong ngôn ngữ ngành thống kê.

Ở dạng đơn giản nhất, bài toán của Wald có thể tóm tắt như sau: Giả sử có một dãy biến ngẫu nhiên độc lập và có cùng hàm phân phối (probability distribution) là P_0 hoặc P_1: X_1, X_2,...,X_n,... Làm thế nào để biết những biến ngẫu nhiên này có hàm phân phối P_0 hay P_1 với sai số nhỏ nhất (cả có thể được mà lại tốn ít mẫu dữ liệu (data sample) nhất? Nếu bạn chỉ cho tôi m mẫu dữ liệu là X_1, X_2,..., X_m, thì vấn đề này đã hoàn toàn đã được giải quyết bằng Neyman-Pearson lemma, và qua đó ta có thể tính được số mẫu dữ liệu tối ưu m là bao nhiêu. Như vậy, lời giải của bài toán radar detection trên là, tùy thuộc vào đòi hỏi tối đa về xác suất báo động giả và xác suất không báo động kịp (type 1 and type 2 probability errors), ta có thể tính được giá trị m tối ưu, và sau khi đã có đủ m mẫu dữ liệu thì sẽ đưa ra quyết định cuối cùng. Phương pháp này gọi là fixed-sample-size test. Tuy nhiên, trên thực tế, nếu bạn là người quan sát radar signal, có lẽ bạn sẽ không chịu làm như vậỵ Nhiều khi bằng cách quan sát chuỗi dữ liệu và theo dõi cách chúng thay đổi, chúng ta có thể đưa ra quyết định chính xác và sớm hơn nhiều.

Những cảm nhận tự nhiên và đơn giản thường là đúng, nhưng phải đợi đến Wald thì mọi việc mới sáng tỏ. Quả thật quan sát này của Wald gây chấn động trong giới thống kê. Hơn nữa, Wald còn đưa ra giải pháp tối ưu cho bài toán trên, sau này đươc gọi là Wald's sequential likelihood ratio test:

Tại từng thời điểm, sau khi nhận được tín hiệu X_i, chúng ta tính likelihood ratio u_n = P_1(X_n)/P_0(X_n). Quan sát sự biến chuyển của tổng S_n = u_1 +...+u_n, và chúng ta sẽ dừng lại khi S_n vượt ra ngoài một khoảng [A,B] thích hợp. Nếu S_n <>P_0, còn nếu S_n > B thì ta kết luận ngược lại. S_n còn gọi là random walk, và thời điểm n mà chúng ta dừng lại chính là một dạng biến ngẫu nhiên, gọi là hitting time của random walk S_n.

Phải hai năm sau, Wald và học trò của mình là Paul Wolfowitz chứng minh một cách chặt chẽ rằng phương pháp trên là tối ưu nhất. Trên thực tế, Wald's test có thể tiết kiệm được từ một nửa đến 1/3 số mẫu dữ liệu nếu ta dùng fixed-sample-size test. Điều đáng nói là cùng thời gian đó Arrow, Blackwell và Girshick cũng xuất bản một bài báo chứng minh về tính tối ưu của Wald's test. Đặc biệt bài báo này lần đầu tiên giới thiệu phương pháp dynamic programming, với khái niệm "cost to go" nổi tiếng, mà 8 năm sau đó được Richard Bellman tổng quát hóa lên cho Markov Decision Processes. Rất tiếc là sau này người ta thường chỉ nhắc đến Bellman với danh nghĩa là người đã sáng tạo ra thuật toán dynamic programming. Bài báo của Wald châm ngòi cho cả lĩnh vực sequential decision-making theory, được áp dụng và phát triển dưới các màu sắc và thuật ngôn khác nhau trong thống kê( sequential analysis), trong operations research (markov decision processes), và trí tuệ nhân tạo ( reinforcement learning)...

Những nhân vật liên quan đến những ngày đầu của sequential analysis đều là những tên tuổi lớn trên bầu trời khoa học. Abraham Wald được coi là một trong những nhà thống kê học lỗi lạc và có ảnh hưỏng nhất của thế kỷ 20, sánh ngang hàng với Fisher và Neyman, những người được coi là ông tổ của thống kê. Kennet Arrow, hiện vẫn là giáo sư ở Stanford, vốn là một học trò của Wald, về sau này được nhận giải Nobel vì những cống hiến trong game-theory. Còn David Blackwell, giáo sư ở Berkeley, được coi là nhà toán học vĩ đại nhất người da đen, có rất nhiều cống hiến về game theory, kinh tế và thống kê học.

Một số tham khảo khác:

Arrow, K. J., Blackwell, D. and Girshick, M. Ạ (1949). Bayes and minimax solutions of sequential decision problems. Econometrica 17, 213-244.

Wald, A and Wolfowitz, J (1948). Optimum character of the sequential probability ratio test. Annal of Math. Statistics 19, 326-339.

Bellman, R (1957). Dynamic programming. Princeton University Press.

Sự phát triển của nhân loại trong quan hệ với tri thức (1)

 

Tác phẩm "Những nguồn gốc của tư duy hiện đại" của Merlin Donald đã xem lại những giai đoạn phát triển tri thức loài người rất sâu sắc. Những điều trình bày dưới đây dựa nhiều vào tác phẩm này nhưng đã mở rộng ở mức độ nào đó bằng cách thêm vào suy nghĩ dự báo về các giai đoạn sắp tới.

Kỷ nguyên: Người nguyên thủy, sinh hoạt mông muội

Được coi là người duy nhất có đủ khả năng quan sát để hiểu biết về những điều đang diễn ra trong môi trường và biết theo "từng đoạn một". Tất nhiên có sự học hỏi và giao tiếp giữa những người ngang hàng nhưng rất ít hoặc không có khả năng tư duy trừu tượng.

Cùng với khả năng tối thiểu để giao tiếp thì chỉ đạt được "hiểu biết" vượt ra khỏi cái một con người có thể quan sát một cách trực tiếp.

1.500.000 - 200.000 BCE ? Con người đi thẳng và có khả năng bắt chước.

Donald tranh luận rằng sự tiến bộ của một "phần cứng" quan trọng xảy ra cùng với tư thế đứng thẳng của con người - khả năng giao tiếp bằng điệu bộ. Cử chỉ hay hành động cung cấp một phương pháp sơ đẳng để ám chỉ những vật hay sự kiện không thấy ngay lập tức - để điều phối hành động, chỉ ra nơi chốn và bản chất thức ăn hay các mối nguy hiểm.

Mặc dù ngôn ngữ cử chỉ cung cấp phương thức truyền đạt rất khó nhọc và không chính xác cho giao tiếp, nhưng có lẽ mọi người vẫn có thể thu được một vài hiểu biết nào đó từ những người khác ngoài cái mà họ có thể phát triển thông qua kinh nghiệm trực tiếp.

100.000 BCE: Tiếng nói của loài người cổ xưa

Vấn đề tại sao ngôn ngữ phát triển và nó đã phát triển như thế nào và liệu đó là một sự tiến bộ về văn hoá hay sự tiến bộ của phần cứng đầu tiên đang là một vấn đề gây tranh cãi hết sức nóng bỏng. Tuy nhiên, có một khả năng được thừa nhận là phạm vi hiểu biết của con người và xã hội được mở rộng đáng kể. Bây giờ con người có thể học hỏi không chỉ từ việc liên lạc trực tiếp với những người khác hay các nhóm khác mà còn từ những câu chuyện được truyền miệng từ xa xưa.

Việc sử dụng ngôn ngữ tuỳ thuộc vào sự tiến bộ trong khả năng nhận thức, và đồng thời nó cũng cung cấp một phương thức để đẩy mạnh những tiến bộ này. Việc xoá bỏ sự hồ nghi trước đây cũng chậm chạp như khả năng nhận thức và sự phong phú của các phương thức chuyển tải lời nói diễn ra dần dần qua các thế hệ.

Rốt cuộc, lời nói đã có thể chuyển tải kiến thức (nếu cùng với sự đáng tin cậy còn hạn chế) từ các thời đại và từ những nơi chốn xa xôi. Donald đã mô tả tỉ mỉ mối quan hệ mật thiết giữa ngôn ngữ lời nói và những nền văn hoá "tượng trưng", những nền văn hoá phát triển và chứa đựng sự hiểu biết cốt yếu trong thần thoại, được giữ gìn bởi một phương thức truyền miệng.

40.000 - 20.000 BCE: Những bức hoạ trong hang động

Những bức hoạ về hang động và nghệ thuật chạm trổ tượng trưng hình thành nên sự khởi đầu của "quá trình lưu trữ ngoài thông tin về lâu dài".

Bộ nhớ ngoài có nhiều ưu điểm thu hút sự quan tâm.

Được sử dụng như là một sự mở rộng của "bộ nhớ làm việc" đáp ứng cho nhu cầu sử dụng ngay lập tức khi đang suy nghĩ.

Cung cấp sự lưu trữ về lâu dài, giúp cho việc khôi phục lại ở một thời đại sau. Được dùng để giao tiếp với những người khác.

Những bức hoạ ban đầu đã giúp cho những kỹ năng suy nghĩ nhiều như thế nào, hay có bao nhiêu kiến thức được chuyển tải từ những bức hoạ đó thì không hề được nói rõ.

Giao tiếp thông qua những bức vẽ quả có sức mạnh tiềm tàng nhưng có lẽ là khó khăn với những vật liệu để vẽ trước kia, và không dễ gì mang chúng theo được. Tuy nhiên, có vẻ những bức vẽ ban đầu, kết hợp với những khả năng giao tiếp đã trở nên tinh tế hơn thông qua việc sử dụng lời nói, đã đóng một vai trò quan trọng trong sự phát triển chữ viết diễn đạt bằng hình tượng thời kỳ đầu.

Sự phát triển của chữ viết: 4000 BCE - 1400 CE

Sự phát triển hệ thống những biểu tượng của chữ viết cho những khái niệm cụ thể và trừu tượng cuối cùng đã đem lại một hình thức tăng cường mạnh mẽ khả năng mọi người viết ra và đóng góp vào dòng kiến thức vô tận của nhân loại, từ xa đến gần, từ hiện tại hay trong quá khứ. Ngoài ra, chữ viết (và những vật liệu "kỹ thuật " đi cùng) đã cung cấp một sự hỗ trợ đắc lực cho một bộ não vốn hạn chế về khả năng suy nghĩ hay giao tiếp ngay lập tức nhiều ý tưởng phức tạp.

Từ đó chữ viết đem đến một sự hỗ trợ thiết yếu về phần cứng cho cơ quan thần kinh, dữ liệu sẵn có ra tăng lớn trong cho cơ quan này để cân nhắc xem xét, và một khả năng đã được cải thiện đáng kể cho hệ thần kinh của con người để cùng suy nghĩ. Hình vẽ cho thấy rằng các cơ quan thần kinh giờ đây đã thường sử dụng bộ nhớ ngoài như một bộ phận hỗ trợ đắc lực cho việc suy nghĩ.

Trong suốt thời gian này các lĩnh vực về khoa học và triết học được khám phá một cách rộng rãi và có hiệu quả, trở nên dễ dàng hơn bởi khả năng suy nghĩ, lưu trữ thông tin và khả năng giao tiếp qua chữ viết. Một số tiến bộ như là: trong toán học người ta đã có thể quy cho gần như là hoàn toàn vào "vai trò của những biểu tượng của chữ viết". Sự tập hợp của những kết quả về một lượng người đang gia tăng một cách rộng lớn bởi những tiến bộ trong việc quản lý những người dù ở cách xa nhau đã được thực hiện phần lớn nhờ vào chữ viết.

Tuy nhiên, việc tiếp cận với chữ viết (hay việc dạy cho mọi người đọc được những chữ viết đó) còn hạn chế bởi những bản sao chép chữ viết phải làm thủ công, và quyền kiểm soát việc tiếp cận chữ viết  này thường nằm trong tay những người ưu tú đang nắm quyền hay những người thống lĩnh tôn giáo.

Nói thêm về xuất bản hàn lâm

 

Trong tờ tin nhanh "the institute " của IEEE tháng 3 năm 2005 có bài viết "thông tin miễn phí cho tất cả?" liên quan đến bài tôi viết cách đây vài hôm. Họ viết về phong trào "truy cập mở" (open access), có vài chi tiết quan trọng. Năm ngoái có ba sự kiện làm cho phong trào này từ "hô hào" biến thành mối quan tâm rất thực tế cho các nhà xuất bản.

Tháng 7 năm 2004, British House of Commons xuất bản một tài liệu 114 trang về xuất bản hàn lâm (academic publishing). Tài liệu cho thấy các nhà xuất bản trong nghiên cứu này (không có IEEE trong đó) đặt giá đến 30,000 USD cho mỗi journal mà một thư viện subscribe. British House of Commons gợi ý rằng " tất cả các học viện ở vương quốc Anh thiết lập một cơ sở dữ liệu mà qua đó các xuất bản của họ có thể được đọc miễn phí". Các tin và bài liên quan: bài 1, bài 2, bài 3 .

Tháng 11 năm 2004, google bắt đầu thử bản beta của http://www.scholar.google.com mà qua đó ta có thể tìm được rất nhiều bài báo online của các khoa học gia. Tôi đã dùng dịch vụ này từ đó, và thấy nó cực kỳ hữu dụng. Thậm chí khoa tôi định sẽ dùng nó như một trong những nguồn thông tin để xét tenure cho các giáo sư (ta sẽ nói về quá trình tenure ở Mỹ trong một post khác).

Tháng 12 năm 2004, tổng thống Bush ra đạo luật cho viện sức khỏe quốc gia Mỹ (National Institutes of Health - NIH) để các khoa học gia trong ngành y tế đưa một bản copy bài báo của họ vào PubMed Central , và các tài liệu này sẽ được đọc miễn phí sau 6 tháng.

Sau đó, bài báo nói đến các tiện ích và khó khăn của phong trào "thông tin cho tất cả". Một chi tiết rất quan trọng, và tôi đồng ý, là phong trào này nghe có vẻ như "cách mạng xã hội", nhưng thực tế còn là một cuộc cách mạng thay đổi mô hình kinh doanh của các nhà xuất bản hàn lâm

Chung qui chỉ tại Cantor (10)

 

Bài toán nào nằm trong P được xem là bài toán "dễ", còn lại là các bài toán khó. Lớp P chỉ có thể được định nghĩa chính xác bằng toán học nếu ta có một mô hình toán học cho khái niệm giải thuật. Dĩ nhiên mô hình này không gì khác hơn là máy Turing.

Máy Turing còn có một dạng bất định, gọi là máy Turing bất định (non-deterministic Turing machine, ký hiệu là NTM). Máy Turing bình thường còn được gọi là máy Turing xác định (deterministic Turing machine, hay DTM). Máy NTM cũng tương tự như DTM, chỉ khác ở chỗ máy NTM có thể chọn bước thực thi kế tiếp tùy hỉ trong một tập cho trước các lệnh. Ta sẽ định nghĩa rõ ràng hơn trong phần tới.

Về mặt trực quan thì rõ ràng NTM có vẻ mạnh hơn DTM. Tuy vậy, chứng minh điều này không dễ dàng chút nào. Lớp các bài toán giải được bằng NTM được gọi là lớp NP. Câu hỏi rằng liệu NTM có thật sự mạnh hơn DTM hay không chính là câu hỏi trung tâm của khoa học máy tính hiện nay. Nói cách khác: "P có bằng NP không?"

Trong cùng tinh thần của các bài toán Hilbert, viện toán Clay (Clay Mathematics Institute) đã treo giải thưởng một triệu đô la cho ai giải được một trong 7 bài toán chưa có lời giải của thế kỷ 20, một trong 7 bài toán này chính là câu hỏi P=NP?. (Một bài khác chính là bài toán số 8 của Hilbert: giả thuyết Riemann).

Năm 1971, Stephen Cook [7] chứng minh rằng có các vấn đề trong lớp NP mà tất cả các vấn đề khác trong NP có thể chuyển giản (reduced) về được trong thời gian đa thức. Phép chuyển giản này có thể được mô tả đại khái như sau: nếu vấn đề A có thể chuyển giản được về vấn đề B trong thời gian đa thức, thì nếu ta giải được B trong thời gian đa thức ta sẽ giải được A trong thời gian đa thức. Theo nghĩa thời gian đa thức thì vấn đề B khó hơn hoặc bằng A. Vì thế, các vấn đề mà Cook đề cập là các vấn đề khó nhất trong lớp NP. Các vấn đề này gọi là các vấn đề NP-đầy đủ. Cook chứng minh rằng sat, 3-sat , và subgraph isomorphism là NP-đầy đủ. Độc lập với Cook, Leonid Levin cũng có một bài báo năm 1973 [22] với kết quả tương tự.

Năm 1972, Richard Karp [18] chứng minh rằng 20 vấn đề tự nhiên khác cũng NP-đầy đủ, như Vertex Cover, Euclidean TSP, Clique, Independent Set, ... Năm 1972, Donald Knuth [20, 21] góp phần định ra các thuật ngữ của ngành này như ta thấy ngày nay, vì lúc đó ông đang viết phần 4 của bộ sách kinh điển "nghệ thuật lập trình máy tính". Quyển sách của Garey và Johnson [12] có thảo luận sơ qua về quá trình thay đổi thuật ngữ trong thời gian đó.

Hầu hết những nhà khoa học ta vừa nhắc đến đều được giải Turing (giải thưởng tương đương với giải Nobel cho khoa học máy tính): Rabin, Hartmanis và Stearns, Blum, Cook, Karp, và Knuth.

[7] S. A. Cook, The complexity of theorem-proving procedures , in Conference Record of the Third Annual ACM Symposium on the Theory of Computing, 1971, pp. 151–158.

[18] R. M. Karp, Reducibility among combinatorial problems , in Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85–103.

[20] D. Knuth, Postscript about np-hard problems , SIGACT News, 6 (1974), pp. 15–16.

[21] _________, A terminological proposal, SIGACT News, 6 (1974), pp. 12–18.

 

[22] L. Levin , Universal search problems (in russian) , Problemy Peredachi Informatsii, 9 (1973), pp. 265–266. English translation in Trakhtenbrot, B. A.: A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing, 6 (1984), pp 384–400.

 

Sinh trắc học

 

Sinh trắc học (biometrics) dùng để chỉ nhánh nghiên cứu các cách dùng các dấu hiệu của các bộ phận trong cơ thể (như dấu tay, ảnh mặt, ảnh mắt, DNA, ...) để nhận ra (identify) một cá thể. Sau vụ 9/11, khách đến Mỹ đều phải để lại vân tay và ảnh mắt ở các cửa khẩu hải quan. Cụm từ sinh trắc xuất hiện 35 lần trong đạo luật cải cách tình báo quốc gia ( National Intelligence Reform Act) năm 2004 của Mỹ. Nhiều chục triệu đô la được đầu tư để nghiên cứu phổ biến sinh trắc học cho các hoạt động chống khủng bố ( xem bài này).

Vấn đề bảo mật trong máy tính là nơi sinh trắc học có thể có các ứng dụng thực tiễn.

Các người quản trị hệ thống đều biết rằng người dùng cực kỳ cẩu thả khi chọn password. Đơn giản là vì có quá nhiều nơi cần có password: một tá email accounts miễn phí, vài chục tệp doc nhật ký, account ở trường, ở chỗ làm, ở nhà, account ở vài tá websites về ngân hàng, mua vé máy bay, khách sạn, ... Hoặc là người ta ghi lại hết các passwords này ở một chỗ (trong cái PDA chẳng hạn), đi đâu cũng mang theo, hoặc có một vài password dùng tất cả mọi nơi, có nghĩ là bị mất 1 password thì mất nhiều account.

Bill Gates có đề nghị đơn giản: dùng hai dạng identifications như các thẻ nhà băng. Một là cái thẻ, hai là cái password cho cái thẻ. Thẻ nhà băng ít có vấn đề trong mấy chục năm nay. Thẻ thông minh (smart card) là một hiện thực hóa của ý kiến này. Vấn đề là mất thẻ thì ... phiền to.

Vậy có cách nào chứng minh cho một hệ thống máy tính biết "ta là ta" mà không phải phụ thuộc vào các thiết bị vật lý không? Hai điều kiện tiên quyết phải là: (a) khó giả, và (b) nhanh chóng. Đến đây thì sinh trắc học dường như là một giải pháp hợp lý. Dùng dấu tay thay cho password chẳng hạn. Nếu một dấu chưa đủ thì dùng cả ngón trỏ và ngón cái, hay cả 10 ngón. Nhưng như thế thì quá phiền và cũng khá dễ giả, ai có truy cập đến cái bàn mà ta hay ngồi viết là có thể lấy dấu tay. Đấy là chưa nói đến việc các phần mềm nhận dạng dấu tay hiện nay vẫn còn sai số khỏang 2 đến 3 phần trăm. Nếu muốn giảm sai số thì phải chờ lâu hơn. Hay ta dùng cả dấu mắt, DNA, khuôn mặt, ... ? Có các vấn đề nhức đầu về privacy ở Mỹ nếu nhà nước có identification của công dân.

Năm ngoái có một quảng cáo rất tếu của một công ty bảo mật ở Mỹ. Trong quảng cáo có một anh chàng bứt sợi tóc cuối cùng trên đầu mình để đưa cho máy tính làm identification.

Cân bằng giữa sức mạnh của một hệ thống bảo mật và privacy là một đề tài nghiên cứu quan trọng, thực tế, và thú vị.

Từ spam đến spim

 

Hiện nay cứ 10 emails thì có đến gần 9 emails là spam (xem thống kê). Đây là vấn đề nhức đầu cho các nhà quản lý mạng. Ngoài chuyện phiền toái cho người dùng: xóa spam-mails, bị virus, mất thì giờ và cả tiền bạc, thì spam emails làm giảm đáng kể hiệu suất sử dụng mạng.

Nay lại có cả spim, một dạng spam cho các dịch vụ intant messenger. Một bài mới ở security focus có bình luận khá hay về spim và luật lệ liên quan đến spim và spam.

Spim và spam là ví dụ rất tốt của cái gọi là "luật hậu quả ngoài ý muốn" (law of unintended consequences). Khi thiết kế các chương trình, dịch vụ, giao thức mới cho các hệ thống máy tính, người thiết kế thường nghĩ đến sự hữu dụng của các chức năng mà ít chú ý đến khả năng chúng bị lạm dụng. Các chức năng nằm trong bản thiết kế thì dễ kiểm tra, các chức năng nằm ngoài ý muốn thì khó khám phá hơn nhiều.

Tôi không biết có ai nghiên cứu về việc xem bản thiết kế hệ thống và liệt kê các khả năng người ta có thể lạm dụng nó không. Đề tài này rất đáng một luận án tiến sĩ.