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

Định lý Gale-Ryser

1. Định lý Gale-Ryser Định lý Gale-Ryser là một trong những định lý cổ điển của toán Tổ Hợp. Định lý này trả lời câu hỏi sau đây: Cho trước hai vectors và gồm các số nguyên dương. Có tồn tại một ma trận nhị phân gồm hàng và cột, sao cho tổng hàng thứ […]

Cũng thuộc về chủ đề Combinatorics, Python | Tagged , | 6 phản hồi »

Thuật toán Yannakakis

Bài trước: Độ phức tạp của bài toán định trị truy vấn Bài sau: Chặn AGM. Bài trước nói về độ phức tạp của bài toán định trị truy vấn hội, trong đó ta thảo luận tầm quan trọng của việc phân biệt độ phức tạp biểu thức và độ phức tạp dữ liệu của […]

Cũng thuộc về chủ đề Cơ sở dữ liệu | Tagged , , , , | 1 phản hồi »

Các câu hỏi phỏng vấn [45]

Cho hai dãy số đã sắp xếp theo thứ tự tăng dần. Mỗi dãy dài n. Cho một tham số 1 ≤ k ≤ n, thiết kế thuật toán trả về số nhỏ thứ k trong tập 2n số.

Chủ đề Thuật Toán | Tagged , | 15 phản hồi »

Các câu hỏi phỏng vấn [44]

(Cập nhật 15/10: Hôm trước gõ thiếu một dòng, đã sửa lại.) Hàm tìm kiếm nhị phân sau đây bị vấn đề gì, sửa ra sao?

Cũng thuộc về chủ đề C++ | Tagged | 14 phản hồi »

Siêu đồ thị phi chu trình và đồ thị dây cung

Bài trước: Phân rã cây và độ rộng cây. Bài kế tiếp: logic bậc nhất và truy vấn hội (conjunctive queries). Bài trước lược khảo các khái niệm độ rộng cây, phân rã cây, đồ thị dây cung và một vài bổ đề quan trọng để hiểu thêm về các khái niệm này. Bài cũng […]

Cũng thuộc về chủ đề Cơ sở dữ liệu | Tagged , , , , , | 1 phản hồi »

Phân rã cây và độ rộng cây

Bài kế tiếp: Siêu đồ thị phi chu trình và đồ thị dây cung 1. Giới thiệu Độ rộng cây (tree-width) là một khái niệm sâu sắc và có nhiều ứng dụng. Độ rộng cây và phân rã cây (tree decomposition) do Robertson và Seymour định nghĩa và phát triển trong công trình 20 bài […]

Cũng thuộc về chủ đề Cơ sở dữ liệu, Xác suất & thống kê | Tagged , , , , | 4 phản hồi »

Cây nhị phân và cây tìm kiếm nhị phân

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++. Bài trước: Danh sách liên kết và danh sách nhảy cóc Bài sau: Các cây tìm kiếm cân bằng: AVL, đỏ đen, (2,4), và cây loe 1. Binary trees 1.1. Terminologies A binary tree is […]

Cũng thuộc về chủ đề C++, Cấu trúc dữ liệu, Combinatorics | Tagged , , | 4 phản hồi »

Bàn thêm về thuật toán randomized quick sort

Trong bài lần trước, thuật toán randomized quick sort được viết như sau: Đây là một trong hai cách chuẩn để viết RQS. (Cách này quyển CLRS dùng.) Cách 2 là chạy 2 chỉ số một từ trái qua, một từ phải lại, đến khi bên trái gặp phần tử lớn hơn giá trị pivot […]

Chủ đề Thuật Toán | Tagged , , | 3 phản hồi »

Tìm kiếm và sắp xếp

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++. Bài trước: thuật toán tồi tệ nhất trong lịch sử nhân loại Bài sau: lớp Vector và phân tích khấu hao. 1. Binary search Searching for a key (int, say) in a vector of integers […]

Cũng thuộc về chủ đề Cấu trúc dữ liệu, Lập trình | Tagged , , , | 16 phản hồi »

Thuật toán tồi tệ nhất trong lịch sử nhân loại

Đặt tít để câu view. Số là học kỳ này tôi dạy lớp cấu trúc dữ liệu. Đây là lớp undergrad đầu tiên tôi dạy từ trước đến nay, cho sinh viên năm 1 năm 2 nên viết bài giảng khá chi tiết. Có bài giảng này mới viết, có vẻ thích hợp cho blog […]

Cũng thuộc về chủ đề Lập trình | Tagged , , | 9 phản hồi »

Thuật toán bẻ ghi

Loài người viết các biểu thức toán học dùng ký hiệu trung tố (infix notation) đã vài nghìn năm: [4+3*(2+7)/3-2]*3. Ký hiệu trung tố có bất lợi lớn là cần nhiều dấu ngoặc để phân biệt các biểu thức khác nhau: (4+2)*3 ≠ 4+2*3. Ký hiệu tiền tố, còn gọi là ký hiệu Ba Lan […]

Chủ đề Thuật Toán | Tagged , , , , , | 3 phản hồi »

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, Lý thuyết thông tin, Toán Ứng Dụng, Xác suất & thống kê | Tagged , , , , | 7 phản hồi »

PM 3: Thuật toán Boyer-Moore

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 […]

Cũng thuộc về chủ đề Lập trình | Tagged , , , | Phản hồi »

PM 2: Pattern matching bằng automaton đơn định

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 […]

Cũng thuộc về chủ đề Lập trình | Tagged , , | 1 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, Lý thuyết thông tin | 18 phản hồi »