Algoritma, prosedur sistematik yang menghasilkan - dalam jumlah langkah yang terbatas - jawapan kepada soalan atau penyelesaian masalah. Nama itu berasal dari terjemahan Latin, Algoritmi de numero Indorum, dari risalah aritmetik al-Khwarizmi ahli matematik Muslim abad ke-9 "Al-Khwarizmi Mengenai Seni Memperhitungkan Hindu."
sains komputer: Algoritma dan kerumitan
Algoritma adalah prosedur khusus untuk menyelesaikan masalah komputasi yang ditentukan dengan baik. Pembangunan dan analisis algoritma adalah asas
Untuk pertanyaan atau masalah dengan hanya set kes atau nilai yang terbatas, algoritma selalu ada (sekurang-kurangnya pada prinsipnya); ia terdiri daripada jadual nilai jawapan. Secara umum, bukan prosedur sepele untuk menjawab soalan atau masalah yang mempunyai banyak kes atau nilai yang perlu dipertimbangkan, seperti "Apakah nombor semula jadi (1, 2, 3,…) Adalah yang utama?" atau "Apakah pembahagi umum terbesar bagi nombor semula jadi a dan b?" Soalan pertama ini termasuk dalam kelas yang disebut decidable; algoritma yang menghasilkan jawapan ya atau tidak disebut prosedur keputusan. Soalan kedua tergolong dalam kelas yang disebut komputasi; algoritma yang membawa kepada jawapan nombor tertentu disebut prosedur pengiraan.
Algoritma wujud untuk sebilangan besar kelas soalan yang tidak terhingga; Euclid's Elements, diterbitkan sekitar 300 bc, berisi satu untuk mencari pembahagi umum yang paling besar dari dua nombor semula jadi. Setiap pelajar sekolah rendah dibahagikan dalam pembahagian panjang, yang merupakan algoritma untuk soalan "Apabila membahagi nombor semula jadi dengan nombor semula jadi b, apakah hasil tambah dan selebihnya?" Penggunaan prosedur pengiraan ini membawa kepada jawapan kepada soalan yang dapat diputuskan "Adakah b membahagi a?" (jawapannya adalah ya jika selebihnya adalah sifar). Aplikasi berulang algoritma ini akhirnya menghasilkan jawapan kepada soalan yang dapat diputuskan "Adakah perdana?" (jawapannya adalah tidak jika a dibahagi dengan nombor semula jadi yang lebih kecil selain 1).
Kadang kala algoritma tidak dapat wujud untuk menyelesaikan masalah yang tidak terhingga, terutama apabila ada sekatan selanjutnya berdasarkan kaedah yang diterima. Sebagai contoh, dua masalah dari zaman Euclid yang memerlukan penggunaan hanya kompas dan garis lurus (pembaris tanpa tanda) —memperoleh sudut dan membina sebuah persegi dengan kawasan yang sama dengan lingkaran tertentu — ditangani selama berabad-abad sebelum terbukti tidak mungkin. Pada pergantian abad ke-20, ahli matematik Jerman yang berpengaruh David Hilbert mencadangkan 23 masalah untuk diselesaikan oleh ahli matematik pada abad yang akan datang. Masalah kedua dalam senarainya meminta penyelidikan mengenai konsistensi aksioma aritmetik. Sebilangan besar ahli matematik tidak mempunyai keraguan tentang pencapaian matlamat ini sehingga 1931, ketika ahli logik kelahiran Kurt Gödel menunjukkan hasil yang mengejutkan bahawa mesti ada cadangan aritmetik (atau soalan) yang tidak dapat dibuktikan atau dibantah. Pada dasarnya, apa-apa cadangan itu membawa kepada prosedur penentuan yang tidak pernah berakhir (keadaan yang dikenali sebagai masalah berhenti). Dalam usaha yang tidak berjaya untuk memastikan sekurang-kurangnya cadangan mana yang tidak dapat diselesaikan, ahli matematik dan logik Inggeris Alan Turing dengan tegas mendefinisikan konsep algoritma yang difahami secara longgar. Walaupun Turing akhirnya membuktikan bahawa mesti ada proposisi yang tidak dapat diputuskan, penerangannya mengenai ciri-ciri penting dari mana-mana mesin algoritma tujuan umum, atau mesin Turing, menjadi asas sains komputer. Hari ini, masalah kebolehtentuan dan kebolehkomputeran menjadi teras kepada reka bentuk program komputer - jenis algoritma khas.
