Category Archives: Xác suất & thống kê

Phương pháp xác suất, thống kê, dùng trong KHMT

Các bài báo kinh điển KHMT (9): Birman and Solomjak’s 1967 paper

Nguyễn Xuân Long | 24/05/2006 | Bản để in Bản để in

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ũng thuộc về chủ đề Lý thuyết tính toán, Lý thuyết thông tin, Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo | 2 phản hồi »

Common sense và AI

Nguyễn Xuân Long | 23/04/2006 | Bản để in Bản để in

Bài blog gần đây của anh Hưng nhắc đến câu chuyện với John McCarthy. Vị GS nổi tiếng này cho rằng: (…) không tin rằng common sense có gì fundamentally statistical hay probabilistic. Tôi nghĩ đây là một vấn đề thú vị — “blog-friendly” topic — nên lôi nó ra đây. JMC là một trong [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Trí tuệ nhân tạo | 12 phản hồi »

Stochastic processes: Thêm một số sách hay miễn phí online

Nguyễn Xuân Long | 14/01/2006 | Bản để in Bản để in

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 [...]

Cũng thuộc về chủ đề Giới thiệu sách, Lý thuyết thông tin, Thuật Toán, Trí tuệ nhân tạo | 13 phản hồi »

“great algorithms” trong KHMT

Nguyễn Xuân Long | 10/01/2006 | Bản để in Bản để in

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 [...]

Cũng thuộc về chủ đề Lý thuyết tính toán, Lý thuyết thông tin, Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo | 2 phản hồi »

Một bài puzzle nữa về sequential decision

Nguyễn Xuân Long | 10/12/2005 | Bản để in Bản để in

Bài này cũng tương tự như (có lẽ dễ hơn một chút) bài toán thổi bóng . Khác ở đây là các quả bóng đã được thổi sẵn , nhưng dẫu sao cũng thuộc một dạng optimal sequential decision making problem: Giả sử có n quả bóng đã được thổi, có thể tích để trong [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo | 1 phản hồi »

Sức mạnh của xác suất [5]

NQH | 06/12/2005 | Bản để in Bản để in

Bài toán đố sau là do Mohammad Mahdian truyền bá ở hội nghị FOCS 2005, biết thông qua 3dpancakes. Có quả bong bóng (chưa thổi) với thể tích . Ta không biết bóng nào có thể tích nào. Thổi quá thể tích thì bóng vỡ. Tìm một phương pháp thổi ngẫu nhiên hóa sao cho [...]

Chủ đề Xác suất & thống kê | 8 phản hồi »

Sức mạnh của xác suất [4]

NQH | 29/11/2005 | Bản để in Bản để in

Có n phong bì, mỗi phong bì đựng một số tiền khác nhau. Các phong bì này được hoán vị ngẫu nhiên và xếp thành một hàng dài. Ta chơi trò chơi sau đây: mở từng phong bì một. Mỗi lần mở xong một phong bì mới ta có quyền quyết định ngừng chơi. Nếu [...]

Chủ đề Xác suất & thống kê | 8 phản hồi »

Sức mạnh của xác suất [3]

NQH | 17/11/2005 | Bản để in Bản để in

Xin viết kỹ hơn về phương pháp giải mã của Bob cho bài toán đang xét. Về căn bản, Alice muốn gửi cho Bob con số . Với chiến lược đã nêu, tỉ lệ q của số bit 1 trên tổng số bit nhận được sẽ gần với p nhưng không có gì đảm bảo [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Mạng máy tính | Phản hồi »

Sức mạnh của xác suất [2]

NQH | 14/11/2005 | Bản để in Bản để in

Tiếp tục với câu hỏi cực kỳ thú vị lần trước. Giả sử Bob biết n, và giả sử chuỗi nhị phân C có các bits . Gọi c là số nguyên có biểu diễn nhị phân là C. Ví dụ, nếu C = 10110 thì c = 22. Chiến lược của Alice như sau: [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Mạng máy tính | 3 phản hồi »

Cúm gà và lý thuyết đồ thị

Lê Hoàng Long | 12/11/2005 | Bản để in Bản để in

Hiện nay, dịch cúm gà đã lan đến 10 tỉnh thành của Việt Nam và đã lan đến nhiều quốc gia trên thế giới. Chính phủ Mỹ đã thông qua kế hoạch 7.1 tỉ đô để chiến đấu với cúm gà. Cũng may mắn cho dân Mỹ là mùa Lễ Tạ Ơn này vẫn còn [...]

Cũng thuộc về chủ đề KHMT và sinh học, Mạng máy tính | Phản hồi »

Sức mạnh của xác suất

NQH | 11/11/2005 | Bản để in Bản để in

Đọc các bài báo về IP traceback, tôi vừa học được bài toán tuyệt đẹp sau đây: Alice có một chuỗi C gồm n bits nhị phân cần gửi cho Bob. Tuy nhiên, mỗi lần Alice chỉ có thể gửi 1 bit và gửi xong thì Alice quên béng mất là mình đã gửi bit [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Mạng máy tính | Phản hồi »

Tại sao bị lạc trên Đào Hoa Đảo (Lê Hoàng Long)

NQH | 12/10/2005 | Bản để in Bản để in

[ Đây là bài của anh Lê Hoàng Long gửi. Các bạn nào viết các bài phù hợp với tinh thần của blog, xin gửi email đến một trong các bloggers, chúng tôi sẽ xem xét và đăng thành bài của khách. ] Nói tới đảo Đào Hoa là nói tới Hoàng Dược Sư, cha [...]

Cũng thuộc về chủ đề Lý thuyết tính toán | 1 phản hồi »

Nghe gõ bàn phím, đoán passwords

NQH | 12/09/2005 | Bản để in Bản để in

Một bài báo mới đây của Li Zhuang, Feng Zhou, và Doug Tygar (Berkeley) cho thấy có thể viết chương trình nghe và đoán ta đang gõ gì trên bàn phím, và đoán cả passwords, nếu chương trình có một đoạn ghi âm sẵn của khoảng 10 phút gõ. Đại ý là âm thanh của [...]

Cũng thuộc về chủ đề Bảo mật và mật mã học, Trí tuệ nhân tạo | 4 phản hồi »

Các bài báo kinh điển của KHMT (3): Chernoff’s bounds/ concentration inequalities

Nguyễn Xuân Long | 03/07/2005 | Bản để in Bản để in

Một bài báo được trích dẫn rộng rãi trong giới KHMT, xử lý thông tin, machine learning, v.v. là bài báo của Chernoff: Chernoff, H. (1952). A measure of asymptotic efficiency for tests of an hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493. Một cách tóm tắt, nếu bạn có n [...]

Cũng thuộc về chủ đề Trí tuệ nhân tạo | 1 phản hồi »

Các bài báo kinh điển của KHMT (2): Wald’s sequential analysis theory

Nguyễn Xuân Long | 29/06/2005 | Bản để in Bản để in

Nối tiếp bài viết về bài báo nổi tiếng của Shannon, tôi muốn nói về một bài báo kinh điển trong thống kê cùng giai đoạn những năm 40, có vai trò đặc biệt đến KHMT, kinh tế, và operations research, và đẻ ra cả một lĩnh vực mới trong thống kê gọi là sequential [...]

Cũng thuộc về chủ đề Toán tối ưu | 3 phản hồi »