Category Archives: Lý thuyết thông tin

Có bao nhiên thông tin mà vẫn chưa thông

Polytime và polydata

Mấy hôm nay đọc một số bài viết về việc học mô hình hỗn hợp (mixture models). Đây là lĩnh vực kinh điển trong thống kê, nhưng vẫn tiếp tục là một lĩnh vực mở đang được quan tâm trong thống kê, học máy cũng như thuật toán. [Tôi cũng vừa upload bài mới trên […]

Cũng thuộc về chủ đề Lý thuyết tính toán, Thuật Toán, Toán Ứng Dụng, Xác suất & thống kê | Tagged , , , , | 7 phản hồi »

Một lớp ngắn ở Bách Khoa về thử nhóm

Tôi sẽ đứng lớp một lớp ngắn hạn ở đại học Bách Khoa về đề tài thử nhóm. Homepage của lớp với lecture notes ở đây. Lớp 3 tuần, 2 buổi mỗi buổi 2 tiếng rưỡi, thứ ba + thứ sáu 9-11:30 sáng. Học phí 300 nghìn. Học phí cho sinh viên đại học là […]

Cũng thuộc về chủ đề Giáo dục, Thuật Toán | 18 phản hồi »

Blessings and curses of dimensionality

Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều […]

Cũng thuộc về chủ đề Giới thiệu sách, 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ê | 2 phản hồi »

Vài talks về lý thuyết mã mạng

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.

Cũng thuộc về chủ đề Lý thuyết tính toán, Mạng máy tính, Thuật Toán | 4 phản hồi »

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

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, Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 2 phản hồi »

Common sense và AI

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ủ đề Trí tuệ nhân tạo, Xác suất & thống kê | 12 phản hồi »

Lý thuyết mã mạng [3]

Nói thêm một chút về định lý của Ahlswede-Cai-Li-Yeung giới thiệu trong bài trước. Ta xét trường hợp tổng quát hơn một chút: mỗi cạnh trong mạng có khả năng truyền packets một giây. (Trong bài trước ta giả sử bằng 1, thật ra chẳng khác nhau gì vì có thể thay một cạnh với […]

Cũng thuộc về chủ đề Mạng máy tính | 9 phản hồi »

Lý thuyết mã mạng [2]

Tiếp theo bài trước, ta xét (và formalilze) một trong nhiều bài toán liên quan đến network coding. Dùng một directed graph để mô hình một mạng máy tính. Để đơn giản hóa vấn đề, ta giả sử là acyclic graph. (Trong trường hợp cyclic, định nghĩa bài toán một cách cụ thể trở nên […]

Cũng thuộc về chủ đề Mạng máy tính | 5 phản hồi »

Lý thuyết mã mạng (1)

Lý thuyết thông tin và mạng máy tính hiển nhiên là có phần giao rất lớn, tương hỗ, bổ túc cho nhau. Trong khoảng 5 năm trở lại đây, một nhánh nghiên cứu cực kỳ thú vị đang càng lúc càng thu hút nhiều nhà nghiên cứu từ cả lý thuyết thông tin (đặc biệt […]

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

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

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, Thuật Toán, Trí tuệ nhân tạo, Xác suất & thống kê | 13 phản hồi »

“great algorithms” trong KHMT

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, Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 2 phản hồi »

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

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ủ đề Thuật Toán, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 1 phản hồi »

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

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ủ đề Mạng máy tính, Xác suất & thống kê | Phản hồi »

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

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ủ đề Mạng máy tính, Xác suất & thống kê | 3 phản hồi »

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

Đọ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ủ đề Mạng máy tính, Xác suất & thống kê | Phản hồi »