Blog Khoa Học Máy Tính

Có n phong bì, mỗi phong bì đựng một số tiền khác nhau. Các phong bì này được hoán vị ngẫu nhiên và xếp thành một hàng dài. Ta chơi trò chơi sau đây: mở từng phong bì một. Mỗi lần mở xong một phong bì mới ta có quyền quyết định ngừng chơi. Nếu ta ngừng chơi ngay khi vừa mở xong phong bì có số tiền lớn nhất (trong n số) thì ta thắng số tiền đó. Ngược lại thì không được gì cả. Làm thế nào để thiết kế một chiến lược chơi sao cho xác suất ta thắng tiền càng lớn càng tốt? Xác suất lớn nhất có thể đạt được là bao nhiêu?

Ví dụ: nếu ngừng ngay sau khi mở phong bì thứ nhất thì xác suất thắng là 1/n. Với n thật lớn, có cách nào mà xác suất thắng ít nhất là một hằng số không?

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

Tin tốt.

Tin bình thường.

Tin xấu.

Chủ đề: Giáo dục | Bình luận »

Đề tài lần này là về bảo mật và cryptography

• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, ISBN: 0-8493-8523-7, October 1996, 816 pages. Fifth Printing (August 2001).
• Oded Goldreich, Foundations of Cryptography, Surveys on various cryptographic topics
• S. Goldwasser and M. Bellare, Lecture Notes on Cryptography
• Cryptography’s Role in Securing the Information Society (1996), Computer Science and Telecommunications Board (CSTB)
• Dĩ nhiên ai muốn học/làm về bảo mật đều phải đọc tạp chí Phrack và alt.2600
• Còn tạp chí CIPHER của IEEE và crypto-gram newsletter của Bruce Schneier mang tính đại chúng hơn
• Một số hội nghị chuyên ngành: IEEE SSP, CRYPTO, EUROCRYPT, CCS, USS, DSN, NDSS, ESORICS

Chủ đề: Bảo mật và mật mã học & Giới thiệu sách | Bình luận »

Với những người đã và đang là nghiên cứu sinh (graduate student). Nếu bạn tò mò xem mọi người nghĩ gì về mình thì vào đây coi.

Ở Việt nam thì sao nhỉ ?

Chủ đề: Chưa phân loại | Bình luận »

Tiếp theo bài trước, lần này ta bàn sơ qua về DFT. Tôi học DFT lần đầu tiên vào khoảng năm 1993. Học xong thấy nó rất bí hiểm, theo kiểu: nếu lấy vector này, tính toán thế này, thì ra các hệ số thế kia, nhưng không hiểu ý tưởng nằm sau các công thức đó. Sau này tôi mới khám phá ra là DFT chẳng qua là một phép thay đổi cơ sở (basis) trong không gian tuyến tính. Từ đó thấy mọi thứ rõ ràng, dễ hiểu hẳn ra.

Một trong những thước đo độ sâu và tầm quan trọng của một ý tưởng hay một nhánh nghiên cứu là ứng dụng của nó vào nhiều nơi (kể cả những chỗ mà ta không ngờ trước được là ý tưởng có thể có ứng dụng). Harmonic analysis nói chung và Discrete Fourier Transform nói riêng là một trong những nhánh như vậy. Ứng dụng của Fourier transforms có ở hầu hết tất cả mọi ngóc ngách của toán học, vật lý, khoa học máy tính, điện/điện tử, xác suất thống kê, vân vân. Ví dụ: Hastad đã dùng Fourier analysis để chứng minh một định lý rất quan trọng trong hệ thống PCP, các phân tích tốt nhất về expansion rate của một vài phép xây dựng expander graphs đều dùng Fourier analysis, v.v. Bạn có thể xem thêm vài lecture notes của giáo sư Nathan Linial về một số ứng dụng của Fourier analysis trong toán rời rạc, và master thesis này có thảo luận vài ứng dụng trong lý thuyết tính toán. (Các links đã dẫn chỉ là chóp đỉnh của tảng băng harmonic analysis khổng lồ!)

Về căn bản, DFT không có gì ghê gớm lắm. Căn bản đại số tuyến tính các bạn có thể xem một lecture note tôi tóm tắt vài thứ cần thiết. Hãy xét một ví dụ (tương đối) đơn giản sau đây. Xét một tập hữu hạn và tập . Dễ thấy rằng nếu thì có thể xem như (nói chính xác hơn thì và isomorphic với nhau). Giả sử ta có một orthonormal basis (hệ cơ sở trực chuẩn) của không gian , thì mọi vector đều có thể viết được dưới dạng:

(Ở đây ta ngầm hiểu các vectors đều là vectors cột.) Các hệ số cũng tạo thành một vector mà ta gọi là . Vector này chính là DFT của , ký hiệu là . Cái DFT mà ta thường gặp trong xử lý tín hiệu số tương ứng với một trường hợp đặc biệt khi mà

Trong đó là th root of unity.

Trong miền số phức, ta thường dùng hermitian form (hiểu nôm na là tích vô hướng của hai vectors) sau đây:

Vì các vectors là một orthonormal basis (nghĩa là chúng vuông góc với nhau và đều có chiều dài bằng , dễ thấy rằng

Đẳng thức này thường được gọi là đẳng thức Parseval. Đôi khi người ta gọi trường hợp đặc biệt khi là đẳng thức Parseval, hoặc đẳng thức Plancherel:

Nói cách khác: đổi hệ cơ sở của một vector space sang một hệ cơ sở trực chuẩn khác thì không thay đổi độ dài của các vectors.

Tập trong phân tích ở trên không nhất thiết là phải hữu hạn, miễn là bilinear form được chọn tốt là ta có thể xây dựng các hệ cơ sở trực chuẩn cho không gian tuyến tính tương ứng. Việc chọn hệ cơ sở như thế nào tùy thuộc rất nhiều vào ứng dụng đang xét. Ý tưởng chính của Fourier analysis là làm thế nào ta có thể phân tích các đặc tính của thông qua và ngược lại. Ví dụ: nếu chọn thì ta có thể dùng Fourier transform này để phân tích influence of variables on boolean functions (Hastad đã dùng ý tưởng này cho hệ thống PCP của ông).

Lần tới tôi sẽ nói thêm về trường hợp khi là một nhóm (thường là nhóm Abel) và cách chọn hệ cơ sở trực chuẩn là các characters của nhóm.

Chủ đề: Thuật Toán | Bình luận (1) »

Theo nhiều nguồn tin truyền thông, “nhân vật năm 2005″ xuất hiện trên bìa tạp chí Time số ra cuối tuần này sẽ không mang gương mặt người. “Thiên nhiên” (Mother Nature) hiện đứng đầu danh sách đề cử các nhân vật trong năm trên thế giới – ngoại lệ hiếm hoi trong các cuộc bình chọn hàng năm. (Năm 1998, Time cũng đã chọn trái đất là “nhân vật trong năm”). Đương đầu với ba cơn bão liên tục trong ba tháng vừa qua, nước Mỹ không còn có thể ngạc nhiên về lựa chọn của Time. Nhân vật trong năm của 2004 chính là tổng thống George W. Bush. Vì thế, việc so sánh các dị biệt giữa thiên nhiên và ông Bush hẳn cũng gợi lên nhiều điều để suy nghĩ.

1. Thiên nhiên trong vòng 100 năm qua đã ấm lên 0.6 độ C toàn cầu. Thập niên 1990 là thập niên ấm nhất kể từ giữa thế kỷ 19 khi người ta bắt đầu ghi lại nhiệt độ. Tổ chức IPCC của UN dự đoán rằng nhiệt độ toàn cầu sẽ tăng từ 1.6 đến 5.5 độ C cuối thế kỷ này. Hiện tượng trái đất ấm dần lên nhiều khả năng gây biến đổi nghiêm trọng môi trường sống của chúng ta: băng ở Greenland tan làm tăng mực nước biển (đã tăng từ 10 đến 20cm trong 100 năm qua), hơi ấm làm tăng độ tàn bạo của bão biển mà Katrina là ví dụ, v.v. Viện nghiên cứu không gian Goddard của NASA dự báo rằng 2005 sẽ là năm ấm nhất trong lịch sử. Trừ hơi nước là khí nhà xanh (greenhouse gas) quan trọng nhất, các khí nhà xanh khác như CO2, methane, và nitrous oxide tích ấm và giữ cho nhiệt độ quả đất ở trạng thái cân bằng. Việc phá rừng và đốt các loại năng lượng hóa thạch của con người làm tăng mật độ CO2 trong không khí, dẫn đến hiện tượng trái đất ấm dần lên.

Cho đến nay, Mỹ vẫn đang bướng bỉnh với nghị định thư Kyoto - hiệp ước quốc tế đặt mục tiêu giảm khí thải nhà xanh xuống 5% so với mốc năm 1990 trong vòng 5 đến 10 năm tới. Kyoto đầu tiên thiết lập năm 1992 và ký năm 1997. Các nước EU đồng ý giảm 8% khí thải, Nhật 5%, Nga lúc đầu chưa ký nhưng đến tháng 9 năm 2004 cũng chấp nhận ủng hộ Kyoto. Hiệp ước này có hiệu lực kể từ ngày 16 tháng 2 năm 2005. Khi ông Bush lên làm tổng thống năm 2001, ông rút Mỹ ra khỏi Kyoto, với lý do rằng Kyoto “phá hủy” kinh tế Mỹ, và rằng Kyoto không đòi các nước đang phát triển (đặc biệt là Trung Quốc và Ấn Độ) phải giảm khí thải của họ. Cần chú ý rằng Mỹ là nước thải CO2 nhiều nhất từ các nguyên liệu xăng dầu, hơn cả toàn bộ khối EU (theo số liệu của IEA năm 2002).

Ngày 28 tháng 2 năm 2004, một tổ chức độc lập của các nhà khoa học và công dân Mỹ — lo lắng về sự thiếu quan tâm đến thực tế khoa học của chính quyền Bush — đã phát hành báo cáo scientific integrity in policymaking cùng với một phát biểu do 62 nhà khoa học danh tiếng ký, bao gồm 20 người đã từng thắng giải Nobel. Báo cáo đưa ra các bằng chứng cho thấy chính quyền ông Bush đã “bẻ cong” các chứng cứ khoa học để phục vụ các mục tiêu chính trị và kinh tế của các tập đoàn công nghiệp lớn. Các bằng chứng khoa học về thay đổi khí hậu bị là một điển hình bị “bẻ cong”.

2. Thiên nhiên, thông qua quá trình tiến hóa, sản sinh ra cơ man nào là các chủng loài sinh vật trong đó có chúng ta. Các nghiên cứu về tiến hóa, DNA, genes, sinh học phân tử, sinh học tế bào, v.v. đã và đang giúp chúng ta càng lúc càng hiểu rõ hơn về cấu thành các sinh vật (đặc biệt là con người), giúp nghiên cứu sự phát triển của vi khuẩn và virus, khám phá các genes xấu, giúp bào chế thuốc chữa các bệnh hiểm nghèo, có rất nhiều ứng dụng trong nông nghiệp, v.v… Khoảng 20 năm trước một nhánh mới của khoa học gọi là y học tiến hóa đã ra đời, nghiên cứu y học dựa trên thuyết tiến hóa.

Giới tôn giáo cực đoan ở Mỹ gần đây tìm đủ mọi cách làm mất uy tín thuyết tiến hóa vì tiến hóa không đồng nhất với niềm tin của họ rằng thượng đế tạo ra con người ở dạng hiện tại, Eva là xương sườn của Adam. Một biến thể của phong trào “tấn công tiến hóa” này là sự đề bạt một giả thiết phi khoa học gọi là “thiết kế thông minh” (intelligence design, viết tắt là ID, xem thêm ở đây, và ở đây về lý do tại sao ID là phi khoa học, cùng với rất nhiều thông tin về thuyết tiến hóa). ID nói rằng sinh vật không thể tiến hóa mà thành, mà phải do một lực lượng siêu nhiên thông minh nào đó “thiết kế” ra.

Đầu tháng 11 vừa qua, hội đồng trường học của tiểu bang Kansas, bao gồm đa phần là tín đồ thiên chúa, đã chấp nhận một chuẩn mới cho các trường công ở tiểu bang này. Đây là lần thứ ba trong vòng 6 năm qua hội đồng này đã thay đổi chuẩn giáo dục - bỏ dần tiến hóa ra khỏi chuẩn.

Ở Dover, tiểu bang Pensylvania, một hội đồng trường địa phương cũng làm chuyện tương tự. Một số phụ huynh kiện hội đồng này đã vi phạm hiến pháp (điều khoản “ngăn cách nhà nước và tôn giáo”). Vụ kiện này vẫn đang tiếp diễn. Trong cuộc bầu cử tháng trước, dân chúng ở Dover đã loại bỏ 8 trong số 9 thành viên của hội đồng này.

Tháng 8 vừa qua ông Bush (là một tiến đồ thiên chúa giáo), công khai ủng hộ việc dạy ID chung với thuyết tiến hóa trong các lớp sinh vật học.

3. Trong bối cảnh nói trên, tạp chí Time đã chọn một bước đi đúng khi quyết tâm thu hút sự chú ý của nước Mỹ (và thế giới) vào những vấn đề lẽ ra phải được nhấn mạnh từ nhiều năm qua. Trong mấy tháng qua, nhân thảm họa Katrina, ông Bush đã vài lần lên truyền hình kêu gọi người dân tiết kiệm năng lượng hơn vì giá xăng dầu tăng lên cao vùn vụt. Ông Bush cũng nhân tiện kêu gọi nước Mỹ quan tâm đến thiên nhiên và môi trường nói chung. Tuy nhiên, các nhà quan sát vẫn nhận định lời kêu gọi này chỉ là một biện pháp ngắn hạn nhằm xoa dịu nỗi lo của người dân trong nước chứ không phải là môt chiến lược môi trường dài hạn dựa trên các chứng cứ khoa học. Nhiều người vẫn hy vọng mối quan ngại ngày càng lớn của cộng đồng khoa học Mỹ và thế giới, và ý thức ngày càng tăng của người dân trong và ngoài nước sẽ làm chính quyền Bush thay đổi vị trí các ưu tiên trong chính sách của mình.

Nhân vật của năm 2005 có sức mạnh gần như tuyệt đối, nhưng sức mạnh đó có đủ để thuyết phục nhân vật của năm 2004 quan tâm nhiều hơn đến các vấn đề môi trường và khoa học không? Câu trả lời nhiều khả năng là không.

Chủ đề: Chưa phân loại | Bình luận (3) »

Xin viết kỹ hơn về phương pháp giải mã của Bob cho bài toán đang xét. Về căn bản, Alice muốn gửi cho Bob con số . Với chiến lược đã nêu, tỉ lệ q của số bit 1 trên tổng số bit nhận được sẽ gần với p nhưng không có gì đảm bảo nó sẽ bằng p. Hơn nữa, làm thế nào ta biết được là q sẽ gần với p?

Trước hết, ta xét vấn đề giải mã. Con số p Alice cần gửi là một bội số của . Có tất cả vị trí từ 0 đến 1 mà p có thể nằm. Các vị trí này cách đều nhau một khoảng bằng , từ đến . Phương pháp giải mã của Bob rất đơn giản: tính tỉ lệ q như đã nêu, sau đó làm tròn nó về bội số gần nhất của . Như vậy, miễn là thì Bob sẽ giải mã đúng.

Cho trước một sai số (ví dụ 0.001%), nếu thì Bob sẽ giải mã sai với xác suất nhiều nhất là . Để ước lượng xác suất này, ta dùng chặn Chernoff. Trong bài giảng ở đây, tôi có ghi lại chặn Chernoff ở một dạng tương đối mạnh. Với bài toán của chúng ta thì ta chỉ cần một dạng đơn giản của chặn này.

Giả sử ta có các biến ngẫu nhiên trong đó và , với là một xác suất cho trước. Dễ thấy rằng

Các chặn Chernoff cho ta ước lượng xác suất mà nằm xa expected value . Phân bố của tổng này có hai cái “đuôi” mỏng ở hai đầu, còn lại tập trung vào gần expected value (giống như hình ngọn núi), gọi là hiện tượng concentration.

Cho trước , Chernoff’s bound cho đuôi trên (upper tail) có thể viết như sau:

và cho lower tail ta có

Nói theo ngôn ngữ bình thường: khi tiến ra vô cùng, khả năng mà nằm xa trung tâm tiến đến theo hàm mũ (exponentially reduced).

Trở lại bài toán của chúng ta. Đặt bằng giá trị của bit thứ mà Bob nhận được. Như vậy, sau khi Alice gửi bits, ta có . Dùng chặn Chernoff, đặt (bỏ qua trường hợp tầm thường khi ), ta có

Như vậy, chỉ cần là Bob có sai số mong muốn.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận »

Nhân hai ma trận là phép tính cực kỳ cơ bản trong toán học. Thiết kế giải thuật nhân hai ma trận một cách hiệu quả là bài toán cực kỳ cơ bản trong KHMT. Tương tự như vậy, Discrete Fourier Transform (DFT - biến đổi Fourier rời rạc) là một trong những biến đổi toán học có cực kỳ nhiều ứng dụng thực tế, đặc biệt là trong xử lý tín hiệu số . Fast Fourier Transform (FFT) là một thuật toán tính DFT dùng phương pháp divide-and-conquer (chia để trị). FFT là một trong những thuật toán cơ bản nhất của KHMT. Lý thuyết nhóm (group theory) cũng cực kỳ hữu dụng trong KHMT, giúp ta giải các bài toán trong cryptography, trong thiết kế mạch, thiết kế expanding graphs, v.v.

Thế ba thứ này có liên quan gì đến nhau?

Một số bài báo gần đây của Henry Cohn, Christopher Umans, Robert Kleinberg, và Balázs Szegedy dùng DFT và group representation theory (lý thuyết biểu diễn nhóm) để thiết kế giải thuật nhân ma trận. Nhân cơ hội, tôi sẽ viết một series giới thiệu sơ bộ về cả ba nhánh này, và kết thúc bằng một combinatorial conjecture chưa ai giải được.

Trước hết, hãy nói về nhân ma trận. Để đơn giản ta chỉ xét các ma trận vuông . Trong suốt một thời gian dài, người ta nghĩ rằng cần ít nhất phép nhân để nhân hai ma trận . Đến năm 1969, Volker Strassen — khi đó là một sinh viên ở MIT — nghĩ ra một thuật toán chia-để-trị chạy trong thời gian . Giải thuật này chính là giải thuật Strassen lừng danh; nó là một kết quả đột phá. Điểm thú vị là Strassen nghĩ ra lời giải này vì nó là bài tập trong một lớp ông đang học. Lúc nghĩ ra lời giải Strassen không biết là kết quả đó có ý nghĩa to lớn thế nào.

Từ đó trở đi, người ta cố gắng thiết kế các giải thuật chạy trong thời gian , trong đó tiến dần đến 2. Dĩ nhiên là chặn dưới vì bản thân ma trận kết quả đã có đến entries. Kết quả tốt nhất hiện nay là của Coppersmith và Winograd từ năm 1990, với . Hiện nay thì người ta tin rằng có thể đạt đến với cho trước bất kỳ.

Tuy nhiên, suốt mười mấy năm trời kể từ bài báo của Coppersmith và Winograd vẫn chưa có kết quả gì mới. Năm 2003, Cohn và Umans tìm ra một cách khác để giải quyết vấn đề nhân ma trận này. Họ liên hệ nó với DFT và representation theory. Một bài báo mới của Cohn, Kleinberg, Szegedy, và Umans đăng ở hội nghị FOCS 2005 tháng 10 vừa qua phát triển hướng này sâu hơn, và họ đạt tới giới hạn của Coppersmith và Winograd dùng phương pháp mới này. Trong bài báo có hai conjectures mà giải được một trong chúng thì tương đương với việc chứng minh được có thể đạt đến với cho trước bất kỳ. Đạt đến đây sẽ là một kết quả đột phá lớn nhất trong tính toán matrix kể từ bài báo năm 1969 của Strassen.

Chủ đề: Thuật Toán | Bình luận (5) »

Tiếp tục với câu hỏi cực kỳ thú vị lần trước.

Giả sử Bob biết n, và giả sử chuỗi nhị phân C có các bits . Gọi c là số nguyên có biểu diễn nhị phân là C. Ví dụ, nếu C = 10110 thì c = 22. Chiến lược của Alice như sau: mỗi lần gửi, gửi bit 1 với xác suất , và gửi bit 0 với xác suất 1-p. Với chiến lược này, Alice không cần phải nhớ xem mình đã gửi bit gì. Sau khi đã gửi thật nhiều bits, Bob tính tỉ lệ q của số bits 1 trên tổng số bits mà Bob đã nhận. Tỉ lệ này sẽ tiến đến p khi tổng số bits nhận được tiến đến vô cùng. Ta có thể dùng Chernoff bound để tính cụ thể xác suất mà p và q nằm trong vòng của nhau là bao nhiêu. Hơn thế nữa, ta có thể ép xác suất lớn tùy ý.

Thật ra thì ta không cần nhỏ lắm, chỉ cần khoảng là đủ. Tóm lại, khi tổng số bits Alice gửi tiến đến vô cùng, thì xác suất Bob giải mã được chuỗi C tiến đến 1. Đó là lời giải cho trường hợp Bob biết trước n.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận (3) »

Khi ta bẻ cong thanh mì spaghetti (chưa luộc, lúc còn cứng), nó thường không gẫy đôi mà gẫy vụn ra làm nhiều mảnh. Tại sao? Câu hỏi này không đơn giản chút nào. Richard Feynman và W. Daniel Hillis hai mươi năm trước nghiên cứu sơ bộ nhưng chưa tìm ra lời giải. Chỉ đến gần đây vài nhà vật lý người Pháp mới tìm ra câu trả lời. Câu hỏi tưởng chừng như trẻ con này liên quan đến độ bền vững của các cấu trúc khác (áo giáp, máy cắt công nghiệp, …).

Chủ đề: Nghiên cứu nghiên kiếc | Bình luận »

Giáo sư Young Suh Kim có lẽ là một trong những bloggers đầu tiên, trước cả khi các bloggers ra đời. Trước cả khi có World Wide Web.
Archives của những bài blog từ năm 1992 đến 2004 vẫn còn ở đây cho những ai quan tâm.

Xin giới thiệu, Y. S. Kim có một background rất thú vị. Ông là một trong những giáo sư đầu tiên về vật lý người Hàn Quốc tại Hoa Kỳ. Tốt nghiệp về vật lý ở Princeton năm 1961, giáo sư vật lý lý thuyết ở Đại học Maryland từ 1962 đến nay; sinh ra ở Bắc Triều Tiên, nhưng sang Nam Hàn học hết phổ thông trung học; là một nhân chứng của cuộc chiến tranh Triều tiên 1950-1953; là người có trí nhớ đáng nể (photographic memory) đến từng chi tiết của các sự kiện lịch sử, có phong cách kể chuyện hóm hỉnh; rất active trong nghiên cứu kể cả khi đã sang tuổi 70; thích chụp ảnh với các cô gái xinh đẹp từ khắp nơi trên thế giới. Ông là một người Triều Tiên kiêu hãnh.

Tôi rất khoái đọc những bài viết trong blog của GS Kim , vì tài kể chuyện cuốn hút và dí dỏm. Những bài blog này rất thú vị không chỉ với những người có background về văn hóa hay lịch sử của Korea, mà có lẽ với cả các DHS châu Á (như dân mít ta) đang học tập, làm việc và tìm cách hòa đồng ở môi trường nước ngoài.

Tex test:

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

Hiện nay, dịch cúm gà đã lan đến 10 tỉnh thành của Việt Nam và đã lan đến nhiều quốc gia trên thế giới. Chính phủ Mỹ đã thông qua kế hoạch 7.1 tỉ đô để chiến đấu với cúm gà. Cũng may mắn cho dân Mỹ là mùa Lễ Tạ Ơn này vẫn còn có thể ăn gà tây vì DƯỜNG NHƯ cúm gà vẫn chưa đến được Mỹ. Chắc là vì mùa đông sắp đến, bọn chim di cư chỉ có bay về gần đường xích đạo?! Ôi, tạ ơn Mùa Đông!

Liệu ta có thể trả lời câu hỏi: Tỉnh thành nào có nhiều khả năng phát cúm gà nhất trong thời gian sắp đến ? Cấp độ vĩ mô hơn là quốc gia nào có nhiều khả năng phát cúm gà nhất. Dĩ nhiên mọi địa phương, mọi quốc gia đều phải đề phòng, ngăn chặn thật cẩn thận, nhưng nếu biết được địa điểm tiềm năng mà cúm gà sẽ ghé đến, người ta có thể tập trung nguồn lực mạnh mẽ hơn để dập tắt cúm. Để tìm câu trả lời, ta thử liếc mắt sơ sơ qua lý thuyết đồ thị xem sao!

Nếu xem các tỉnh thành của nước Việt Nam chúng ta là các đỉnh, còn những đường lối mà cúm gà có thể đi qua (đường giao thông, chim di cư …) là các cạnh thì ta có một đồ thị. Trên đồ thị này, ta có thể ước lượng được khả năng nhiễm cúm của một đỉnh khi đỉnh lân cận của nó bị nhiễm là bao nhiêu. Vậy cho trước một số đỉnh đã bị nhiễm cúm, ta có thể tính được xác suất để một đỉnh khác sẽ nhiễm cúm sau một thời gian T hay không?

Đây cũng là một bài toán hay trong lý thuyết đồ thị và có ứng dụng trong an ninh mạng. Nếu thay cúm gà bằng mấy con worm, và nước Việt Nam bằng một hệ thống mạng thì ta có bài toán: Biết trước một số máy tính trong mạng bị dính sâu, sau một thời gian, ta có ước lượng được khả năng để một máy tính khác cũng bị dính đòn hay không. Hiện đã có một số cách để mô hình hóa bài toán này, kể cả dùng đến mô hình của sinh thái học, nhưng vẫn chưa có cái nào hiệu quả. Nguyên nhân chủ yếu là vì không xem xét được hình dạng của mạng, do đó chỉ có thể tính được số lượng bị nhiễm chứ không biết được cụ thể đỉnh nào bị nhiễm.

Nhìn vào tình hình dịch bệnh như hiện nay, nếu ta có thể giải quyết được triệt để bài toán trên thì thật là “công đức vô lượng”. Dĩ nhiên còn nhiều yếu tố khác nữa để có thể khống chế và tiêu diệt được một cơn dịch nguy hiểm, chỉ một bài toán đồ thị thôi thì không thể được gì. Nhưng thật ra, nếu giải được bài toán mấy con worm thì ta cũng có thể trở nên “nổi tiếng nhưng được ít người biết đến” rồi nhỉ ?!
___________________________________________
Xin cám ơn anh Hà Trần Đức vì mấy buổi nói chuyện về worm :-).

Chủ đề: KHMT và sinh học & Mạng máy tính & Xác suất & thống kê | Bình luận »

Đọc các bài báo về IP traceback, tôi vừa học được bài toán tuyệt đẹp sau đây:

Alice có một chuỗi C gồm n bits nhị phân cần gửi cho Bob. Tuy nhiên, mỗi lần Alice chỉ có thể gửi 1 bit và gửi xong thì Alice quên béng mất là mình đã gửi bit gì (hay bit nào). Thiết kế một protocol để Alice có thể gửi C cho Bob.

Chú thích: Alice có thể gửi bao nhiêu bits cho Bob tùy ý, miễn là trong giới hạn các ràng buộc trên. Giải bài toán trong hai trường hợp: (i) Bob biết trước n bằng bao nhiêu, và (ii) Bob không biết cả n luôn.

Impossible? Tựa đề của post đã có gợi ý.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận »

Hồi bé thỉnh thoảng lại có phong trào kế hoạch nhỏ, nghĩa là phong trào ra chợ giấy lộn mua báo cũ về đem nộp cho trường làm … giấy lộn; phong trào đổ tiệt các thứ ra khỏi bất kỳ cái chai nào tìm thấy trong nhà để nộp chai tính điểm “dũng sĩ kế hoạch nhỏ”, khi nào may mắn lại được thêm vài cái “sao chiến công” dán vào một mảnh giấy vuông vuông đeo trên ngực, hiên ngang vào lớp.

Tôi nhìn lại môi trường xung quanh mình và chợt nhận ra mình đã quen thế nào với “kế hoạch nhỏ” ở đây. Tôi hầu như không bao giờ nghĩ đến sự tồn tại của chúng, chúng như không khí.

• Ở cái chỗ đổ rác công cộng trong khu condo tôi ở, ngoài cái thùng rác 2mét x 2mét x 2mét to đùng ra thì còn có vài thùng nhỏ hơn, cao ngang ngực, thùng dành cho báo chí, thùng cho các lon thiếc, thùng cho chai lọ thủy tinh, thùng cho giấy carton.
• Trong trường thì các thùng rác để khắp nơi: hành lang, gần cửa, sân, bãi xe buýt, … Mỗi vị trí có đến 3, 4 thùng đứng cạnh nhau với chức năng tương tự.

Tự nhiên khi bỏ rác ta bỏ vào đúng loại thùng. Chẳng cần giáo dục công dân gì sất.

Tôi cũng làm kế hoạch nhỏ trong học tập và nghiên cứu. Thường thì khi đọc hoặc nghĩ được cái gì mới tôi viết notes (trên giấy, trên máy, trên blog!) rồi bỏ chúng vào các cặp giấy, thư mục trong laptop, đề tài trong blog, … Chuyện này không phải lúc nào cũng làm được vì khá mất thời gian. Có không ít các quyển sách mà notes của tôi về chúng rất dài. Thậm chí có một số quyển tôi gần như chép lại sách theo ý mình hiểu. Ở Minneapolis có một quán cà fê trước cổng trường mà hồi còn đi học tôi chuyên môn ngồi “viết sách” kiểu này. Quán tên là Expresso Exposé. Khi nào bạn có dịp ghé Minneapolis, nên đến đường Washington ngồi quán này cho biết. Nhìn ra đường rất dễ chịu.

Càng lúc tôi càng nhận ra cái “hệ thống” mà mình tự động hóa kế hoạch nhỏ này có lợi về lâu về dài. Các bài báo kinh điển, sách hay, tôi phải đọc ít nhất 3 lần mới hiểu sơ sơ. (Có vài tầng “hiểu”, tầng thấp nhất của sự hiểu là khả năng trình bày lại toàn bộ bài báo cho người khác mà không cần notes và bài báo trong tay.) Hệ thống kế hoạch nhỏ này giúp cho các lần đọc sau rất nhiều. Qua một thời gian, gom các entries cùng đề tài nào đó của blog lại, tổ chức và thêm một ít suy nghĩ mới, là ta có thể có một bài viết không tệ.

Tôi đọc khá nhiều sách của Noam Chomsky (đặc biệt giới thiệu quyển Fateful Triangle), và luôn thấy rất ấn tượng rằng mỗi một sự kiện trong sách đều có các tham khảo rất kỹ lưỡng. Các citation của ông không phải kiểu citation lười như kiểu “đọc sách này thì biết”, mà ông cite các bài báo của các nhật báo chính xác đến từng số. Hiển nhiên ông phải có một “cơ sở dữ liệu” kế hoạch nhỏ được tổ chức rất tốt thì mới có thể cite các bài nhật báo từ hồi thập niên 50, 60.

Nếu Chomsky cũng làm kế hoạch nhỏ thì kế hoạch đó hẳn là không nhỏ.

Chủ đề: Dành cho du học sinh & Giáo dục | Bình luận (6) »

Mấy hôm nay bà con xôn xao về vụ SONY cài vào vài đĩa nhạc do họ sản xuất phần mềm mà khi chơi đĩa nhạc này trên máy tính, phần mềm này để lại một rootkit trong máy. Người khám phá vụ này là Mark Russinovich (xem thêm bài follow-up về vụ này của Mark).

Rootkit — thường dùng trong các virus máy tính — về căn bản là một bộ các phần mềm có chức năng “che” các processes, log entries, files, registries, … để tránh bị phát hiện bởi người dùng và các phần mềm quét (virus) khác. Packet sniffers và keyloggers là các thành viên thường trực trong các rootkits. Nhiều chuyên gia nghĩ rằng cách duy nhất để xóa hoàn toàn rootkit trong máy là … reformat và cài lại hệ điều hành. Xem thêm ở đây, đây, và đây.

Chắc chắn là phải có cách khác để quản lý cái gì có thể chui vào máy mình, trách nhiệm này nằm ở những nhà thiết kế hệ điều hành. Dennis Richie nói đúng, đã lâu lắm rồi chưa thấy ý tưởng gì thật mới trong thiết kế hệ điều hành. Có chăng thì chỉ là vài thay đổi về cách phân phối (windows live), hay đổi giao diện (trong *nux thì đổi windows manager là được).

Chủ đề: Bảo mật và mật mã học & Nhân vật và sự kiện | Bình luận »