Blog Khoa Học Máy Tính

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.

Chủ đề: Bảo mật và mật mã học & Lý thuyết tính toán | Bình luận »

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 (q) ((lambda (x) `((lambda (q) ,((eval q) x)) ',q))
                '(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
   '(lambda (x) `(,x ',x)))
  

• Perl:

  #!/usr/local/bin/perl
  
  $a='#!/usr/local/bin/perl%c$a=%c%s%c;printf($a,10,39,$a,39,10);%c';printf($a,10,39,$a,39,10);
  

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?
2. Các chương trình lọai này có ứng dụng gì không?

Chủ đề: Bảo mật và mật mã học & Lý thuyết tính toán | Bình luận (1) »

Ở cuối quyển “Các cuộc phiêu lưu của một nhà toán học“, nhà toán học Stan Ulam (1909-1984) có nhắc đến bài toán 20-câu hỏi nổi tiếng: giả sử anh A nghĩ trong đầu một số nguyên từ 1 đến 1 triệu, anh B phải hỏi bao nhiêu câu hỏi nhị phân (nghĩa là chỉ trả lời có hoặc không) để đoán được bí mật này?

Giả sử anh A nghĩ một số từ 1 đến n, dễ thấy rằng phương pháp tìm kiếm nhị phân có thể áp dụng được ở đây. Anh B hỏi: “số anh nghĩ có phải từ 1 đến n/2 không?”, nếu có thì ta chia đôi đọan [1,n/2], nếu không thì ta chia đôi đọan [n/2+1, n], vân vân.

Bài toán căn bản này có nhiều biến thể khó, thú vị, và có rất nhiều ứng dụng: từ sàng DNA (DNA screening), thử máu, nghi thức giải quyết tranh chấp trong mạng máy tính (conflict resolution protocol), đến tăng hiệu suất hệ thống mạng (xem tin), vân vân.

Các điều kiện sau đây, hoặc một tập con của chúng, dẫn đến các câu hỏi toán học thú vị có tính ứng dụng cao:

1. A nghĩ trong đầu d số thay vì 1 số.
2. B phải hỏi tất cả các câu hỏi cùng một lúc, và dựa trên tất cả các câu trả lời đoán (các) bí mật của A.
3. A có thể trả lời dối vài lần.
4. Có một xác suất nhất định là A sẽ nghĩ một số.

Ví dụ: trong thời thế chiến thứ hai, khi thử máu cả trăm nghìn lính xem những ai trong đó bị một bệnh nhất định (lúc đó giang mai - syphilis - là đối tượng chính), người ta thường phải bỏ một tập con các mẫu máu vào một hợp chất hóa học. Nếu hợp chất có phản ứng (đổi màu chẳng hạn), thì trong tập con các mẫu máu đó có ít nhất một mẫu bị bệnh.

Các tập con mẫu máu này là các câu hỏi nhị phân. Các tập con phải được thiết kế trước, vì ta không thể lấy mẫu một nửa số lính, rồi tùy theo kết quả thử lấy nửa số khác hoặc chia đôi số đã lấy. Việc thiết kế trước các tập con này chính là biến thể số 2 nêu trên. Rõ ràng là tổng số “bí mật” (trong trường hợp này là số lính bị bệnh) nhiều hơn một (biến thể số 1). Ngoài ra, ta cũng không biết có nhiều nhất bao nhiêu lính bị bệnh, cho nên có thể phải tìm một xác suất bệnh (biến thể thứ 4). Các hợp chất có thể có phản ứng sai do mẫu máu không tinh khiết (biến thể thứ 3). Hiển nhiên là vì máu có hạn, nên ta phải tối ưu tổng số phép thử (đồng nghĩa với tối ưu tổng số câu hỏi).

Các bài toán này thuộc về nhánh nghiên cứu gọi là “thử nhóm” (group testing), một đề tài rất thú vị. Bạn xem thêm bài survey tôi viết đã lâu, và một bài báo khác tôi thiết kế một giải thuật như vậy.

Chủ đề: Lý thuyết thông tin & Nghiên cứu nghiên kiếc & Vui - Giải Trí | Bình luận (1) »

Hiện nay có lẽ SPAM là vấn đề lớn nhất và email có lẽ là một trong những phần mềm phổ dụng nhất hiện nay. Việc lọai bỏ SPAM là cuộc chiến không ngừng giữa người gửi và người viết phần mềm lọai bỏ SPAM (vì hiện nay và sắp tới khó có bộ luật nào có thể lọai bỏ hòan tòan vấn đề này). Hiện nay có ba cách có lẽ là hiệu quả nhất để lọai bỏ SPAM:

Cách thứ nhất là dùng kỹ thuật machine learning để học thư nào là thư tốt và thư xấu , cách này có cái dở là những người gửi SPAM tìm mọi cách thay đổi cấu trúc của SPAM mails liên tục để lừa các công cụ lọc. Do đó, dù các phần mềm có tốt đến đâu cũng không thể lọai hết các spam mails.

Cách thứ hai dùng Turing test để kiểm tra xem nguồn gửi thư là máy hay người (ví dụ: gửi lại người gửi thư một bức ảnh có các chữ đảo ngược, giống phương pháp Yahoo mails dùng để chống phần mềm tự động lấy accounts của họ, và chỉ cho thư qua khi người gửi đã vượt qua bài thử này. Cách này cũng có cái dở là sẽ rất phiền cho người gửi vì sẽ luôn phải xác nhận cho thư họ đã gửi đi. Ngòai ra, cũng có vấn đề với nhiều thư hữu ích mà lại do phần mềm tự động gửi đi.

Cách thứ ba là đánh vào hầu bao của spammer. Hiện nay, chi phí gửi một thư spam chỉ khỏang 0.01 cent hay 0.00001 USD. Như vậy, nếu gửi 10000 thư mà có một người mua sản phẩm qua spam mail thì thường đã rất lãi rồi. Để tăng chi phí cho người gửi spam, có thể áp dụng phương pháp là nếu đến tay người nhận thì người gửi phải mất tiền “tem” (postage). Cách khác là không đánh vào việc tốn tiền mà phải tốn thời gian chạy máy . Nếu một cái thư phải tiêu hao năng lượng máy tính nhiều hơn bây giờ thì sẽ gây khó khăn cho việc gửi hàng trăm ngàn thư rác từ một máy trong một ngày.

Còn một cách khác nữa mà khó khả thi hơn là đánh vào người đọc thư rác ;). Lý do là nếu không có ai đọc thư rác nữa thì nó sẽ tự mất đi. Ông Joshua Goodman (Microsoft Research) trong buổi nói chuyện gần đây nói rằng ông đề nghị người quản lý hotmail đóng cửa tất cả các hòm thư tại Hotmail nếu người dùng account đó click vào thông tin trong thư rác (nhưng tất nhiên yêu cầu đó đã bị từ chối)

Chủ đề: Bảo mật và mật mã học & Xác suất & thống kê | Bình luận »

Khoảng 10 năm trước, một nhóm các khoa học gia máy tính đầu ngành bao gồm cả các tên tuổi lớn như Richard Karp, Alfred Aho, David Johnson, và Christos Papadimitriou viết một báo cáo với tựa đề “Lý thuyết tính toán: mục tiêu và hướng đi” với dự định giới thiệu hướng nghiên cứu và mục tiêu cho toàn ngành. Trong thời gian đó (và đến nay), tiền dự án nghiên cứu cho nhóm lý thuyết tính toán không còn được nhiều như xưa, các sinh viên làm về lý thuyết tính toán tìm việc cũng khó hơn so với thời gian từ 1965 đến 1995. Báo cáo này đề nghị mọi người tìm cách hợp tác nhiều hơn với các nhánh khác của khoa học máy tính, các nhánh ứng dụng của khoa học máy tính (applied computer science), vân vân.

Có rất nhiều khoa học gia về lý thuyết tính toán không đồng ý với các điểm cơ bản trong báo cáo này, trong đó có giáo sư Goldreich (lúc đó đang ở MIT) và tiến sĩ Avi Wigderson (hiện ở khoa toán viện IAS [nơi Einstein làm khi xưa]). Goldreich và Wigderson viết một bài rất hay, bác cáo ở hội nghị STOC 1996 và đăng trong journal ACM Computing Surveys cùng năm, với tựa đề “Lý thuyết tính toán dưới góc nhìn khoa học“.

Ngoài hai báo cáo trên, có một workshop của NSF bảo trợ năm 1999 cũng ra một báo cáo trong tinh thần của đề tài này. Giáo sư Alan Selman của khoa tôi là một trong 14 người tham gia workshop này. Tham gia workshop còn có cả Richard Karp (!) và các tên tuổi lớn khác như Micheal Rabin (Harvard), Eva Tardos (Cornell), Richard Lipton (Princeton), v.v. Alan cho tôi biết các người tham dự workshop đã tránh các sai lầm trong báo cáo của Aho et al. lần đầu.

Tiến sĩ David Johnson của AT&T cũng đang viết một báo cáo với tựa đề “các thách thức cho khoa học máy tính lý thuyết“.

Chủ đề: Chính trị trong ngành & Lý thuyết tính toán | Bình luận »

Trong khoa học máy tính, bài báo ở các hội nghị chuyên ngành danh tiếng đóng vai trò rất lớn trong sự nghiệp của các khoa học gia. Được nhận đăng bài ở một số hội nghị hàng đầu khó hơn ở nhiều journals có tiếng. (Xem thêm bài “tản mạn về mảnh bằng Ph.D” tôi viết vài năm trước.) Trong lý thuyết tính toán và giải thuật, ta có STOC, FOCS, SODA; trong cơ sở dữ liệu có SIGMOD, trong datamining có KDD, trong mạng máy tính có INFOCOM, SIGCOMM; vân vân. (Danh sách này không nhất thiết là đủ, nhưng khá đặc trưng cho các ví dụ này.)

Ở nhiều ngành khác (như toán, lý, xã hội học, …) thì các journal papers giá trị hơn nhiều so với các conference papers. Ví dụ: các nhà toán học thường là không ghi các báo cáo ở hội nghị vào trong danh sách bài báo của họ.

Có vài nguyên do của sự “tréo ngoe” này trong ngành khoa học máy tính. Thứ nhất, KHMT phát triển cực nhanh trong vài thập niên gần đây, phần vì nó còn rất trẻ so với các ngành khác. Chờ khi công trình của mình được nhận đăng ở một journal (mất khoảng 1-2 năm) thì kết quả đó đã lỗi thời, thậm chí bản thân tác giả có khi cũng không thích thú gì lắm với nó nữa vì đã có những kết quả tốt hơn trong cùng thời gian. Vòng quay của các hội nghị tốn khoảng 6 tháng (từ khi nộp đến khi đi báo cáo). Thứ hai, đây cũng là vấn đề “văn hóa” của ngành. Thứ ba, hội nghị là một trong những phương tiện tốt nhất để mọi người làm quen, tìm hiểu nghiên cứu của nhau, tìm cơ hội hợp tác nghiên cứu, giới thiệu công trình của mình với thế giới các đồng nghiệp.

Các sinh viên, nhà nghiên cứu, giáo sư nào chưa có bài trong hội nghị lớn của ngành mình thì nói chung là kẻ ngoài cuộc, nghiên cứu không ai biết tới, và sẽ xa rời dòng chảy chính của các nghiên cứu trong ngành. Các bài báo này còn được dùng làm tiêu chí xét tenure, nhận giáo sư mới, thăng cấp giáo sư, vân vân.

Thế làm thế nào để biết là một hội nghị là “có giá” hơn các hội nghị khác? Dĩ nhiên người trong ngành sẽ biết (dù có thể hơi chủ quan nếu có hơn một hội nghị hàng đầu). Người ngoài ngành thì … hỏi người trong ngành. Nếu không có ai để hỏi thì có thể tìm danh sách xếp hạng (ranking) các hội nghị (các danh sách loại này, dù là dựa trên chỉ số nào, cũng đều chủ quan và thiếu giá trị khoa học). Một cách nữa người ta cũng làm là nhìn vào tỉ lệ nhận bài của các hội nghị và danh sách các thành viên trong ủy ban chương trình kỹ thuật của hội nghị (technical program committee, hay TPC).

Thành viên TPC là những người sẽ đọc và quyết định bài nào được nhận, bài nào không. Ở các hội nghị lớn thì chất lượng TPC khá tương đồng. Như vậy chỉ số còn lại là tỉ lệ nhận bài (acceptance ratio). Thế tỉ lệ nhận bài thấp có đồng nghĩa với giá trị cao của hội nghị không? Graham Cormode, Artur Czumaj, và Muthu Muthukrishnan có một bài rất khôi hài (nhưng nghiêm túc) về các hội nghị trong khoa học máy tính và tỉ lệ nhận bài của chúng. Vấn đề chính họ muốn giải quyết là làm thế nào loại nhanh các bài báo tồi để các thành viên TPC đỡ mất thời gian.

Quay lại với câu hỏi trên. Câu trả lời dứt khoát là không. Đồng ý là có một tương quan nhất định giữa tỉ lệ nhận bài và giá trị hội nghị. Hội nghị nào (trong KHMT) có tỉ lệ nhận 50% hay nhiều hơn thì ta có thể tự tin kết luận là hội nghị thường thường bậc trung. Phần còn lại thì rất khó nói. Những năm gần đây, MOBICOM nhận khoảng 8% đến 10%, INFOCOM nhận khoảng 16% đến 18%, còn STOC, FOCS, SODA nhận khoảng 25%-35%. Khó mà nói cái nào giá trị hơn cái nào trong các hội nghị trên, một phần vì chúng ở các nhánh khác nhau.

Lấy STOC và MOBICOM làm ví dụ. Đăng bài trong STOC rất khó, dù tỉ lệ nhận cao hơn MOBICOM khá nhiều. Một lý do là người ta thường không nộp các bài vớ vẩn vào STOC nữa. Ngoài ra chuyện này còn liên quan đến bản chất của ngành nghiên cứu. STOC là hội nghị về lý thuyết, kết quả tốt xấu khá rõ ràng. Ở các hội nghị đăng cả các bài báo thực nghiệm (simulation, experimentation) như mạng máy tính hay datamining thì kế quả không rõ ràng như thế, và sẽ có nhiều chỗ trống hơn cho các bài báo linh tinh. (Dù rằng các hội nghị danh tiếng thường chỉ đăng các bài có cơ sở lý thuyết vững chắc; phần simulation chỉ mang tính xác minh.)

Chuyện dài nhiều tập này xứng đáng vài posts nữa.

Chủ đề: Chính trị trong ngành & Các hội nghị KHMT & Dành cho du học sinh | Bình luận (6) »

Cố giáo sư Edsger W. Dijkstra có rất nhiều bản thảo, bài viết, bài nói, được lưu trữ thành một thư khố. Các bài được đánh số từ EWD 0001 đến EWD 1318. Ông viết về rất nhiều đề tài khác nhau. Bản thảo EWD 1175 với tựa đề “Sức mạnh của tổ chức hàm lâm” có nhiều điểm thú vị.

Ông mở đầu bài viết với thống kê: từ năm 1530 đến nay, có 66 tổ chức giữ được các đặc trưng mà đến nay ta vẫn có thể nhận ra chúng, trong đó có tòa thánh Roman Catholic, tòa thánh Lutheran, nghị viện Iceland, và Isle of Man. Điểm cực kỳ thú vị là: 62 tổ chức còn lại đều là các trường đại học. Điều này cho thấy các trường đại học có tiềm lực cực lớn cho sự bền lâu.

Dijkstra sau đó bàn đến những điểm căn cốt mà ta phải giữ để “nuôi” sự bền vững của môi trường hàn lâm. Ông từ chối thảo luận về môi trường đại học dưới góc nhìn tài chính, cho rằng tâm lý “kinh tế hóa” các thảo luận là một thứ bệnh cần phòng chống.

Tôi tóm lược ra đây vài điểm mà tôi thấy hay từ bài của ông:

• Môi trường trí thức trong khuôn viên đại học là môi trường của các tinh thần không ngừng nghỉ (restless mind). Trong khuôn viên đại học thì sự lỗi lạc được chấp nhận xã hội (socially acceptable), điều này thường là không đúng ở “ngoài đời” - nơi mà sự tuân thủ (conformity) thường được xã hội chấp nhận dễ dàng hơn. Môi trường đại học là nơi dễ dàng chấp nhận nhất các ý tưởng mang tính cách mạng.
• Môi trường đại học không chỉ là nơi cư ngụ của các tinh thần không nghỉ, mà còn là nơi bảo lưu (reservation) của các tinh thần đó. Khuôn viên đại học không chỉ “bảo vệ” các tinh thần này khỏi thế giới bên ngoài, mà còn bảo vệ thế giới bên ngoài khỏi chúng!!!
• Môi trường đại học không chỉ là nơi mà sự công khai (openness) và sự trung thực (honesty) được (và phải được) dung dưỡng, nó còn là nơi bảo bọc các phấn đấu không ngơi nghỉ đến sự hoàn hảo (ruthless striving for perfection). Về mặt hàn lâm, không có lý do hợp lý cho sự thỏa hiệp.

Đến đây, tôi chợt nhớ đến hiệu trưởng Larry Summers của đại học Harvard và bình luận gây tranh cãi rùm beng gần đây của ông về khả năng của phụ nữ trong các ngành kỹ thuật và khoa học. Các tranh cãi - nhiều khi khá thiếu văn minh này - trên các phương tiện truyền thông và từ cả các giáo sư khả kính, cho thấy môi trường hàn lâm còn xa mới đạt đến viễn cảnh của Dijkstra.

Tôi rất tâm đắc với bốn thứ phải được dung dưỡng trong môi trường đại học: “sự lỗi lạc”, “sự công khai”, “sự trung thực”, và “sự phấn đấu không nghỉ đến tính hoàn hảo”. Có lẽ lần sau ta sẽ nghĩ thêm về việc làm thế nào có thể đạt được các điều này trong bối cảnh một đại học ở Việt Nam.

Chủ đề: Giáo dục & Nhân vật và sự kiện | Bình luận »

Ở hội nghị INFOCOM vừa qua có một cuộc hội thẩm (panel) về truyền thông nano (nano-communications, dùng để chỉ dạng truyền thông ở tầm vực cực bé). Các hội thẩm viên bao gồm các giáo sư Tatsuya Suda (University of California, Irvine), Ron Weiss (Princeton University), Kamal Abdali (National Science Foundation), các tiến sĩ Satoshi Hiyama (NTT DoCoMo, Japan), và Kazu Oiwa (NICT, Japan).

“Truyền thông nano” dùng để chỉ việc làm sao truyền thông tin bằng các phân tử, vi sinh vật, … dùng các phản ứng sinh hóa (như tín hiệu Ca2+). Để so sánh truyền thông bình thường và truyền thông nano, ta có thể so sánh sóng điện từ và các phân tử, tín hiệu điện và tín hiệu sinh hóa, tốc độ ánh sáng và tốc độ cực chậm trong môi trường sinh hóa, hình ảnh/âm thanh và các trạng thái hóa học. Trong truyền thông nano có các phân tử thông tin như DNAs, proteins, ions, …, và các phân tử tải thông tin (carrier) như rail molecules, hormones, …

Ứng dụng của truyền thông nano khá rộng, từ các máy nano đến các hệ thống chuyển giao DNA và truyền thuốc bằng các tế bào.

Các đề tài nghiên cứu trong truyền thông nano gồm có: (a) thiết kế các phân tử phát (transmitter), phân tử thu (receiver), phân tử tải (carrier); (b) làm thế nào để mã hóa thông tin với các phân tử; (c) làm thế nào có thể điều khiển được việc phóng (emit) thông tin; (d) làm thế nào để nạp thông tin vào trong các phân tử; (e) làm thế nào để lấy thông tin ra khỏi các phân tử; (f) làm thể nào để giải mã thông tin; (g) làm thế nào để dùng lại (recycle) các phân tử thông tin; vân vân.

Bài nói hay nhất (có cả demo) là của Ron Weiss, một giáo sư trẻ của khoa điện tử trường đại học Princeton. Nghiên cứu của Ron là làm thế nào để lập trình các tế bào dùng cho kỹ thuật mô (tissue engineering), biofabrication, biosensing, và nói chung là để hiểu biết các quá trình tự nhiên. Về căn bản, Ron đã có thể thiết kế một số mạch logic (logical circuit) sinh học, theo kiểu các mạch số and/or thông thường.

Các demo nhỏ trong panel này làm tôi tin tưởng hơn vào cái gọi là DNA computing, dù không biết gì về sinh học và hóa học.

Chủ đề: Các hệ thống máy tính & Các hội nghị KHMT & Mạng máy tính | Bình luận »

Tôi không phải là người chơi game nhiều đã khá lâu rồi, nhưng nếu có thời gian để chơi game, chắc tôi sẽ chọn Second Life, đã được người thiết kế và viết chính Cory Ondrejka giới thiệu ở PARC gần đây . So với các game nhập vai và nhiều người chơi (multi-user) khác thì Second Life còn tương đối mới, nhưng nếu thăm website của game này sẽ thấy là nó đã được viết trên rất nhiều tờ báo nổi tiếng .

Vậy cái gì làm nên sự hấp dẫn của Second Life, cái chính là ở đó người chơi có thể làm gần như tất cả các thứ mà họ có thể tưởng tượng và muốn làm ở thế giới thực . Hầu hết các trò chơi online hiện nay thì người chơi sẽ hóa thân thành một nhân vật anh hùng, vào một thế giới được tạo ra trước bởi người viết game và thường là tham gia các cuộc chiến đấu . Trong Second Life, ngươi viết game chỉ định ra các yếu tố vật lý của thế giới và tất cả các vật thể trong thế giới đó hoàn toàn được tạo ra bởi người chơi , miễn là các vật thể đó tuân theo các nguyên tắc vật lý của thế giới ảo (digital world) đó. Người chơi hoàn toàn có thể tạo hình ảnh nhân vật của mình một cách tùy thích (sửa khuôn mặt, mầu da, quần áo etc). Khi mới vào, người chơi sẽ chỉ có nhân vật ảo của mình, nếu có tiền, anh ta có thể mua một mảnh đất, mua các dụng cụ và làm bất cứ cái gì trên mảnh đất của anh ta như xây nhà, tạo công xưởng sản xuất ôtô, mở lớp dạy nhạc, mở sàn nhảy, cùng các bạn tạo ra một thế giới nhỏ của mình trong một quần thể xã hội lớn hơn. Nếu không có tiền, người chơi vẫn có thể đến thăm tất cả các nơi mà người sở hữu mảnh đất nơi muốn đến cho phép .

Nếu thế giới trong Second Life không khác gì và mô phỏng nhiều thế giới thực, thì có cái gì hay mà làm cho số người chơi tăng với tỷ lệ 15% mỗi tháng như vậy? Hãy quên chuyện sản xuất tàu con thoi bay vào vũ trụ (mặc dù điều đó hoàn toàn làm được trong Second Life), tưởng tượng bạn là người yêu thích làm các mẫu ôtô, nhưng ở ngoài để lắp được một cái ôtô như ý muốn cần rất nhiều thời gian và công sức . Trong Second Life, bạn có thể mua các bộ phận (chế tạo bởi các thành viên khác) hoặc tự chế tạo chúng, sau đó lắp thử và chạy, nếu không đồng bộ thì chỉnh sứa, sau đó đem chạy thử trong Second Life và tham khảo ý kiến cúa các thành viên khác . Nếu nhiều người thích, bạn có thể bán kiếm tiền , hoặc quyết định chế một cái tương tự ngoài thế giới thực. Toàn bộ công đoạn chế tạo và chạy thử ở trong thế giới ảo chỉ mất vài tuần, nhưng có thể giúp ích rất nhiều trong việc chế tạo thật bên ngoài. Hiện nay, theo Cory thì có rất nhiều người đã sống bằng việc chế tạo các sản phẩm, mở lớp dạy học trong Second Life và bán lại cho các thành viên khác. Có nhiều người Linden Lab mời vào làm và tham gia phát triển Second Life, nhưng họ từ chối vì kiếm tiền trong digital world còn nhiều hơn trong real world. Hiện nay hàng tháng số sản phẩm, dịch vụ trao đổi qua lại trong thế giới ảo này là hơn 1 triệu USD.

Ngoài những người bình thường vào chơi, học tập, hoặc để sáng tạo ra thế giới ảo riêng của họ, có cả nhiều trường đại học mua cả một số hòn đảo trong Second Life để làm một thí nghiệm về giao tiếp giữa con người. Điều đó cho thấy thế giới ảo thực sự có thể vượt xa ra ngoài lĩnh vực giải trí. Trên thực tế, khi tôi vừa vào lại trang web của Linden Lab thì thấy có tin nói là có một trò chơi (game) được phát triển trong Second Life để phục vụ nhóm người trong đó đã rất thành công và được bán bản quyền ra ngoài để sản xuất game cho người chơi ở thế giới thực. Một điều đặc biệt là những thứ tạo ra trong thế giới ảo này có thể được cấp bằng phát minh sáng chế và thu tiền từ việc license nó cho cả thế giới ảo và thế giới thật

Một câu hỏi được đặt ra trong buổi nói chuyện là “nếu thế giới ảo này hoàn toàn được tạo ra bởi các thành viên, thế thì ai là người làm ra luật lệ và quản lý thế giới này ?” Theo tôi hiểu thì người viết game có thể là super-user, nhưng không có ai quản lý thế giới này cả mà chỉ có một số luật cơ bản như “không giết được người khác” “không ăn cắp được của người khác” (nhưng Cory cũng nói là đối với các thành viên thích “chiến đấu” thì có riêng một hòn đảo mà ở đó được bắn giết nhau thoải mái. Hơi tiếc là không trả lời được rõ ràng câu hỏi là nếu một người chẳng may vào chơi ở shooting zone và bị bắn chết thì sẽ thế nào.)

Kết luận là tôi thấy second life là một ý tưởng rất hay, khác với Sim City trong đó thế giới được tạo bỏi nhân vật ảo và người chơi như chúa trời, thế giới trong second life được tạo hoàn toàn bỏi từng cá thể và sự tưởng tượng phong phú của họ . Second Life hơn Matrix ở điểm mọi người đều có thể là Neo nếu trí tưởng tượng của họ cho phép, nhưng thế giới ảo này cũng không bao giờ được như thật. Ngoài chuyện không thể ăn miếng thịt bò trong digital world mà thấy ngon, còn nhiều vấn đề mà các nhà phát triển game muốn làm cho nhân vật ảo giống thực còn rất khó . Ví dụ như ngoài đời, con người rất giỏi trong các buổi gặp gỡ trong chuyện nhận biết nét mặt, ánh mắt của người tham gia, trong một đám đông biết cách nói chuyện với người đứng gần, loại bỏ các tạp âm từ ngoài, nhưng cũng vẫn lọc ra được các thông tin quan trọng qua âm thanh, hình ảnh từ xa. Điều đó cho vào thế giới ảo như Second Life không phải dễ và còn rất nhiều vấn đề cần nghiên cứu chung giữa khoa học máy tính và các ngành khác (ví dụ: nghiên cứu về giao tiếp trong xã hội).

Chủ đề: Games | Bình luận (4) »

Hội nghị Infocom năm 2005 tổ chức ở Miami, Florida. Một trong hai bài nói chính (keynote speeches) là của tiến sĩ Hossein Eslambolchi, giám đốc nhánh dịch vụ kỹ thuật mạng toàn cầu của AT&T (President of AT&T’s Global Networking Technology Services (GNTS). Ông cũng là CTO và CIO và giám đốc của AT&T Labs.

Eslambolchi nói về cái nhìn tổng thể của ông và của AT&T về các xu hướng kỹ thuật mạng và máy tính trong tương lai gần trên toàn thế giới. Mười xu hướng chính bao gồm:

10. Các mạng cục bộ tại gia (Home LANs) sẽ lan tràn.

9. Khai thác thông tin (information mining) là quan trọng. Ông phân biệt khai thác dữ liệu (data mining) và khai thác thông tin như một tầm mức cao hơn của khai thác dữ liệu. Hiện nay số lượng dữ liệu và thông tin mà AT&T hàng ngày vận chuyển qua mạng của họ là cực kỳ lớn. Ông muốn các thông tin này được dùng để xây dựng các mạng máy tính thông minh hơn.

8. Sự hội tụ của các mạng có và không dây.

7. Các dịch vụ broadband sẽ cực kỳ phổ biến trên thế thới. Một điểm thú vị là định nghĩa về “broadband” ở Mỹ và Nhật/Âu khác nhau. Ở Mỹ chỉ cần cable/dsl với khoảng 1-2Mbps thì đã được gọi là broadband, trong khi xu hướng ở Nhật thì broadband phải đến 25Mbps trở lên.

6. Tính địa phương (locality) sẽ dần biến. Hiện nay các địa chỉ IP vẫn còn có thể được dùng để tìm địa chỉ địa lý, điều này sẽ biến dần trong thời gian không xa. Máy laptop và các thiết bị di động (mobile devices) khác sẽ giữ nguyên một IP bất kể chúng đang ở đâu.

5. Các mạng cảm biến (sensor networks) sẽ lan tràn. IP phiên bản 6 (IPv6) sẽ phải được phổ biến, để ít nhất là theo kịp với sự bùng nổ tổng số địa chỉ IP (cho các cảm biến và các thiết bị khác).

4. Các mạng không dây sẽ đóng vai trò then chốt cho truy cập Internet.

3. Các mạng Ethernet sẽ bùng phát khắp nơi (điểm này khác với số 10).

2. Truyền thông (communications) và ứng dụng (applications) sẽ hội tụ. Theo một nghĩa nhất định, người dùng sẽ không còn ý thức được là họ đang dùng một ứng dụng bình thường hay một ứng dụng truyền thông.

1. IP sẽ ăn tất (IP will eat everything!), theo nghĩa như anh chàng PacMan trong trò chơi điện tử nổi tiếng. IP – Interenet Protocol – là giao thức chính để chuyển dữ liệu trên Internet.

“Mạng thông minh”, “mạng quang học” (optical networks), “mạch chuyển gói quang học” (optical packet switches) được nhấn mạnh nhiều lần như các công nghệ trọng tâm của tương lai.

Bờ biển Miami khá nổi tiếng trong giới sinh viên Mỹ. Kỳ nghỉ xuân bọn họ hay xuống đây chơi. Nước biển khá lạnh, nhưng hoàn toàn có thể bơi được. Khí hậu tuyệt vời, là chỗ nghỉ xuân rất tốt.

Chủ đề: Các hội nghị KHMT & Mạng máy tính | Bình luận »

Nhân anh Hưng nói về xuất bản hàn lâm, tôi muốn nhắc tới chuyện giáo sư Jim Pitman và các nhà xác suất học (probabilists) hàng đầu khác đang phát động một dự án lớn về xuất bản on-line. Dự án này gọi là The Mathematics Surveys, với mục đích thiết lập một hệ thống tạp chí on-line lớn cho các ngành hẹp khác nhau của toán học, trong đó có kể cả ngành khoa học máy tính. Hiện tại, dự án được bắt đầu với ngành xác suất (probability and stochastic processes), với hy vọng ý tưởng này sẽ được copy đến các ngành khác trong toán học.

Tạp chí điện tử The Probability Surveys là một sự khởi đầu có triển vọng. Ðiều khác biệt của dự án Mathematics Survey với các tạp chí điện tử khác là ở chỗ, những bài báo sẽ có tính chất survey hơn, và như vậy sẽ có tác dụng rất tốt với những người nghiên cứu ngoài ngành toán muốn ứng dụng các công cụ toán học mới, cũng như những người muốn tìm hiểu ngành hẹp khác nhau nắm bắt và tiếp thu được xu hướng phát triển của nhau.

Như chùm bài về Cantor đã gợi, toán học, đặc biệt là lý thuyết logic và tập hợp, có vai trò nền móng cho sự hình thành của khoa học và công nghệ máy tính. Ngày nay, càng có nhiều ngành trong công nghệ máy tính đòi hỏi các công cụ toán học cao cấp khác, từ xác suất thống kê, hình học topo cho đến lý thuyết tối ưu hóa. Những người học và nghiên cứu lý thuyết khoa học máy tính, lý thuyết thông tin (information theory) và xử lý tín hiệu (signal processing), trí tuệ nhân tạo (artificial intelligence), v.v. chắc chắn sẽ thu lượm được nhiều từ những tạp chí survey điện tử toán học trong tương lai.

Chủ đề: Xuất bản & Xác suất & thống kê | Bình luận »

Có ba khả năng trả lời câu hỏi P chọi NP: (a) P = NP, (b) P chọi NP không quyết định được, nghĩa là độc lập với hệ thống, (c) P = NP hoặc P khác NP tùy theo ta chọn hệ tiên đề nào (tương tự như continuum hypothesis), và (d) P khác NP. (Bài báo của Micheal Sipser [30] là tham khảo tốt cho tình trạng hiện tại của câu hỏi này.)

Nếu (a) đúng thì cả chục nghìn vấn đề NP-đầy đủ có giải thuật đa thức để giải, mật mã khóa công cộng (public key cryptography) là vô vọng, vân vân. Các giao thức (protocol) bảo mật trên Internet hiện nay đều ít nhiều dựa vào mật mã khóa công cộng, nếu P = NP thì các giao dịch tiền tệ trên Internet đều cực kỳ bất ổn. Nếu P = NP thì hàng nghìn hàng vạn các nhà khoa học, toán học, kỹ sư máy tính trong hơn năm chục năm qua đã bỏ qua một ý tưởng căn bản nào đó có thể giải một trong số cả chục nghìn bài toán NP-đầy đủ. Chuyện này quá hy hữu. Vì thế, khả năng (a) rất khó xảy ra.

Các khả năng (b) và (c) liên quan đến trạng thái logic của vấn đề (thay vì tính thuật toán của nó). Scott Aaronson [1] có một bài báo tổng quan rất hay, thảo luận các khả năng này. Kết luận chung là các khả năng này rất khó xảy ra. Một tham khảo thú vị là nghiên cứu của Razborov và Rudich [27] năm 1993, trong đó các tác giả đưa bằng chứng cho thấy: “có lẽ lý do mà chứng minh P != NP rất khó là tại vì … P != NP !!!” Ta sẽ thảo luận kỹ hơn về kết quả “oái oăm” này vào dịp khác.

Như vậy, khả năng cuối cùng là P != NP, và đa số khoa học gia đều tin vào khả năng này. Thế ta phải làm gì nếu P thật sự khác NP? Ta thử liệt kê vài hướng đi hiện nay:

• Có lẽ mô hình máy Turing không phải là mô hình tính toán mạnh nhất. Điều này có nghĩa là ta phải thiết kế các máy tính theo kiểu khác, dựa trên một nguyên tắc hoàn toàn khác với nguyên tắc thiết kế hiện tại (với bộ vi xử lý, bộ nhớ, bus, thiết bị ngoại vi, vân vân). Đã có vài đề cử, trong đó quan trọng nhất là tính toán lượng tử (quantum computing, [25]), và tính toán sinh học (biological computing) [2]. Công trình đột phá của Peter Shor [28,29] cho thấy ta có thể phân tích một số nguyên ra thừa số (factorization) trong thời gian đa thức với một máy tính lượng tử. Bài toán này là một trong số rất ít các bài toán trong NP mà ta không biết là nó ở trong P hay là NP-đầy đủ. Ngoài bài báo của Peter Shor, thật sự vẫn chưa có bằng chứng nào ủng hộ khả năng là ta có thể giải các bài toán NP-đầy đủ trong thời gian đa thức với máy tính lượng tử. Tình hình với máy tính sinh học còn tệ hơn.
• Trong hướng đi thứ hai, ta chấp nhận rằng các bài toán NP-đầy đủ không thể giải được nhanh bằng các máy tính vật lý (bất kể mô hình vật lý nào). Đến đây thì có vài nhánh nghiên cứu khác:
  • Tìm cách hiệu quả nhất (dù là trong thời gian không đa thức) để giải các bài toán này. Các nghiên cứu về quy hoạch nguyên (integer programming) là một ví dụ tốt.
  • Trong thời gian đa thức, tìm lời giải càng gần tối ưu càng tốt. Đây là hướng đi của các giải thuất xấp xỉ (approximation algorithms), một hướng rất quan trọng trong khoa học máy tính hiện đại.
  • Một hướng khác cũng quan trọng không kém là dùng các giải thuật ngẫu nhiên hóa (randomized algorithms). Ta có thể tìm lời giải tối ưu trong thời gian kỳ vọng là đa thức (expected polynomial time), hoặc tìm lời giải với giá kỳ vọng (expected cost) gần tối ưu trong thời gian đa thức.

Tất cả các khả năng và hướng đi trên đưa chúng ta đến các phương trời mới của khoa học máy tính, toán học và vật lý, là các bước tiến quan trọng cho quá trình tìm hiểu vũ trụ và các quy luật hoạt động của tự nhiên (trong đó tính toán là một quá trình căn bản).

Người mở một trong những cánh cửa quan trọng nhất chính là Cantor!

[1] S. Aaronson, Is P versus NP formally independent?, Bulletin of the European Association for Theoretical Computer Science, 81 (2003).

[2] L. M. Adleman, Computing with DNA, Scientific American, 279 (1998), pp. 54–61.

[25] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.

[27] A. A. Razborov and S. Rudich, Natural proofs, J. Comput. System Sci., 55 (1997), pp. 24–35. 26th Annual ACM Symposium on the Theory of Computing (STOC ’94) (Montreal, PQ, 1994).

[28] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), pp. 1484–1509.

[29] _________, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41 (1999), pp. 303–332 (electronic).

[30] M. Sipser, The history and status of the p versus np question, in STOC ’92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM Press, 1992, pp. 603–618.

Chủ đề: Lý thuyết tính toán | Bình luận (2) »

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.

Chủ đề: Xuất bản | Bình luận »

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.

Chủ đề: Lý thuyết tính toán | Bình luận »

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ị.

Chủ đề: Bảo mật và mật mã học | Bình luận »