Blog Khoa Học Máy Tính

đăng ở IEEE Spectrum. Tình hình đại khái như đã viết trong các posts trước đây trên blog này.

Chuyên mục: Chính trị trong ngành & Dành cho du học sinh | Bình luận »

Vài điều suy nghĩ về Toán học Việt Nam là tên bài viết mới của giáo sư Nguyễn Tiến Dũng.

Chuyên mục: Dành cho du học sinh & Giáo dục | Bình luận (1) »

Và Java không phải là ngôn ngữ tốt để dạy sinh viên chập chững vào nghề. C và Scheme tốt hơn nhiều. C và Scheme thích các sinh viên thông minh, nhờ đó lọc ra những người vốn không thích hợp học KHMT. Scheme rất mạnh về mặt biểu cảm các khái niệm.

Tôi đã nhấn mạnh các điểm này trong một bài viết còn dang dở. Joel Spolsky đồng ý. Đoạn sau trích từ một bài viết gần đây của anh:

Now, I freely admit that programming with pointers is not needed in 90% of the code written today, and in fact, it’s downright dangerous in production code. OK. That’s fine. And functional programming is just not used much in practice. Agreed.

But it’s still important for some of the most exciting programming jobs. Without pointers, for example, you’d never be able to work on the Linux kernel. You can’t understand a line of code in Linux, or, indeed, any operating system, without really understanding pointers.

Without understanding functional programming, you can’t invent MapReduce, the algorithm that makes Google so massively scalable.

Bài viết có nhiều điểm đáng đọc, và tôi đồng ý gần như hoàn toàn với Joel (bạn có thể thấy sự tương tự trong hai bài viết).

Chuyên mục: Dành cho du học sinh & Giáo dục | Bình luận (2) »

Hồi còn học phổ thông, môn Văn đối với đa số lũ con trai chúng tôi nói chung là … cực hình. Tôi nghĩ có 3 lý do chính:

• Chương trình và phương pháp dạy Văn. Điều này báo chí đã la làng lâu nay, có phần đúng có phần sai, nhưng chắc chắn là một yếu tố quan trọng.
• Thầy cô dạy Văn. Cho dù có chương trình và phương pháp đúng, ta vẫn cần thầy cô tốt. (Tôi đã may mắn có rất nhiều thầy cô dạy Văn tốt, nhưng học vẫn tệ vì lý do trên và dưới .)
• Stereotyping: bọn trẻ con – một cách mặc định – thường cho rằng Văn dành cho bọn ủy mị, bọn con gái. Chú nào học Văn giỏi thường bị chọc là bê-đê, đồng bóng. Cái suy nghĩ thiển cận này, không hiểu bắt đầu từ đâu ra, được truyền từ thế hệ học trò này sang thế hệ học trò khác. Sức ép của stereotyping trong lứa tuổi cần “khẳng định mình” rất mạnh. Tuổi đó mà ở nhà đọc thơ Xuân Diệu thay vì đi đá bóng thì có khi bố mẹ cũng nghĩ là thằng con mình có vấn đề. Dĩ nhiên, với tôi – kể cả cho đến bây giờ – thì đá bóng vẫn hấp dẫn hơn thơ Xuân Diệu, nhưng điều này không liên quan lắm đến cái tôi muốn nói.

Một loại tâm lý khác ảnh hưởng đến việc học Văn nói riêng và các môn “thuộc lòng” nói chung là: “bọn học kỹ thuật thường là ghét học thuộc lòng”, sau đó bọn học trò phân loại các môn học ra: Sinh – Sử – Địa – Văn là thuộc lòng, Toán – Lý – Hóa yêu cầu tư duy phân tích, ít thuộc lòng. Từ phân loại này bọn học trò có một preconception về một môn học trước khi thật sự tìm hiểu xem môn đó có đáng học không. (Dĩ nhiên, chương trình, phương pháp, và người dạy đóng vai trò nhất định trong việc hình thành định kiến này.) Cái sai của tâm lý này nằm ở chỗ: nếu ta thật sự yêu thích Văn thì nó sẽ tự chui vào đầu, công sức bỏ ra “thuộc lòng” chẳng đáng là bao. Lên đại học học môn Điện Từ Trường cũng học thuộc lòng ói máu luôn, cho nên không phải mấy đồ kỹ thuật là ít thuộc lòng hơn.

Tại sao tôi lại lan man đến các định kiến xung quanh việc học Văn (và Sử-Địa-etc)? Vì có hai suy nghĩ hay lởn vởn trong đầu:

• Tôi luôn mong muốn là dân kỹ thuật trình bày ý tưởng của mình tốt hơn bình diện chung hiện nay (xin phép không đưa dẫn chứng). Không nhất thiết là ý tưởng kỹ thuật, mà cả các ý tưởng về xã hội, chính trị, tôn giáo, …
• Một định kiến nữa của XH: một người biết Văn/Sử cực tốt thì thường được xem là uyên kim bác cổ, trong khi đó một người cực rành về Toán/Lý thì không? Đơn giản là vì các kiến thức Văn-Sử nói ra nhiều người (tưởng là) hiểu.

Đọc lại những gì vừa viết, rõ ràng là trình bày của tôi thiếu trơn tru, dù có nhiều ý. Tiếp tục tập viết thôi!

Chuyên mục: Dành cho du học sinh & Giáo dục | Bình luận (1) »

“Đầu độc” DNS (tạm dịch từ DNS poisoning, hay DNS cache poisoning) là tác vụ lừa một (số) DNS server nào đó rằng một địa chỉ IP-giả là IP của một tên miền nào đó. Ví dụ, IP của website ngân hàng vietcombank.com là 216.104.161.209 và 216.104.161.109; nếu ISP của ta có DNS bị “thuốc”, tưởng rằng IP của vietcombank.com là x.y.z.w thì truy cập vào vietcombank.com sẽ bị “chuyển hướng” (redirected) đến x.y.z.w; Ở địa chỉ x.y.z.w này, có thể có sẵn một webserver với interface giống hệt vietcombank.com – người dùng không để ý (rất kỹ mới biết) sẽ có thể giao trứng cho ác. (x.y.z.w chơi trò “man-in-the-middle attack“, và đó không phải là trò duy nhất chơi được sau khi “thuốc” DNS.)

Thế làm thế nào để “thuốc” một DNS server? Có khá nhiều cách. Các tài liệu sau đây phác họa bức tranh tổng quan. Không đơn giản nhưng cũng chẳng khó khăn gì lắm. Một ít tài liệu đã cũ nhưng vẫn còn tính thời sự, ngoài ra còn là một mốc lịch sử của trò “đầu độc” DNS.

• Schuba, Christoph. Addressing Weaknesses in the Domain Name System Protocol. Aug. 1993 [ PDF ]
• Doug Sax, DNS Spoofing (Malicious Cache Poisoning)
• Vagner Sacramento. Vulnerability in the sending requests control of BIND versions 4 and 8 allows DNS spoofing. 19 Nov. 2002. 15 Dec. 2002
• CERT/CC Vulnerability Note VU#457875. 5 Dec. 2002. 15 Dec. 2002
• D.J. Bernstein. djbdns: Domain Name System tools. 15 Dec. 2002
• Zalewski, Michal. Strange Attractors and TCP/IP Sequence Number Analysis. 21 Apr. 2001. 15 Dec. 2002
• DNS Cache Poisoning – The Next Generation. LURHQ
• March 2005 DNS Poisoning Summary, SANS – Internet Storm Center

Chuyên mục: Bảo mật và mật mã học | Bình luận »

Survey về tội phạm máy tính 2005 của FBI đã có bản online (dạng PDF).

Chuyên mục: Bảo mật và mật mã học | Bình luận »

Vào thứ năm hàng tuần ở PARC có một buổi forum, những topic rất phong phú và đa dạng. Forum này có lịch sử khỏang gần 30 năm và thường khá nhiều người ở Silicon Valley ngòai PARC đến dự, một số bài phát biểu được ghi lại dưới dạng audio và video. Bạn nào quan tâm có thể vào archive để xem.

Điểm qua topics ở một số forum được ghi lại dưới dạng video/audio gần đây:

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

Theo một nghiên cứu mới đây, bàn phím máy tính thường có 33000 vi khuẩn trên một xăng ti mét vuông; Trong khi đó một ghế ngồi toilet chỉ có khoảng 130 vi khuẩn trên một cm2.

Giải pháp Bài học: nhất định không dùng laptop trong toilet.

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

25. Cho một dãy số A gồm n số thực: . Một dãy con của A là một dãy liên tục các phần tử của A. Ví dụ: dãy là một dãy con của A. Tìm một thuật toán chạy trong thời gian để in ra dãy con có tổng lớn nhất của A. (Chú ý là A có thể lẫn lộn các số âm, dương.)
26. Định nghĩa ( lần), và
    
    Hỏi: trong hai hàm và thì hàm nào tăng nhanh hơn khi lớn?
27. Viết một đoạn chương trình C để xác định xem máy chạy chương trình là big-endian hay little-endian.

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

kể từ năm học 2006-2007, đại trà từ lớp 10 trên phạm vi toàn quốc. Better late than never.

Chuyên mục: Giáo dục | Bình luận (8) »

Tôi cũng mới về thăm nhà và quay trở lại Berkeley tuần trước. Cũng giống như anh Hưng, tôi ít khi được (bị) hỏi: anh/bạn/cháu nghiên cứu về cái gì, ứng dụng của chúng đến đâu? Đôi khi thì được hỏi: lương của cháu bao nhiêu, có làm thêm gì cho đủ sống không? Câu hỏi thường xuyên hơn thì: bao giờ thì lấy vợ đây. Học nhiều nhưng cũng để ý chuyện đấy nghe bạn/cháu/anh, không thì hâm đấy. Này, có biết cậu Hưng Buffalo không…..

Đáng tiếc là thí dụ trên hôm nay không còn chính xác cho mọi người nữa.

Với số hiếm hoi những người hỏi về công việc của tôi bên này, sau khi được biết tôi học về KHMT, thường thì câu hỏi sâu nhất (của cả một số là sinh viên đại học về KHMT) là: Anh làm về phần cứng, hay phần mềm. Tôi thường phải giải thích là công việc của tôi cũng như nhiều người làm về lĩnh vực tin học có thể liên quan phần cứng hoặc phần mềm, nhưng đó chỉ là công cụ, ngôn ngữ mà thôi. Tôi làm về statistical machine learning. Cốt lõi của vấn đề là làm thế nào để máy tính giao diện với thế giới bên ngoài tốt, có khả năng khái quát hóa từ những sự tiếp xúc đó, có khả năng khái quát từ các dữ liệu và kiến thức đã có thay vì chỉ có ghi nhớ v.v. Ồ, chà chà, thế thì cao siêu quá nhỉ. Chắc Việt nam chưa cần đến đâu!?

Thế là tôi bắt đầu từ những ứng dụng cụ thể, quen thuộc nhưng không kém phần hoành tráng Ví dụ như làm sao phải nén ảnh này. Làm sao phải chuyển thông tin đi mà không bị mất mát này, cho dù đường truyền có thể đôi khi có lỗi. Làm sao phải phân loại ảnh hoặc các documents này. Làm sao tạo ra những chương trình như amazon là này. Rằng rất dễ. Rất cần. Hoàn toàn có thể làm được. Nhiều khi, chỉ cần một chút kiến thức về xác suất thống kê, một chút giải tích, một chút đại số tuyến tính, và một chút kỹ năng lập trình C (hoặc java, hoặc matlab), là đã có thể hiểu và xây dựng được prototype những sản phẩm công nghệ thông tin tối tân nhất như kiểu google hay amazon.

Được nói chuyện sâu hơn một chút với người ngoại đạo về công việc cụ thể của mình kể ra cũng lý thú, tuy thật khó khăn. Tôi cũng thử giải thích về graphical models. Cuối cùng thì tôi thường dùng analogy sau. Nghiên cứu của tôi về graphical models hay các stochastic processes khác cũng giống như nghiên cứu về tử vi. Tức là dựa vào một số dữ liệu quan sát được (như ngày tháng năm sinh, và danh tính một số người thân) để xây dựng một mô hình (tử vi), và qua đó suy diễn và dự đoán một số ẩn biến khác (như tính tình hay đường tình của bạn và người bạn đời của bạn)… Cái biến ngẫu nhiên trong mô hình của tôi cũng bao gồm những ngôi sao trong lá số của bạn. Công việc của tôi không chỉ liên quan đến những suy đoán, mà còn liên quan đến việc tìm tòi và cải thiện mô hình tử vi tốt hơn nữa. Thế là bắt được sự chú ý của khá nhiều người. Qua đó, giải thích về những giải thuật như markov chain monte carlo (mcmc) cũng trở nên dễ dàng hơn.

Ngoài những lần nói chuyện tầm phào, đợt vừa rồi tôi rất hân hạnh có dịp gặp gỡ với một số anh chị và một số bạn đang nghiên cứu và giảng dạy về trí tuệ nhân tạo và xử lý ảnh ở ĐHTH Hà nội và Viện Tin Học thuộc Viện KHCN. Rất vui được thấy nhiều bạn trẻ rất nhiệt tình quan tâm đến những vấn đề nghiên cứu khác nhau trong KHMT. Hy vọng trong tương lai không xa chúng ta sẽ được nghe nhiều từ họ.

Chuyên mục: Giáo dục & Nghiên cứu nghiên kiếc | Bình luận (9) »

Là tên bài viết của giáo sư Thomas Vallely, trong đó có đoạn

Đối với chúng ta, những người theo sát VN, nhu cầu hiện tại về tri thức ở VN còn yếu. GS tại các trường ĐH hàng đầu ở Hà Nội tin rằng SV chủ yếu coi bằng cấp là bàn đạp để có một việc làm trong khu vực kinh tế quốc doanh.

Tình trạng thiếu nhu cầu về tri thức khuếch đại những vấn đề tồn tại bấy lâu trong hệ thống giáo dục ĐHVN. Do có quá ít nhu cầu đối với những nhân tài thực sự và thành tích học tập chẳng quan trọng bằng các mối quan hệ, bằng cấp bị mất giá trị. Tiêu cực ngày càng tràn lan trong nhà trường. Không chỉ có vậy, người sử dụng lao động tại TP.HCM thường phàn nàn, cử nhân ra trường hiện không làm đúng ngành nghề họ theo học.

GS Malcom Gilis, cựu Chủ tịch ĐH Rice, thành viên của Hội đồng quản trị VEF, là một chuyên gia quốc tế lão luyện về mối quan hệ giữa khoa học và sáng tạo. GS Gillis giải thích với tôi rằng đa số những sáng chế kỹ thuật tiên tiến nhất bắt nguồn từ các ngành khoa học cơ bản.

Kỳ về Việt Nam vừa qua, không ít người – sau vài câu xã giao – hỏi tôi: “lương anh bên đó là bao nhiêu? Mua nhà bao nhiêu tiền?”. Hãy bỏ qua tính tế nhị của các câu hỏi loại này. Cực kỳ ít người hỏi: “anh làm nghiên cứu về ngành gì? ngành đó đang phát triển đến đâu? nội dung chính của nghiên cứu của anh là gì?” Quan trọng hơn cả, rất nhiều người xem các buổi gặp gỡ là cơ hội tạo quan hệ làm ăn.

Dĩ nhiên cái sample space của những người tôi đã gặp mặt không nhất thiết là đặc trưng, nhưng thực tế này vẫn đáng chú ý.

Chuyên mục: Giáo dục | Bình luận (1) »

Khi chúng ta học những kiến thực cơ bản đầu tiên probability theory, ta biết đến những hàm phân phối cho biến thực/tự nhiên ngẫu nhiên kinh điển như Gaussian, Poisson, Bernoulli, Laplace, Dirichlet, Cauchy, v.v. Stochastic processes là gì ? Một cách nôm na, stochastic processes là những hàm phân phối cho những objects phức tạp hơn, như một collection of variables, hoặc các hàm số, hoặc các đồ thị (graphs), v.v.

Có thể định nghĩa đủ thứ hàm phân phối lên các objects cần quan tâm. Cuộc sống của chúng ta có thể được mô hình bằng các loại objects khác nhau, khi thì có tính chất combinatorial, khi thì analytical. (Ví dụ, Graphical models là một phương pháp tổng quát để định nghĩa một dạng stochastic processes). Do đó, stochastic processes có nhiều ứng dụng trong việc mô hình, tìm hiểu và dự đoán với data. Về mặt lý thuyết, nghiên cứu tính chất và cách sử dụng các stochastic processes mới rất thú vị không chỉ với những người nghiên cứu về xác suất thống kê thuần túy, mà cả với những người làm về data modeling.

Một số sách sau đây rất tốt về probability theory và stochastic processes.

• Convergence of Stochastic Processes của David Pollard (Yale). Sự trình bày về empirical processes được coi là kinh điển, tuy đây chỉ là một phần nhỏ của quyển sách. Một phần lớn sách nói về khái niệm weak convergence (convergence in distribution) trong không gian Euclidean và các metric spaces khác. Hiểu biết các khái niệm này là bước đệm quan trọng trong việc nghiên cứu và sử dụng các loại stochastic processes trong không gian vô hạn chiều (function spaces).
  Empirical processes theory hiện là một trong những nền tảng lý thuyết cơ bản của machine learning, đặc biệt là nonparametric statistic/learning.

• The random geometry of equilibrium phases của Olle Häggström (Chalmers Univ of Technology, Sweden). Một quyển sách hay về các mô hình Markov Random Fields trong statistical physics, và các hiện tượng phase transition và percolation trong những loại mô hình này. MRF cũng chính là một dạng graphical models (với undirected graphs), có nhiều ứng dụng trong parametric machine learning và statistics. Một trong những topics có thể học được từ quyển sách này là làm thế nào có thể định nghĩa được consistent stochastic processes cho graph với infinite vertices mà chỉ dựa vào các local constraints của graphs. Đối với finite graphs thì không có vấn đề gì. Các graphical models chúng ta gặp trong ứng dụng (như Hidden markov models chẳng hạn) đều chỉ có số đỉnh (vertices) là hữu hạn. Nghiên cứu về infinite graphs cho chúng ta hiểu biết sâu hơn về finite graphs có số lượng đỉnh rất lớn. Các khái niệm phase transition, mixing time of Monte Markov chains, uniqueness of Gibbs measures có liên hệ cực kỳ thú vị trong stochastic graphs cho infinite graphs. Đây là một trong những lĩnh vực có sự giao thoa rất lý thú giữa vật lý thống kê, lý thuyết tính toán, và lý thuyết về learning/ xác suất thống kê.
• Reversible Markov Chains and Random Walks on Graphs của David Aldous (Berkeley) và Jim Fill (Johns Hopkins). Đây là một quyển sách khá sâu về Markov Chains.
• Probability in Banach spaces của Ledoux và Michel Talagrand (Paris 6). Đây là quyển sách advanced về lý thuyết xác suất đối với biến ngẫu nhiên thuộc Banach spaces. Nhiều chủ đề quan trọng như isoperimetric inequalities, concentration of product measures, và ứng dụng cho empirical processes.

Vào thăm homepage của Talagrand còn có nhiều quyển sách miễn phí rất hay khác, như quyển sách về Mean field models for spin glass nghiên cứu về hiện tượng phase transition trong vật lý bằng lý thuyết xác suất chặt chẽ. Có thể rất lý thú cho dân làm về statistical physics, lý thuyết các thuật toán ngẫu nhiên monte carlo markov chain, và dân làm về machine learning.

• Stochastic Calculus for mathematical finance của Steven Shreve (CMU). Quyển sách rất hay để học về stochastic partial differential equations; các mô hình thống kê cho finance và stochastic control.
• Lecture notes về stochastic processes của Amir Dembo (Stanford).

Ngoài ra, có thể tham khảo thêm danh sách sách miễn phí trên mạng của nhiều ngành toán, trong đó có lý thuyết xác suất nói chung, và stochastic processes nói riêng.

Chuyên mục: Giới thiệu sách & Lý thuyết thông tin & Thuật Toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (13) »

trong vòng 2 năm. Tôi đã đề cập sơ bộ về cái song đề khó chịu của chính quyền Trung Quốc trong kỷ nguyên của quả đất phẳng.

Chuyên mục: CNTT các nước và VN | Bình luận »

Prof. Richard Karp chuẩn bị dạy một lớp bậc cao học về những thuật toán quan trọng và nổi tiếng trong KHMT. Lời giới thiệu của syllabus:

From time to time a new algorithm comes along that causes a sensation in
theoretical computer science or in an area of application because of
its resolution of a long-standing open question, its surprising efficiency,
the novelty of its setting or approach, the elegance of its structure, the
subtlety of its analysis or its range of applications.

Không phải là tất cả (tất nhiên!), nhưng dây là một danh sách của Prof. Karp để ta tham khảo. Một số đã được nhắc tới đâu đó trong blog này:

• Elementary examples: Binary arithmetic, sorting, Euclidean algorithm,
  greedy algorithm, Dijkstra shortest-path algorithm, Gaussian elimination
• Simplex algorithm for linear programming (1947)
• Fast Fourier Transform (1959)
• Gale-Shapley proposal algorithm (1962)
• Edmonds’ nonbipartite matching algorithm (1965)
• Union-find algorithm (1975)
• Lattice basis reduction algorithm (1982)
• Buchberger’s Grobner basis algorithm (1982)
• Ajtai-Komlos-Szemeredi sorting network (1983)
• Randomized algorithms for approximating volume (1989)
• Koutsoupias-Papadimitriou k-server algorithm (1994)
• Shor’s quantum factoring algorithm (1994)
• The Winnow (1988) and Adaboost (1995) algorithms for statistical
  classification
• Interior-point algorithms for linear programming(1984) and semidefinite
  programming (1995)
• Streaming algorithms for computing moments (1995)
• Sudan’s list decoding algorithm (1997)
• LT codes and Raptor codes for data distribution (2002, 2003)
• Reingold’s logspace algorithm for st-connectivity (2004)

Chuyên mục: Lý thuyết thông tin & Lý thuyết tính toán & Thuật Toán & Toán tối ưu & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (1) »