Blog Khoa Học Máy Tính

76. Có một số ( lớn tùy ý) các anh lính đứng thành vòng tròn, cầm súng hướng mặt ra ngoài. Mỗi người có bộ nhớ kích thước bằng hằng số (nghĩa là memory space = O(1)) và chỉ có thể trao đổi thông tin với người đứng bên trái và người đứng bên phải. Giả sử thời gian được chia thành các thời điểm rời rạc: 0, 1, 2, 3, … Tại thời điểm số 0, ông tướng vỗ vai một anh lính nào đó và hạ lệnh “bắt đầu”.

    Các anh lính phải trao đổi thông tin thế nào để tất cả bóp cò cùng một lúc?

77. Có N anh cướp biển sắp bị xử chém. Họ xếp thành một hàng dài. Mỗi người đội một chiếc nón, xanh hoặc đỏ. Cướp biển số 1 chỉ thấy nón (và màu nón) của cướp biển số 2, 3, … N; cướp biển số 2 chỉ thấy nón của số 3, 4, … N; vân vân. Dĩ nhiên, vì thế mỗi cướp biển không biết màu nón mình đang đội và màu nón của các cướp biển đứng trước mình trong hàng.

    Đao phủ bắt đầu chém từng cướp biển một, từ số 1 đến số N. Tuy nhiên, trước khi chém mỗi cướp biển thì đao phủ cho hắn một cơ hội: đoán màu nón của mình. Nếu nói đúng màu nón thì được tha. Tất cả các cướp biển đều nghe thấy nhau trả lời, nhưng không biết ai bị chém ai không.

    Trước hôm ra xử bắn, bọn cướp biển họp lại và tìm một thuật toán trả lời để cho tổng số cướp biển bị chém là ít nhất trong trường hợp tệ nhất (in the worst case). Ví dụ: nếu cướp biển số 2k-1 trả lời bằng màu nón của cướp biển 2k, và cướp biển 2k lập lại câu trả lời này, thì tệ nhất cũng chỉ có một nửa số cướp biển bị chém.

    Nếu bạn là cướp biển thì bạn thiết kế thuật toán thế nào?

Chuyên mục: Dành cho du học sinh & Vui - Giải Trí | Bình luận (10) »

Một bạn email cho tôi với câu hỏi sau:

ban oi! minh hien nay dang dinh thi vao nghanh khoa hoc may tinh! Vay ban co the cho minh biet doi net ve no, tuc la se hoc ve cai gi va sau nay hoc ra thi se lam ve cai gi duoc khong? Cam on !

Tôi đã viết rất nhiều thứ trên blog này có liên quan đến câu hỏi này, nhưng thật sự chưa có một câu trả lời ngắn gọn và dễ hiểu cho một học sinh trung học.

Thay vì tự ba hoa một mình như thường lệ, xin đặt câu hỏi này cho các bạn đọc blog. Câu trả lời phải tránh tối đa các thuật ngữ chuyên môn. Các bạn đọc blog đa phần là dân chuyên ngành. Bạn giải thích về ngành nghề của mình cho một học sinh trung học như thế nào?

Chuyên mục: Chưa phân loại | Bình luận (14) »

Đây là guest post từ anh Nguyễn Viết Hoàng.

Hồi tuần trước người bạn gửi một danh sách các bài “Considered Harmful” mà anh ta tìm được trên ACM và IEEE. Tôi cũng tò mò lên google tìm thử (google: +“considered harmful”) và tìm thấy khoảng… vài ngàn article dạng “considered harmful”. Hầu như mọi thứ đều có thể viết dưới dạng “considered harmful”: từ “HREF considered harmful”, “Hello World! Considered Harmful” cho tới cả những bài nổi tiếng của Dijsktra “Go To Statement Considered Harmful” chỉ ra tác hại của lệnh “Go To” và “Fragmentation Considered Harmful” chỉ ra tác hại của việc phân mảnh gói tin trong mạng máy tính. Có lẽ ngạc nhiên nhất là article được đưa lên top rank là bài “Considered Harmful Essays Considered Harmful” nói về tác hại của… chính những bài dạng “Considered Harmful”.

Ý kiến cá nhân của tôi (và anh bạn) cũng nên cấm, hay ít nhất giảm bớt xuất bản những article loại này vì về bản chất nó chỉ đưa ra những tác hại mà không đưa ra những cách giải quyết vấn đề. Hơn thế nữa, ngoại trừ bài của Dijsktra là bài đầu tiên có tiêu đề “Considered Harmful” rất lạ lẫm, các bài khác với tiêu đề ăn theo sẽ không còn lạ nữa, thậm chí là… nhàm chán nếu như ai đó tò mò như tôi google và nhận được… vài ngàn bài cùng kiểu.

Chuyên mục: Vui - Giải Trí | Bình luận »

• Tai nạn xe cộ là nguyên nhân làm chết nhiều du khách Mỹ nhất ở nước ngoài. Thế mà người ta cứ sợ khủng bố, bệnh, hay tội phạm khi đi nước ngoài. Thống kê này gợi nhơ đến vụ mấy giáo sư bị xe đâm ở Việt Nam mấy tháng trước.
• Bác Đào Tiến Khoa đang kêu gọi viết bài ủng hộ mở thư viện điện tử cho khoa học Việt Nam trên Tia Sáng. Tôi đã viết về đề tài này nhiều lần trên blog, khởi đầu bằng bài từ một ước mơ. Có nhiều thứ hiển nhiên đến mức bảo viết về nó ta không biết bắt đầu từ đâu. Sự cần thiết của thư viện điện tử cho nghiên cứu khoa học ở Việt Nam là một trong những thứ như thế.
• Một bài viết giàu thông tin về máy tính và âm nhạc.

Chuyên mục: Nhân vật và sự kiện | Bình luận (3) »

Q: Should I have a baby after 35?
A: No, 35 children is enough.

Q: I’m two months pregnant now. When will my baby move?
A: With any luck, right after he finishes college.

Q: What is the most reliable method to determine a baby’s sex?
A: Childbirth.

Q: My wife is five months pregnant and so moody that sometimes she’s borderline irrational.
A: So what’s your question?

Q: My childbirth instructor says it’s not pain I’ll feel during labour, but pressure. Is she right?
A: Yes, in the same way that a tornado might be called an air current.

Q: When is the best time to get an epidural?
A: Right after you find out you’re pregnant.

Q: Is there any reason I have to be in the delivery room while my wife is in labour?
A: Not unless the word “alimony” means anything to you.

Q: Is there anything I should avoid while recovering from childbirth?
A: Yes, pregnancy.

Q: Do I have to have a baby shower?
A: Not if you change the baby’s diaper very quickly.

Q: Our baby was born last week. When will my wife begin to feel and act normal again?
A: When the kids are in college.

Chuyên mục: Vui - Giải Trí | Bình luận (2) »

Booktruck chú ý rằng:

The public spaces on the internet served as the most important arena for exchange of information on the events yesterday. Almost every news story cited a Facebook or Myspace page or a livejournal entry as a source. The Wikipedia entry and discussion on the event hashed out validity of sources and the semantics of tragedy. And then the jarring cell phone footage on Liveleak was among the realest indicators that this gruesome event had actually happened. The events as documented on the social web became the authority.

MTV was among the first to track web reactions, and the Washington Post has a fairly full blog roundup. Mydeathspace.com, a site that tracks online profiles of the deceased, has links to Facebook and Myspace profiles for many of the victims at Virginia Tech. The New York Times is soliciting comments and photos of the victims.

Sau hôm thứ Hai vừa qua, cụm từ “Ismael Ax” (mà hung thủ viết bằng mực đỏ trong cánh tay) nằm trong top-10 tìm kiếm của Technorati. Washington Post có hẳn một bài xung quanh ý nghĩa cụm từ này.

Bài hát mà hung thủ nghe đi nghe lại trên máy tính là bài Shine của nhóm Collective Soul:

Give me a word
Give me a sign
Show me where to look
Tell what will I find ( will I find )

Lay me on the ground
Fly me in the sky
Show me where to look
Tell me what will I find ( will I find )

Oh, heaven let your light shine down

Love is in the water
Love is in the air
Show me where to go
Tell me will love be there ( love be there )
Teach me how to speak
Teach me how to share
Teach me where to go
Tell me will love be there ( love be there )

Oh, heaven let your light shine down

I’m going to let it shine
Heavens little light gonna shine on me
Yea yea heavens little light gonna shine on me
Its gonna shine, shine on me.

Chuyên mục: Nhân vật và sự kiện | Bình luận »

Vụ thảm sát tại Virginia Tech University này mới diễn ra sáng nay. Cho đến thời điểm này, đã có 33 nạn nhân được xác nhận đã chết, hơn 20 người khác bị thương. Hung thủ là một người châu Á, bắn chết bạn gái cũ và một vài người nữa trong ký túc xá, sau đó đến Engineering Building (Norris Hall) và xả súng vào lớp học, giết số nạn nhân còn lại rồi tự sát.
Trước đây cũng có những vụ thảm sát trong trường học kiểu này, chẳng hạn ở Columbine High gần 8 năm trước, nhưng với số nạn nhân kể trên, vụ ở Virginia Tech này trở thành vụ thảm sát nghiêm trọng nhất trong lịch sử nước Mỹ. Tin tức vẫn đang được báo chí và truyền hình cập nhật. Tên tuổi của hung thủ cũng như lý do khả dĩ của hành động xả súng này vẫn chưa được tiết lộ.
Dĩ nhiên có rất nhiều lý do trực tiếp và gián tiếp cho hành động cuồng sát của hung thủ, mà một trong những lý do có thể là áp lực học hành quá căng thẳng. Nói đến đây tôi lại nhớ đến vụ một sinh viên Ph.D của Princeton sát hại advisor của mình vì sau 10 năm mà vẫn chưa cho anh này tốt nghiệp. Nhưng ta cũng có thể thấy rằng việc mua bán súng một cách tự do ở Mỹ càng khiến những vụ việc như thế này dễ xảy ra hơn. Bà con có thể xem một trong những phim tài liệu nổi tiếng của Michael Moore về vấn đề này: Bowling for Columbine.
Những vụ cuồng sát kiểu này cuối cùng chỉ để lại nỗi đau cho dân thường. Người chết đi đã đành, mà người còn sống cũng sẽ không bao giờ có thể bình yên. Chỉ có tầng lớp buôn bán súng là không cảm thấy cuộc sống của mình bị ảnh hưởng xíu nào.

Chuyên mục: Nhân vật và sự kiện | Bình luận (3) »

(Biết qua Marginal Revolutions.)

Một bài viết hay trên tạp chí Far Eastern Economic Review của Carsten A. Holz có đoạn:

of the 3,220 Chinese citizens with a personal wealth of 100 million yuan ($13 million) or more, 2, 932 are children of high-level cadres. Of the key positions in the five industrial sectors—finance, foreign trade, land development, large-scale engineering and securities—85% to 90% are held by children of high-level cadres.

Chuyên mục: Nhân vật và sự kiện | Bình luận »

(Biết tin qua Freakonomics.)

Tờ Washington Post đặt một câu hỏi rất khó chịu. Khó chịu vì ta biết câu trả lời, nhưng cứ muốn không tin vào câu trả lời.

In a banal setting at an inconvenient time, would beauty transcend?

Để trả lời câu hỏi này, họ làm thí nghiệm như sau: sáng thứ Sáu ngày 12 tháng 1 vừa qua, họ mời Joshua Bell, violinist lừng danh thế giới, mang cái violon đắt gần nhất thế giới (3.5 triệu USD) xuống một trạm tàu điện ngầm ở D.C. chơi 6 siêu kiệt tác nhạc cổ điển, xem … bà con phản ứng thế nào.

Each passerby had a quick choice to make, one familiar to commuters in any urban area where the occasional street performer is part of the cityscape: Do you stop and listen? Do you hurry past with a blend of guilt and irritation, aware of your cupidity but annoyed by the unbidden demand on your time and your wallet? Do you throw in a buck, just to be polite? Does your decision change if he’s really bad? What if he’s really good? Do you have time for beauty? Shouldn’t you? What’s the moral mathematics of the moment?

Bạn nghĩ chuyện gì sẽ xảy ra? Bao nhiêu người nhận ra Bell? Ông sẽ kiếm được bao nhiêu tiền trong buổi sáng đó? Bài báo hay quá! Lâu lắm rồi mới đọc được một bài báo viết tốt như thế.

Cập nhật 1: tác giả bài báo — Gene Weingarten — có phần followup với bình luận của các bạn đọc về bài này. Hai mươi năm trước, Bruce Springsteen “làm thí nghiệm” tương tự ở Copenhagan (xem video).

Cập nhật 2: à quên, đọc xong bài báo tôi liên tưởng ngay đến 2 bài hát tôi rất thích: Vienna của gã piano và Feeling groovy của Paul Simon.

Chuyên mục: Nhân vật và sự kiện & Âm Nhạc | Bình luận (3) »

Là (cựu) du học sinh, lần đầu tiên sống ở nước ngoài hẳn chúng ta có nhiều vụ “quê một cục”. Tôi sang Mỹ năm 1995, trình độ tiếng Anh chỉ đến hết quyển Streamline 1 (có nghĩa là chỉ biết nói hello, goodbye, how do you do). Có mấy lần “quê một cục” đáng nhớ.

• Thời gian đầu mới sang, ở nhà một gia đình host family người Mỹ, xung quanh chẳng có người Việt nào. Tôi có một vali lớn toàn mì ăn liền, ăn mì ăn liền 1 tuần liền. Đi lòng vòng tìm mua đồ thấy cái gì cũng đắt cứa cổ (vì vẫn còn tâm lý chuyển ngoại tệ ra tiền đồng ). Tuần sau đó thì rón rén mua vài ổ bánh mì ăn với chà bông mang theo. Muốn uống nước, đi chợ thấy họ bán soda mua về uống hết một chai, sau đó mới biết đó là … baking soda. Quê một cục!
• Có một hôm đi chơi xa, bỏ tiền vào máy bán cà fê, tôi mới thấy máy bán cà fê lần đầu tiên trong đời. Thấy máy đẩy một cái ly giấy ra, tôi thò tay lấy cái ly giấy lên xem; ngay sau đó cà fê chảy xuống chỗ mà đáng lẽ cái ly giấy phải nằm chờ. Quê hai cục!
• Năm 1996, tôi vào grad school. Đến xem phòng lab, thấy có một đống máy SGI và Sun Sparc nhưng không biết dùng thế nào. Lệnh duy nhất trên Unix mà tôi biết là “ls”. Quê ba cục!

Càng về sau, khi Việt Nam giao lưu văn hóa sâu sắc hơn với thế giới thì các bạn đi nước ngoài sẽ đỡ bỡ ngỡ hơn nhiều. Ngoài ra, ta sẽ càng ít “nhà quê” nếu mới sang là có bạn Việt chỉ dẫn tận tình, hoặc tiếng Anh đã biết kha khá trước khi đi.

Các vụ “quê một cục” của bạn là gì?

Chuyên mục: Dành cho du học sinh & Vui - Giải Trí | Bình luận (8) »

Blog KHMT bị bom

Chuyên mục: Trang web hay | Bình luận »

Vài bài về cuộc tranh luận Bayesian chọi frequentist:

• Bài phát biểu của giáo sư Bradley Efron, giáo chủ đời 99 của thống kê thần giáo Hoa Kỳ (ASA) trong đại hội giáo dân 2005.
• Một bài nữa của Roderick Little, có rất nhiều tham khảo đến lịch sử và tài liệu của cả hai phe.

Bài của Efron có một đoạn rất hay:

A cartoon history of western thought might recognize three eras: an unpredictable pre-scientific world ruled by willful gods and magic; the precise clockwork universe of Newton and Laplace; and the modern scientific perspective of an understandable world, but one where predictability is tempered by a heavy dose of randomness. Deterministic Newtonian science is majestic, and the basis of modern science too, but a few hundred years of it pretty much exhausted nature’s storehouse of precisely predictable events. Subjects like biology, medicine, and economics require a more flexible scientific world view, the kind we statisticians are trained to understand.

Suy nghĩ cho kỹ, tôi thấy tiến trình phát triển tư duy của mình cũng hao hao cái cartoon history này. Hồi mới bắt đầu đi học, các lý thuyết, định lý như từ trên trời rơi xuống, như “ảo thuật” của các thượng đế tối cao Karp, Cook, Turing, … Sau đó đến classical complexity theory, theory of computation, deterministic algorithms, toán cổ điển … là vũ trụ chính xác của Newton và Laplace. Cuối cùng, khi đối chọi với nhiều vấn đề thực tế như phân tích dữ liệu mạng, bảo mật và mật mã hóa, và cả lý thuyết đương đại như thuật toán xấp xỉ, expanding graphs, định lý PCP và các lớp BPP, ZPP, vân vân, tôi đến với thế giới của các probability distributions, statistical learning theories, và randomness nói chung.

Efron tóm tắt hai phe như sau:

The Bayesian-Frequentist debate reflects two different attitudes to the process of doing science, both quite legitimate. Bayesian statistics is well-suited to individual researchers, or a research group, trying to use all the information at its disposal to make the quickest possible progress. In pursuing progress, Bayesians tend to be aggressive and optimistic with their modeling assumptions. Frequentist statisticians are more cautious and defensive. One definition says that a frequentist is a Bayesian trying to do well, or at least not too badly, against any possible prior distribution. The frequentist aims for universally acceptable conclusions, ones that will stand up to adversarial scrutiny.

Cuộc tranh luận về nền tảng của khoa học thống kê này có hơi hướng của cuộc tranh luận về nền tảng của toán học và logic nói riêng thời đầu thế kỷ 20. Đến hồi (tạm thời) ngã ngũ thế nào cũng có một đột phá trong ngành thống kê.

Chuyên mục: Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (26) »