Thư viện bài, chủ đề ‘Dành cho du học sinh’

Thư học trò

Ngô Quang Hưng | 18 tháng 08, 2008 | Bản để in Bản để in

Như mọi năm, đến gần thời gian mà các sinh viên chuẩn bị nộp đơn vào grad school tôi nhận được khá nhiều emails từ các prospective students từ nhiều nơi trên thế giới. (Nhiều nơi = TQ và Ấn.) Hôm nay mới nhận được một thư khá dài dòng, kể thành tích nghiên cứu MPLS, traffic engineering đủ loại, xong rồi kết luận, và tôi trích nguyên văn

I hope we can keep touching

Email còn gửi kèm ảnh, một chú … húi cua đeo kính cận.

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

Du học sinh

Ngô Quang Hưng | 03 tháng 07, 2008 | Bản để in Bản để in

Xem cái này bên PhD Comics.

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

Lại nói về viết paper

Ngô Quang Hưng | 09 tháng 01, 2008 | Bản để in Bản để in

Một trách nhiệm xã hội của nghề nghiệp tôi là làm phê bình (referee, reviewer) cho các bài báo nộp vào các tạp chí và hội nghị chuyên ngành. Tôi mong gì ở một bài báo mà mình làm “trọng tài”? Đã viết về đề tài này, hôm nay xin lập lại theo một góc nhìn khác:

  1. Tôi muốn học được một cái gì đó mới từ bài báo!
  2. Tôi muốn ý tưởng chính của cái mới này được thể hiện một cách rõ ràng mà không bị chìm trong đống ký hiệu, định nghĩa, thuật toán, chứng minh, v.v. Nhất là khi các ký hiệu, định nghĩa này là do bài báo tự đặt ra để giải quyết một vấn đề cụ thể mà không phải là ký hiệu, định nghĩa có giá trị phổ quát từ một nhánh nghiên cứu trưởng thành.

Phải đến 80% số bài báo tôi đọc trong ngành networking không thể hiện được 1 hoặc 2 hoặc cả hai. Cực kỳ frustrating (mệt mỏi và thất vọng). Cực kỳ tốn thời gian.

Dưới đây là vài ví dụ.

1. Cách đây hai hôm, vừa nộp phê bình một bài báo có nội dung như sau: (1) bài toán là tìm cách thiết kế multicast routing algorithm trên mạng mobile ad hoc networks để tối ưu life-time của mạng do nguồn năng lượng của các mobile nodes là hữu hạn, (2) bài báo formulate bài toán này theo dạng mixed integer linear program (MILP). Cái formulation tốn mất 5 trang bài báo. Chấm hết.

Trời đất!

Nội dung bài báo tương đương với “giải pháp” sau đây cho bài toán giết gà: dùng dao mổ trâu, nhắm cổ gà chặt thật mạnh.

MILP là một công cụ cực kỳ hùng mạnh. Việc ta có thể formulate một bài toán optimization dùng MILP thì không gọi là nghiên cứu., mà gọi là bài tập về nhà loại dễ của lớp combinatorial optimization. Quan trọng hơn, giải một MILP thường là khó hơn bài toán optimization đang xét!!!

Có một số hướng để justify việc dùng MILP formulation cho một bài toán nào đó:

  • Có thể giải cái MILP này một cách hiệu quả cho một typical instance của bài toán optmization. Nghĩa là mặc dù MILP khó nói chung, nhưng không “khó” đối với các instance thông thường của bài toán đang xét. Có thể chứng minh điều này bằng analysis hoặc experiment/simulation
  • Cái MILP cho ta một framework để thiết kế một thuật toán xấp xỉ cho bài toán đang xét.
  • Cái MILP cho ta một framework để thiết kế một distributed protocol cho bài toán đang xét.

2. Năm ngoái review một bài báo giải quyết vấn đề intrusion prevention bằng cách nối hai gateways với nhau: một gateway nối với local network, một gateway nối ra ngoài Internet. Hai gateway giao tiếp bằng một crytographic protocol.

Tôi đề nghị ta viết một C-compiler bằng cách viết chương trình dịch C program sang Fortran, sau đó viết chương trình dịch Fortran sang Java, sau đó dùng Java Virtual Machine để chạy.

3. Hôm qua và hôm nay đọc một bài báo routing trên Delay Tolerant Network. Sau khi đưa ra một đống giả thiết, bài báo tốn 5 trang định nghĩa và ví dụ, xong rồi 2 trang thuật toán được mô tả rất formal, với cấu trúc dữ liệu cẩn thận. Tóm lại là dùng thuật toán Dijkstra :-)

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

Sư tử và thỏ

Ngô Quang Hưng | 18 tháng 10, 2007 | Bản để in Bản để in

Câu chuyện sau đây, không biết từ đâu ra, rất phổ biến trong đám sinh viên sau đại học.

Một ngày nắng đẹp, thỏ ngồi gõ bàn phím trước cửa hang.

Cáo đi qua thấy, ngạc nhiên hỏi: “mày đang làm gì đấy thỏ?”

“Tớ đang gõ luận án”, thỏ trả lời.

– “Luận án về đề tài gì?”

– “Đề tài của tớ là ‘tính khả thi của việc thỏ ăn thịt cáo’”

Cáo tí nữa thì sặc, hỏi tiếp: “phét lác vừa vừa thôi, mày có dữ liệu nào để phân tích và minh chứng cho luận án này không?”

– “Vào hang với tớ, tớ cho xem.”

Cáo và thỏ vào hang. Một lúc sau, thỏ đi ra tiếp tục gõ bàn phím.

Sói đi qua thấy, ngạc nhiên hỏi: “mày làm gì thế thỏ?”

“Tớ đang gõ luận án”, thỏ trả lời.

– “Luận án về đề tài gì?”

– “Đề tài của tớ là ‘tính khả thi của việc thỏ ăn thịt sói’”

Sói lại đòi xem data, thỏ lại dẫn vào hang.

Một lúc sau thỏ lại ra ngoài gõ tiếp.

Trong hang thoang thoảng có tiếng sư tử liếp mép, gầm gừ.

Bài học: nội dung luận án là gì không quan trọng, quan trọng là advisor của bạn là ai!

Nói đi thì cũng phải nói lại:
Đọc tiếp toàn bài »

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

Một bài toán đố nhỏ

Ngô Quang Hưng | 12 tháng 09, 2007 | Bản để in Bản để in

Khi số nguyên n tiến đến vô cùng, n |\sin(n)| có tiến đến vô cùng hay không? Tại sao? (Nhớ rằng n là số nguyên.)

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

Lớp phân tích và thiết kế giải thuật

Ngô Quang Hưng | 06 tháng 09, 2007 | Bản để in Bản để in

Học kỳ này tôi (lại) dạy lớp phân tích và thiết kế giải thuật. Đây là lớp mở đầu phân tích thiết kế thuật toán cho sinh viên sau đại học (năm đầu). Các chủ đề sẽ được thảo luận bao gồm:

asymptotic notations and analysis, greedy algorithms, divide and conquer, dynamic programming, linear programming, network flows, NP-completeness, approximation algorithms, randomized algorithms

Bạn nào quan tâm có thể xem homepage của lớp cùng với một blog cho lớp. Trên blog này sẽ có các thông báo, bình luận, tin tức, và liên kết đến các nguồn tin, bài báo, v.v. liên quan đến phân tích và thiết kế thuật toán. Ngoài ra trên homepage của lớp còn có bài tập và các bài kiểm tra, cùng với tóm tắt bài giảng.

Tôi sẽ để bài tập và bài kiểm tra cho mọi người đều truy cập được. Tuy nhiên, phần đáp án thì chỉ có sinh viên trong lớp tôi truy cập được dùng username/password tôi cho. Lý do mà tôi không muốn để đáp án mở: nếu ai đó thật sự quan tâm và muốn học phân tích và thiết kế thuật toán thì nên tự giải quyết các bài tập. Sinh viên của tôi phải nộp bài rồi mới được xem đáp án. Tương tự như việc tôi đăng các câu hỏi phỏng vấn nhưng không đăng câu trả lời. Cuộc đời sẽ thú vị hơn nhiều khi không có đáp án.

Từ quan điểm cá nhân, tôi không thể tưởng tượng một lớp đại học trong thế kỷ 21 mà lại không có homepage cùng một loại forum nào đó để thảo luận các đề tài trong lớp! Bây giờ làm homepage trên Internet dễ cực: wordpress, blogger, googlepages, etc.

Chủ đề: Dành cho du học sinh & Thuật Toán | Bình luận (8) »

Vô chiêu thắng hữu chiêu

Ngô Quang Hưng | 24 tháng 08, 2007 | Bản để in Bản để in

Các mẩu chuyện dưới đây nói về cùng một ý, trả lời cùng một câu hỏi — thế nào là hiểu?

  • Độc cô cửu kiếm rắc rối phức tạp, thông minh như Lệnh Hồ Xung mà học mãi mới được vài thức. Vậy mà đến tuyệt đỉnh thì gã chẳng nhớ thức nào. Trương Tam Phong dạy Trương Vô Kỵ Thái Cực Quyền/Kiếm. Dạy xong chiêu nào lại hỏi “con đã quên chưa”? Tiêu Phong loạn đả Tụ Hiền Trang chỉ cần dùng mấy đường Thái Tổ Trường Quyền ai cũng biết.
  • Quyển blink của Gladwell kể lại đầy rẫy những chuyện mà quyết định trực quan trong tích tắc của một cá nhân dày công rèn luyện là các quyết định đúng đắn và hữu lý đến kinh ngạc.
  • Trong bài “mã hóa tri thức như thế nào“, tôi đã viết rằng khi ta thật sự hiểu một môn học thì trong đầu tôi có một mô hình tái sinh cần cực ít dữ liệu vẫn có thể tái tạo lại nền tảng môn học. Ngoài ra, ta có thể trình bày lại các ý tưởng của môn học một cách rất ngẫu hứng, không cần theo một “giáo trình” xắp sẵn nào cả.
  • Tôi học bơi từ năm lớp 5 ở hồ CLB Lao Động (Xẹc cũ). Tôi bơi được cả 4 kiểu ếch, sải, bướm, ngửa. Ngoại trừ bơi ếch còn tương đối, tôi biết rằng 3 kiểu còn lại tôi chỉ biết hình thức mà không hiểu nội dung — bằng chứng cụ thể nhất là tôi thấy mình bơi rất tốn sức mà lại không hiệu quả. Ví dụ: dân bơi chuyên nghiệp bơi sải trung bình cần 30 sải tay (nghĩa là mỗi tay quạt 15 cái) là bơi được 50 mét, rất nhẹ nhàng và hiệu quả. Mỗi sải tay họ bơi được gần 2 mét!

    Hai tháng vừa qua, tôi đi tìm hiểu thêm để tìm cách tăng hiệu suất bơi sải của mình. Tôi biết hết các kỹ thuật cơ bản của bơi sải: (a) giữ người thẳng tròng trành như một chiếc thuyền dài (b) thở hai bên (nhịp lẻ) và thở dùng cái rãnh nước do đầu tạo ra khi lướt trên mặt nước, (c) khi quạt tay thì có 4 bước là vươn tới, bẻ ngang, kéo, và đẩy, cùng với giữ tay sát người, (d) đá chân thì phải thẳng và có 4 kiểu nhịp chính: 2, 4, 6-nhịp, và 2-nhịp xéo. Bạn xem thử đoạn video clip dưới đây để biết tôi nói gì:


    (Bill Kirby là một nhà vô định Olympic)

    Tôi cố gắng tập hơn một tháng qua và đã giảm được tổng số sải tay trên 50 mét từ 70 sải xuống còn 48 sải, một tiến bộ lớn và tôi rất vui! (Vui không kém gì viết được một bài báo hay!) Thế nhưng tôi vẫn thấy mình biết bơi sải hình thức hơn là hiểu nội dung. Khi bơi vẫn còn phải nhớ các “chiêu” a, b, c, d ở trên. Muốn bơi thật hiệu quả thì phải “cảm” được cơ thể mình và giao tiếp của nó với nước. Bạn muốn xem dân chuyên nghiệp bơi “vô chiêu” không? Hãy xem Alex Popov — khủng hoảng luôn :-)


    (Để ý cú bơi sải thở đằng trước.)

  • Trong quyển Surely you are joking, Mr. Feynman, Richard Feynman kể lại chuyện ông đi Brazil hồi thập niên 50, thấy học sinh Brazil đọc sách Vật Lý nhiều, làm bài kiểm tra rất tốt, nhưng lại khám phá ra rằng họ chẳng hiểu gì về Vật Lý cả. Cuối chuyến đi, Feynman có cơ hội giải thích cho các nhà Vật Lý Brazil tại sao ông lại nghĩ thế, và làm thế nào để cải thiện sách giáo khoa Vật Lý. Tôi trích ra đây vài đoạn trong chương “O Americano, Outra Vez!” (đoạn tôi trích hơi dài, nhưng tôi rất thích vì rất giống tình trạng học tập ở Việt Nam khi tôi còn đi học — các bạn chịu khó đọc)

    The lecture hall was full. I started out by defining science as an understanding of the behavior of nature. Then I asked, “What is a good reason for teaching science? Of course, no country can consider itself civilized unless . . . yak, yak, yak.” They were all sitting there nodding, because I know that’s the way they think.

    Then I say, “That, of course, is absurd, because why should we feel we have to keep up with another country? We have to do it for a good reason, a sensible reason; not just because other countries do.” Then I talked about the utility of science, and its contribution to the improvement of the human condition, and all that - I really teased them a little bit.

    Then I say, “The main purpose of my talk is to demonstrate to you that no science is being taught in Brazil!

    I can see them stir, thinking, “What? No science? This is absolutely crazy! We have all these classes.”

    So I tell them that one of the first things to strike me when I came to Brazil was to see elementary school kids in bookstores, buying physics books. There are so many kids learning physics in Brazil, beginning much earlier than kids do in the United States, that it’s amazing you don’t find many physicists in Brazil - why is that? So many kids are working so hard, and nothing comes of it.

    Then I gave the analogy of a Greek scholar who loves the Greek language, who knows that in his own country there aren’t many children studying Greek. But he comes to another country, where he is delighted to find everybody studying Greek - even the smaller kids in the elementary schools. He goes to the examination of a student who is coming to get his degree in Greek, and asks him, “What were Socrates’ ideas on the relationship between Truth and Beauty?” - and the student can’t answer. Then he asks the student, What did Socrates say to Plato in the Third Symposium?” the student lights up and goes, “Brrrrrrrrr-up” - he tells you everything, word for word, that Socrates said, in beautiful Greek.

    But what Socrates was talking about in the Third Symposium was the relationship between Truth and Beauty!

    What this Greek scholar discovers is, the students in another country learn Greek by first learning to pronounce the letters, then the words, and then sentences and paragraphs. They can recite, word for word, what Socrates said, without realizing that those Greek words actually mean something. To the student they are all artificial sounds. Nobody has ever translated them into words the students can understand.

    I said, “That’s how it looks to me, when I see you teaching the kids ’science’ here in Brazil.” (Big blast, right?)

    Then I held up the elementary physics textbook they were using. “There are no experimental results mentioned anywhere in this book, except in one place where there is a ball, rolling down an inclined plane, in which it says how far the ball got after one second, two seconds, three seconds, and so on. The numbers have ‘errors’ in them - that is, if you look at them, you think you’re looking at experimental results, because the numbers are a little above, or a little below, the theoretical values. The book even talks about having to correct the experimental errors - very fine. The trouble is, when you calculate the value of the acceleration constant from these values, you get the right answer. But a ball rolling down an inclined plane, if it is actually done, has an inertia to get it to turn, and will, if you do the experiment, produce five-sevenths of the right answer, because of the extra energy needed to go into the rotation of the ball. Therefore this single example of experimental ‘results’ is obtained from a fake experiment. Nobody had rolled such a ball, or they would never have gotten those results!

    “I have discovered something else,” I continued. “By flipping the pages at random, and putting my finger in and reading the sentences on that page, I can show you what’s the matter - how it’s not science, but memorizing, in every circumstance. Therefore I am brave enough to flip through the pages now, in front of this audience, to put my finger in, to read, and to show you.”

    So I did it. Brrrrrrrup - I stuck my finger in, and I started to read: “Triboluminescence. Triboluminescence is the light emitted when crystals are crushed..

    I said, “And there, have you got science? No! You have only told what a word means in terms of other words. You haven’t told anything about nature-what crystals produce light when you crush them, why they produce light. Did you see any student go home and try it? He can’t.

    “But if, instead, you were to write, ‘When you take a lump of sugar and crush it with a pair of pliers in the dark, you can see a bluish flash. Some other crystals do that too. Nobody knows why. The phenomenon is called “triboluminescence.”‘ Then someone will go home and try it. Then there’s an experience of nature.” I used that example to show them, but it didn’t make any difference where I would have put my finger in the book; it was like that everywhere.

    Finally, I said that I couldn’t see how anyone could he educated by this self-propagating system in which people pass exams, and teach others to pass exams, but nobody knows anything. “However,” I said, “I must be wrong. There were two students in my class who did very well, and one of the physicists I know was educated entirely in Brazil. Thus, it must be possible for some people to work their way through the system, had as it is.”

    Well, after I gave the talk, the head of the science education department got up and said, “Mr. Feynman has told us some things that are very hard for us to hear, but it appears to he that he really loves science, and is sincere in his criticism. Therefore, I think we should listen to him. I came here knowing we have some sickness in our system of education; what I have learned is that we have a cancer!” - and he sat down. That gave other people the freedom to speak out, and there was a big excitement. Everybody was getting up and making suggestions. The students got some committee together to mimeograph the lectures in advance, and they got other committees organized to do this and that.

    Then something happened which was totally unexpected for me. One of the students got up and said, “I’m one of the two students whom Mr. Feynman referred to at the end of his talk. I was not educated in Brazil; I was educated in Germany, and I’ve just come to Brazil this year.”

    The other student who had done well in class had a similar thing to say. And the professor I had mentioned got up and said, “I was educated here in Brazil during the war, when, fortunately, all of the professors had left the university, so I learned everything by reading alone. Therefore I was not really educated under the Brazilian system.”

    I didn’t expect that. I knew the system was bad, but 100 percent - it was terrible!

    Điều mà Feynman muốn nói cũng chính là điều mà Phong Thanh Dương và Trương Tam Phong dạy bảo: chiêu thức chỉ là hình thức, là các từ mô tả các khái niệm (sóng, hạt, nhiệt, năng lượng), v.v. Biết chiêu thức là chỉ biết cái hình thức mà không biết nội dung. Một học sinh thông minh có thể thao tác cái hình thức (công thức, ký hiệu, tên gọi) để làm bài kiểm tra cho tốt, nhưng điều đó không nhất thiết cho thấy là học sinh nọ thật sự hiểu môn học. Feynman viết một câu thật chí lý: “tôi không thể hiểu được một hệ thống giáo dục khi nó chỉ là một hệ thống tự lan truyền, trong đó người ta thi cử, và dạy học trò mình thi cử“.

    Viết đến đây tôi lại nhớ Tú Xương:

    Tập tễnh người đi tớ cũng đi,
    Cũng lều cũng chõng cũng vào thi.
    Tiễn chân, cô mất hai đồng chẵn,
    Sờ bụng: thầy không một chữ gì!

    Lộc nước còn mong thêm giải ngạch
    Phúc nhà nay được sạch trường qui.
    Ba kì trọn vẹn thêm kì nữa,
    Ú ớ u ơ ngọn bút chì.

  • Bà xã tôi đọc được đoạn bình văn sau đây (xin phép không trích nguồn), bạn đọc xong sẽ hiểu thế nào là “có hình dạng mà thiếu nội dung”:

    Những câu văn của Nguyễn Nguyên Phước rất có thể trở thành đích ngắm cho các nhà ngôn ngữ học purist, nhưng mặt khác, chúng đang chứng minh rằng ngôn ngữ rất không có khuôn mẫu, và không có tính kế thừa nhất định. Và đang thay đổi rất nhanh. Có lẽ đã đến lúc tiếng Việt được cung cấp những khả năng diễn đạt mới mẻ, điều mà ngôn ngữ nào cũng xứng đáng được hưởng.

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

Nhan đề, đầu đề, tựa đề, tiêu đề

Ngô Quang Hưng | 23 tháng 08, 2007 | Bản để in Bản để in

Cái nào là cái nào? Quả thật là đôi khi tôi đã dùng tựa đề để chỉ nhan đề.

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

Các câu hỏi phỏng vấn [29]

Ngô Quang Hưng | 17 tháng 07, 2007 | Bản để in Bản để in

Đề tài hôm nay là các số trên vòng tròn.

  1. 25 hòn sỏi đen và 25 hòn sỏi trắng được xếp thành vòng tròn. Chứng minh rằng có một hòn sỏi mà hai hòn hai bên (trái, phải) đều trắng.
  2. Có n số thực nằm trên một vòng tròn với tổng không âm. Chứng minh rằng tồn tại một trong n số này, tạm gọi là số x, thỏa mãn điều kiện sau đây: với mọi k > 0 thì tổng của k số thực, kể từ x theo chiều kim đồng hồ, là không âm.
  3. Giả sử ta có n số nguyên trên một vòng tròn. Ta được phép làm một phép biến đổi, gọi là “biến đổi tếu“, như sau: tìm 3 số (a,b,c) nằm kề nhau liên tục trên vòng tròn, trong đó b < 0, và đổi chúng thành (a+b, -b, c+b). Mệnh đề sau đây đúng hay sai: có thể gán n số nguyên vào một vòng tròn để ta có thể biến đổi tếu mãi mãi, không bao giờ bị kẹt

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

Machine learning và Michael Moore

Ngô Quang Hưng | 11 tháng 07, 2007 | Bản để in Bản để in

… chẳng liên quan gì đến nhau :-).

  • Theo Computer World thì machine learning đứng đầu danh sách 12 kỹ năng nhờ đó bạn đảm bảo sẽ có việc. Trong 11 mục còn lại, có đến 3, 4 mục liên quan đến networking.
  • Trận đại chiến giữa Michael Moore và Sanjay Gupta tối qua trên CNN làm tôi mất hẳn bất kỳ sự tôn trọng còn lại nào với bác Michael Moore. Tôi biết đến Michael Moore qua Bowling for Columbine, một phim tài liệu tôi rất thích (và bác Moore được giải Oscar rất xứng đáng). Đến Farenheit 911 thì thấy khá tếu, giải trí được vài phút, nhưng không thể gọi là phim tài liệu nghiêm túc. Nghe một số báo chí (NY Times, Time) bảo Sicko “mềm mại” trở lại, là phim tài liệu không tệ. Tôi đã hào hứng định xem Sicko. Nhưng trận đại chiến tối qua làm tôi chán hẳn. (Vụ thách đấu thì bắt đầu từ hôm kia khi Moore loạn đả Blitzer.) Moore đã biến thành một Ann Coulter của cánh trái. Chán hẳn!

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

Học toán được gì?

Ngô Quang Hưng | 20 tháng 06, 2007 | Bản để in Bản để in

Stobaeus ghi lại truyền thuyết sau đây về Euclid.

Khi một chú học trò hỏi Euclid: “chúng ta học hình học thì được cái gì?”, Euclid gọi một anh nô lệ vào bảo: “cho nó một đồng xu, vì nó muốn kiếm lời từ cái nó học”.

Đáng lẽ tôi phải kể câu chuyện này để kết thúc bài học bao nhiêu là đủ.

Chủ đề: Danh ngôn & Dành cho du học sinh | Bình luận (14) »

Mã hóa tri thức như thế nào?

Ngô Quang Hưng | 12 tháng 06, 2007 | Bản để in Bản để in

Bên gỡ rối tơ lòng, bạn tvhvt có câu hỏi thú vị:

Sử dụng ngôn ngữ gì để mã hóa và lưu trữ thông tin, tri thức?

Nói chung, tôi mã hóa thông tin/tri thức học được bằng một algorithm/generative model. Thông tin/tri thức nào có Kolmogorov complexity càng thấp thì tôi nhớ càng lâu, hiểu càng sâu. Nói cách khác, sự đơn giản của algorithm và/hoặc sự đơn giản của generative model tạo thông tin đó tỉ lệ thuận với độ dễ hiểu và dễ nhớ của thông tin.

Xin giải thích lại đoạn văn trên bằng tiếng Việt như sau.

Tôi đã viết là khi đọc một quyển sách mới, tôi thường có thói quen “viết lại” sách theo ý mình. Viết lại theo nghĩa đen, hoặc ghi rất nhiều notes ở khắp nơi (trên giấy, trên blog, v.v.). Tôi cho rằng cá nhân mình chưa thật sự hiểu một môn học nào đó cho đến khi mình có thể từ một lượng data rất nhỏ là đã có thể tự xây dựng lại nền tảng lý thuyết của môn đó. Cách tốt nhất để thử xem mình có hiểu môn học không là trình bày lại toàn bộ môn học mà không cần bất kỳ tham khảo gì xung quanh mình (Internet, sách vở, v.v.). Vì thế, tôi đi giảng bài trong lớp không bao giờ mang notes/books theo. Với các môn lý thuyết thì 95% số lectures là tôi vào lớp với vài cục phấn. Năm phần trăm còn lại, phải mang notes theo, là dành cho các đề tài tôi chưa thật sự hiểu.

Để làm được như thế, ta không thể nào đọc/học theo kiểu cưỡi ngựa xem hoa. Trước khi đọc chứng minh một định lý nào đó, tôi luôn dành một ít thời gian thử tự chứng minh nó. Nếu quyển sách viết rất tốt thì chúng ta thật sự không cần đọc nhiều chứng minh cho lắm (trừ các định lý cực kỳ bất ngờ, là đột phá trong ngành!).

Trong các ví dụ trên tôi dùng các môn lý thuyết làm dẫn chứng. Đối với các môn kỹ thuật hơn một chút, networking chẳng hạn, thì có cực kỳ nhiều chi tiết kỹ thuật lắt nhắt khó nhớ. Điều này đúng cho hầu hết các ngành engineering phải giải quyết các vấn đề thực tế. Generative model của mình sẽ phải deal với nhiều noise. Trong trường hợp này, tôi sẽ cố tạo generative model cho các ý tưởng chính của ngành: nguyên tắc KISS, distributive tốt hơn centralized, local tốt hơn global, ARQ, randomization, v.v. Sau một thời gian, ta sẽ thấy là tổng số ý tưởng original trong networking có thể đếm trên đầu ngón tay. Còn lại chỉ là các biến thể be bé để giải quyết nhiễu.

Đoạn trên có … nhiễu quá không?

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

Kinh nghiệm viết paper

Ngô Quang Hưng | 17 tháng 05, 2007 | Bản để in Bản để in

Bạn NDD hỏi kinh nghiệm viết technical paper tiếng Anh. Tôi xin chia sẻ 2 cents của mình, mặc dù đã có đề cập vài nơi trong blog này đến đề tài viết lách, ví dụ như đừng viết sấm Hegel như chị Vàng Anh đã cảnh báo, hoặc dùng gợi ý của Manuel Blum. Ngoài ra còn có vài nguồn khác về viết lách trên Internet.

Chất lượng technical papers có thể chia thành 3 phần chính:

  1. Stylistic element: cấu trúc câu, chấm phẩy thế nào, tổ chức một paragraph ra sao? Xin đọc quyển sách kinh điển Elements of styles. Đây là quyển sách phải-đọc cho tất cả các thể loại viết lách tiếng Anh. (Phải đọc cho cả người bản xứ!)
  2. Organizational element: tổ chức bài viết cho tốt. Thông thường, một bài báo nên có cấu trúc như sau (không nhất thiết phải theo thứ tự này)
    1. Phần giới thiệu: đặt kết quả của mình vào ngữ cảnh lớn hơn, giải thích tại sao vấn đề là quan trọng, tại sao nó khó khăn, tại sao các kết quả hiện nay chưa thỏa đáng, đóng góp kỹ thuật của bài báo là gì, và đóng góp này “khớp” ra sao vào bức tranh lớn của (phân) ngành.
    2. Phần literature review: mô tả chi tiết hơn các nghiên cứu đã có, phân tích sơ bộ tại sao chúng chưa thỏa đáng cho vấn đề mình muốn giải quyết.
    3. Phần formulation: định nghĩa vấn đề một cách chặt chẽ hơn, nêu rõ các giả thiết (assumptions) mà mình dùng và giải thích tại sao mình lại có thể dùng các giả thiết này. Phần giải thích giả thiết có thể phải bao gồm cả simulations và experiments.
    4. Phần lời giải: trình bày các định lý, thuật toán, mô hình, v.v. những thứ cấu thành lời giải. Cái nào dài dòng rắm rối về mặt chi tiết mà không tải nhiều ý thì bỏ ra appendix cũng được.
    5. Phần validation của lời giải: nếu bạn có một thuật toán, một mô hình mới thì phải validate nó analytically và/hoặc experimentally. Analytical validation bao gồm phân tích độ phức tạp không/thời gian của thuật toán, chứng minh soundness, completeness, hay rate of convergence của một thuật toán tối ưu, v.v. Experimental validation bao gồm chạy thử và so sánh chất lượng giải pháp của mình với những giải pháp tốt nhất đã có, cẩn thận control các tham số khi so sánh, giải thích các drawbacks nếu có của giải pháp là ở đâu, có đáng “hy sinh” các drawbacks này không, v.v.
    6. Phần kết luận và phân tích hướng nghiên cứu tương lai: chẳng có giải pháp nào là hoàn hảo trong một bài báo, ta phải kết luận và phân tích xem tương lai cần làm gì tiếp, giải pháp của ta đã mở ra hướng nghiên cứu mới nào, v.v.
  3. Novelty: giá trị của đóng góp của ta dĩ nhiên không chỉ nằm ở cái cấu trúc của bài báo hay ở việc viết tiếng Anh xuôi chèo mát mái. Có nhiều bài báo có tất cả các thành tố vừa nêu (bao gồm giải pháp và validation) nhưng vẫn không được nhận đăng ở các hội nghị và tạp chí danh tiếng. Tại sao? Tại vì technical novelty không đủ mạnh! Mặc dù “technical novelty” là một khái niệm chủ quan, nếu bạn là người ở lâu trong ngành thì sự đánh giá này sẽ ngày càng trở nên khách quan. Tôi không có một định nghĩa chặt chẽ cho khái niệm này, nên sẽ nêu vài ví dụ.

    Ví dụ 1: bạn có một implementation tốt của thuật toán quicksort, trong đó có nhiều mẹo dùng pointers, memory allocation, v.v. làm cho implementation của bạn tốt hơn tất cả các implementation hiện có khoảng 20 phần trăm về mặt thời gian chạy. Đây rõ ràng là một đóng góp không tồi cho KHMT. Trên thực tế công trình này làm tăng tốc các cơ sở dữ liệu trên toàn thế giới 20 phần trăm. Bạn viết một bài báo mô tả chi tiết implementation của mình theo đúng sườn bài ở trên, và … không hội nghị lớn nào nhận đăng.

    Ví dụ 2: bạn có một thuật toán sorting mới hoàn toàn, tư tưởng khác hẳn với các thuật toán sorting thông thường như quicksort, merge-sort, insertion-sort, v.v. Phân tích cho thấy nó chạy trong thời gian O(n log log n), và experiments cho thấy nó chạy nhanh hơn tất cả các implementation của các thuật toán hiện có khoảng 10 phần trăm (nghĩa là tệ hơn Ví dụ 1). Bài báo này của bạn sẽ được đăng ở hội nghị tốt nhất về thuật toán.

    Hai ví dụ trên tôi bịa ra trong vài phút suy nghĩ, nên không hoàn hảo lắm. (Ví dụ như cái running time O(n log log n).) Tôi hy vọng là chúng đủ để minh họa cho điều tôi muốn nói. Trên thực tế các bài báo trải một spectrum rất rộng giữa ví dụ 1 và 2 và tràn cả xuống dưới ví vụ 1. Nhiều bài báo đọc thấy nực cười, bảo phê bình không biết bắt đầu từ đâu. Nhiều bài báo có giải pháp thuần túy là một biến thể nào đó của các ý tưởng sẵn có. Nếu biến thể này “tầm thường” thì novelty kém, nếu biến thể này “thú vị” thì novelty cao.

Tóm lại, muốn viết bài báo tốt thì phải thực hành nhiều và tự học từ các sai lầm đã có của mình. Đừng nản khi paper của mình bị từ chối mà phải xem referees nói gì và rút ra bài học. Dĩ nhiên là có đôi khi referees rất tệ, nói bậy nói bạ; nhưng tình trạng này sẽ ít xảy ra hơn khi bạn nộp bài vào một hội nghị hay tạp chí danh tiếng hơn. Chúc bạn may mắn!

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

Các câu hỏi phỏng vấn [28]

Ngô Quang Hưng | 16 tháng 05, 2007 | Bản để in Bản để in

  1. Bạn có 300 lít xăng và một cái xe tải. Xa tải chỉ chở được tối đa 100 lít xăng. Bạn muốn chở xăng đến bán ở chợ xăng cách khởi điểm 100 cây số. Vấn đề là xe tải chạy rất tốn xăng, mỗi cây số tốn 1 lít. Bạn được phép chở xăng để dọc đường rồi sau đó quay lại lấy để chở đi tiếp. Hỏi: Làm thế nào để bán được nhiều xăng nhất? (Nhớ là nếu bạn để xăng đâu đó dọc đường rồi quay lại lấy thêm xăng thì đoạn quay lại cũng tốn xăng.)
  2. Có một bàn cờ 8 x 8, các ô là các hình vuông đơn vị. Làm thế nào để cắt 3 mảnh giấy thỏa mãn điều kiện sau đây: với bất kỳ một ô X nào trên bàn cờ ta cũng có thể dùng 3 mảnh giấy để phủ bàn cờ sao cho
    • Ô X không bị phủ bất kỳ chỗ nào
    • Tất cả các ô còn lại đều bị phủ
    • Các mảnh giấy không có phần nào chồng lên nhau
    • Không có phần nào phủ ra ngoài bàn cờ

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

Các câu hỏi phỏng vấn [27]

Ngô Quang Hưng | 27 tháng 04, 2007 | Bản để in Bản để in

  1. Có một số 2^n (n 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?

  2. 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?

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

Các bài kế »