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, …

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

NQH | 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ê | Tagged , | 10 phản hồi »

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

NQH | 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ê | Tagged , | Phản hồi »

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

NQH | 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 | Tagged , , , | 2 phản hồi »

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

NQH | 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 | Tagged , , , | 3 phản hồi »

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

NQH | 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

NQH | 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 | 1 phản hồi »

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

NQH | 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ê | 31 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

NQH | 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ê | 7 phản hồi »

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

NQH | 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

NQH | 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 | Tagged , , , , | 2 phản hồi »

PCP 8 — Expanders: tiết kiệm random bits và khuếch đại gap

NQH | 31/05/2009 | Bản để in Bản để in

Trong bài này ta thảo luận các phép xây dựng đồ thị expander, và một vài ứng dụng của chúng: tiết kiệm bit ngẫu nhiên và khuếch đại gap.

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

PCP 7 — Expanders: góc nhìn xác suất

NQH | 29/05/2009 | Bản để in Bản để in

8.d. Spectral expanders và tốc độ hội tụ của random walks trên expanders Trong bài này chúng ta sẽ chứng minh rằng một đồ thị có spectral gap lớn thì “tương đương” với tốc độ hội tụ của một random walk trên đồ thị càng cao. (Sở dĩ ta để tương đương trong ngoặc kép [...]

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

PCP 6 — Expanders: góc nhìn đại số

NQH | 22/05/2009 | Bản để in Bản để in

8.c. Algebraic graph theory và spectral expansion Để định nghĩa expanders từ góc nhìn đại số, ta cần biết một chút về algebraic graph theory và đại số tuyến tính. Về AGT thì tôi giới thiệu 2 quyển sau đây: Algebraic Graph Theory của Biggs, Spectral Graph Theory của Fan Chung. Về đại số tuyến [...]

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

PCP 5 — Expanders: định nghĩa và góc nhìn tổ hợp

NQH | 20/05/2009 | Bản để in Bản để in

8. Expanding graphs, còn gọi là expanders Hôm nay chúng ta “de-tour” một chút để nói về expanders. Đã dùng một loại expander đặc biệt trong bài trước. Bây giờ cần giới thiệu kỹ hơn để dùng vào nhiều việc sau. Chắc sẽ cần ít nhất 3 bài để nói về expanders. Bài survey của [...]

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

PCP 4 — Gap-preserving reduction và bài toán LabelCover

NQH | 19/05/2009 | Bản để in Bản để in

7.d. Vài ví dụ về gap-preserving reduction Những reduction tầm thường như kiểu từ Gap-Max-Clique về Gap-Max-IndependentSet sẽ có tính chất gap-preserving một cách hiển nhiên. Chúng ta xét vài ví dụ không tầm thường: Gap-Max-3SAT(d), Gap-Max-E3SAT(Ed) và Gap-Max-LabelCover; sau này sẽ dùng chúng để chứng minh định lý Hastad và làm động cơ giới [...]

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