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

Vài talks về lý thuyết mã mạng

NQH | 11/01/2007 | Bản để in Bản để in

Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất. Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.

Cũng thuộc về chủ đề Lý thuyết tính toán, Lý thuyết thông tin, Mạng máy tính | 4 phản hồi »

Các kết quả về tính không xấp xỉ được

NQH | 11/10/2006 | Bản để in Bản để in

Quyển Computers and Intractability: A Guide to the Theory of NP-Completeness của Garey và Johnson là tham khảo kinh điển về lý thuyết NP-đầy đủ. Trong 30 năm qua, Johnson vẫn tiếp tục viết các NP-complete columns để cho ta biết các cập nhật mới nhất về các bài toán NP-đầy đủ. Hồi xưa, ta [...]

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

Tất cả các hàm đều liên tục?

NQH | 02/06/2006 | Bản để in Bản để in

Sau lớp 11, chắc ai cũng biết định nghĩa (vô hạn các) hàm không liên tục. Tuy nhiên, có một số nhà toán học theo trường phái constructive mathematics cho rằng tất cả các hàm tính được (computable) đều liên tục. Andrej Bauer có một bài ngắn về đề tài này. Constructive Mathematics và intuitionism [...]

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

Các bài báo kinh điển KHMT (9): Birman and Solomjak’s 1967 paper

Nguyễn Xuân Long | 24/05/2006 | Bản để in Bản để in

Làm thế nào để biểu diễn xấp xỉ một hàm số bằng các đại lượng giải tích đơn giản hơn? Đây là một câu hỏi cơ bản của lý thuyết xấp xỉ (approximation theory) . Tầm quan trọng và ứng dụng của nó rất lớn với KHMT: Hàm số ở đây có thể hiểu là [...]

Cũng thuộc về chủ đề Lý thuyết tính toán, Lý thuyết thông tin, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 2 phản hồi »

Về đề thi ACM ICPC 2006

NQH | 18/04/2006 | Bản để in Bản để in

Cuộc thi ICPC đã xong. Bảng tổng sắp đã có. Kết quả của BK Eagles còn khiêm tốn, nhưng lần đầu đi thi thế là tốt. Tôi vừa xem qua đề thi (PDF), có các phân tích sơ bộ như sau: Problem A: bài quy hoạch động (dynamic programming) thứ nhất. Problem B: về cơ [...]

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

Stochastic processes: Thêm một số sách hay miễn phí online

Nguyễn Xuân Long | 14/01/2006 | Bản để in Bản để in

Khi chúng ta học những kiến thực cơ bản đầu tiên probability theory, ta biết đến những hàm phân phối cho biến thực/tự nhiên ngẫu nhiên kinh điển như Gaussian, Poisson, Bernoulli, Laplace, Dirichlet, Cauchy, v.v. Stochastic processes là gì ? Một cách nôm na, stochastic processes là những hàm phân phối cho những objects [...]

Cũng thuộc về chủ đề Giới thiệu sách, Lý thuyết thông tin, Trí tuệ nhân tạo, Xác suất & thống kê | 13 phản hồi »

“great algorithms” trong KHMT

Nguyễn Xuân Long | 10/01/2006 | Bản để in Bản để in

Prof. Richard Karp chuẩn bị dạy một lớp bậc cao học về những thuật toán quan trọng và nổi tiếng trong KHMT. Lời giới thiệu của syllabus: From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application because of its resolution of [...]

Cũng thuộc về chủ đề Lý thuyết tính toán, Lý thuyết thông tin, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 2 phản hồi »

Một bài puzzle nữa về sequential decision

Nguyễn Xuân Long | 10/12/2005 | Bản để in Bản để in

Bài này cũng tương tự như (có lẽ dễ hơn một chút) bài toán thổi bóng . Khác ở đây là các quả bóng đã được thổi sẵn , nhưng dẫu sao cũng thuộc một dạng optimal sequential decision making problem: Giả sử có n quả bóng đã được thổi, có thể tích để trong [...]

Cũng thuộc về chủ đề Lý thuyết thông tin, Toán tối ưu, Trí tuệ nhân tạo, Xác suất & thống kê | 1 phản hồi »

Gợi ý cho một series bài mới

NQH | 07/12/2005 | Bản để in Bản để in

Một post ở Computational Complexity weblog liệt kê một danh sách các kết quả đáng ngạc nhiên và lớn trong lý thuyết tính toán 75 năm qua. Từ từ tôi sẽ duyệt qua từng kết quả một, nhưng có lẽ sẽ phải viết bằng tiếng Anh. Viết tiếng Việt phải suy nghĩ xem dịch thế [...]

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

Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (3)

NQH | 04/12/2005 | Bản để in Bản để in

Trong các bài trước, tôi đã đề cập sơ qua về nhân ma trận và biến đổi Fourier rời rạc. Chủ đề lần này là lý thuyết biểu diễn nhóm. Trong các bài tới ta sẽ liên hệ chúng với nhau. Đại khái, lý thuyết biểu diễn nhóm cho phép ta nghiên cứu các nhóm [...]

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

Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (2)

NQH | 25/11/2005 | Bản để in Bản để in

Tiếp theo bài trước, lần này ta bàn sơ qua về DFT. Tôi học DFT lần đầu tiên vào khoảng năm 1993. Học xong thấy nó rất bí hiểm, theo kiểu: nếu lấy vector này, tính toán thế này, thì ra các hệ số thế kia, nhưng không hiểu ý tưởng nằm sau các công [...]

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

Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (1)

NQH | 16/11/2005 | Bản để in Bản để in

Nhân hai ma trận là phép tính cực kỳ cơ bản trong toán học. Thiết kế giải thuật nhân hai ma trận một cách hiệu quả là bài toán cực kỳ cơ bản trong KHMT. Tương tự như vậy, Discrete Fourier Transform (DFT – biến đổi Fourier rời rạc) là một trong những biến đổi [...]

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

Các bài báo kinh điển của KHMT (7)

NQH | 08/09/2005 | Bản để in Bản để in

Một mạng sắp xếp (sorting network) là một dạng cấu hình mạch xử lý song song với n cổng vào và n cổng ra như hình sau đây: Các hình vuông là các bộ so sánh (comparator) có hai đầu vào và hai đầu ra. Bộ so sánh sẽ đưa số nhập nhỏ hơn lên [...]

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

Bão Katrina và KHMT

NQH | 03/09/2005 | Bản để in Bản để in

Tình hình bão, các nguy hại, phương thức cứu trợ, … đã được các nhà khoa học dự báo từ lâu. Đây là một ví dụ dự báo năm 2004. Có thể liên hệ gì từ một cơn bão như Katrina và khoa học máy tính? Việc dùng máy tính thực thi các mô hình [...]

Cũng thuộc về chủ đề Nghiên cứu nghiên kiếc, Nhân vật và sự kiện | 1 phản hồi »

Bài toán tháp Hà Nội

Đỗ Bình Minh | 16/07/2005 | Bản để in Bản để in

Theo tôi đây có lẽ là bài toán gắn với một từ tiếng Việt đựợc biết nhiều nhất. Bài toán này như sau: Cho ba cái cọc với 2 cọc trống và 1 cọc có n đĩa với cỡ khác nhau được xếp từ thấp lên cao, chuyển hết đĩa qua một cọc trống với [...]

Cũng thuộc về chủ đề Vui - Giải Trí | 6 phản hồi »