Blog Khoa Học Máy Tính

Trích một bạn đọc nào đó của Tuổi Trẻ:

Khi hỏi đa số các bạn sinh viên của tôi thì hầu như ai cũng có suy nghĩ chung, không phải môn đại cương nào cũng nhàm chán và vô bổ, điển hình như môn Triết học Mac-Lê, đó là nền tảng cho mọi suy luận, rất cần thiết, bản thân tôi thấy rất hay.

Ừm, à, ồ, … nói gì nhỉ.

Hay là không nói gì cả, mà trỏ đến Stanford Encyclopedia of Philosophy.

Điều cực kỳ oái oăm là: mục bạn đọc viết nọ là để bàn về những thiếu sót của chương trình giáo dục đại học ở ta, nên dạy đại cương cái gì, v.v.

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

“Mang đại nghĩa để thắng hung tàn,
Lấy trí nhân để thay cường bạo.”

Đó là hai câu kết phần bào chữa cho các luật sư Đài và Nhân của bác Định hai hôm trước. Hùng biện!

Chuyên mục: Tin tức đó đây | Bình luận (9) »

Nhắc đến Chopin tôi nghĩ ngay đến các bản Nocturnes, đặc biệt là Op. 55 No. 1 và Op. 9 No. 2. Tôi có bộ đĩa Rubinstein chơi Nocturnes, tuyệt hảo! Tiếc rằng trên youtube chỉ có Rubinstein chơi Op. 9 No. 2, còn Op. 55 No. 1 (đậm cảm xúc hơn nhiều) thì nghe tạm cái này vậy. Youtube có cả clip bác Đặng chơi Op. 62 No. 2 hồi bác ấy thi năm 80.

Một khúc solo rất nổi tiếng của Chopin là Fantasie Impromptu. Khúc này rất khác với Chopin. Lúc tặng cho Julian Fontana, Chopin dặn đừng quảng bá ra ngoài. Người ta đồn rằng Chopin nghĩ nó hơi giống Moonlight Sonata. Tình cờ tôi thấy trên youtube cái clip Valentina Igoshina chơi Fantasie Impromptu. Đẹp!

Chuyên mục: Âm Nhạc | Bình luận (4) »

Nhân đọc một entry về xếp thứ tự giấy tờ bên unfogged: trong cuộc sống hàng ngày có không ít các trường hợp ta có thể áp dụng một ý tưởng thuật toán nào đó. Vài ví dụ:

• Nếu phải xếp thứ tự an-pha-bê khoảng trăm bài kiểm tra cuối kỳ nào đó, bạn dùng quick sort, merge sort, insertion sort, bubble sort, hay radix sort, v.v.? Tôi thường dùng chung insertion & merge sort.
• Hàng tuần có nhiều việc phải làm. Làm gì trong ngày nào là một dạng bin-packing hoặc weighted scheduling with deadlines. Ta không muốn ngắt một việc làm nhiều ngày (nếu có thể) vì mất công re-boot. Tôi thường ghét các việc lắt nhắt, nên dồn chúng lại làm một lúc và để đến sau cùng, tương tự như thuật toán FFD cho bin-packing.
• Mua quà Noel cho nhiều người với một túi tiền có hạn là bài toán Knapsack.
• Mồng 2 Tết, đi lòng vòng chúc tết nhà bà con bạn bè là bài toán TSP.
• Chọn thức ăn từng bữa cho đủ chất và giá rẻ nhất là bài toán qui hoạch tuyến tính (mixed với quy hoạch nguyên).
• …

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

Trích bài viết từ Cognitive Daily:

In short, if you want your kids to value helping others in a variety of ways, this research suggests that you’re likely to be effective when you actively encourage those behaviors through conversation, experiential learning, and other actions. This approach appears to be more effective than general parenting philosophies such as demandingness or responsiveness to children’s emotional needs. But of course, as a correlational study, these results alone don’t show that these parenting strategies cause the desired results. It’s possible that kids with better attitudes about helping others inspire more action from their parents.

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

Bên gỡ rối tơ lòng, bạn Thắng hỏi:

Trong một cuốn sách em thì nó nói rằng nếu có cái điều kiện gì gì đó thì A |– B sẽ suy ra A |= B. Nhờ anh chỉ giùm cho em thấy sự khác biệt giữa 2 khái niệm A|–B và A|== B này cái
…
rồi có Gentzen type và Hilbert type gì gì đó …

Tôi không biết nhiều lắm về các loại deductive calculus, nhưng cũng cố thử trả lời bằng những gì tôi biết, qua một năm học logic cổ điển từ khoa Toán. Trong khi đó nhứng gì bạn Thắng và đa số dân KHMT đọc về logic (tôi đoán là) lại hướng đến logic cho AI cổ điển (hoặc databases), có nhiều chi tiết kỹ thuật hơn những gì tôi biết. Logic dành cho bên Toán không quan tâm đến implementation efficiency của deductive systems, còn logic cho AI và database buộc phải quan tâm vì lý do hiển nhiên. Các bác nào làm AI cổ điển (chắc hơi hiếm) và database giứp giùm nhé!

Đoạn dưới đây chỉ nói về first-order logic (và trường hợp đặc biệt của nó là propositional logic).

thường được dùng để nói rằng “mệnh đề” có thể suy ra (deduce) được từ các mệnh đề trong tập mệnh đề cùng với một tập hợp các tiên đề cho trước. (Chính xác hơn, thay vì “mệnh đề” thì phải dùng cụm từ well-formed formula (wff).)

Để thật sự biết là hay không, ta phải có một số luật suy dẫn và một tập tiên đề. Tập tiên đề cùng với tập luật suy dẫn gọi là deductive calculus. Hai loại calculus chính là loại Gentzen và loại Hilbert. Loại Gentzen có ít tiên đề, nhiều luật, và (có vẻ) thích hợp hơn cho tính toán [các bác làm AI, automatic theorem proving confirm nhé]. Loại Hilbert có rất nhiều tiên đề (có thể vô hạn) nhưng lại có rất ít luật. Loại này thích hợp cho chứng minh toán học.

Deductive calculus chỉ là một tập hợp các luật cơ bắp. Ví dụ, luật modus ponens bảo , nghĩa là nếu đã có và có thì ta có thể “suy ra” . Vì chúng chỉ là luật cơ bắp, ta có thể lập chương trình cho máy tính dựa trên các luật này.

thì phức tạp hơn nhiều. Nó đòi hỏi là dưới một “cấu trúc” bất kỳ nào thì cũng suy được từ trong cấu trúc đó. Định nghĩa cấu trúc thỉ rắc rối, nhưng có thể lấy ví dụ đơn giản: có nhiều phép suy dẫn hay mệnh đề chỉ đúng cho cấu trúc số thực nhưng không đúng cho cấu trúc số tự nhiên, tỉ dụ như mệnh đề “với mọi x, tồn tại y sao cho x+y=0“.

Một deductive calculus gọi là “sound” nếu dẫn đến . Điều này hiển nhiên là cần thiết vì nếu không luật suy dẫn của ta bị hổng trong một nhánh nào đó của Toán học. Hầu hết các deductive calculus hữu dụng đều sound.

Ngược lại, Godel chứng minh được rằng, nếu ta chọn một deductive calculus đơn giản (kiểu Hilbert) với một số vô hạn các tiên đề và một luật suy dẫn duy nhất là luật modus ponens, thì cái calculus này còn “complete” nữa cơ, nghĩa là thì dẫn đến . (Cái calculus này cũng sound luôn, dễ chứng minh hơn completeness nhiều.)

Godel completeness theorem cho ta thấy rằng cái calculus nọ cực tốt: thay vì phải chứng minh rằng dưới một cấu trúc bất kỳ (số nguyên, số thực, phức, nhóm, trường, vành, hình topo, combinatorics và vô hạn các “cấu trúc” có thể có), thì ta “chỉ cần” duy dẫn logic dùng hệ tiên đề nọ và luật modus ponens là có thể chứng minh được

Chuyên mục: Lý thuyết tính toán | Bình luận (4) »

Câu chuyện này rất tếu và hay. Một sys admin biết hệ thống bị hacked. Hacker tạo một account. Sys admin không biết password của account nọ. Dĩ nhiên, hắn biết MD5-image của password. Làm thế nào để tìm pre-image của một hash function? Google!

Hah. Một chú khác thấy trò này vui tạo cả một webpage chơi. Nếu bạn muốn thử, gõ password của bạn vào. Website này tạo MD5-image của password và cho bạn một cái link tìm trên Google. Nếu tìm thấy thì password của bạn đã có người dùng, và tìm pre-image chỉ đơn giản là một Google search. Có cả một database của MD5-images để bạn tìm ngược lại các passwords.

Bài học: duyệt qua /etc/password trong hệ thống của trường/sở bạn đang học/làm việc. Tìm pre-images bằng Google. Thế nào cũng tìm ra một vài passwords mà không cần viết script duyệt từ điển gì hết. Bị phạt tôi không chịu trách nhiệm.

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

Ai ở Mỹ chắc cũng biết vấn đề embryonic stem cell research là đề tài chính trị nóng bỏng. Giới bảo thủ và sùng đạo cho đó là giết người. Giới cấp tiến và khoa học biết nó dùng để cứu người. Các ứng cử viên tổng thống Mỹ đều phải suy nghĩ rất kỹ trước khi phát biểu ủng hộ phía nào. Không nhất thiết là cứ Republican thì chống. Các chính trị gia cấp tiến (ở các tiểu bang hay thành phố buộc họ phải cấp tiến) của đảng Cộng Hòa vẫn ủng hộ embryonic stem cell research như thường. Anh chàng Arnold the Terminator “I’ll be back” là một ví dụ.

Hôm nay mới có tin về đột phá mới làm các tranh luận về tính đạo đức của embryonic stem cell thành vô nghĩa:

On Thursday afternoon, Science will publish the decade’s most significant breakthrough in stem cell research. James Thomson and colleagues at the University of Wisconsin and in Japan have reprogrammed human skin cells to create cells indistinguishable from embryonic stem cells.
…
“It’s going to completely change the field,” says Thomson, the scientist who in 1998 isolated stem cells from human embryos for the first time. “They are probably more clinically relevant than embryonic stem cells,” he explains. “Immune rejection should not be a problem using these cells.”

“This is a tremendous scientific milestone, the biological equivalent to the Wright Brothers’ first airplane,” Robert Lanza, chief scientific officer of Advanced Cell Technology told Rick Weiss of the Washington Post.

Chuyên mục: Tin tức đó đây | Bình luận (2) »

Lâu rồi không dùng một phần mềm cho symbolic computation như Mathematica hay Maple. Hồi xưa còn làm về q-series nhiều tôi chọc ngoáy Mathematica hàng ngày. Mấy hôm nay tôi cần chúng cho một bài toán đang giải, dùng lại Maple thấy quả thật là hùng mạnh. Dưới đây là ví dụ về output của Maple. Dĩ nhiên, tôi có GUI output cẩn thận chứ không phải output kiểu text cổ điển như thế này.

> x := 2/5;
                                      2
                                      -
                                      5
> y := 1/3;
                                      1
                                      -
                                      3
> C := [2*x*a+2*y*b+(1/2)*c >= 2, max(2*y, 1-x)*b+(1-x)*c >= 2, (1-y)*c >= 2];
              [     4     2     1         2     3         2  ]
              [2 <= - a + - b + - c, 2 <= - b + - c, 2 <= - c]
              [     5     3     2         3     5         3  ]
> P := a+b+c;
                                  a + b + c
> with(Optimization);
> LPSolve(P, C, assume = nonnegative);
[3.67500000000000,
  [a = 0.374999999999999834, b = 0.300000000000001098, c = 2.99999999999999868]
]
> with(simplex);
> minimize(P, C, NONNEGATIVE);
                           /    3       3       \
                          { b = --, a = -, c = 3 }
                           \    10      8       /

Các phần mềm tính toán như Matlab, Mathematica, Maple đều rất đắt tiền (cỡ 500USD chứ không ít). May mà trường tôi có deal gì đó với Mathematica và Maple nên tôi mua chúng chỉ mất 10USD. Sinh viên thì còn mua thêm được phiên bản sinh viên của Matlab, 50USD. Nếu dùng máy trong khoa thì tôi có thể dùng Matlab thoải mái vì có license tập thể. Tôi không biết có open-source symbolic hay scientific computation softwares nào dùng được không?

Muốn viết các phần mềm cho scientific computation hay symbolic computation cần phải rất giỏi cả KHMT lẫn Toán. Tính hữu dụng của chúng trong nghiên cứu khoa học thì phải nói là vô hạn.

Chuyên mục: Công nghệ phần mềm & Thuật Toán | Bình luận (5) »

Theo bài báo này ở Journal of Economics Psychology:

In soccer penalty kicks, goalkeepers choose their action before they can clearly observe the kick direction. An analysis of 286 penalty kicks in top leagues and championships worldwide shows that given the probability distribution of kick direction, the optimal strategy for goalkeepers is to stay in the goal’s center

Chưa chi đã thấy sai. Nếu các thủ môn đa số đều không nhảy sang trái hay sang phải, như bài gợi ý, thì phân bố hướng đá bóng sẽ không còn như cũ nữa vì bọn cầu thủ đâu có đá ngẫu nhiên theo một “kick direction distribution” nào đó. Các bác nào làm về game theory ném đá bài báo nọ đi! (Có khi lại được thêm một publication.)

Khi thủ môn đổi chiến lược theo cái posterior thì các cầu thủ sẽ đổi prior.

Chuyên mục: Nghiên cứu nghiên kiếc & Xác suất & thống kê | Bình luận (2) »

Không có gì hay ho để viết. Chốc nữa đi bơi. Để ảnh hồ bơi của trường lên đây cho một số bà con ghen tức chơi. Hà hà!

(Hồ bơi UB.)

Chuyên mục: Mỹ quốc | Bình luận (1) »

(Nguồn)

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

Có một số bài hát mới nghe đã nhớ ngay. Một số nghe mãi thì thấy quen, quen rồi thì thấy phê, nhưng vẫn không nhớ được. Một số thì nghe phê rồi và nhớ mãi, nhớ từng chi tiết, từng instruments tại từng thời điểm. Đó là một cách phân loại các bài hát hay. Mà sự phân loại này là tương đối với từng người. Nhưng hình như mỗi người lại thường chỉ thích một trong ba loại thôi. Hôm nay tôi muốn nói về một mô hình liên hệ sự thưởng thức âm nhạc với sự kích hoạt của các synapse trong hệ thần kinh, và phong cách sáng tạo của mỗi người.

E hèm… Kỳ thực tôi chỉ thử nghịch nhúng video nhạc vào blog của bác Hưng một tí. Như anh chàng Barkley này nói, đúng là điên .

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

Lũ miền Trung càng lúc càng dữ dội. Sau đợt kêu gọi lần trước, bọn tôi đã chuyển tiền quyên được và sắp cứu trợ vùng Thanh/Nghệ trong vài ngày tới.

Bây giờ đến Huế, Quảng như thế này đây. Đóng góp đợt 2 tiếp thôi.

(Ngọ Môn — Huế)

Năm ngoái, trong cơn bão Chanchu, xã Bình Minh (huyện Thăng Bình, Quảng Nam) bị thiệt hại nặng nề về người. Còn với trận lũ kinh hoàng này, họ lại bị thiệt hại rất nặng về vật chất. 100% số tàu cá của ngư dân xã Bình Minh chưa có chiếc nào được tìm thấy. Hàng trăm ngư dân xã Bình Minh đang đau khổ tột cùng vì số tài sản duy nhất của họ đã nằm dưới lòng biển.

Chủ tịch UBND xã Bình Minh Trương Công Hùng cho biết hàng trăm ngư dân chạy về xã kêu khóc suốt hai ngày nay nhưng xã không thể làm gì hơn là khuyên nhủ, động viên họ không liều mạng xuống biển vớt tài sản bị trôi. Rất nhiều người trong số họ còn nợ ngân hàng hàng trăm triệu đồng vay để đóng tàu hành nghề chưa được bao lâu.

Chuyên mục: Thông báo | Bình luận »

Theo tin:

“A team from the University of Tokyo has genetically engineered a mouse that does not fear cats. By tweaking genes to disable certain functions of the olfactory bulb (the area of the brain that receives information about smells directly from olfactory receptors in the nose) the researchers were able to create a ‘fearless’ mouse that does not try to flee when it smells cats, foxes and other predators.

Dễ òm. Muốn làm cho Tám Khỏe không sợ xe đụng, cho hắn … nhậu ba xị đế. Việc quái gì phải “genetically engineer” cái gì.

Không liên quan gì, có bài trên tờ Time về Ieng Sary và Ieng Thirith:

Daughters of a judge and among the country’s first female intellectuals, Ponnary and Thirith were sent to study in Paris in the 1950s where they met and later married two other Cambodian students — creating a foursome that went on to form the nucleus of one of the world’s most brutal regimes.

Đọc mấy câu sau thấy buồn cho nhân loại:

As court and police officers prepared the Iengs for the drive to the tribunal’s detention center on the outskirts of Phnom Penh Monday, neighbors came out to wish them good riddance. “They killed many people and they must be prosecuted,” says Pouk Salonn, 57, the owner of a small shop near the Iengs’ villa who lost her parents during the regime. But with the passage of some 30 years since the Khmer Rouge regime committed its crimes, the arrest of the elderly pair — Sary is 82 and Thirith is 75 — was little consolation. “Why are you only coming to ask questions now?” she asks, noting that there seemed to be more media attention on Pol Pot’s terrifying reign now than there was when he was actually in power. “[The regime] was a long time ago already.”

Chuyên mục: Nghiên cứu nghiên kiếc & Tin tức đó đây | Bình luận »