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 [...]
PM 2: Pattern matching bằng automaton đơn định PM 4: Thuật Toán Apostolico-Crochemore Thuật toán KMP được thiết kế khoảng 1969-1970, mặc dù bài báo KMP phải đến 1977 mới ra bản in. Năm 1974, Robert S. Moyer và J. Strother Moore (và độc lập với họ, cả R. W. Gosper) đã đề xuất một [...]
PM 1: Thuật toán Knuth-Morris-Pratt PM 3: Thuật toán Boyer-Moore 1. Phép xây dựng DFA cơ bắp Chúng ta đang xét bài toán tìm tất cả các xuất hiện của chuỗi p[0..m-1] trong chuỗi s[0..n-1], với bộ ký tự là Σ. Thuật toán KMP thật ra cũng chỉ là mô phỏng một automaton đơn định [...]
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à [...]
PM 2: Pattern matching bằng automaton đơn định Pattern matching là một trong những bài toán cơ bản và quan trọng nhất của ngành máy tính. Tìm patterns trong các chuỗi-DNA là bài toán cơ bản của sinh tin học. Các phần mềm quét virus hiện đại có mấy chục triệu “patterns” là các “chữ [...]
Ta tiếp tục với bài lính bắn laser. Nhờ định lý Loomis-Whitney, ta đã biết điều sau đây. Cho ba tập điểm thì không tồn tại nhiều hơn điểm sao scho , , và . Gọi các điểm này là các điểm ba màu. Với inputs là , để in ra các điểm ba màu [...]
Trong tinh thần lễ hội, và cũng rất tình cờ là một bài toán về truyền video trên mạng một anh học trò hỏi tuần trước lại dẫn đến bài toán Santa Claus, do Nikhil Bansal và Maxim Srividenko giới thiệu ở STOC 2006. Thật ra thì cách định hình bài này rất tự nhiên, [...]
Miễn phí online: Sách của hai chuyên gia hàng đầu về các thuật toán xấp xỉ, nhất là mấy TTXX dựa trên quy hoạch tuyến tính và SDP (semi-definite programming, tiếng Việt?).
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 [...]
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.
Trong bài này chúng ta giới thiệu biến đổi Fourier trên các nhóm Abel hữu hạn, giải tích Fourier của các hàm Bool, và giới thiệu lý thuyết bầu cử cùng với chứng minh định lý Arrow về tính duy lý của sự độc tài.
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 [...]
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 [...]
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, [...]
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 [...]
