Blog Khoa Học Máy Tính

Tôi đã viết nhiều lần trên blog về xu hướng tất yếu của việc xuất bản khoa học miễn phí và trực tuyến. Mấy hôm trước, có tin sốt dẻo từ tạp chí Nature rằng một số nhà xuất bản lớn, bao gồm Elsevier, Wiley, và American Chemical Society đã họp mặt với một tay luật sư có (tai) tiếng để tìm cách chọc phá xu hướng này:

Now, Nature has learned, a group of big scientific publishers has hired the pit bull to take on the free-information movement, which campaigns for scientific results to be made freely available. Some traditional journals, which depend on subscription charges, say that open-access journals and public databases of scientific papers such as the National Institutes of Health’s (NIH’s) PubMed Central, threaten their livelihoods.
…
The consultant advised them to focus on simple messages, such as “Public access equals government censorship”. He hinted that the publishers should attempt to equate traditional publishing models with peer review, and “paint a picture of what the world would look like without peer-reviewed articles”.

Hừm “public access” bằng “government censorship”. Một thông điệp như thế mà cũng có người gợi ý dùng làm chiến lược được. Điều đáng sợ là chiến lược này vẫn có thể thành công phần nào, vì công chúng không hiểu được rằng “public access” thì vẫn có thể peer-reviewed được như thường, và nhà nước không đóng bất kỳ một vai trò gì trong việc quyết định cái gì được đăng báo khoa học, cái gì không.

In an enthusiastic e-mail sent to colleagues after the meeting, Susan Spilka, Wiley’s director of corporate communications, said Dezenhall explained that publishers had acted too defensively on the free-information issue and worried too much about making precise statements. Dezenhall noted that if the other side is on the defensive, it doesn’t matter if they can discredit your statements, she added: “Media messaging is not the same as intellectual debate.

Câu nói của bà Susan Spilka là tóm lược tốt nhất cho chiến lược của các nhà xuất bản. Nếu chỉ dùng intellectual debate thì chắc chắn họ sẽ thua!

Chủ đề: Xuất bản | Bình luận »

Cảm ơn anh Phú Bình cho biết cái link này:

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

Với dạng cây nhị phân như hiện nay, có khả năng đấu thủ mạnh thứ hai trong giải (do bị đấu thủ mạnh nhất loại từ trước) không được huy chương bạc. Nếu ai đó (như Andy Rodick) mà xui xẻo nằm ở nửa nhánh cây chung với Federer thì coi như là … hẻo.

Lewis Carroll (tác giả Alice in Wonderland) còn là một nhà toán học có cỡ. Ông đã nêu vấn đề bất công này từ hồi 1883 trong tạp chí St. James’s Gazette. Chương 5 quyển 3 của bộ sách của Knuth ghi lại khá chi tiết các phát triển sau đó của câu hỏi này.

1 Nếu bạn phải thiết kế một lịch thi đấu tennis để xác định đấu thủ mạnh nhất và đấu thủ mạnh nhì, bạn cần tối thiểu bao nhiêu trận đấu, cho biết tổng số đấu thủ ban đầu là n?

2 Nếu ta muốn biết cả đấu thủ mạnh thứ 3 (huy chương đồng), thì cần tổng cộng bao nhiêu trận đấu, lịch thi đấu thế nào?

(Dĩ nhiên, câu hỏi tổng quát nhất là xác định m đấu thủ mạnh nhất, và đã có vài câu trả lời gần tối ưu cho câu hỏi này, nhưng chưa phải là tối ưu.)

Chủ đề: Thuật Toán | Bình luận (6) »

(Biết qua Pharyngula.) Bản đồ sau đây cho biết nền kinh tế của các tiểu bang của Mỹ ngang bằng với quốc gia nào trên thế giới. Kinh tế Việt Nam tương đương với tiểu bang Rhode Island, Canada bằng Texas, Pháp bằng California, Đại Hàn bằng Florida, vân vân.

(Click vào bản đồ cho hình lớn hơn.)

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

Tờ Wall Street Journal vừa có bài thú vị. Vài trích đoạn:

Money, as the Beatles once said, can’t buy you love. But according to a new survey, wealth can bring you better sex.
…
Fully 63% of rich men said wealth gave them “better sex,” which they defined as having more-frequent sex with more partners. That compares to 88% of women who said more money gave them better sex, which they defined as “higher quality” sex.

“This tells us that the women as a whole receive more sexual benefits from wealth than men,” says Ms. Grove.

Còn nhiều dữ liệu hay ho trong bài. (Biết qua Marginal Revolution.)

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

Bản nháp báo cáo của một workshop do NSF tài trợ.

Chủ đề: Lý thuyết tính toán & Mạng máy tính | Bình luận (4) »

• M. E. J. Newman, The structure and function of complex networks, SIAM Review, vol. 45, no. 2, pp. 167–256, 2003. [pdf]
• J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845. [pdf]
• J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. [pdf]

Chủ đề: Mạng máy tính & Thuật Toán | Bình luận »

Vụ này thú vị quá:

Yale freshman Jian Li has filed a federal civil rights complaint against Princeton for rejecting his application for admission, claiming the University discriminated against him because he is Asian. The complaint, which was filed with the U.S. Department of Education’s Office for Civil Rights on Oct. 25, alleges that the University’s admissions procedures are biased because they advantage other minority groups, namely African-Americans and Hispanics, legacy applicants and athletes at the expense of Asian-American applicants.
…
Li cites a recent study conducted by two Princeton professors as evidence for his case. The study, published in June 2005, concluded that removing consideration of race would have little effect on white students, but that Asian students would fill nearly four out of every five places in admitted classes that are currently taken by African-American or Hispanic students.

Xem thêm một số phát triển sau đó. Biết qua Crooked Timber.

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

Tôi thỉnh thoảng khá bức xúc với các “tin tức/bình luận” về các đề tài khoa học của các phương tiện truyền thông đại chúng (cả Tây lẫn Ta). Tạp chí Columbia Journalism Review có bài khá hay của Chris Mooney và Matthew C. Nisbet về cách truyền thông đại chúng Mỹ đối xử với đề tài Creationism/Intelligent Design chọi Tiến Hóa.

If news editors fail to recognize the growing demand for journalists with specialized expertise and backgrounds who can get beyond this form of writing, the news media risk losing their ability to serve as important watchdogs over society’s institutions.

Ở ta cũng có vụ tương tự, ở tầm mức nhỏ hơn. Tuy nhiên, bản chất vấn đề là giống nhau.

“Công bằng và cân bằng” là tiêu chí quan trọng của ngành truyền thông, nhưng tiêu chí này chỉ có thể áp dụng vào những đối trọng có (gần) cùng thứ nguyên.

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

Trong bài trước ta kết thúc với định lý Maschke rằng bất kỳ phép biểu diễn (phức) nào trên một nhóm hữu hạn đều là tổng của các phép biểu diễn tối giản. (Biểu diễn các nhóm vô hạn cũng được, nhưng ta không xét ở đây.)

Như vậy, ta có thể nghiên cứu các phép biểu diễn dùng các phép biểu diễn “đơn giản” hơn một chút. Tuy nhiên, một phép biểu diễn vẫn là một đối tượng rất phức tạp để mô tả (nó là một phép đồng cấu thỏa mãn một số tính chất đại số, hoặc cũng có thể xem nó là một ma trận nếu ta chọn trước một hệ cơ sở trên không gian ). Thậm chí, có bao nhiêu phép biểu diễn (không isomorphic với nhau) ta cũng không biết. Có thể có vô hạn các phép biểu diễn không? Làm thế nào để phân loại chúng?

Để phân loại các phép biểu diễn, có một cách để loại bỏ đa số thông tin về phép biểu diễn, chỉ giữ lại một vài con số! Các con số này chứa rất nhiều thông tin về phép biểu diễn, và ta có thể dùng chúng để phân loại các phép biểu diễn. Kết quả này là một trong những định lý đẹp nhất trong đại số.

Các con số “kỳ diệu” này được chứa trong một hàm gọi là đặc trưng (character) của phép biểu diễn. Đặc trưng của phép biểu diễn trên nhóm là một hàm định nghĩa như sau

(Nhớ rằng là một toán tử tuyến tính khả nghịch trên không gian phức , cái trace của là tổng các eigenvalues — trị đặc trưng — của nó.) Hàm đặc trưng cũng có thể được xem như một vector mà các tọa độ được đánh chỉ sổ bởi các thành viên của nhóm .

Định nghĩa số chiều (dimension) của một character là số chiều của không gian V của phép biểu diễn. Định nghĩa một tích vô hướng Hermitian giữa các characters như sau:

( là complex conjugate của .) Đặc trưng của phép biểu diễn chứa cực kỳ nhiều thông tin về phép biểu diễn. Sau đây tôi trích ra vài kết luận quan trọng:

• chính là số chiều của phép biểu diễn
• , với mọi phần tử , nghĩa là character có giá trị như nhau trên mỗi conjugacy class của nhóm.
• 
• Character của là tổng của các characters thành phần .
• Gọi , và là các đại diện của các isomorphism classes của các phép biểu diễn tối giản trên , và gọi là character của . Ta có:
  • Các vectors vuông góc với nhau và có chiều dài đơn vị. (Orthogonality relation.) Gọi là tổng số các conjugacy classes của nhóm. Gọi là không gian vector của các hàm sao cho có giá trị như nhau trên mỗi conjugacy class của . Ta có, các characters tạo thành một hệ cơ sở trực chuẩn của . Ta sẽ dùng tính chất này để nói thêm về DFT trên các nhóm Abel trong bài tới.
  • Tổng số các isomorphism classes của các phép biểu diễn tối giản bằng với tổng số các conjugacy classes của nhóm . Gọi là tổng số này.
  • Gọi là số chiều của , ta có chia hết cho , và
    
• Một character bất kỳ của nhóm đều có thể biểu diễn (theo một cách duy nhất) thành tổ hợp tuyến tính của các characters tối giản.
• Hai phép biểu diễn có character giống nhau thì isomorphic với nhau
• Một character là tối giản nếu và chỉ nếu nó có chiều dài đơn vị (nghĩa là )
• Nếu là một nhóm Abel thì các characters tối giản của nó đều có số chiều bằng (nghĩa là ta có thể nghĩ về chúng như một số phức, thay vì một vector phức).

Có một hệ quả tuyệt đẹp của lý thuyết biểu diễn nhóm khi là nhóm các hoán vị của phần tử. Gọi là số các standard Young tableaux dạng . Ta có:

Định lý này cũng có thể chứng minh bằng giải thuật Robinson-Schensted.

Chủ đề: Thuật Toán | Bình luận (13) »

70. Tèo leo đỉnh Phan-xi-pang. Bắt đầu sáng thứ bảy từ chân núi đến tối thì lên đến đỉnh. Ngủ một đêm, sáng chủ nhật Tèo leo xuống, đến hoàng hôn thì đến chân núi. Chứng minh rằng có cùng một thời điểm (ví dụ như 1 giờ 2 phút chiều) trong ngày thứ bảy và chủ nhật mà Tèo ở cùng một độ cao.
71. Có một tập hợp các điểm trên mặt phẳng. Không phải tất cả cùng nằm trên một đường thẳng. Chứng minh rằng có một đường thẳng chỉ đi qua hai điểm mà thôi.
72. Có n điểm xanh và n điểm đỏ trên mặt phẳng, không có 3 điểm nào thẳng hàng, các điểm đều khác nhau. Chứng minh rằng có một cách ghép cặp 1-1 xanh đỏ sao cho các đoạn thẳng nối các cặp này không cắt nhau.

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

Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất.

Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán & Mạng máy tính & Thuật Toán | Bình luận (3) »

econphd.net, trong đó có ranking.

Chủ đề: Dành cho du học sinh & Trang web hay | Bình luận (1) »

Theo NY Times

In their recent paper “Paying Not to Go to the Gym,” the economists Stefano DellaVigna and Ulrike Malmendier showed that people who buy an annual membership to a health club overestimate by more than 70 percent how much they’ll actually use it. Many people, therefore, would be better off buying monthly or daily passes.

Ta có gặp trường hợp này trong học tập và nghiên cứu không?

• Kiểm tra lại những quyển sách đã mua (vài trăm), có khoảng 20 quyển tôi chưa đọc (dù rất muốn nhưng chưa có thời gian), khoảng 10-20 quyển khác không được tận dụng hết giá trị vì chúng là sách tham khảo, khi nào cần mới mở ra đọc chương cần thiết. Có lẽ, đối với một số quyển sách loại này thì về mặt kinh tế tôi nên mượn thư viện. Đấy là rất may mà tôi chưa áp dụng “chiêu” của O’Rourke là “always read stuff that makes you look good if you die in the middle of it” :-).
• Các subscriptions vào các tạp chí chuyên ngành cũng nhiều khả năng bị phung phí như thế. Có mấy tháng bận quá bỏ không đọc CACM hoặc Mathematical Monthly.
• Đôi khi in một đống bài báo về một đề tài nào đó ra rồi … bỏ xó cả năm trời.

Cũng may mà từ 2001 đến nay hầu hết các sách chuyên ngành và toàn bộ subscriptions tôi không phải bỏ tiền túi ra mua.

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

Matthias Grossglauser ghi lại một danh sách 10 bài báo về network models tốt nhất (theo Matthias) đến nay.

Chủ đề: Mạng máy tính | Bình luận »