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ư [...]
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 [...]
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 [...]
Tiếp theo các bài trước, bài này nói về DFT trên các nhóm Abel. Ta đã biết rằng các phép biểu diễn tối giản trên một nhóm Abel bất kỳ đều là các phép biểu diễn 1 chiều. Tổng số các (isomorphism classes của) các phép biểu diễn một chiều này bằng với tổng số [...]
Mấy tháng nay tôi đang giải một bài toán rất thú vị. Sau đây là mô tả bằng ngôn ngữ bình dân một trường hợp (rất) đặc biệt của nó. Tí và Tèo chơi trò chơi sau đây: Cho trước các tham số nguyên dương m và n cho trò chơi Khi bắt đầu trò [...]
Các routers trên Internet phải xử lý cực nhiều packets với tốc độ cực cao. Giả sử ta phải thiết kế một thuật toán để chỉ ra, trong một dòng các packets đã thấy cho đến thời điểm này (n packets, và n có thể cực lớn), có source-IP nào xuất hiện hơn n/2 lần [...]
Nhân đọc một entry về xếp thứ tự giấy tờ bên unfogged: trong cuộc sống hàng ngày có không ít các trường hợp ta có thể áp dụng một ý tưởng thuật toán nào đó. Vài ví dụ: Nếu phải xếp thứ tự an-pha-bê khoảng trăm bài kiểm tra cuối kỳ nào đó, bạn dùng [...]
Lâu rồi không dùng một phần mềm cho symbolic computation như Mathematica hay Maple. Hồi xưa còn làm về q-series nhiều tôi chọc ngoáy Mathematica hàng ngày. Mấy hôm nay tôi cần chúng cho một bài toán đang giải, dùng lại Maple thấy quả thật là hùng mạnh. Dưới đây là ví dụ về output [...]
Học kỳ này tôi (lại) dạy lớp phân tích và thiết kế giải thuật. Đây là lớp mở đầu phân tích thiết kế thuật toán cho sinh viên sau đại học (năm đầu). Các chủ đề sẽ được thảo luận bao gồm: asymptotic notations and analysis, greedy algorithms, divide and conquer, dynamic programming, linear programming, [...]
Nhân bạn npson thắc mắc về chữ Hanoi trong bài toán “Tower of Hanoi”, tôi đi tìm hiểu thêm ngọn ngành thì ra đại khái thế này. Trong quyển L’arithmétique amusante của chính Lucas, người sáng tạo ra trò chơi “Tower of Hanoi”, có đoạn như sau: : Un de nos amis, le professeur N. [...]
Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều [...]
Cha đẻ của kỹ thuật dynamic prorgramming (quy hoạch động) là Richard Bellman. Hồi đầu những năm 50, Bellman làm tư vấn cho RAND Corp, một trong những think tank có ảnh hưởng cực lớn của quân đội Mỹ. (Lý thuyết game, quy hoạch tuyến tính, và nhiều nhánh khác của toán học, kinh tế [...]
Với dạng cây nhị phân như hiện nay, có khả năng đấu thủ mạnh thứ hai trong giải (do bị đấu thủ mạnh nhất loại từ trước) không được huy chương bạc. Nếu ai đó (như Andy Rodick) mà xui xẻo nằm ở nửa nhánh cây chung với Federer thì coi như là … hẻo. [...]
M. E. J. Newman, The structure and function of complex networks, SIAM Review, vol. 45, no. 2, pp. 167–256, 2003. [pdf] J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845. [pdf] J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. [pdf]
Trong bài trước ta kết thúc với định lý Maschke rằng bất kỳ phép biểu diễn (phức) nào trên một nhóm hữu hạn đều là tổng của các phép biểu diễn tối giản. (Biểu diễn các nhóm vô hạn cũng được, nhưng ta không xét ở đây.) Như vậy, ta có thể nghiên cứu các [...]
