“great algorithms” trong KHMT
Nguyễn Xuân Long | 10 tháng 01, 2006 | 
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 a long-standing open question, its surprising efficiency,
the novelty of its setting or approach, the elegance of its structure, the
subtlety of its analysis or its range of applications.
Không phải là tất cả (tất nhiên!), nhưng dây là một danh sách của Prof. Karp để ta tham khảo. Một số đã được nhắc tới đâu đó trong blog này:
-
Elementary examples: Binary arithmetic, sorting, Euclidean algorithm,
greedy algorithm, Dijkstra shortest-path algorithm, Gaussian elimination - Simplex algorithm for linear programming (1947)
- Fast Fourier Transform (1959)
- Gale-Shapley proposal algorithm (1962)
- Edmonds’ nonbipartite matching algorithm (1965)
- Union-find algorithm (1975)
- Lattice basis reduction algorithm (1982)
- Buchberger’s Grobner basis algorithm (1982)
- Ajtai-Komlos-Szemeredi sorting network (1983)
- Randomized algorithms for approximating volume (1989)
- Koutsoupias-Papadimitriou k-server algorithm (1994)
- Shor’s quantum factoring algorithm (1994)
-
The Winnow (1988) and Adaboost (1995) algorithms for statistical
classification -
Interior-point algorithms for linear programming(1984) and semidefinite
programming (1995) - Streaming algorithms for computing moments (1995)
- Sudan’s list decoding algorithm (1997)
- LT codes and Raptor codes for data distribution (2002, 2003)
- Reingold’s logspace algorithm for st-connectivity (2004)
Thuật toán logspace cho bài st-connectivity của Reingold rất đẹp và đơn giản, nếu người đọc có kiến thức về cách xây dựng expander graphs dùng zig-zag product. Thuật toán của Edmonds cho bài toán tìm matching trong đồ thị tổng quát là một cột mốc cực kỳ quan trọng trong các ngành Algorithms, Complexity Theory, và Combinatorial Optimization.
Thiếu thuật toán nhân ma trận của Strassen, Quicksort, một số thuật toán xấp xỉ kinh điển, …