Algoritma, prosedur sistematis yang menghasilkan — dalam sejumlah langkah terbatas — jawaban atas pertanyaan atau solusi dari suatu masalah. Nama ini berasal dari terjemahan Latin, Algoritmi de numero Indorum, dari matematikawan Muslim abad ke-9 al-Khwarizmi, risalah aritmatika "Al-Khwarizmi Mengenai Seni Reckoning Hindu."
ilmu komputer: Algoritma dan kompleksitas
Algoritma adalah prosedur khusus untuk memecahkan masalah komputasi yang terdefinisi dengan baik. Pengembangan dan analisis algoritma sangat mendasar
Untuk pertanyaan atau masalah dengan hanya sejumlah kasus atau nilai yang terbatas, algoritma selalu ada (setidaknya pada prinsipnya); itu terdiri dari tabel nilai-nilai jawaban. Secara umum, ini bukan prosedur sepele untuk menjawab pertanyaan atau masalah yang memiliki jumlah kasus atau nilai tak terbatas untuk dipertimbangkan, seperti "Apakah bilangan asli (1, 2, 3, …) prima?" atau "Apa pembagi umum terbesar dari bilangan asli a dan b?" Pertanyaan pertama adalah milik kelas yang disebut decidable; suatu algoritma yang menghasilkan jawaban ya atau tidak disebut prosedur keputusan. Pertanyaan kedua milik kelas yang disebut computable; suatu algoritma yang mengarah ke jawaban nomor tertentu disebut prosedur perhitungan.
Algoritma ada untuk banyak kelas pertanyaan yang tak terbatas; Elemen Euclid, diterbitkan sekitar 300 SM, berisi satu untuk menemukan pembagi umum terbesar dari dua bilangan alami. Setiap siswa sekolah dasar dibor dalam pembagian panjang, yang merupakan algoritma untuk pertanyaan "Setelah membagi bilangan alami a dengan bilangan alami lainnya b, apa hasil bagi dan sisanya?" Penggunaan prosedur komputasi ini mengarah pada jawaban untuk pertanyaan yang dapat diputuskan, “Apakah b membagi a?” (jawabannya adalah ya jika sisanya nol). Penerapan berulang algoritma ini pada akhirnya menghasilkan jawaban untuk pertanyaan yang dapat diputuskan, “Apakah yang utama?” (jawabannya adalah tidak jika a dapat dibagi dengan angka natural yang lebih kecil selain 1).
Kadang-kadang algoritma tidak bisa ada untuk memecahkan kelas masalah yang tak terbatas, terutama ketika beberapa pembatasan lebih lanjut dilakukan pada metode yang diterima. Sebagai contoh, dua masalah dari zaman Euclid yang hanya membutuhkan penggunaan kompas dan penggaris-sejajar (penggaris tanpa tanda) —memandang sudut dan membangun sebuah bujur sangkar dengan luas yang sama dengan lingkaran tertentu — dikejar selama berabad-abad sebelum mereka terbukti mustahil.. Pada pergantian abad ke-20, matematikawan Jerman berpengaruh David Hilbert mengusulkan 23 masalah untuk matematikawan untuk dipecahkan di abad mendatang. Masalah kedua dalam daftar meminta penyelidikan konsistensi aksioma aritmatika. Sebagian besar matematikawan memiliki sedikit keraguan tentang pencapaian akhir dari tujuan ini sampai tahun 1931, ketika ahli logika kelahiran Austria Kurt Gödel menunjukkan hasil yang mengejutkan bahwa harus ada proposisi aritmatika (atau pertanyaan) yang tidak dapat dibuktikan atau dibantah. Pada dasarnya, setiap proposisi seperti itu mengarah pada prosedur penentuan yang tidak pernah berakhir (suatu kondisi yang dikenal sebagai masalah penghentian). Dalam upaya yang gagal untuk memastikan setidaknya proposisi mana yang tidak dapat diselesaikan, matematikawan dan ahli logika bahasa Inggris Alan Turing mendefinisikan dengan cermat konsep algoritma yang dipahami secara longgar. Meskipun Turing akhirnya membuktikan bahwa harus ada proposisi yang tidak dapat diputuskan, uraiannya tentang fitur penting dari setiap mesin algoritma tujuan umum, atau mesin Turing, menjadi dasar dari ilmu komputer. Saat ini masalah decidability dan computability sangat penting dalam desain program komputer — jenis algoritma khusus.
