Blog Khoa Học Máy Tính

Numa Numa Dance là một hiện tượng của Internet:

Numa Numa is an Internet phenomenon based on amateur videos made for the song Dragostea din Tei by Romanian pop band O-Zone. The phrase “Numa Numa” comes from the chorus of the song, “nu mă, nu mă iei,” meaning, roughly, “(you) won’t take, won’t take me.”

Numa video nổi tiếng nhất có lẽ là của gã Gary Brolsma. Tôi thích cái Numa hoạt hình In the jungle … the lion sleeps tonight (nhạc phim Lion King). Châu Á có Backstreet boys Trung Hoa. Canada có UBC Numa Numa, vân vân.

Năm kia tôi tình cờ nghe được một bản nhạc ráp vui tiếng Việt. Đã có vài posts trên blog này với clips vui và nhạc vui. Tuy nhiên, tôi không biết có Numa Numa made in Việt Nam nào.

Chủ đề: Vui - Giải Trí & Âm Nhạc | Bình luận (2) »

Một sinh viên của tôi vừa phỏng vấn với Google và Yahoo. Ba câu hỏi sau đây còn “nóng hổi”:

37. Cho một linked list (danh sách liên kết) và pointer đến đầu linked list. Ta không biết trước tổng số phần tử trong list là bao nhiêu. Viết một function trả về pointer đến một phần tử ngẫu nhiên trong list (uniform distribution), mà chỉ được duyệt qua linked list 1 lần. (Nghĩa là không được đếm tổng số phần tử n, chọn ngẫu nhiên từ 1 đến n, rồi duyệt lần 2 để trả về con trỏ ngẫu nhiên.)
38. Cho một array A các ký tự trong một bộ ký tự nào đó, và một tập S của vài ký tự. Viết một function chạy trong thời gian tuyến tính, trả về sub-array nhỏ nhất của A chứa tất cả các ký tự trong S.
39. Cho một ma trận m hàng n cột. Các con số trên các hàng đều tăng dần từ trái sang phải, và trên các cột đều tăng dần từ trên xuống dưới. Viết một thủ tục tìm một số xem nó có trong ma trận không? Thời gian chạy là bao nhiêu? (Lưu ý: đây là phiên bản 2-D của binary search.)

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

Phát hiện một công ty vi phạm bản quyền phẩm mềm

Đoàn thanh tra liên ngành đã lập biên bản vi phạm và thu giữ 10 CPU máy tính có cài đặt nhiều phần mềm bất hợp pháp như Microsoft Windows XP, Microsoft Office, Từ điển Lạc Việt, Vietkey 2000, Symantec Antivirus Corporate Edition…

Đáng lẽ, khi tìm ra một công ty không dùng phần mềm lậu thì mới gọi là … phát hiện chứ nhỉ, khi mà BSA ước lược tỉ lệ phần mềm lậu ở VN là 90-95%

Vietnam had the highest software piracy rate at 90 percent — in the league with Zimbabwe, it said. Indonesia came next with 87 percent, China 86 percent and Pakistan also at 86 percent.

Chủ đề: CNTT các nước và VN | Bình luận »

Một người bạn vừa gửi cho cái link này qua bên diễn đàn tin học.

Chủ đề: CNTT các nước và VN & Nhân vật và sự kiện | Bình luận »

Lần trước có vẻ chưa “đủ đô” :-), tiếp tục nhé

34. Có ba bình nước có dung tích rất lớn, chứa x, y, và z lít nước theo thứ tự. Trong đó, x, y, z là các số nguyên dương. (Dung tích của các bình lớn hơn x, y, z nhiều. Ta cần sớt nước giữa các bình để có một bình trống. Không được đổ nước ra ngoài. Tuy nhiên, mỗi lần san nước từ bình A sang bình B thì ta phải nhân đôi thể tích nước trong bình B. Ví dụ: nếu x, y, z = 4, 6, 3, thì ta có thể làm như sau
    
4 6 3
8 2 3
5 2 6
5 4 4
5 8 0

    Chứng minh rằng: với x, y, z bất kỳ ta đều có thể san nước để có bình trống.
35. Thằng Tí có một ma trận vuông A (kích thước n x n) chứa toàn các số thực dương. Tèo muốn tìm tổng các số trên đường chéo chính. Tèo được quyền hỏi Tí tổng các số trong một ma trận vuông con bất kỳ của A, nhưng mỗi lần hỏi thì tốn 1 đô la. Hỏi: Tèo phải tốn ít nhất bao nhiêu đô la để biết được số cần tìm? (Ví dụ: n đô la dĩ nhiên là đủ!)
36. Tèo phải gán màu cho các điểm trong mặt phẳng . Mỗi điểm một màu. Hai điểm cách nhau 1 đơn vị phải khác màu nhau. Chứng minh rằng Tèo cần ít nhất 4 màu và nhiều nhất 7 màu.

(À quên, câu tôi thích nhất là câu số 4 vẫn chưa có ai giải - chú ý rằng mỗi lần dùng căn bậc 2 là mỗi lần dùng một số 2)

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

31. Có bao nhiêu số 0 ở đằng cuối của biểu diễn thập phân của ?
32. Khi ta soi gương, giơ tay trái lên thì hình nhân trong gương giơ tay phải của hắn. Tuy nhiên, khi ta cúi đầu thì hình nhân trong gương cũng cúi đầu. Tại sao gương “lật” trái/phải, nhưng không “lật” trên/dưới?
33. Có 9 túi đựng tiền, mỗi túi chứa ít nhất 100 đồng tiền, trong đó có một túi chứa toàn tiền giả. Các đồng tiền thật đều nặng 100 grams. Các đồng tiền giả đều nặng 90 grams. Cho một cái cân đĩa (1 đĩa và đồng hồ chỉ cân nặng), cân 1 lần để xác định túi nào chứa tiền giả?

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

tốt nhất là bắt đầu từ đỉnh cao:

Lost in the argument over whether young people today know how to work, however, is the mounting evidence produced by labor economists of just how important it is for current graduates to ignore the old-school advice of trying to get ahead by working one’s way up the ladder. Instead, it seems, graduates should try to do exactly the thing the older generation bemoans — aim for the top.

The recent evidence shows quite clearly that in today’s economy starting at the bottom is a recipe for being underpaid for a long time to come. Graduates’ first jobs have an inordinate impact on their career path and their “future income stream,” as economists refer to a person’s earnings over a lifetime.

Xem thêm bình luận ở Marginal Revolution. Đề tài hay!

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

Kêu gọi đóng góp cứu trợ nạn nhân bão số 1

Chủ đề: Thông báo | Bình luận »

Thông cảm với họ sau vụ ồn ào do phát biểu ở một concert ở Anh, tôi đã mua album Home ngay sau đó (có bài Traveling Soldier). Vừa đọc xong tờ Time có feature về Dixie Chicks, với câu kết của Maines:

Everything was so nice and fine and happy for us for the longest time. It was awesome to feel those feelings again that I felt in highschool: to be angry, to be sure that you’re right and that the things you do matter. You don’t realize that you’re not feeling those feelings until you do. And then you realize how much more interesting life is.

Chắc phải mua album Taking the Long Way quá. Album này toàn nhạc họ viết, rất cá nhân và trưởng thành, không phải loại “commercial salad” như xưa.

Chủ đề: Âm Nhạc | Bình luận »

Làm thế nào để biểu diễn xấp xỉ một hàm số bằng các đại lượng giải tích đơn giản hơn? Đây là một câu hỏi cơ bản của lý thuyết xấp xỉ (approximation theory) . Tầm quan trọng và ứng dụng của nó rất lớn với KHMT: Hàm số ở đây có thể hiểu là các signal, các mô hình learning (thống kê), v.v những gì mà ta cần biểu diễn và estimate. Các cuộc “cách mạng” trong các ngành trong KHMT này thường được đánh dấu bởi một phương pháp xấp xỉ mới (như phương pháp waveless trong signal processing, hay neural networks và kernel methods trong machine learning, đều xảy ra trong thập kỷ 80/90).

Bài báo sau đây là một landmark paper trong approximation theory (có thể download từ Sbornik Mathematics — amazing !):

M. S. Birman and M. Z. Solomjak, Piecewise-polynomial approximations of functions in the classes , Math. USSR-Sbornik Vol. 2 (3), pages 295–317, 1967. Full text (pdf)

Không gian Sobolev bao gồm các hàm số smooth. Một chút background về không gian Sobolev có thể tìm ở đây . Chi tiết hơn thì nên đọc thêm quyển sách kinh điển của Robert Adams (title: Sobolev spaces) hoặc Second Edition.

Trước Birman và Solomjak, phần lớn lý thuyết xấp xỉ được tập trung vào phương pháp xấp xỉ tuyến tính cổ điển. Phương pháp này tập trung vào các không gian đa thức tuyến tính (như đa thức Bernstein, Fourier bases, đa thức Chebyshev, …). Bài báo của Birman và Solomjak giới thiệu và phân tích một thuật toán adaptive. Ý tưởng rất đơn giản: Chia nhỏ miền xác định của hàm số ra thành các mảnh nhỏ, và mỗi mảnh đó được xấp xỉ bằng một đa thức (dùng công cụ tuyến tính). Chỗ nào mà sự xấp xỉ chưa được tốt thì dùng các mảnh nhỏ hơn. Đặc biệt số lượng của các mảnh partition này được hạn chế tối thiểu. Vì với mỗi mảnh khác nhau của miền xác định, một không gian đa thức tuyến tính được sử dụng, kết quả là ta có một phương pháp xấp xỉ phi tuyến. Đây chính là ý tưởng căn bản của multi-resolution approximation, rất quen thuộc trong lĩnh vực xử lý ảnh hiện nay.

Sau Birman và Solomjak, những thập niên 70/80 chứng kiến sự phát triển rất nhanh về lý thuyết xấp xỉ phi tuyến. Có nhiều cộng đồng khác nhau cùng nghiên cứu về vấn đề này: Dân làm về lý thuyết xấp xỉ, lý thuyết giải tích điều hòa (harmonic analysis), dân làm về multigrid theory cho integral và differential equations, và dân làm về multiscale filterbanks trong image processing. Đến cuối thấp niên 80, những nhánh nghiên cứu này hội tụ tại cùng một điểm: kết quả là một phương pháp xấp xỉ phi tuyến hiệu quả về mặt ứng dụng, nhưng rất đẹp và elegant về mặt toán học. Đó là phương pháp xấp xỉ wavelet. Có một số chuyên gia người Việt làm về lĩnh vực này trong image processing, như các giáo sư Nguyễn Quang Trường ở UCSD, Trần Duy Trác ở John Hopkins, Đỗ Ngọc Minh ở UIUC. Ở Việt nam có nhiều chuyên gia nghiên cứu về lý thuyết xấp xỉ ở các khoa toán và tin, trước đây được đào tạo từ Soviet school của Birman, Solomjak và các vị tiền bối khác.

Bài báo của Birman và Solomjak có nhiều chi tiết technical rất thú vị:

• Thuật toán partition miền xác định của một hàm số như đã nhắc trên. Rất tổng quát, có ứng dụng trực tiếp trong việc xấp xỉ một hàm số bằng các đa thức, nhưng còn có ứng dụng trong nhiều vấn đề khác nữa. Ý tưởng và cách chứng minh thuật toán rất sơ cấp, một học sinh chuyên toán cấp 3 có thể hiểu được dễ dàng.
• Cho phép estimate -entropy và -diameters của một không gian hàm số. Đây là những khái niệm hết sức quan trọng, được dùng để định lượng độ complex của một không gian hàm số, do Kolmogorov giới thiệu. Khái niệm này không chỉ có ứng dụng trực tiếp trong lý thuyết xấp xỉ, mà còn có ứng dụng trực tiếp đến lý thuyết empirical processes trong xác suất, và statistical learning theory. Qua đó ta có thể ước lượng được số lượng data cần thiết để có thể học được một mô hình thống kê với độ chính xác nhất định.
• Các kết quả của Birman và Solomjak không chỉ giới hạn đến không gian Sobolev, mà còn được áp dụng đến các không gian khác trong giải tích có ứng dụng trực tiếp đến signal processing.

Chủ đề: 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) »

Theo VNExpress

Theo dự luật Điện ảnh trình Quốc hội chiều 23/5, những cảnh đầu rơi máu chảy, cận cảnh làm tình, khỏa thân sẽ bị cấm trong hoạt động điện ảnh. Tuy nhiên, nhiều đại biểu cho rằng, những quy định cấm quá cụ thể như trên sẽ cản trở hoạt động sáng tạo nghệ thuật.
…
Điều luật này cũng cấm các cảnh đầu rơi máu chảy, chặt từng bộ phận con người, cảnh đánh đập khoái trá của kẻ gây tội ác (trừ trường hợp phê phán lên án các ác).

NBA Commissioner David Stern cấm Micheal Jordan vừa dunk bóng vừa thè lưỡi

trừ trường hợp thè lưỡi một cách nghệ thuật như sau

Dĩ nhiên, vụ thè lưỡi là tôi chế ra. Còn quy chế hoạt động biểu diễn và tổ chức biểu diễn nghệ thuật chuyên nghiệp thì là đồ thiệt 100%:

Đối với loại hình ca, múa, nhạc hiện đại: (cấm -PV) hoá trang tạo ra kiểu đầu kinh dị, sơn, nhuộm tóc lòe loẹt, cạo trọc hoặc để tóc quá dài bù xù, trang phục hở hang, lộ liễu

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

Tiếp tục về các trò ảo thuật. Ta Rum Te Tum Tum là một trò xếp giấy của Nhật. Đơn giản và hiệu quả! Xem video ở đây (1.3 MB)

(Source: grand-illusions.com)

Nói về illusion, có một cái trick rất hay sau đây (lấy từ grand-illusions) có thể làm ảo thuật cho bạn bè trên bàn nhậu. Viết cụm từ “CARBON DIOXIDE” trên một mảnh giấy, CARBON bằng mực đỏ và DIOXIDE bằng mực xanh. Đặt mảnh giấy sau cán một cốc rượu như trong hình. Các chữ đỏ bị lộn ngược, còn các chữ xanh thì không. Đố biết tại sao?

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

Theo một poll mới của National Geographic:

Young Americans answer about half (54 percent) of all the survey questions correctly. But by and large, majorities of young adults fail at a range of questions testing their basic geographic literacy.

* Only 37% of young Americans can find Iraq on a map—though U.S. troops have been there since 2003.
* 6 in 10 young Americans don’t speak a foreign language fluently.
* 20% of young Americans think Sudan is in Asia. (It’s the largest country in Africa.)
* 48% of young Americans believe the majority population in India is Muslim. (It’s Hindu—by a landslide.)
* Half of young Americans can’t find New York on a map.

Hừm. Nếu họ tìm không ra New York thì làm sao tìm ra Iraq hay Sudan. Mặt khác, con số “6 in 10 young Americans don’t speak a foreign language fluently” có nghĩa là 40% dân Mỹ nói lưu loát một thứ tiếng khác ngoài tiếng Anh, khá ấn tượng - không bằng dân Châu Âu, nhưng chắc là hơn dân Châu Á Thái Bình Dương.

Một trong những thứ tôi chán nhất ở Mỹ là phần tin tức. Khi mà một cô bé mất tích được các “chuyên gia” phân tích, ỉ ôi ngày này qua tháng khác; còn các tin thế giới khác hầu như là zero. CNN International khác hẳn với CNN chiếu trong nước Mỹ.

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

Lại thêm một vụ làm giả dữ liệu và ăn cắp ý tưởng, lần này là từ Trung Quốc. (Tôi đã viết về vài vụ trước và dự đoán chính xác rằng sớm muộn gì cũng có dân máy tính dính vào vụ làm giả dữ liệu.) Theo NY Times:

SHANGHAI, May 13 — China said Friday that a prominent university scientist who had developed one of the nation’s first homegrown computer chips had fabricated his research and stolen the technology from a foreign company, according to the official Xinhua News Agency.
…
The case is a huge embarrassment for China and for Shanghai, which in 2003 had touted the first of Professor Chen’s three digital signal processor chips as a major scientific breakthrough, a milestone for the nation.

Chủ đề: CNTT các nước và VN & Chính trị trong ngành | Bình luận (1) »

Trong các ngành giải trí, có hai thứ tôi rất phục là

• Hài hước gia (loại standup comedians kiểu Chris Rock, George Carlin, và loại political comedy shows như của Bill Maher, Jon Steward)
• Ảo thuật gia loại ảo thuật gia đường phố như David Blaine. Tôi không thích illusionists kiểu David Copperfield, cho dù cái illusion họ làm có vĩ đại đến đâu (chui qua vạn lý trường thành xem chẳng có gì hay). Vì thế, tôi cũng không thích các trò ngâm mình trong băng, vụ stunt 44-ngày ở London, hay vụ ngâm mình trong nước 7 ngày ở Lincoln center tuần trước của David Blaine.

Hai nghề này đòi hỏi óc quan sát và sáng tạo tuyệt vời.

Hồi David Blaine mới nổi, hắn chuyên đi ra đường phố làm nhiều trò ảo thuật “on your face” hay cực. Ví dụ: có video clips của các trò làm thủng đồng xu, ném bài vào chai, chiếc nhẫn, đồng tiền, nửa đồng tiền, và một mớ trò khác. Có lẽ cái trick ấn tượng nhất là trò Balducci Levitation: người ta thấy David từ từ nâng người khỏi mặt đất khoảng 10 phân, ngay trước mặt mình!

Cũng nhự vụ ảo thuật gia mặt nạ nổi đình nổi đám chục năm trước, các magic tricks của Blaine cũng có nhiều người biết. Đây là một trong số rất nhiều các tài liệu giải thích các trò ảo thuật của Blaine. Dĩ nhiên, nếu bạn chưa xem street magic của Blaine thì đừng đọc các tài liệu này, mất hứng đi. Thử cái này trước.

Chủ đề: Nhân vật và sự kiện & Vui - Giải Trí | Bình luận (2) »