Hội nghị INFOCOM 2005

 

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.

Lý thuyết tính toán đi về đâu?

 

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

Ai làm nghiên cứu về khoa học máy tính đều rất nên đọc hai báo cáo này và rút ra bài học cho riêng mình.

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

Thế giới ảo trong Second Life

Người viết: Đỗ Bình Minh

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

Truyền thông nano

 

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

Các câu hỏi phỏng vấn (6)

 

16. (Bài toán Monty Hall) Monty Hall làm MC của một trò chơi trên truyền hình. Có ba cái cửa chắn trước người chơi. Đằng sau một trong các cánh cửa là phần thưởng. Bạn chọn một trong ba cánh cửa. Monty Hall xem đằng sau hai cánh còn lại và mở một cửa không có phần thưởng.
    Hỏi: bạn sẽ giữ chọn lựa cũ hay đổi sang cửa còn lại để lấy phần thưởng? Tại sao?
17. Tèo yêu hai cô gái Tấm và Cám. Cả ba sống trên cùng một con đường, Tèo ở đoạn giữa. Các xe buýt đi cả hai chiều của con đường, mỗi chiều một tiếng một lần có xe buýt đến (tốc độ đều). Sáng sáng Tèo ra bến xe buýt và đón xe nào đến trước thì đi về hướng ấy. Sau một thời gian dài thì Tèo đi thăm Tấm gấp ba lần đi thăm Cám.
    Hỏi: sao lại thế được?
18. Có hai xe tải đứng đối diện nhau, cách nhau 100km. Xe 1 có tốc độ 50km/h, xe 2 có tốc độ 30km/h, một con ruồi đậu trên mũi xe 1 bay qua bay lại giữa hai mũi xe với tốc độ 5000km/h. Cả hai xe và con ruồi đều xuất phát cùng một lúc.
    Hỏi: đến khi con ruồi bị đè bẹp gí giữa hai xe (đụng nhau) thì con ruồi bay được bao xa?

Các câu hỏi phỏng vấn (5)

13. Tí ở tầng 3, Tèo ở tầng 33 của một chung cư. Một hôm hứng chí cả hai ra ban công hét lên cùng một lúc.
    Hỏi: ai nghe thấy tiếng của người kia trước?
14. Có 10 đồng tiền, thật có giả có. Cho một cái cân đĩa không có quả cân. Các đồng thật nặng bằng nhau, các đồng giả nặng bằng nhau và nhẹ hơn các đồng thật.
    Hỏi: cân ba lần và chỉ ra các đồng giả.
15. Ba người cần chia một cái bánh sao cho ai cũng thỏa mãn về phần bánh của mình.
    Hỏi: tìm giải pháp chia bánh với giả thiết ai cũng tin rằng mình cắt bánh công bằng.

Mở rộng Các câu hỏi phỏng vấn

 

 

Nhân tiện đọc bài về mấy câu phỏng vấn của MS của anh Hưng, em nghe giang hồ đang "chửi" nhau ầm ầm về cách tuyển người của MS. Mấy hôm trước ở CNet có bài Microsoft's personnel puzzle (link1). Đại để là chỉ trích MS về cách tuyển người kiêu ngạo. Theo bài báo đó thứ tự xếp hạng của MS trong 100 Best Companies to Work for in America tụt từ thứ 8 năm 98 xuống 57 vào năm nay.
Nhân cái bài báo đó mà bên Slashdot dân tình nêu mấy ý kiến khá là hay trong đó có một bài của 1 anh tự xưng là cựu cán bộ MS
Anh này phân tích 2 điểm lợi trong cách tuyển người của MS. Thứ nhất là tạo cơ hội công bằng cho tất cả mọi người không phân biệt xuất thân từ trường xịn hay trường thấp. Thứ hai và quan trọng nhất là tìm ra được người thực sự có thể làm được việc và đóng góp cho cty.
Hai điểm tai hại của cách tuyển dụng này là nó được áp dụng cho toàn bộ cty điều này sẽ không thích hợp cho một số công việc ko cần kiến thức công nghệ sâu. Thứ hai là cách làm này áp dụng cả cho những cán bộ đang làm việc cho MS, tức là nếu chuyển sang nhóm khác thì cũng phải interview như người bình thường.

Mà để đối phó với các câu hỏi của MS cũng không phải là khó lắm. Có quyển "How Would You Move Mount Fuji?" là cẩm nang ôn tập trước phỏng vấn :-). Với lại gú gồ cũng ra khối câu trả lời.

Năm ngoái em có được tham gia phỏng vấn của Google với MS. Em thấy Google còn khiếp hơn MS. Em bị quay 2h với 2 người mỗi người 1h. Toàn technical questions, với viết code lên trên bảng luôn. Được cái Google cho bọn được mời đến phỏng vấn 1 bữa ăn thịnh soạn :-)). MS thì phỏng vấn online luôn, dùng cái MS Online Meeting thì phải. Cũng code online luôn cho người ta xem. Nói chung là mấy cái trò phỏng vấn đấy căng thẳng bỏ xừ.

Em nghĩ là cách làm của MS phù hợp nếu MS muốn tuyển software developer. Cứ lập trình siêu, tư duy tốt, thông minh thì phù hợp với job đó. Chẳng cần phải PhD làm gì cả. Nếu như có PhD thì có khi là xin làm ở MS Research thì phù hợp hơn.
 

Bản thảo EWD 1175

 

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.

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

 

Thời đại chúng ta: 1999-2005: Web có mặt ở khắp mọi nơi, Sự quá tải rất rõ ràng, Tập trung về các mô hình

Có một số người nhất trí cho rằng trong vài năm tới hiện tượng nổi bật nhất trên nền nhận thức sẽ là những hạn chế về khả năng của con người trong việc giải quyết những rắc rối leo thang của các tình huống chúng ta gặp phải. Điều này được đặc trưng bởi lượng thông tin khổng lồ sẵn có, tuy nhiên cấu trúc nhỏ bé đã giúp cho việc chưng cất sự chi tiết hoá thành những khối tập hợp dễ tiêu hoá và các mối quan hệ có thể hiểu được. Dưới những điều kiện như vậy, các quy trình quản lý truyền thống bị phá bỏ, và các doanh nghiệp tiến hành các hướng hành động mà có khả năng thành công, dù nó không tốt hơn là cơ hội.

Thực chất, vấn đề này có thể coi như một sai sót trong khả năng của con người  trong việc giành được hay phát triển các mô hình của một tình huống phức tạp một cách thích đáng. Vì vậy theo sau nó là: một câu trả lời tiềm tàng nằm trong việc phát triển khả năng đó. Điều này sẽ đòi hỏi phải phát triển một vốn từ vựng được mô hình hoá và phát triển môi trường đáp ứng vài đặc trưng như sau:

Cho phép mọi người đọc và viết ra được các mô hình để trao đổi với một môi trường cục bộ xa xôi một cách nhanh hơn.

Cho phép các cơ quan thần kinh phát triển và giao tiếp một cách phong phú về các hình thức chia sẻ với mỗi người khác. (chẳng hạn, đã từng xảy ra trong những tên miền thiết kế bị giới hạn).

Tạo điều kiện thuận lợi cho các hình thức trao đổi một cách công khai - để mọi người có thể thu được các hình thức trao đổi đã được tập hợp lại (và đóng góp cho những cải tiến một cách hợp lý).

 

Trong tương lai xa (?)

Đó dường như là một sự thoả thuận nào đó giữa các nhà tương lai học mà một hoặc cả hai viễn cảnh dưới đây sẽ xuất hiện. Đồng thời cũng có nhiều sự bất đồng quan điểm, mặc dù có vẻ như có nhiều người quả quyết rằng điều đó có thể xảy ra vào đầu năm 2030. Có vẻ như là lỗi thời khi đưa ra giả thuyết là "có thể phải mất ít nhất 1000 năm nữa".

Một mối liên hệ thú vị khi nêu về chủ đề này là tác phẩm "Điều phi thường của nền công nghệ sắp tới" của Vernor Vinge, bài này được phê bình nhiều trên các trang web (có thể thấy trong bất cứ công cụ tìm kiếm nào). Nếu những khả năng này có vẻ khác thường thì cũng cần nhớ rằng còn có một truyền thống lâu đời của những thay đổi về công nghệ trông còn khác thường hơn nhiều sau khi chúng xảy ra so với trước đó.

Máy móc thông minh đạt được ngang bằng với con người.

Dòng suy nghĩ này coi đó chỉ như một vấn đề của thời đại trước khi máy tính cũng sẽ thông minh như con người. Nếu bạn không nắm lấy ý tưởng rằng công nghệ phần mềm và phần cứng hiện nay đơn giản đã tạo ra tốc độ nhanh hơn và sự lớn mạnh hơn để làm được điều đó, khi đó những người say mê công nghệ nano gợi ý rằng chúng ta sẽ chỉ xây dựng lên một thứ trông giống như một bộ não.

Dù ở tốc độ nào, vẫn có một quan điểm rằng nếu chúng ta có thể tự cố gắng vươn lên bằng phương pháp của mình để xây dựng lên một cái gì đó ngang bằng với tính năng của đầu óc con người, thì không lâu sau đó chúng ta hoặc họ sẽ có thể xây dựng lên những máy móc siêu đẳng v.v... Điều gì sẽ xảy ra sau đó? Liệu chúng có thể tiếp tục nếu không có chúng ta?

 

Trí tuệ của con người tăng lên một cách giả tạo

Những tiến bộ trong công nghệ thuộc về khoa giải phẫu thần kinh ở một số điểm nào đó được xem như khả năng cung cấp một sự kết nối trực tiếp từ bộ não vào máy tính, cuối cùng xoá bỏ sự thúc ép của những nguồn thông tin về lời nói và cử chỉ (từ con người sang máy tính) và những nguồn thông tin nghe được/nhìn thấy được (từ máy tính sang con người).

Điều này được hình dung tới sự gia tăng một cách khổng lồ khả năng tương tác với các mô hình và thông tin bên ngoài, và cũng tương tác với những người khác nữa, bởi vì nó xoá bỏ sự cần thiết để phát hành thông tin thông qua các giác quan hay dây thần kinh vận động. Có một số ý tưởng  về việc "tải lên" và "tải xuống" các ý tưởng hay các trạng thái tinh thần một cách trực tiếp.

Cùng với viễn cảnh "những cỗ máy có ý thức", thì ngay sau đó "bộ phối hợp xử lý suy nghĩ" cũng có tính khả thi, người ta hy vọng rằng con người với sự phát triển như vậy sẽ nhanh chóng thiết kế ra những phiên bản thậm chí còn tiến bộ hơn nhiều.

Các hội nghị và tỉ lệ nhận bài

Copy from : Pro. Ngo Quang Hung CSE of Buffalo

 

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

Lại nói về SPAM

 

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)

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

 

Thời đại của các phương tiện truyền thông và máy phát sóng.

• 1450: Công việc in ấn được hình thành.
• 1750-???: Cách mạng công nghiệp nổ ra.
• 1800: Máy in dùng năng lượng hơi nước xuất hiện.
• 1930: Đài phát thanh ra đời.
• 1955-60: Xuất hiện vô tuyến truyền hình.

Cuộc cách mạng công nghiệp đã hỗ trợ đắc lực cho báo in, và báo in đã đem lại hình thức phổ biến rộng rãi kiến thức, giúp mọi người biết chữ, kiểm soát quản lý v.v... Đó không hẳn là một bước nhảy vọt trong khả năng nhận thức được các thành tựu đã đạt được đối với những người ưu tú nhưng lại là một sự tiếp cận rộng rãi hơn nhiều với sự phát triển của khả năng nhận thức với người bình thường, và là một sự bùng nổ dựa trên những cái sẵn có và trong sự trao đổi thông tin, trao đổi ý kiến.

Trong khi đó cuộc cách mạng công nghiệp đã cung cấp và được cung cấp nhiên liệu đốt bởi sự dấy lên các cuộc thăm dò ở tất cả các hình thức, bằng cách ấy đã nhanh chóng tăng thêm vào cơ sở kiến thức.

 

1980-1990: Sự phổ biến rộng rãi của các máy tính cá nhân và các trạm phát sóng. 

Đây là lần đầu tiên phổ biến rộng rãi sử dụng không chỉ sự lưu trữ những gì hỗn độn bên ngoài mà cả khả năng xử lý bên ngoài nữa. Tất nhiên, bộ lưu trữ những dữ liệu bên ngoài cơ quan Thần kinh đã được mở rộng, và sự tự động hoá của những công việc lặp đi lặp lại trên dữ liệu đó rất có giá trị.

Tuy nhiên đó là khả năng định hình mà hầu hết những khả năng nhận thức tiến bộ đã khiến cho những suy nghĩ phải được suy xét mà điều đó trước đây là không thể. Những điều này bao gồm các mô hình của tất cả các kiểu hệ thống từ nguyên tử cho đến phạm vi giữa các hành tinh, từ các lĩnh vực về chủ đề khoa học khó hiểu đến những quy trình kinh doanh, việc đưa ra quyết định và sử dụng các lực lượng vũ trang hàng ngày. Những điều này lần lượt dẫn tới một bước nhảy phi thường trong tốc độ khám phá khoa học, phát triển sản phẩm v.v... Tất nhiên bao gồm cả việc phát triển hiện trạng hệ thống máy tính và phần mềm...

Vì vậy, máy tính cá nhân của thời đại này cho thấy hai tiến bộ về phần cứng - 1 là sự tiến bộ về số lượng khổng lồ trong khả năng xử lý dữ liệu bằng những phương thức thông thường, thứ 2 là một bước nhảy vọt trong năng lực của cơ quan thần kinh (bao gồm PC) để tiến hành một mô hình. Nói cách khác, trong suốt kỷ nguyên 1980-90, 2 khâu sản xuất đình trệ nổi bật rất rõ ràng: nhiều mối tương tác với bộ nhớ ngoài của một cá nhân không được kết nối với phạm vi mở rộng hữu ích của tính năng tin học, và cả sự tương tác giữa não bộ, bộ nhớ ngoài và mô hình bên ngoài đều thông qua các kênh "tuần tự" có dải băng tần thấp - chuỗi văn bản hoặc các dãy số.

1994-1999 CE: Web mô phỏng Thế giới rộng lớn

Web - nói phóng đại thì rõ ràng là một sự gia tăng khổng lồ trong việc lưu hành thông tin (cùng với âm thanh, hình ảnh).

Có lẽ chỉ với sự lớn mạnh, những tiến bộ đã đạt được, sự kết hợp của một máy tính cục bộ cộng với phần mềm tốt cộng với web là có vẻ như cuối cùng nó có thể thống nhất được khả năng nhận thức máy tính não cộng đang ngày một gia tăng của chúng ta với sự truy cập vào một khối lượng thông tin khổng lồ đã được thực hiện.

Thậm chí rằng nếu đạt được điều đó, ở thời điểm mà hầu hết những hạn chế rõ ràng nhất vẫn ở giữa bộ não và sự lưu trữ thông tin của máy tính cục bộ và khả năng định hình - " hầu hết vẫn theo thứ tự" - dù sao ít nhất thì cũng sinh động hơn trong những thập niên 80.

Trong khi đó, máy tính cùng với web đã đánh dấu sự khởi đầu thời đại thương mại điện tử, trong đó tốc độ thay đổi về xã hội và thương mại đã tăng lên một cách đáng kể. Điều này đã dẫn tới nhu cầu mở rộng đối với nhiều người hơn trong việc đưa ra nhiều quyết định có ý nghĩa hơn một cách nhanh hơn. Mỗi quyết định kéo theo nhiều phụ thuộc một cách đáng kể, và sự quá tải về lượng thông tin sẵn có, nhưng khả năng nhận thức của Hệ thần kinh (thậm chí dưới cả những viễn cảnh đã được cải thiện ở trên) vẫn không đủ khả năng để chuyển đổi những thông tin này thành những mô hình thông tin cần thiết cho ra các quyết định.

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

Năm 2005 là năm đáng tiếc của ngành optimization. Hai người khổng lồ của môn quy hoạch tuyến tính ( linear programming) mất trong vòng hai tuần: giáo sư Leonid Khachiyan mất ngày 29 tháng 4, và giáo sư George Dantzig mất ngày 13 tháng 5. Nhân dịp này, tôi xin đề cập đến các bài báo kinh điển của họ.

Tôi có một lecture note giới thiệu sơ bộ về linear programming ở dạng PDF. Các bạn có thể tham khảo thêm.

Bài báo hôm nay là bài

Dantzig, G. B. Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation, Koopman (Ed.), Cowles Commission Monograph, 13, John Wiley and Sons, New York, (1951).

của George Dantzig.

Bài báo này có thể xem là khởi nguồn của môn quy hoạch tuyến tính (QHTT) và phương pháp đơn hình (simplex method ). QHTT là bài toán tối ưu các hàm tuyến tính dưới các ràng buộc là một hệ phương trình/bất phương trình tuyến tính.

Giáo sư Alexander Schrijver trong quyển "Theory of Linear and Integer Programming" cho biết nhà toán học Joseph Fourier đã có các ý tưởng khởi điểm của phương pháp đơn hình, và chính George Dantzig cũng cho biết các thảo luận với John von Neumann đã giúp ông phần nào trong khám phá này. Các chi tiết này hoàn toàn không có nghĩa là đóng góp của George Dantzig cho quy hoạch tuyến tính là nhỏ bé. Ta có thể xem Dantzig chính là cha đẻ của môn QHTT.

Năm 1980, tiến sĩ Laci Lovasz từng nói: "nếu ta thống kê bài toán nào lấy nhiều thời gian máy tính nhất (không kể các vấn đề tìm kiếm trong cơ sở dữ liệu), thì có lẽ nó phải là bài toán quy hoạch tuyến tính ".

Ý tưởng căn bản của phương pháp đơn hình (PPĐH) rất đơn giản. Một hệ phương trình hoặc bất phương trình tuyến tính nói chung định nghĩa một đa diện ( polyhedron) trong không gian n chiều:

(ảnh này tôi link từ Mathworld).

Ta cần tìm một điểm trong hoặc trên đa diện này tối ưu một hàm tuyến tính nào đó. Có thể chứng minh được rằng ta chỉ cần tìm điểm tối ưu trong các đỉnh của đa diện (nếu hệ phương trình được viết theo một dạng chuẩn nhất định). Để tìm đỉnh này thì ta bắt đầu từ một đỉnh bất kỳ và di chuyển từ đỉnh này sang đỉnh kia dọc theo các cạnh kề đỉnh đang xét, mỗi lần ta chuyển đến đỉnh ưu việt hơn. Khi không di chuyển được nữa thì ta tìm được đỉnh tối ưu.

Xếp bài báo này vào dạng kinh điển của KHMT thì hơi có vẻ "thấy người sang bắt quàng làm họ", vì quy hoạch tuyến tính và phương pháp đơn hình có ứng dụng cực kỳ rộng rãi ở khắp mọi nơi: kinh tế học, vận trù học, hình học, vân vân. Cần vài chục quyển sách mới nói hết được tầm ảnh hưởng rộng rãi của quy hoạch tuyến tính.

Để biện hộ cho vụ "quàng làm họ" này, tôi sẽ chỉ đề cập ở đây các ứng dụng của quy hoạch tuyến tính trong việc thiết kế các thuật toán xấp xỉ cho các bài toán NP-hard. Ứng dụng của quy hoạch tuyến tính trong KHMT dĩ nhiên là không chỉ giới hạn ở đó.

Như đã viết , ta không hy vọng có thuật toán hiệu quả để giải các vấn đề NP-hard. Một trong những lối thoát là, thay vì tìm nghiệm tối ưu, ta tìm một nghiệm càng gần tối ưu càng tốt trong thời gian đa thức. Đây là đối tượng của nhánh nghiên cứu các giải thuật xấp xỉ ( approximation algorithms).

Rất nhiều các bài toán NP-hard có thể được chuyển về dạng quy hoạch nguyên ( integer programming). Quy hoạch nguyên (QHN) giống như QHTT, chỉ khác ở chỗ các biến bị ràng buộc phải là biến nguyên. Về mặt hình học thì ta phải tìm một điểm tối ưu trong đa diện với các tọa độ nguyên. Có hai cách phổ biến dùng QHTT để tìm nghiệm xấp xỉ một bài toán QHN:

• Tìm đỉnh tối ưu của đa diện (dùng PPĐH chẳng hạn), sau đó bằng một phương pháp làm tròn (rounding) nào đó, ta chuyển đỉnh này về một điểm P trong đa diện với các tọa độ nguyên. Điểm P không nhất thiết là điểm tối ưu của bài toán QHN, nhưng nếu ta làm tròn một cách thông minh thì P sẽ rất gần với điểm tối ưu, và vì thế ta có một xấp xỉ tốt. Cách này thường được gọi là phương pháp nới lỏng và làm tròn (relaxation and rounding).
• Cách thứ hai áp dụng một khái niệm rất sâu sắc trong toán tối ưu, gọi là khái niệm đối ngẫu (duality). Phương pháp primal-dual là một trong những phương pháp hiện đại nhất để thiết kế các thuật toán xấp xỉ.

Gần đây nhất, một bài báo (tôi chưa đọc) với tựa đề "Error correcting codes via linear programming " của Candes, Rudelson, Tao, và Vershynin sẽ xuất hiện ở hội nghị FOCS 2005.

Tôi tạm dừng ở đây, dù mới chỉ chạm đến chóp của tảng băng QHTT khổng lồ mà Dantzig để lại cho chúng ta.

Đoán bí mật

 Copy from Pro. Ngo Hung

 

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