Category Archives: Thuật Toán

Các giải thuật, kỹ thuật thiết kế, lý thuyết và ứng dụng, …

Cân xu

Ngô Quang Hưng | 04/08/2010 | Bản để in Bản để in
Bạn Huân hỏi về một bài toán đố cổ điển: bài toán cân xu tìm xu giả. Phiên bản thường nghe là như thế này: cho 12 đồng xu trong đó có 1 đồng xu giả (không biết nặng hay nhẹ hơn các đồng khác) và một cái cân thăng bằng, cân 3 lần tìm [...]
Cũng thuộc về chủ đề Combinatorics | 6 phản hồi »

Trả lời nhanh vài câu hỏi về phân tích thuật toán

Ngô Quang Hưng | 02/08/2010 | Bản để in Bản để in
Bạn Thắng có vài câu hỏi về phân tích độ phức tạp thuật toán, tôi trả lời vắn tắt dưới đây.
Cũng thuộc về chủ đề Lý thuyết tính toán | 4 phản hồi »

PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

Ngô Quang Hưng | 29/07/2010 | Bản để in Bản để in
Như vậy chúng ta đã có chuyến “de-tour” sang các phép xây dựng đồ thị expanders, tính chất của chúng, và tích zig-zag. Đáng lẽ bài kế tiếp này tôi định viết về kết quả của Omer Reingold hồi 2005. Nhưng lại thôi vì thật ra nếu hiểu tích zig-zag rồi thì hiểu chứng minh [...]
Cũng thuộc về chủ đề KHMT và Kinh Tế, Lý thuyết tính toán, Xác suất & thống kê | 13 phản hồi »

GT 10: Thuật toán AMS ước lượng mô-măng tần số

Ngô Quang Hưng | 12/07/2010 | Bản để in Bản để in
10. Thuật toán AMS ước lượng mô-măng tần số Tưởng tượng một chuỗi (rất nhiều, cả triệu) gói dữ liệu đi qua một router trong thời gian ngắn. Gói thứ có địa chỉ IP nguồn nào đó thuộc tập . Với mỗi , gọi là số lần xuất hiện của địa chỉ , còn gọi [...]
Cũng thuộc về chủ đề Xác suất & thống kê | Phản hồi »

GT 9: Tiền xu Chernoff-Bernstein và mẹo trung vị

Ngô Quang Hưng | 10/07/2010 | Bản để in Bản để in
9. Tiền xu Chernoff-Bernstein và mẹo trung vị 9.1. Tiền xu Chernoff-Bernstein Thảy lần độc lập một đồng xu mà xác suất ra mặt ngửa là thì trị kỳ vọng của số lần ra mặt ngửa là . Ông Chernoff bảo rằng xác suất mà tổng số mặt ngửa quấn quít xung quanh sẽ tiến [...]
Cũng thuộc về chủ đề Xác suất & thống kê | Phản hồi »

GT 8: Con gà của ông Chebyshev

Ngô Quang Hưng | 09/07/2010 | Bản để in Bản để in
8. Con gà của ông Chebyshev 8.1. Khoảng cách giữa tư bản hút máu và xã hội chủ nghĩa Tiếp theo bài trước, hãy nói về con gà của bác nông dân. Bác nông dân và địa chủ ăn hết một con gà, nhưng địa chủ ăn sạch cả con, bao gồm xương, lông, cánh, [...]
Cũng thuộc về chủ đề Xác suất & thống kê | 3 phản hồi »

GT 7: Con gà của ông Markov

Ngô Quang Hưng | 08/07/2010 | Bản để in Bản để in
7. Con gà của ông Markov 7.1. Việt Nam có bao nhiêu trọc phú? Tí và Tèo ăn hết một con gà. Ông Markov bảo rằng không thể nào cả Tí lẫn Tèo đều ăn hơn nửa con gà được. Nếu 10 người ăn hết một con gà, thì không thể có hơn 4 anh [...]
Cũng thuộc về chủ đề Xác suất & thống kê | Phản hồi »

GT 6: Thử nhóm bất ứng biến giải mã nhanh

Ngô Quang Hưng | 29/01/2010 | Bản để in Bản để in
6. Thử nhóm bất ứng biến giải mã nhanh 6.1. Ý tưởng của Kautz-Singleton Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số trên cột) đủ lớn và nếu hai cột [...]
Cũng thuộc về chủ đề Combinatorics, Lý thuyết mã hóa | 2 phản hồi »

GT 5: Sơ lược lý thuyết mã hóa

Ngô Quang Hưng | 26/01/2010 | Bản để in Bản để in
5. Sơ lược lý thuyết mã hóa Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc [...]
Cũng thuộc về chủ đề Combinatorics, Lý thuyết mã hóa | Phản hồi »

GT 4: Bassalygo, Erdős, và Sperner

Ngô Quang Hưng | 29/12/2009 | Bản để in Bản để in
4. Chặn dưới Leonid Bassalygo là một học trò giỏi của người khổng lồ Kolmogorov. Từ những năm 1970, ông đã có nhiều đóng góp cơ bản trong lý thuyết thông tin, lý thuyết mã hóa, và lý thuyết các mạng chuyển mạch (switching networks). Có nhiều định lý và chặn mang tên ông. Ví [...]
Cũng thuộc về chủ đề Combinatorics | 1 phản hồi »

GT 3: Ứng dụng trong dòng dữ liệu và bảo mật

Ngô Quang Hưng | 17/12/2009 | Bản để in Bản để in
3. Vài ứng dụng của thử nhóm bất ứng biến Muthu Muthukrishnan là một khoa học gia máy tính có rất nhiều đóng góp nặng ký trong nhiều nhánh khác nhau: cơ sở dữ liệu, thuật toán, dòng dữ liệu, v.v. Gần đây anh chuyển về Google làm về các thuật toán ad bidding, một [...]
Cũng thuộc về chủ đề Bảo mật và mật mã học | Phản hồi »

GT 2: Phân Ly và Phân Cách

Ngô Quang Hưng | 15/12/2009 | Bản để in Bản để in
( tiếp theo bài trước ). 2. Ma trận phân ly và ma trận phân cách Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay [...]
Cũng thuộc về chủ đề Combinatorics, Xác suất & thống kê | 4 phản hồi »

GT 1: Bệnh giang mai, đại số, hồi phục tín hiệu thưa, và dòng dữ liệu

Ngô Quang Hưng | 14/12/2009 | Bản để in Bản để in
1. Đại số và bệnh giang mai Hòa thượng (HT) Thích Học Toán là chuyên gia đại số hàng đầu thế giới. (Tôi học đòi cách viết bài của giáo sư Richard Lipton mà tôi rất thích.) Gần đây HT lại thành celebrity sau bầu chọn của tạp chí Time. Nhất định sẽ có nhiều [...]
Cũng thuộc về chủ đề Bảo mật và mật mã học, KHMT và sinh học, Xác suất & thống kê | 6 phản hồi »

Một bài tập lớp mạng máy tính

Ngô Quang Hưng | 21/10/2009 | Bản để in Bản để in
Học kỳ này tôi dạy lớp mạng máy tính. Tôi thiết kế một bài tập mà cá nhân tôi rất thích vì nó chứa các thành tố của cả mạng lẫn thuật toán (quy hoạch động). Ý tưởng của bài tập này đến từ một bài báo mà anh Hà Trần Đức và tôi viết [...]
Cũng thuộc về chủ đề Mạng máy tính | Phản hồi »

PCP 9 — Expanders: tích zig-zag

Ngô Quang Hưng | 25/06/2009 | Bản để in Bản để in
8.j. Tích zig-zag Chúng ta đã thấy rằng đã số các ứng dụng của expanders không những cần sự tồn tại của expanders mà còn cần thuật toán xây dựng expanders hiệu quả (hoặc tương đối cụ thể, hoặc rất cụ thể). Bài này viết về một phương pháp/thuật toán hiệu quả để xây dựng [...]
Cũng thuộc về chủ đề Lý thuyết tính toán | 2 phản hồi »