Category Archives: Lý thuyết tính toán

Lý thuyết độ phức tạp, độ phức tạp thuật toán, vân vân.

HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

Ngô Quang Hưng | 30/08/2010 | Bản để in Bản để in
Chúng ta tiếp tục chuỗi bài về đề tài “Học máy từ góc nhìn của lý thuyết tính toán”. Các bài trước là: HM1 — Giới thiệu học máy và mô hình nhất quán HM2 — Một số ví dụ trong mô hình nhất quán HM3 — Mô hình PAC và ví dụ HM4 — [...]
Cũng thuộc về chủ đề Trí tuệ nhân tạo, Xác suất & thống kê | 10 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ủ đề Thuật 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ế, Thuật Toán, Xác suất & thống kê | 13 phản hồi »

Mật mã dưới góc nhìn độ phức tạp tính toán

Phan Dương Hiệu | 20/09/2009 | Bản để in Bản để in
I. Khởi động: Bài toán quyết định và bài toán tìm kiếm (Decision versus Search) Trong thực tế, khi có một bài toán, ta thường quan tâm tới việc tìm ra lời giải cho bài toán đó hơn là xem xét liệu bài toán đó có tồn tại lời giải hay không. Tuy nhiên, trong [...]
Cũng thuộc về chủ đề Bảo mật và mật mã học | 12 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ủ đề Thuật Toán | 2 phản hồi »

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

Ngô Quang Hưng | 31/05/2009 | Bản để in Bản để in
8.f. Sơ lược về các kết quả xây dựng một họ expanders Định nghĩa. (Họ expanders) Cho trước các hằng số , một chuỗi các đồ thị là một họ của các spectral expanders nếu là -spectral expander. Trong đó, , và tồn tại một đa thức sao cho với mọi . Điều kiện cuối [...]
Cũng thuộc về chủ đề Thuật Toán | Phản hồi »

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

Ngô Quang Hưng | 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ủ đề Thuật Toán, Xác suất & thống kê | 1 phản hồi »

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

Ngô Quang Hưng | 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ủ đề Thuật Toán | 2 phản hồi »

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

Ngô Quang Hưng | 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ủ đề Thuật Toán | 9 phản hồi »

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

Ngô Quang Hưng | 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ủ đề Thuật Toán | 10 phản hồi »

PCP 3 — Khó xấp xỉ, gap-producing reductions, FGLSS reduction

Ngô Quang Hưng | 18/05/2009 | Bản để in Bản để in
7. Cơ bản về chứng minh sự khó xấp xỉ Trong bài trước, chúng ta đã chứng minh rằng định lý PCP tương đương với Gap-Max-E3SAT là NP-Hard với một hằng số nào đó. Chúng ta sẽ thấy rằng định lý PCP cũng tương đương với một số gap-problems khác là NP-Hard, ví dụ như [...]
Cũng thuộc về chủ đề Thuật Toán | 11 phản hồi »

PCP 2 — ĐL PCP và NP-hardness của Gap-Max-E3SAT

Ngô Quang Hưng | 16/05/2009 | Bản để in Bản để in
5. Các thuật toán xấp xỉ cho các bài toán NP-Hard Một trong các cách để giải quyết một bài toán tối ưu nhưng lại bị NP-hard là thiết kế một thuật toán xấp xỉ cho nó. Đối với các bài toán này, có một trade-off về mặt bản chất giữa chất lượng lời giải [...]
Cũng thuộc về chủ đề Thuật Toán | 13 phản hồi »

PCP 1 — Định lý PCP và sự không xấp xỉ được

Ngô Quang Hưng | 07/04/2009 | Bản để in Bản để in
1. Phi lộ Sau định lý Cook-Levin về sự tồn tại của các bài toán NP-complete (và Karp cho biết có rất nhiều các bài toán tự nhiên cũng NP-complete), thì định lý PCP là đỉnh cao thứ hai của lý thuyết tính toán. Lịch sử các kết quả dẫn đến định lý PCP cực [...]
Cũng thuộc về chủ đề Thuật Toán | 60 phản hồi »

HM4 — Độ phức tạp mẫu và VC-dimension

Ngô Quang Hưng | 18/07/2008 | Bản để in Bản để in
Trong các bài trước ta đã đề cập đến một số vấn đề không học được trong mô hình PAC và tầm quan trọng của việc biểu diễn lớp giả thuyết như thế nào. Có lẽ bài báo đầu tiên nói về tầm quan trọng của (cách biểu diễn) lớp giả thuyết là bài của [...]
Cũng thuộc về chủ đề Trí tuệ nhân tạo, Xác suất & thống kê | 4 phản hồi »

HM 3 — Mô hình PAC

Ngô Quang Hưng | 14/07/2008 | Bản để in Bản để in
3. Mô hình có lẽ xấp xỉ đúng (Probably Approximately Correct) (viết tắt là mô hình PAC) Hạn chế lớn nhất của mô hình nhất quán, như đã nói, là nó không đếm xỉa gì đến khả năng dự đoán tương lai. Một hạn chế thứ hai là trên thực tế training data ta thường [...]
Cũng thuộc về chủ đề Trí tuệ nhân tạo, Xác suất & thống kê | 9 phản hồi »