Blog Khoa Học Máy Tính

Or, more than a thousand words. Biết qua thinkprogress.org. Sau đây là cover của Newsweek tuần rồi qua các vùng địa lý khác nhau:

Chủ đề: Nhân vật và sự kiện | Bình luận »

Top 10 annoying news anchors on TV, theo Giant magazine, có videos làm bằng chứng. Đứng đầu là, còn ai trồng khoai đất này, Bill O’Reilly. Đứng thứ hai, khá xứng đáng, là Nancy Grace. Trong này có cả đoạn trích Chris Wallace phỏng vấn Bill Clinton gần đây, đang là hot item trên Net mấy ngày qua.

Chủ đề: Vui - Giải Trí | Bình luận (2) »

Theo bài của Dubner và Levitt trên NY Times:

In its 2000 report “To Err Is Human,” the Institute of Medicine estimated that anywhere from 44,000 to 98,000 Americans die each year because of hospital errors — more deaths than from either motor-vehicle crashes or breast cancer — and that one of the leading errors was the spread of bacterial infections.
…
In 1847, the Hungarian physician Ignaz Semmelweis was working in a Viennese maternity hospital with two separate clinics. In one clinic, babies were delivered by physicians; in the other, by midwives. The mortality rate in the doctors’ clinic was nearly triple the rate in the midwives’ clinic. Why the huge discrepancy? The doctors, it turned out, often came to deliveries straight from the autopsy ward, promptly infecting mother and child with whatever germs their most recent cadaver happened to carry. Once Semmelweis had these doctors wash their hands with an antiseptic solution, the mortality rate plummeted.

Làm thế nào để bắt các bác sĩ rửa tay? Giải pháp 1: gọi điện thoại cho các bà mẹ các bác sĩ để bắt con các bà rửa tay trước khi khám bệnh. Các bà đã từng dạy “rửa tay trước khi ăn” thành công thì “rửa tay trước khi mổ” chắc không phải là quá vô lý. OK, giải pháp này không khả thi lắm. Nếu con cái mà nghe lời mẹ đến thế thì thế giới này đã ít có chiến tranh. Giải pháp 2: thiết kế một dạng incentive nào đó. (Incentives works wonder!)

For the next six weeks, Silka and roughly a dozen other senior personnel manned the parking-lot entrance, handing out bottles of Purell to the arriving doctors. They started a Hand Hygiene Safety Posse that roamed the wards and let it be known that this posse preferred using carrots to sticks: rather than searching for doctors who weren’t compliant, they’d try to “catch” a doctor who was washing up, giving him a $10 Starbucks card as reward. You might think that the highest earners in a hospital wouldn’t much care about a $10 incentive — “but none of them turned down the card,” Silka says.

When the nurse spies reported back the latest data, it was clear that the hospital’s efforts were working — but not nearly enough. Compliance had risen to about 80 percent from 65 percent, but the Joint Commission required 90 percent compliance.

Hừm, các bác sĩ lương vài trăm nghìn 1 năm nên 10-usd incentive chưa đủ. Đọc tiếp bài xem kết thúc.

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

Lần trước có đến 5 câu, lần này chỉ 1 để giữ trung bình 3 câu mỗi lần. Câu này rất phản trực quan, và là nội dung một định lý nằm trong hầu hết các sách về real analysis với một ít measure theory trong đó.

54. Có tồn tại một mớ đoạn mở (open intervals) trên trục các số thực với tổng chiều dài (measure) hữu hạn sao cho một số hữu tỉ bất kỳ đều thuộc về một trong các đoạn mở này? (Gợi ý: không những tồn tại “mớ” đoạn mở này, mà tổng chiều dài của chúng có thể nhỏ tùy ý!)

Chủ đề: Dành cho du học sinh & Vui - Giải Trí | Bình luận »

Một sinh viên trong lớp tôi, dù đã dành nhiều thời gian, vẫn không thể hiểu được khái niệm vector space với số chiều nhiều hơn 3. Lý do chính anh ta đưa ra là: I can’t visualize n-dimensional spaces. Hừm, làm thế nào bây giờ? Trong quyển linear programming, Chvatal viết: “Do not try to visualize n-dimensional objects for n>=4. Such an effort is not only doomed to failure - it may be dangerous to your mental health. (If you do succeed, then you are in trouble!)” Bây giờ tôi trở nên nghi ngờ các lớp đại số tuyến tính dạy ở bậc đại học. Tôi đã từng học một lớp như thế, và hoàn toàn không nhớ là thầy giáo đã giảng một cách trực quan không gian n-chiều như thế nào. Một trăm phần trăm trừ epsilon những gì tôi biết/hiểu về đại số tuyến tính tôi đều học/đọc được từ quyển Matrix Analysis của Horn và Johnson. Dĩ nhiên, đọc thêm Gilbert Strang thì càng tốt.

Quay lại đề tài chính: visualize không gian (tuyến tính) n-chiều thế nào? Với tôi, câu trả lời là: tùy ngữ cảnh. Có lúc tôi chỉ cần một định nghĩa cơ học kiểu: là tập hợp tất cả các bộ n số thực; đôi khi tôi hình dung nó như một tập hợp “quai quái” và vẽ trong đầu một cái Venn diagram cho nó; hoặc tôi hình dung một mặt phẳng trong không gian 3 chiều (chứa tâm); vân vân. Khi đối mặt với một vấn đề trong đại số tuyến tính, tôi nhìn vấn đề bằng tất cả các cách này (trong tiềm thức), và áp dụng cái trực quan “gần” vấn đề nhất để hiểu và giải quyết nó. Ví dụ: để hình dung ra phần giao của hai không gian tuyến tính là một không gian tuyến tính khác (với số chiều lơn lớn), có lẽ cách tốt nhất là dùng cái Venn-diagram quai quái nọ. Bài tập 1: bạn hình dung kernel và image của một linear transformation thế nào? Bài tập 2: bạn hình dung eigenvalues của một matrix thế nào? Bài tập 3: bạn hình dung một không gian tuyến tính hữu hạn (trên trường ) thế nào? Bài tập 4: thế còn các không gian Hilbert hay Banach thì sao?

Thế nhưng, sinh viên nọ, vì chưa phát triển được các trực quan này (dù đã học đại số tuyến tính), không “chịu” các giải thích của tôi. Tôi dùng tất cả các analogies có thể có để giải thích rằng các vectors độc lập tuyến tính không nhất thiết phải vuông góc với nhau, nhưng anh ta vẫn nhăn nhó.

Bây giờ, có hai lối ra: một là tôi nghi ngờ khả năng giảng dạy của mình, hai là tôi phải tin rằng “phát triển tư duy trừu tượng” về đại số tuyến tính không phải là việc ngày một ngày hai cho sinh viên nọ. Cơ chế tự bảo vệ bắt tôi chọn chọn lựa số hai :-).

Chọn lựa số hai dĩ nhiên là hữu lý! Pythagoras vĩ đại còn không “visualize” được — và vì thế không tin vào — các số vô tỉ nữa mà! Ta hoàn toàn có thể visualize một số hữu tỉ m/n bằng cách chia một đoạn thẳng chiều dài m thành n phần bằng nhau. Bạn thử hình dung xem sao?

Các câu hỏi tự nhiên kế tiếp là: làm thế nào để ta phát triển trực quan trừu tượng về một đề tài nào đó? Có thể nào tồn tại những đề tài mà đầu óc ta không đủ thông minh để làm một cú quantum leap như kiểu từ 3-chiều lên n-chiều không? Tôi dành câu trả lời cho các bạn.

Chủ đề: Dành cho du học sinh | Bình luận (12) »

Quyển Introduction to computational complexity của Daniel Bovet và Pierluigi Crescenzi vừa được để miễn phí. Quyển này viết súc tích và trực quan. Các đề tài khá cập nhật. (Bạn phải cho set cookies thì mới vào website này được.)

Sanjeev Arora và Boaz Barak viết gần xong quyển Complexity Theory: A Modern Approach. Quyển này hứa hẹn sẽ là “the book on complexity theory” cho thập niên tới, download nhanh nhanh kẻo họ sẽ lấy xuống khi quyển sách ra bản in. “The book on complexity theory” của 2 thập niên trước là quyển Computational Complexity của Christos H. Papadimitriou. (Xem thêm quyển sách xuất sắc của Michael Sipser.)

Sách miễn phí trên Net [1] đã giới thiệu vài quyển về lý thuyết tính toán.

Chủ đề: Giới thiệu sách | Bình luận »

Sau bài báo ở New Yorker, Sing-Tung Yau đang đòi kiện.

Chủ đề: Chính trị trong ngành & Nhân vật và sự kiện | Bình luận »

Vài phát biểu của Homer Simpson:

(Image Source: wikipedia)

How is education supposed to make me feel smarter? Besides, every time I learn something new, it pushes some old stuff out of my brain. Remember when I took that home winemaking course, and I forgot how to drive?

Scully: Homer, we’re going to ask you a few simple yes or no questions. Do you understand?
Homer: Yes. (lie dectector blows up)

English? Who needs that? I’m never going to England!

I think Mr. Smithers picked me for my motivational skills. Everyone always says they have to work twice as hard when I’m around!

Marge, it takes two to lie … One to lie, and one to listen.

Oh, people can come up with statistics to prove anything. 14% of people know that.

You know boys, a nuclear reactor is a lot like women. You just have to read the manual and press the right button.

I hope I didn’t brain my damage!

First you don’t want me to get the pony, then you want me to take it back. Make up your mind!

Now what is a wedding? Well, Webster’s dictionary describes a wedding as the process of removing weeds from one’s garden.

Chủ đề: Danh ngôn & Vui - Giải Trí | Bình luận »

Tôi vốn là big fan của Vàng Anh và các tản văn thứ sáu của chị. Chị rất dí dỏm, cay nhưng không nghiệt. Ví dụ:

• Nhân trường hợp chị thỏ bông
• Tôi muốn đời tôi màu gì?
• Lên đường đi các bác
• Gửi ông X, người ghét Karaoke
• Cụ Rùa thuộc biên chế bộ nào?
• Không sợ nghèo, chỉ sợ …
• Không có chồng thì đừng có làm giầu
• vân vân

Trong tản văn Tôi nghi ngờ ông Heghen có đoạn

“Trong khi cố gắng tác động ra ngoài và biểu hiện cái bên ngoài nghệ thuật nhằm mục đích gây tác động ra ngoài, và nét chung nhất là cố gắng gây ấn tượng. Nghệ thuật có thể đạt được những hiệu quả này nếu như nó xử dụng yếu tố xấu xí, gò ép, đồ sộ… để gây nên những tương phản nhất định…”

Hoặc:

“Ðối lập lại thiên nhiên bên ngoài là nội cảm có tính chủ thể, tâm hồn con người nhờ đó và qua đó yếu tố tuyệt đối biểu hiện sự có mặt của mình.”

Và đến cả câu đơn, đưa đẩy thôi, cũng khó hiểu nốt:

“ …, chúng tôi trình bày chi tiết hơn sự phân chia của phần thứ ba này phần chính của tác phẩm.”

Nếu bạn hiểu được ba câu này, tôi sẽ không nghi ngờ ông Heghen nữa, mà chuyển sang nghi ngờ tôi.

Chị kết luận

Và Triết thì phải khó (không thế sao vẫn có nhiều người lấy việc hiểu được nó làm tiêu chuẩn hơn thua nhau?). Thành ra tôi phải xem lại, xem ngoài cái khó về mặt tư tưởng, sách Triết (dịch) có bắt buộc phải khó (thêm) về mặt ngữ pháp không.

Tình trạng này không phải là độc quyền của sách Triết made-in-Vietnam. Quyển Intellectual Impostures chỉ ra đầy các loại ví dụ kiểu Sấm Hegel như Vàng Anh đã nêu. Bạn thử đọc các câu này:

We can clearly see that there is no bi-univocal correspondence between linear signifying links or archi-writing, depending on the author, and this multireferential, multi-dimensional machinic catalysis. The symmetry of scale, the transversality, the pathic non-discursive character of their expansion: all these dimensions remove us from the logic of the excluded middle and reinforce us in our dismissal of the ontological binarism we criticised previously.
…
In the first place, singularities-events correspond to heterogeneous series which are organized into a system which is neither stable nor unstable, but rather ‘metastable’, endowed with a potential energy wherein the differences between series are distributed… In the second place, singularities possess a process of auto-unification, always mobile and displaced to the extent that a paradoxical element traverses the series and makes them resonate, enveloping the corresponding singular points in a single aleatory point and all the emissions, all dice throws, in a single cast.
…

Xem thêm, ví dụ, reviews của Richard Dawkins.

Tình trạng “hoa môi múa mỏ” kiểu này cũng không phải độc quyền của Triết học. Quyển sách kinh điển và rất khôi hài Mathematics made difficult của Carl Linderholm cũng đầy các ví dụ làm cho toán học khó hơn cần thiết bởi cách lạm dụng ký hiệu, cùng các “abstract nonsense”. Ví dụ:

If is the set of functions with the property that

then there exists a bijection such that if then

Here, is the prime numbers and .

Theo kinh nghiệm của tôi, nhiều sinh viên KHMT không biết viết một chứng minh cho ra hồn. Đọc các chứng minh của sinh viên lớp algorithms/complexity đôi khi rất sốt ruột. Làm referee cho các non-theory conference/journal đôi khi cũng vậy, các tác giả viết dông dài và rối rắm cho một khái niệm hay chứng minh cực kỳ đơn giản. Khi cần notations để đơn giản chứng minh thì lại không dùng, khi không cần thì lại làm cho chứng minh (có vẻ) phức tạp hơn đáng kể vì các notations thừa thãi. Don Knuth có một quyển sách về Mathematical writing cho sinh viên KHMT: [pdf], trong đó có nhiều ví dụ và hướng dẫn rất cụ thể - từ writing styles đến writing flow. Rất nên đọc! Nhất là khi bạn đang tập tành viết papers.

Dĩ nhiên, ta cũng có thể làm cho các chương trình trông phức tạp hơn cần thiết.

Tóm lại, đừng làm khó nhau hơn mức cần thiết. Độ sâu của toán học không tỉ lệ thuận với tổng số ký hiệu nó dùng.

Chủ đề: Dành cho du học sinh & Giới thiệu sách | Bình luận »

Hôm nọ, đang thao thao chứng minh rằng Bland’s pivoting rule sẽ giúp phương pháp đơn hình (simplex method) không bị lặp vô hạn, thì một sinh viên hỏi

Why are we studying this?

Số là tôi cần khoảng 2, 3 tuần nói về quy hoạch tuyến tính (linear programming) để sau đó dùng vào thiết kế các giải thuật xấp xỉ. Theo một nghĩa nào đó, sinh viên này có lý vì bản thân Bland’s pivoting rule sẽ chẳng có ứng dụng gì (trực tiếp) vào các phương pháp thiết kế giải thuật xấp xỉ sẽ được trình bày trong phần còn lại của học kỳ.

Tôi có hai lý do kỹ thuật giải thích cho việc trình bày một terminating rule cho simplex method: (1) tôi muốn sinh viên làm quen với các kỹ thuật đại số (tuyến tính) để giải quyết các hệ thống phương trình và bất phương trình tuyến tính, kỹ năng này cực kỳ quan trọng trong thiết kế các giải thuật xấp xỉ dùng linear programming; và (2) đã dành 2 tuần để nói về linear programming và simplex method, về duality, separation theorem, và một ít polyhedral combinatorics, thì việc chứng minh rằng simplex method không loop vô tận sẽ hoàn tất thảo luận này.

Khi đó tôi trả lời sinh viên này như vậy. Trong đầu tôi lại nghĩ khác.

Các định lý và thuật toán cơ bản liên quan đến linear programming có thể nói là một trong những khám phá quan trọng nhất của thế kỷ 20. Bản thân việc này đã đủ để tôi muốn biết về linear programming, cho dù chẳng dùng nó làm gì đi nữa! Chẳng lẽ — khi có cơ hội — ta lại không muốn biết Kantorovich và Koopmans đã nhận giải Nobel về cái gì, không buốn biết von Neumann và Morgenstern có ảnh hưởng lớn thế nào đến kinh tế học (đến năm ngoái — 2005 — mà các game theorists vẫn nhận Nobel). Nhu cầu tri thức định lượng được chăng? Ai lại chẳng muốn bước lên nấc kế tiếp trong 5 mức dốt?

Lẽ nào “thú vị và sâu sắc” không đủ làm lý do cho ta muốn biết một điều gì đó? Với tôi, như vậy là quá đủ. Tôi không cần thêm “có ứng dụng” để quyết định xem mình muốn biết điều đó hay không.

Nhưng rồi tôi lại nghĩ: thế khi nào thì đủ? Hay là câu hỏi của sinh viên nọ vẫn hợp lý? “Tri thức vị tri thức” hay “tri thức vị nhân sinh”? Tôi rất ghét thái độ “tri túc tắc túc” trong quá trình tìm tòi tri thức.

Tôi chợt nhận ra là, trong rất nhiều posts trên blog này tôi đã viết một câu kiểu “những ai học/làm về KHMT đều phải đọc/biết cái này, cái kia, …” Chắc sẽ có bạn nghĩ: “những ai học/làm về KHMT đều phải … sống đã!” Chẳng phải chính tôi đã viết rằng pleasure time thì quan trọng hơn leisure time hay sao? Muốn có pleasure thì còn “phải” làm những thứ thế này nữa chứ (cảm ơn anh Thái đã cho link), thời gian đâu mà “phải” đọc cái này, “phải” đi tìm hiểu cái kia nữa?

Đến đây thì tôi nhận ra rằng câu hỏi “học bao nhiêu là đủ?” là câu hỏi sai. Đáng lẽ ta phải hỏi “học cái gì thì cho ta pleasure?” Với tôi, “thú vị và sâu sắc” là một nguồn pleasure vô tận.

Có lẽ, áp đặt pleasure của mình lên sinh viên là việc làm thiếu công bằng. Nhưng tôi tin rằng một trong những vai trò chính của người thầy là truyền cảm hứng cho sinh viên tìm được pleasure trong những thứ thú vị và sâu sắc, và trong cả quá trình lao động để tìm tòi ra những thứ ấy. Khi tìm được pleasure thì tri thức sẽ vị cả tri thức lẫn nhân sinh.

Pleasure thì bao nhiêu cho đủ?

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

Một bài tổng quan rất rất hay của Avi Wigderson, bổ túc cho cái talk ông nói ở ICM 2006. Bài này đào sâu vào phần cuối (và các phát triển sau đó) của bài Chung Qui Chỉ Tại Cantor. Tôi tin rằng tất cả các sinh viên KHMT đều phải đọc qua bài của Avi. Các khái niệm trung tâm của KHMT lý thuyết hiện nay đều được duyệt qua một cách đơn giản và trực quan: computation, undecidability, P vs NP, NP-completeness, lower bounds (and the difficulty of proving them), proof complexity, randomness in computations and proofs (bao gồm interactive proof, zero-knowledge proof, probabilistically checkable proofs).

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

Trích tản văn của Belle Waring viết năm ngoái nhân kỷ niệm ngày 11 tháng 9. Rất hay!

I have looked at that picture of Osama Bin Laden many times. He doesn’t look quite right, I mean, not as I would want him to look. Not angry enough. Khomeini was a very satisfactory villian for the American public. Bin Laden? He looks thoughtful. Inward-gazing. I try to imagine thoughts to put there, behind his too-soft eyes. I put my imaginary desert landscapes there: life reduced to its essentials, a single man trudging along the horizon under a bowl of infinite blue. Is this what he wants? The whole world pared down, all taking the same journey into desert as Arabia Felix did, that was once so green? Nothing extraneous, nothing human? Nothing female, certainly. On Cyprus they used to worship Aphrodite in an aniconic form: a cone of volcanic rock, five feet high. You can see it there, in a museum. Even that would be too much for him.

Last year I went to New York for the first time since September 11, 2001. Driving over the 59th Street bridge I looked back at the curiously balanced skyline. It used to be massively weighted at the tip, anchored by those vertical marks. Now it just floated there, behind the car, the buildings of the east side lowering behind the tombstones of that massive graveyard in Queens, serried rank upon rank, until I could see them no more.

Chủ đề: Nhân vật và sự kiện | Bình luận »

Đã có không ít các nhà kinh tế và chính trị gia đề nghị bỏ hẳn đồng 1 cent của Mỹ

Pennies are copper-coated zinc, and due to a recent run-up in the prices of those metals — with zinc up to about $1.49 cents a pound from about 50 cents in 2000 — the penny now costs 1.4 cents to make, according to the United States Mint.

Producing and handling pennies costs the United States about $900 million a year, according to Wake Forest University professor Robert M. Whaples, whose research Kolbe cites.

Nghe cũng có lý. Thế 1 cent có thể dùng làm gì? Hay là mua quyển sách này ở Amazon? Người ta vẫn còn tranh cãi lâu.

Chủ đề: Vui - Giải Trí | Bình luận (1) »

Trích một bài gần đây ở Talawas

Cách nay khoảng một năm, lượn nhà sách, nhác thấy cuốn (bìa) đỏ Cha thánh của Mario Puzo, “linh tính” đã mách bảo có điều gì, nhưng phải khi mua về cầm giở ra xem mới biết đó chính là tác phẩm The Godfather mà Ngọc Thứ Lang đã dịch hơn 30 năm trước thành Bố Già, còn Ðoàn Tử Huyến và Trịnh Huy Ninh năm 1987 cũng phải mượn chữ Bố Già cực hay và không thể thay khác đi được

Vài ví dụ dịch (sai) buồn cười khác mà tôi còn nhớ:

• Legends of the Fall = Huyền thoại về cái thác (cú này lấy từ một điểm phim trên báo, bà xã tôi kể lại)
• the act of god-eating = nghệ thuật chọn đồ ăn cho Chúa (cú này ở bản dịch đầy tai tiếng quyển Da Vinci code)
• His Holiness = sự linh thiêng của ngài; (cú này cũng ở bản dịch quyển Da Vinci code)

Còn cụm từ nào đã/hay bị dịch sai một cách khôi hài không nhỉ?

Chủ đề: Vui - Giải Trí & Xuất bản | Bình luận (8) »

Theo bài của Dubner và Levitt ở NY Times Magazine:

… the study found a tax gap — the difference between taxes owed and taxes actually paid — of $345 billion, or nearly one-fifth
of all taxes collected by the I.R.S. This sum happens to be just a few billion dollars less than the projected federal budget deficit for
2007;
… So why do people really pay their taxes: because it is the right thing to do, or because they fear getting caught if they don’t? It sure seems to be the latter.
… A few years later, however, with Congress clamoring for more tax revenue, Szilagyi’s idea was dug up, rushed forward and put into law for tax year 1986. When the returns started coming in the following April, Szilagyi recalls, he and his bosses were shocked: seven million dependents had suddenly vanished from the tax rolls, some incalculable combination of real pets and phantom children.

Bài học: incentives work wonder! Nói chung, người ta cheat được là cheat. Cơ cấu tổ chức là quan trọng chứ không phải mấy trò hề duy ý chí kiểu “nhân chi sơ tính bản thiện”. Lại nhớ vụ xả rác, recycle, và kế hoạch nhỏ.

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