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
- Phân tích liên kết
- 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
- 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
- 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 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
- Tam giác phân Delaunay
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ố
- 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
Hình học[sửa | sửa mã nguồn]
- Phương pháp tập mức (LSM): một phương pháp theo dõi bề mặt và vật thể
Nội suy và ngoại suy[sửa | sửa mã nguồn]
- Nội suy Birkhoff: một mở rộng của nội suy đa thức
- Nội suy bậc ba
- Nội suy Hermite
- Nội suy Lagrange: nội suy bằng đa thức Lagrange
- Nội suy tuyến tính: phương pháp hợp chỉnh đường cong bằng đa thức tuyến tính
- Nội suy bậc ba đơn điệu: biến thể của nội suy bảo toàn tính đơn điệu của tập dữ liệu
- Nội suy đa biến
- Nội suy nhị bậc ba: tổng quát của nội suy bậc ba cho hai chiều
- Nội suy song tuyến tính: mở rộng của nội suy tuyến tính cho hai biến trên mặt phẳng
- Lọc Lanczos ("Lanzosh"): phương pháp nội suy nhiều biến cho tập dữ liệu kỹ thuật số
- Nội suy hàng xóm gần nhất
- Nội suy tam bậc ba: mở rộng của nội suy bậc ba cho ba chiều
- Nội suy Pareto: phương pháp xấp xỉ trung vị và những tính chất khác của tập dữ liệu theo phân bố Pareto
- Nội suy đa thức
- Nội suy spline: giảm sai số do hiện tượng Runge.
- Nội suy lượng giác
Đại số tuyến tính[sửa | sửa mã nguồn]
- Thuật toán giá trị riêng
- Quá trình Gram–Schmidt: trực chuẩn hóa các vectơ
- Thuật toán nhân đa thức
- Thuật toán Cannon: một thuật toán phân tán để nhân đa thức phù hợp với máy tính trong mạng lưới N × N
- Thuật toán Coppersmith–Winograd: nhân đa thức vuông
- Thuật toán Freivalds: thuật toán ngẫu nhiên để kiểm tra kết quả nhân đa thức
- Thuật toán Strassen: nhân đa thức nhanh
- Giải hệ phương trình tuyến tính
- Phương pháp gradient song liên hợp
- Phương pháp gradient liên hợp: thuật toán giải một dạng hệ phương trình tuyến tính
- Phép khử Gauss
- Phép khử Gauss–Jordan
- Phương pháp Gauss–Seidel: giải hệ phương trình tuyến tính từng bước
- Đệ quy Levinson: giải hệ phương trình bằng ma trận Toeplitz
- Phương pháp Stone (SIP): giải hệ tuyến tính thưa
- Over-relaxation liên tục (SOR): tăng tốc độ hội tụ của phương pháp Gauss–Seidel
- Thuật toán ma trận ba đường chéo (thuật toán Thomas): giải hệ phương trình ba đường chéo
- Thuật toán ma trận thưa
- Thuật toán Cuthill–McKee: giảm băng thông của một ma trận thưa đối xứng
- Thuật toán bậc tối thiểu: hoán đổi các hàng và cột của một ma trận thưa đối xứng trước khi phân hủy Cholesky
- Phân hủy Cholesky ký hiệu: lưu trữ ma trận thưa hiệu quả
Monte Carlo[sửa | sửa mã nguồn]
- Lấy mẫu Gibbs: tạo một chuỗi mẫu từ phân bố xác suất chung của hai hoặc nhiều biến ngẫu nhiên
- Monte Carlo Hamilton: tạo một chuỗi mẫu dùng Monte Carlo chuỗi Markov trọng số Hamiltonian
- Thuật toán Metropolis–Hastings: tạo một chuỗi mẫu từ phân bố xác suất của một hoặc nhiều biến
- Thuật toán Wang và Landau: mở rộng của thuật toán Metropolis–Hastings
Tích phân số[sửa | sửa mã nguồn]
- Tích phân Monte Carlo (thuật toán MISER)
Tìm nghiệm[sửa | sửa mã nguồn]
- Phương pháp chia đôi
- Regula falsi: xấp xỉ nghiệm của hàm số
- Phương pháp ITP: thuật toán tìm nghiệm nhanh hơn phương pháp chia đôi
- Phương pháp Newton: tìm nghiệm bằng đạo hàm
- Phương pháp Halley: dùng đạo hàm bậc một và hai
- Phương pháp giao tuyến: 2 điểm, 1 bên
- Phương pháp Ridder: 3 điểm, nhân hàm mũ
- Phương pháp Muller: 3 điểm, nội suy bậc hai
Thuật toán tối ưu hóa[sửa | sửa mã nguồn]
- Cắt tỉa alpha–beta: tìm kiếm để giảm số đỉnh trong thuật toán minimax
- Branch và bound
- Thuật toán Bruss
- Phép nhân chuỗi ma trận
- Tối ưu hóa tổ hợp: những bài toán tối ưu hóa với tập kết quả là rời rạc
- GRASP: xây dựng liên tục một lời giải ngẫu nhiên tham lam và cải thiện nó bằng tìm kiếm địa phương
- Phương pháp Hungary: giải quyết bài toán phân công trong thời gian đa thức
- Thỏa mãn ràng buộc
- Các thuật toán chung cho thỏa mãn ràng buộc
- Thuật toán Chaff: thuật toán để giải bài toán tính thỏa được Bool
- Thuật toán Davis–Putnam: kiểm tra sự hợp lệ của công thức logic bậc nhất
- Thuật toán Davis–Putnam–Logemann–Loveland (DPLL): quyết định tính thỏa được của công thức logic mệnh đề dưới dạng chuẩn liên kết, ví dụ như bài toán CNF-SAT
- Bài toán phủ chính xác
- Thuật toán X: một thuật toán bất định
- Dancing Links: một triển khai hiệu quả cho thuật toán X
- Phương pháp cross-entropy: một phương pháp Monte Carlo tổng quát cho tối ưu rời rạc và liên tục đa cực
- Tiến hóa vi phân
- Quy hoạch động: những bài toán có tính chất bài toán con trùng nhau và cấu trúc con tối ưu
- Phương pháp ellipsoid: is an algorithm for solving convex optimization problems
- Thuật toán tiến hóa: tối ưu hóa phỏng theo cơ chế sinh học của tiến hóa
- Chiến lược tiến hóa
- Lập trình biểu hiện gen
- Thuật toán di truyền
- Chọn lọc tỉ lệ thể chất – also known as roulette-wheel selection
- Lấy mẫu phổ ngẫu nhiên
- Chọn lọc giải đấu
- Thuật toán memetic
- Trí tuệ bầy đàn
- Tối ưu đàn kiến
- Thuật toán ong: thuật toán tìm kiếm bắt chước hành vi kiếm ăn của đàn ong
- Tối ưu bầy đàn
- Tìm kiếm lát vàng: thuật toán tìm cực trị của một hàm số thực
- Suy giảm độ dốc
- Tối ưu hóa siêu tham số
- Phương pháp điểm trong
- Quy hoạch tuyến tính
- Thuật toán Benson: giải quyết các bài toán tối ưu vectơ tuyến tính
- Phân tích Dantzig–Wolfe
- Tạo cột
- Quy hoạch số nguyên
- Thuật toán Karmarkar: thuật toán hiệu quả đầu tiên giải quyết quy hoạch tuyến tính trong thời gian đa thức.
- Thuật toán simplex
- Tìm kiếm đường thẳng
- Tìm kiếm địa phương
- Tìm kiếm hàng xóm gần nhất (NNS): tìm những điểm gần nhất trong không gian metric
- Best Bin First: tìm đáp án xấp xỉ cho bài toán tìm kiếm hàng xóm gần nhất trong không gian rất nhiều chiều
- Phương pháp Newton trong tối ưu hóa
- Quy hoạch phi tuyến tính
- Phương pháp BFGS: một thuật toán tối ưu hóa phi tuyến tính
- Thuật toán Gauss–Newton: giải các bài toán bình phương tối thiểu phi tuyến tính
- Thuật toán Levenberg–Marquardt: giải các bài toán bình phương tối thiểu phi tuyến tính
- Phương pháp Nelder–Mead (phương pháp hạ dốc simplex): thuật toán tối ưu hóa phi tuyến tính
- Thuật toán odds (thuật toán Bruss): tìm phương án tối ưu để dự đoán một sự kiện trong một chuỗi các sự kiện ngẫu nhiên
- Simulated annealing
- Chui hầm ngẫu nhiên
- Thuật toán tổng tập con
Xem thêm[sửa | sửa mã nguồn]
- Danh sách cấu trúc dữ liệu
- Danh sách thuật toán học máy
- Danh sách các thuật ngữ liên quan đến cấu trúc dữ liệu và giải thuật
- Heuristic