Algoritme
Algoritme pengacakan Algoritme ini membuat pilihan secara acak (atau pseudo-acak). Ia sangat berguna untuk menemukan solusi perkiraan untuk masalah dimana solusi yang pasti tidak praktis (lihat metode heuristik di bawah). Untuk beberapa masalah, diketahui bahwa perkiraan tercepat harus mengikutkan beberapa pengacakan. Apakah algoritme pengacakan dengan kompleksitas waktu polinomial bisa menjadi
algoritme tercepat untuk beberapa masalah masih menjadi pertanyaan terbukan yang dikenal sebagai Masalah P versus NP. Ada dua kelas besar dari algoritme ini:
Algoritme Monte Carlo mengembalikan jawaban yang benar dengan probabilitas-tinggi. Misalnya, RP adalah sub-klas dari algoritme ini yang berjalan dalam waktu polinomial) Algoritme Las Vegas selalu mengembalikan jawaban yang benar, tetapi waktu prosesnya adalah hanya terikat secara probabilistik, misalnya ZPP.
Reduksi Teknik ini menyelesaikan masalah sulit dengan mengubahnya menjadi permasalahan yang lebih diketahui yang mana kita (berharap) memiliki algoritme asimptotikal optimal. Tujuannya yaitu untuk menemukan sebuah algoritme reduksi yang kompleksitasnya tidak didominasi oleh algoritme hasil reduksi. Sebagai contoh, algoritme seleksi untuk menemukan rata-rata dalam daftar
tak terurut mengikutkan mengurutkan daftar (bagian yang paling mahal) dan menarik elemen paling tengah dalam daftar terurut (bagian yang paling mudah). Teknik ini juga diketahui dengan ubah dan taklukan.
Pemrograman Linear Saat mencari solusi optimal terhadap sebuah fungsi linear yang terikat persamaan linear dan ketidaksamaan konstrain, batasan dari permasalahan bisa digunakan secara langsung untuk menghasilkan solusi optimal. Ada algoritme yang dapat memecahkan setiap permasalahan dalam kategori ini, seperti algoritme simpleks yang terkenal. Permasalahan yang dapat diselesaikan dengan pemrograman linear termasuk permasalahan
alur maksimum untuk grafik terarah). Jika sebuah masalah sebagai tambahan membutuhkan satu atau lebih jawaban haruslah integer maka ia diklasifikan dalam pemrograman integer. Algoritme pemrograman linear dapat menyelesaikan masalah seperti itu jika dapat dibuktikan bahwa semua batasan untuk nilai integer adalah tidak benar, yaitu solusi memenuhi batasan tersebut. Pada
kasus umum, algoritme yang dikhususkan atau algoritme yang menemukan solusi perkiraan digunakan, bergantung pada kesulitan dari permasalahan.
Pemrograman dinamis Bila sebuah masalah memperlihatkan substruktur optimal, artinya solusi optimal terhadap sebuah masalah bisa direkonstruksi dari solusi optimal ke sub-masalah, dan submasalah tumpang-tindih, artinya sub-masalah yang sama digunakan untuk menyelesaikan banyak instasi masalah berbeda, pendekatan tercepat disebut pemrograman dinamis menghindari penghitungan solusi yang telah dikomputasi.
Sebagai contoh, algoritme Floyd-Warshall, jalan terpendek ke tujuan dari sebuah vertex dalam grafik berbobot bisa ditemukan dengan menggunakan jalan terpendek ke tujuan dari semua simpul yang berdekatan. Pemrograman dinamis dan memoisasi berpadanan. Perbedaan utama antara pemrograman dinamis dan bagi-dan-taklukan adalah submasalah kurang lebih independen dalam
bagi-dan-taklukan, sementara submasalah tumpang tindik dalam pemrograman dinamis. Perbedaaan antara pemrograman dinamis dan rekursi langsung adalah dalam 'caching' atau memoisasi dari pemanggialan rekursif. Saat submasalah independen dan tidak ada pengulangan, memoisasi tidak membantu sama sekali; makanya pemrograman dinamis bukalanh solusi untuk semua permasalahan
kompleks. Dengan menggunakan memoisasi atau tabel dari submasalah yang telah diselesaikan, pemrograman dinamis mereduksi eksponensial dari banyak permasalahan menjadi kompleksitas polinomial.
Metode rakus Sebuah algoritme rakus mirip dengan algoritme pemrograman dinamis, tetapi perbedaannya adalah solusi dari submasalah tidak harus diketahui pada setiap tahap; melainkan pilihan yang "rakus" bisa dibuat dengan melihat apa yang terbaik untuk saat tersebut. Metode rakus mengembangkan solusi dengan kemungkinan keputusan yang terbaik (bukan dengan keputusan yang
ada) pada tahap algoritmis berdasarkan optimasi lokal yang ada sekarang dan keputusan yang terbaik (bukan semua kemungkinan keputusan) yang dibuat pada langkah sebelumnya. Algoritme ini tidak terlalu mendalam, dan tidak memberikan jawaban yang akurat terhadap banyak permasalahan. Tapi bila ia bekerja, ia menjadi metode yang paling cepat. Algoritme rakus paling terkenal adalah menemukan rentang pohon minimal seperti pada Pohon Huffman, Kruskal, Prim, Sollin.
Metode heuristik Dalam masalah optimisasi, algoritme heuristik bisa digunakan untuk menemukan suatu solusi yang terdekat dengan solusi optimal jika seandainya menemukan solusi optimal tidak praktis. Algoritme ini bekerja dengan mendekati sedikit demi sedikit ke solusi optimal saat ia berjalan. Secara prinsipnya, jika dijalankan tanpa batas waktu, ia akan menemukan solusi optimal. Kebaikan mereka
adalah mereka dapat menemukan suatu solusi sangat dekat dengan solusi optimal dalam waktu yang relatif sangat pendek. Algoritme tersebut termasuk pencarian lokal, pencarian tabu, simulasi pelunakan, dan algoritme genetik. Beberapa dari mereka, seperti simuasi pelunakan, adalah algoritme non-deterministik sementara yang lainnya, seperti pencarian tabu, adalah deterministik. Saat batas dari galat dari solusi non-optimal diketahui, algoritme kemudia dikategorikan sebagai algoritme pendekatan.
Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan algoritme yang efisien. Masalah yang berkaitan di satu bidang terkadang dipelajari bersama. Beberapa contoh yaitu algoritme pencarian, algoritme penggabungan, algoritme numerik, algoritme grafik, algoritme deret, algoritme komputasi geometri, algoritme kombinatorial, algoritmas medis, mesin belajar, kriptografi, algoritme kompresi data dan teknik penguraian.
Terkadang bidang-bidang tersebut saling tumpang tindih, dan perkembangan algoritme di satu bidang bisa meningkatkan bidang lainnya yang terkadang tidak berkaitan. Sebagai contohnya, pemrograman dinamis ditemukan untuk optimisasi konsumsi sumber daya dalam industri, tetapi sekarang digunakan untuk menyelesaikan sejumlah besar permasalahan dalam banyak bidang.
Algoritme bisa diklasifikasikan berdasarkan jumlah waktu yang dibutuhkan untuk selesai dibandingkan dengan ukuran inputnya. Ada berbagai varietas: beberapa algoritme selesai dalam waktu linear relatif terhadap ukuran input, beberapa selesai dalam jumlah waktu yang eksponensial atau lebih buruh, dan beberapa berhenti. Sebagai tambahan, beberapa masalah bisa memiliki berbagai
algoritme dengan kompleksitas yang berbeda, sementara permasalahan yang lain bisa saja tidak memiliki algoritme atau tidak diketahui algoritmanya yang efisien. Ada juga pemetaan dari beberapa algoritme terhadap permasalahan lain. Karena itu, lebih cocok untuk mengklasifikasikan permasalahan itu sendiri bukannya algoritme menjadi kelas-kelas yang sama berdasarkan kompleksitas dari kemungkinan algoritme terbaik baginya.
Burgin (2005, p.24) menggunakan definisi algoritme secara umum yang melonggarkan kebutuhan bersama yang keluaran dari algoritme yang menjalankan sebuah fungsi harus ditentukan setelah sejumlah langkah. Dia mendefinisikan kelas super-rekursif dari algoritme sebagai "sebuah kelas algoritme yang mana memungkinkan untuk menghitung fungsi yang tidak bisa dihitung oleh mesin Turing manapun" (Burgin 2005, p.107). Hal ini berkaitan dekat dengan kajian dari metode hiperkomputasi.
Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam masyarakat, seseorang bisa mengklasifikasikan algoritme berdasarkan tipe dari evaluasi yang mereka lakukan. Sejumlah filsuf telah berhipotesis bahwa masyarakat diuntungkan dari keragaman evaluatif seperti mereka diuntungkan keragaman jender dan tipe darah (misalnya, Dean 2012, Sober dan Wilson 1998) Hertzke dan McConkey 1998, dan