Danh sách thuật toán

Bài viết này là danh sách các thuật toán cùng một mô tả ngắn cho mỗi thuật toán.

Thuật toán tổ hợp[sửa | sửa mã nguồn]

Thuật toán tổ hợp tổng quát[sửa | sửa mã nguồn]

Thuật toán Brent: tìm một chu trình trong một dãy các giá trị của hàm số chỉ dùng hai biến lặp
Thuật toán rùa và thỏ của Floyd: tìm một chu trình trong một dãy các giá trị của hàm số
Thuật toán Gale–Shapley: giải quyết bài toán hôn nhân bền vững
Bộ sinh số giả ngẫu nhiên (phân bố đều—xem thêm Danh sách bộ sinh số giả ngẫu nhiên với bậc hội tụ và các tính chất khác):

Thuật toán đồ thị[sửa | sửa mã nguồn]

Thuật toán tô màu: các thuật toán để tô màu đồ thị
Thuật toán Hopcroft–Karp: biến đồ thị hai phía thành một cặp ghép cực đại
Thuận toán Hungary: tìm một cặp ghép hoàn hảo
Mã Prüfer: biến một cây gắn nhãn thành chuỗi Prüfer của nó và ngược lại
Thuật toán ngoại tuyến tìm tổ tiên chung thấp nhất Tarjan: tìm tổ tiên chung thấp nhất cho các cặp đỉnh của một cây
Sắp xếp tô pô: tìm thứ tự tuyến tính của các đỉnh dựa trên quan hệ phụ thuộc của chúng

Vẽ đồ thị[sửa | sửa mã nguồn]

Thuật toán hướng lực (còn gọi là thuật toán lò xo)
Spectral layout

Lý thuyết mạng[sửa | sửa mã nguồn]

Phân tích mạng lưới
- Phân tích liên kết
  - Thuật toán Girvan–Newman: tìm những cộng đồng trong hệ thống phức tạp
  - Phân tích liên kết web
    - Tìm kiếm Chủ đề dựa trên Siêu liên kết (thuật toán HITS)
    - PageRank
    - TrustRank
Mạng luồng
- Thuật toán Dinitz: thuật toán đa thức mạnh để tìm luồng cực đại trong một mạng lưới luồng.
- Thuật toán Edmonds–Karp: trường hợp đặc biệt của Ford–Fulkerson
- Thuật toán Ford–Fulkerson: tìm luồng cực đại trong một đồ thị
- Thuật toán Karger: phương pháp Monte Carlo để tính phép cắt cực tiểu của một đồ thị
- Thuật toán đẩy–đổi tên: tìm luồng cực đại trong một đồ thị

Đường đi[sửa | sửa mã nguồn]

Thuật toán Edmonds (còn gọi là thuật toán Chu–Liu/Edmonds): tìm số nhánh cực tiểu hay cực đại
Cây bao nhỏ nhất Euclid: tìm cây bao nhỏ nhất của một tập hợp các điểm trên mặt phẳng
Đường đi ngắn nhất Euclidean: tìm đường đi ngắn nhất giữa hai điểm không đi qua chướng ngại vật
Bài toán đường đi dài nhất: tìm đường đi dài nhất trong một đồ thị
Cây bao nhỏ nhất
Bài toán đường đi ngắn nhất
- Thuật toán Bellman–Ford: tìm đường đi ngắn nhất trong một đồ thị có trọng số (trọng số cạnh có thể âm)
- Thuật toán Dijkstra: tìm đường đi ngắn nhất trong một đồ thị có trọng số cạnh không âm
- Thuật toán Floyd–Warshall: tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị trọng số có hướng
- Thuật toán Johnson: tìm đường ngắn nhất giữa tất cả cặp đỉnh trong một đồ thị trọng số có hướng thưa
Bài toán đóng bắc cầu: tìm đóng bắc cầu của một quan hệ hai ngôi
Bài toán người bán hàng
- Thuật toán Christofides
- Thuật toán láng giềng gần nhất
Quy tắc Warnsdorff: phương pháp heuristic để giải bài toán mã đi tuần.

Tìm kiếm đồ thị[sửa | sửa mã nguồn]

A*: trường hợp đặc biệt của tìm kiếm theo lựa chọn tốt nhất sử dụng heuristic để tăng tốc độ tìm kiếm
B*: một thuật toán tìm kiếm đồ thị theo lựa chọn tốt nhất, tìm đường đi từ một đỉnh đến đỉnh khác với chi phí thấp nhất
Quay lui: từ bỏ lời giải toàn phần khi chúng không thỏa mãn toàn bộ bài toán
Tìm kiếm beam: thuật toán tìm kiếm heuristic tối ưu hóa tìm kiếm theo lựa chọn tốt nhất, làm giảm yêu cầu bộ nhớ
Tìm kiếm beam stack search: kết hợp tìm kiếm beam với quay lui
Tìm kiếm theo lựa chọn tốt nhất: duyệt một đồ thị theo thứ tự quan trọng sử dụng một hàng đợi ưu tiên
Tìm kiếm hai hướng: tìm đường đi ngắn nhất từ một đỉnh đến đỉnh khác trong đồ thị có hướng
Tìm kiếm theo chiều rộng: duyệt đồ thị theo từng cấp độ
Tìm kiếm brute force: phương pháp tìm kiếm chính xác, nhưng không hiệu quả trong nhiều trường hợp
D*: thuật toán tìm kiếm heuristic gia tăng
Tìm kiếm theo chiều sâu: duyệt đồ thị từng nhánh một
Thuật toán Dijkstra: trường hợp đặc biệt của A* khi không có hàm heuristic nào được dùng
General Problem Solver: một thuật toán chứng minh định lý với mục đích giải những bài toán tổng quát
Tìm kiếm theo chiều sâu tăng dần (IDDFS): một chiến thuật tìm kiếm không gian trạng thái
Tìm kiếm điểm nhảy: một phiên bản tối ưu của A*
Tìm kiếm theo chiều rộng lexicographic (Lex-BFS): một thuật toán thời gian tuyến tính để sắp xếp các đỉnh của đồ thị
Tìm kiếm chi phí đều: thuật toán tìm kiếm cây tìm đường đi ngắn nhất
SSS*: tìm kiếm không gian trạng thái duyệt cây trò chơi theo lựa chọn tốt nhất giống A*

Đồ thị con[sửa | sửa mã nguồn]

Clique
- Thuật toán Bron–Kerbosch: tìm clique cực đại trong đồ thị vô hướng
- Thuật toán clique lớn nhất MaxCliqueDyn: tìm clique lớn nhất trong đồ thị vô hướng
Thành phần liên thông mạnh
Bài toán đồ thị con đẳng cấu

Thuật toán chuỗi[sửa | sửa mã nguồn]

Approximate sequence matching[sửa | sửa mã nguồn]

Thuật toán bitap: thuật toán mờ xác định nếu hai chuỗi (string) gần bằng nhau
Thuật toán ngữ âm
- Daitch–Mokotoff Soundex: một biến thể của Soundex dùng được cho họ tiếng Slav và tiếng Đức
- Double Metaphone: một phiên bản cải thiện của Metaphone
- Metaphone: thuật toán sắp xếp từ dựa vào phát âm trong tiếng Anh
- NYSIIS: một phiên bản cải thiện của Soundex
- Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English
String metric: tìm mức độ giống nhau hoặc khác nhau (khoảng cách) giữa hai strings
- Khoảng cách Damerau–Levenshtein: cải thiện khoảng cách Levenshtein
- Hệ số Dice: một đo lường giống nhau liên quan đến chỉ số Jaccard
- Khoảng cách Hamming: tổng số vị trí khác nhau
- Khoảng cách Jaro–Winkler: đo độ giống nhau giữa hai string
- Khoảng cách sửa đổi Levenshtein: đo sự khác nhau giữa hai string dựa trên số sửa đổi cần để biến string này thành string kia

Thuật toán chọn lựa[sửa | sửa mã nguồn]

Tìm kiếm chuỗi[sửa | sửa mã nguồn]

Tìm kiếm tuần tự: tìm một đối tượng trong một chuỗi không thứ tự
Thuật toán chọn lựa: tìm đối tượng lớn thứ k trong một chuỗi
Tìm kiếm bậc ba: tìm giá trị lớn nhất hoặc nhỏ nhất của một hàm đơn điệu chặt
Chuỗi đã sắp xếp
- Tìm kiếm nhị phân: tìm một đối tượng trong một chuỗi có thứ tự
- Tìm kiếm Fibonacci: dùng chia để trị nhằm giảm số vị trí khả dĩ sử dụng dãy Fibonacci
- Tìm kiếm nhảy (tìm kiếm khối): tìm kiếm tuần tự trên một phần của chuỗi
- Tìm kiếm nội suy (tìm kiếm từ điển): biến thể của tìm kiếm nhị phân sử dụng độ lớn của đối tượng cần tìm với giá trị lớn nhất và nhỏ nhất trong chuỗi
- Tìm kiếm nhị phân đều: một tối ưu của thuật toán tìm kiếm nhị phân cổ điển

Trộn chuỗi[sửa | sửa mã nguồn]

Thuật toán trộn đơn giản
Thuật toán trộn k chiều
Hợp (trộn sao cho các phần tử trong đầu ra là duy nhất)

Hoán vị chuỗi[sửa | sửa mã nguồn]

Xáo trộn Fisher–Yates (còn gọi là xáo trộn Knuth): xáo trộn ngẫu nhiên một tập hữu hạn
Thuật toán Schensted: thiết lập một cặp bảng Young từ một hoán vị
Thuật toán Steinhaus–Johnson–Trotter (còn gọi là thuật toán Johnson–Trotter): tạo ra hoán vị
Thuật toán sinh hoán vị của Heap: đổi chỗ các phần tử để tạo hoán vị tiếp theo

Tổ hợp chuỗi[sửa | sửa mã nguồn]

Bắt cặp trình tự[sửa | sửa mã nguồn]

Biến đổi thời gian động: đo sự giống nhau của hai chuỗi trình tự, có thể khác nhau về thời gian hay vận tốc
Thuật toán Hirschberg: tìm bắt cặp trình tự với chi phí nhỏ nhất giữa hai chuỗi trình tự, dựa trên khoảng cách Levenshtein
Thuật toán Needleman–Wunsch: tìm bắt cặp toàn bộ giữa hai chuỗi
Thuật toán Smith–Waterman: tìm bắt cặp cục bộ giữa hai chuỗi

Sắp xếp chuỗi[sửa | sửa mã nguồn]

Sắp xếp đổi chỗ
- Sắp xếp nổi bọt: với mỗi cặp phần tử, đổi chỗ nếu chúng không theo thứ tự
- Sắp xếp cocktail hay sắp xếp nổi bọt hai chiều, một sắp xếp nổi bọt đi lần lượt từ đầu về cuối và từ cuối lên đầu
- Sắp xếp lược
- Sắp xếp gnome
- Sắp xếp chẵn lẻ
- Sắp xếp nhanh: chia chuỗi thành hai phần, với các phần tử thuộc phần này lớn hơn các phần tử thuộc phần kia, rồi sắp xếp mỗi phần
Hài hước hoặc không hiệu quả
Lai
- Flashsort
- Introsort: bắt đầu với sắp xếp nhanh và chuyển sang sắp xếp vun đống khi độ sâu truy hồi vượt quá ngưỡng nhất định
- Timsort: thuật toán dựa trên sắp xếp trộn và sắp xếp chèn. Được dùng trong Python 2.3 trở lên và Java SE 7.
Sắp xếp chèn
- Sắp xếp chèn: xác định vị trí của phần tử hiện tại trong chuỗi đã sắp xếp và chèn nó vào vị trí đó
- Sắp xếp thư viện
- Shellsort: cải tiến sắp xếp chèn
- Sắp xếp cây (sắp xếp cây nhị phân): xây dựng và duyệt cây nhị phân để tạo ra chuỗi được sắp xếp
- Sắp xếp chu kỳ: sắp xếp tại chỗ với số lần viết lý thuyết tối ưu
Sắp xếp trộn
- Sắp xếp trộn: sắp xếp nửa đầu và nửa sau của chuỗi một cách riêng biệt, rồi trộn hai chuỗi
- Slowsort
- Sắp xếp sợi
Sắp xếp không so sánh
- Sắp xếp hạt đậu
- Sắp xếp xô
- Burstsort
- Sắp xếp đếm
- Sắp xếp chuồng bồ câu
- Sắp xếp người đưa thư: biến thể của sắp xếp xô sử dụng cấu trúc cấp bậc
- Sắp xếp theo cơ số: sắp xếp chuỗi từng chữ cái một
Sắp xếp chọn
- Sắp xếp vun đống: biến chuỗi thành một đống, bỏ phần tử lớn nhất khỏi đống và thêm vào cuối chuỗi
- Sắp xếp chọn: chọn phần tử nhỏ nhất trong chuỗi còn lại, thêm nó vào chuỗi đã sắp
- Smoothsort
Khác

Chuỗi con[sửa | sửa mã nguồn]

Thuật toán Kadane: tìm mảng con lớn nhất với kích thước bất kỳ
Bài toán chuỗi con chung dài nhất: tìm chuỗi con chung dài nhất của các chuỗi đã cho
Chuỗi con tăng dài nhất: tìm chuỗi con tăng dài nhất của một chuỗi đã cho
Bài toán chuỗi mẹ chung ngắn nhất: tìm chuỗi mẹ chung ngắn nhất chứa hai hoặc nhiều hơn các chuỗi cho trước

Xâu con[sửa | sửa mã nguồn]

Bài toán xâu con chung dài nhất: tìm xâu con dài nhất của hai hoặc nhiều hơn các xâu cho trước
Tìm xâu con
- Thuật toán Aho–Corasick: thuật toán dùng trie để tìm tất cả xâu con thuộc một tập hữu hạn các xâu
- Thuật toán tìm xâu Boyer–Moore: thuật toán tuyến tính để tìm xâu con
- Thuật toán Boyer–Moore–Horspool: đơn giản hóa Boyer–Moore
- Thuật toán Knuth–Morris–Pratt: tìm kiếm xâu con mà không cần kiểm tra lại những ký tự đã thỏa
- Thuật toán Rabin–Karp: tìm nhiều mẫu hình hiệu quả
- Thuật toán tìm xâu Zhu–Takaoka: một biến thể của Boyer–Moore
Thuật toán Ukkonen: một thuật toán trực tuyến, thời gian tuyến tính để xây dựng cây hậu tố
Đối sánh kí tự đại diện
- wildmat: một thuật toán đệ quy mã nguồn mở được sử dụng rộng rãi
- Thuật toán đối sánh kí tự đại diện Krauss: một thuật toán không đệ quy mã nguồn mở

Toán học tính toán[sửa | sửa mã nguồn]

Đại số trừu tượng[sửa | sửa mã nguồn]

Tìm kiếm Chien: một thuật toán đệ quy để xác định nghiệm của một đa thức trên một trường hữu hạn
Thuật toán Schreier–Sims: tính một cơ sở và tập sinh mạnh (BSGS) của một nhóm hoán vị
Thuật toán Todd–Coxeter: thuật toán tạo lớp kề (coset).

Đại số máy tính[sửa | sửa mã nguồn]

Thuật toán Buchberger: tìm một cơ sở Gröbner
Thuật toán Cantor–Zassenhaus: phân tích đa thức trên trường hữu hạn
Thuật toán Faugère F4: tìm một cơ sở Gröbner
Thuật toán Gosper: tìm tổng các số hạng siêu hình học mà bản thân chúng cũng là số hạng siêu hình học
Thuật toán hoàn thành Knuth–Bendix: thuật toán viết lại hệ thống quy luật
Thuật toán chia đa biến: dùng cho đa thức nhiều biến
Thuật toán kangaroo Pollard (còn gọi là thuật toán lambda Pollard): thuật toán để giải quyết bài toán lôgarit rời rạc
Phép chia đa thức lớn: thuật toán chia đa thức cho một đa thức khác có bậc bằng hoặc nhỏ hơn
Thuật toán Risch: thuật toán tìm tích phân bất định, tức nguyên hàm

Hình học[sửa | sửa mã nguồn]

Bài toán cặp điểm gần nhất: tìm hai điểm gần nhất từ các điểm cho trước
Thuật toán phát hiện va chạm: kiểm tra sự va chạm hay giao nhau của hai khối
Thuật toán hình nón: xác định các điểm trên bề mặt
Thuật toán bao lồi: xác định bao lồi của một tập các điểm
- Quét Graham
- Quickhull
- Thuật toán gói quà hay hành quân Jarvis
- Thuật toán Chan
- Thuật toán Kirkpatrick–Seidel
Biến đổi khoảng cách Euclid: tính khoảng cách giữa tất cả các điểm trong mạng lưới và một tập hợp các điểm.
Băm hình học: tìm vật thể hai chiều biểu diễn bởi các điểm rời rạc dưới một biến đổi afin
Thuật toán khoảng cách Gilbert–Johnson–Keerthi: tìm khoảng cách nhỏ nhất giữa hai hình lồi.
Thuật toán Jump-and-Walk: định vị điểm trong phép đạc tam giác
Làm mịn Laplace: thuật toán làm mịn một lưới đa giác
Giao điểm đường thẳng: xác định liệu hai đường thẳng cắt nhau, thường với một thuật toán đường quét
- Thuật toán Bentley–Ottmann
- Thuật toán Shamos–Hoey
Thuật toán hộp giới hạn tối thiểu: tìm hộp giới hạn tối thiểu có hướng chứa các điểm cho trước
Tìm kiếm hàng xóm gần nhất: tìm các điểm gần điểm cho trước nhất
Thuật toán điểm trong đa giác: kiểm tra xem liệu điểm cho trước có nằm trong một đa giác không
Thuật toán phối chuẩn tập điểm: tìm biến đổi giữa hai tập điểm để canh chuẩn chúng tốt nhất
Thước kẹp xoay: xác định tất cả những cặp điểm đối cực trên một đa giác lồi hay bao lồi.
Thuật toán dây giày: xác định diện tích của đa giác
Tam giác phân
- Tam giác phân Delaunay
  - Thuật toán Ruppert: tạo tam giác phân Delaunay chất lượng
  - Thuật toán Chew thứ hai: tạo tam giác phân Delaunay ràng buộc
- Thuật toán tam giác phân đa giác: chia một đa giác thành các tam giác nhỏ hơn
- Sơ đồ Voronoi, đối ngẫu hình học của tam giác phân Delaunay
  - Thuật toán Bowyer–Watson: tạo sơ đồ Voronoi với số chiều bất kỳ
  - Thuật toán Fortune: tạo sơ đồ Voronoi

Thuật toán lý thuyết số[sửa | sửa mã nguồn]

Thuật toán Stein (còn gọi là thuật toán GCD nhị phân): tính ước chung lớn nhất một cách hiệu quả
Phương pháp Chakravala: một thuật toán tuần hoàn để giải phương trình b6ạc hai không xác định, bao gồm phương trình Pell
Lôgarit rời rạc:
Thuật toán Euclid: tính ước số chung lớn nhất của hai số
Thuật toán Euclid mở rộng: giải phươgn trình $ax + by = c$
Phân tích số nguyên: phân tích một số nguyên thành tích các ước nguyên tố
Thuật toán nhân: nhân hai số với nhau
- Thuật toán nhân Booth: thuật toán nhân hai số nhị phân trong ký hiệu bù hai
- Thuật toán Fürer: thuật toán nhân số lớn với độ phức tạp thấp
- Thuật toán Karatsuba
- Thuật toán Schönhage–Strassen
- Toom–Cook multiplication (Toom3)
Thặng dư bình phương: tính căn bậc hai modulo một số nguyên tố
Thuật toán Odlyzko–Schönhage: tính giá trị của hàm zeta Riemann
Thuật toán Lenstra–Lenstra–Lovász (còn gọi là thuật toán LLL): tìm một cơ sở lưới ngắn và gần vuông góc trong thời gian đa thức
Kiểm tra tính nguyên tố: kiểm tra xem một số có phải số nguyên tố

Thuật toán số[sửa | sửa mã nguồn]

Giải phương trình vi phân[sửa | sửa mã nguồn]

Phương pháp Euler
Phương pháp Euler đảo
Quy tắc hình thang (phương trình vi phân)
Phương pháp đa bước tuyến tính
Phương pháp Runge–Kutta
Phương pháp đa lưới (phương pháp MG): một nhóm các thuật toán giải phương trình vi phân sử dụng hệ thống rời rạc hóa
Phương trình vi phân riêng phần:
- Phương pháp hiệu hữu hạn
- Phương pháp Crank–Nicolson cho phương trình khuếch tán
- Phương pháp Lax–Wendroff cho phương trình sóng for wave equations
Tích phân Verlet: lấy tích phân một phương trình chuyển động Newton

Hàm sơ cấp và đặc biệt[sửa | sửa mã nguồn]

Tính π:
- Thuật toán Borwein: tính giá trị của 1/π
- Thuật toán Gauss–Legendre: tìm các chữ số của π
- Thuật toán Chudnovsky: tính các chữ số của π
- Công thức Bailey–Borwein–Plouffe (công thức BBP): một thuật toán nhỏ giọt để tính chữ số nhị phân thứ n của π
Thuật toán chia: tính thương và/hoặc số dự khi chia hai số
- Phép chia số lớn
- Phép chia hồi phục
- Phép chia không hồi phục
- Phép chia SRT
- Phép chia Newton–Raphson: dùng phương pháp Newton để tìm nghịch đảo của D, và nhân nghịch đảo đó với N để tìm thương số Q
- Phép chia Goldschmidt
Hàm lượng giác và hyperbolic:
- Thuật toán BKM: tính hàm sơ cấp sử dụng bảng lôgarit
- CORDIC: tính giá trị của hàm lượng giác và hyperbolic sử dụng bảng arctan
Lũy thừa:
- Lũy thừa chuỗi cộng: lũy thừa số mũ nguyên dương với số phép nhân tối thiểu
- Thuật toán bình phương và nhân: tính lũy thừa số mũ lớn của một số nhanh chóng
Phép nhân mô-đun Montgomery: thuật toán thực hiện số học môđun hiệu quả khi cơ số lớn
Thuật toán nghịc đảo phép nhân: tính nghịch đảo phép nhân của một số
- Phương pháp Newton
Làm tròn: làm tròn số
Thuật toán nhỏ giọt: tính giá trị của một hằng số toán học mà không cần biết những chữ số trước đó
Căn bậc hai và căn bậc n của một số
- Thuật toán alpha max cộng beta min: xấp xỉ căn bậc hai của tổng hai bình phương
- Phương pháp tính căn bậc hai
- Căn bậc n
- Thuật toán dịch căn bậc n: tính từng chữ số
Lấy tổng:
- Tách nhị phân: một phương pháp chia để trị giúp tăng tốc việc tính toán nhiều chuỗi với hệ số hữu tỉ
- Thuật toán tổng Kahan: phương pháp lấy tổng số dấu phẩy động chính xác