|
kuantitas]] yang diberikan padanya sejak awal sebelum algoritma dijalankan"
(Knuth 1973:5).
</ref>
[[File:Euclid's algorithm Inelegant program 1.png|thumb|right|"Inelegan" adalah terjemahan dari versi Knuth terhadap algoritma berdasarkan pengulangan-sisa mengganti pembagian (atau instruksi "modulus").
Diambil dari Knuth 1973:2-4.
Bergantung pada kedua angka "Inelegan" bisa menghitung f.p.k dengan sedikit langkah daripada "elegan".]]
Algoritma berikut disebut sebagai versi Euclid dan Nichomachus 4-langkah-nya Knuth, tapi bukannya menggunakan pembagi untuk menentukan sisa ia menggunakan pengurangan berturut-turut dari panjang terkecil ''s'' dari sisa panjang ''r'' sampai ''r'' kurang dari ''s''.
Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:
'''INPUT''':
: 1 [Kedalam dua lokasi L dan S taruh angka ''l'' dan ''s'' yang merepresentasikan kedua panjang]: INPUT L, S
: 2 [Inisialisasi R: buat supaya sisa panjang ''r'' sama dengan panjang awal ''l''] R ← L
'''E0: [Pastikan ''r'' ≥ ''s''.]'''
: 3 [Pastikan angka terkecil dari kedua angka ada dalam S dan yang terbesar di R]: IF R > S THEN isi dari L adalah angka terbesar jadi lewati langkah 4, 5 dan 6: GOTO step 6 ELSE tukar isi R dan S.
: 4 L ← R (langkah pertama ini berlebih, tapi berguna untuk diskusi nanti).
: 5 R ← S
: 6 S ← L
''' E1: [Cari sisa]''': Sampai sisa panjang ''r'' di R kurang dari panjang terkecil ''s'' pada S, kurangi angka ''s'' dalam S berulang kali dari sisa panjang ''r'' dalam R.
: 7 IF S > R THEN selesai mengukur jadi GOTO 10 ELSE ukur lagi,
: 8 R ← R - S
: 9 [Pengulangan-sisa]: GOTO 7.
'''E2: [Apakah sisa 0?]''': APAKAH (i) pengukuran terakhir adalah sama dan sisa di R adalah 0 program dapat berhenti, ATAU (ii) algoritma harus terus jalan: hasil pengukuran meninggalkan sisa di R kurang dari angka pengukuran dalam S.
: 10 IF R = 0 maka selesai jadi GOTO langkah 15 ELSE lanjut ke langkah 11.
'''E3: [Interchange ''s'' dan ''r'']''': Sulitnya algoritma Euclid. Menggunakan sisa ''r'' untuk mengukur angka terkecil sebelumnya ''s'':; L sebagai lokasi sementara.
: 11 L ← S
: 12 R ← S
: 13 S ← L
: 14 [Ulang proses pengukuran]: GOTO 7
'''OUTPUT''':
: 15 [Selesai. S berisi faktor persekutuan terbesar]: PRINT S
'''DONE''':
: 16 HALT, END, STOP.
==== Program elegan untuk algoritma Euclid ====
Versi algoritma Euclid berikut hanya membutuhkan 6 instruksi inti untuk melakukan 13 langkah pada solusi "inelegan"; parahnya, "inelegan" membutuhkan ''tipe'' instruksi lebih banyak.
Diagram alur dari "elegan" bisa dilihat pada bagian atas artikel ini.
Dalam bahasa Basic (tak terstruktur) langkahnya diberi nomor, dan instruksi LET [] = [] adalah instruksi penetapan disimbolkan dengan ←.
<pre>
5 REM Algortima Euclid untuk faktor persekuturan terbesar
6 PRINT "Masukan dua integer besar dari 0"
10 INPUT A,B
20 IF B=0 THEN GOTO 80
30 IF A > B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 PRINT A
90 END
</pre>
'''Bagaimana cara kerja "Elegan"''': Sebagai pengganti "pengulangan Euclid" luar, "Elegan" mengulang antara dua pengulangan, pengulangan A > B yang menghitung A ← A - B, dan pengualang B ≤ A yang menghitung B ← B - A.
Ini bekerja karena, saat yang dikurang M lebih kecil pengurang S ( Selisih = pengurang - yang_di_kurang ), dikurang bisa menjadi ''s'' (panjang pengukuran yang baru) dan pengurang bisa menjadi ''r'' yang baru (panjang yang akan diukur);
dengan kata lain "arti" dari pengurangan dibalik.
=== Menguji algoritma Euclid ===
Apakah algoritma berjalan seperti yang penulis inginkan?
Beberapa kasus uji cukup menentukan fungsi inti.
Sumber pertama
<ref>{{cite web
|url=http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html
|title=Euclid's Elements, Book VII, Proposition 2
|publisher=Aleph0.clarku.edu
|date=
|accessdate=May 20, 2012
}}</ref>
menggunakan 3009 dan 884.
Knuth menyarankan 40902, 24140.
Kasus menarik lainnya yaitu dua angka [[relatif prima]] 14157 dan 5950.
Tapi kasus pengecualian harus teridentifikasi dan diuji.
Apakah "inelegan" berjalan benar saat R > S, S > R, R = S?
Sama juga dengan "Elegan": B > A, A > B, A = B?
(Semuanya benar).
Apa yang terjadi bila salah satu bilangan nol, atau keduanya nol?
("Inelegan" terus berjalan pada kedua kasus; "elegan" terus berjalan saat A = 0.)
Apa yang terjadi bila angka ''negatif'' dimasukan?
Angka desimal?
Bila angka masukan, misalnya [[domain (matematika)|domain]] dari fungsi yang dihitung oleh algoritma/prgoram, mengikutkan hanya integer positif termasuk 0, maka kegagalan pada nol mengindikasikan bahwa algoritma (dan program [[instansi (ilmu komputer)|instansiasi]]nya) adalah sebuah [[fungsi parsial]] bukannya [[fungsi total]].
Kegagalan yang terkenal karena istimewa adalah kegagalan roket [[Ariane V]].
'''Bukti dari kebenaran program menggunakan induksi matematika''': Knuth mendemonstrasikan penggunaan [[induksi matematika]] untuk versi "pengembangan" dari algoritma Euclid, dan dia mengajukan "metode umum yang digunakan untuk membuktikan validitas dari setiap algoritma."
<ref>
Knuth 1973:13-18. Dia memuji "the formulation of algorithm-proving in terms of asertions and induction" kepada R. W. Floyd, Peter Naur, C. A. R. Hoare, H. H. Goldstine dan J. von Neumann. Tausworth 1977 meminjam contoh Euclid Knuth dan mengembangkan metoda Knuth di bab 9.1 ''Formal Proofs'' (pages 288–298).
</ref>
Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari bukti kebenarannya.
<ref>
Tausworthe 1997:294
</ref>
=== Menghitung dan meningkatkan algoritma Euclid ===
'''Elegan (kepadatan) lawan kebaikan (kecepatan)''': Dengan hanya 6 instruksi dasar, "Elegan" adalah jelas pemenang dibandingkan dengan instruksi "inelegan" yang 13.
Namun, "Inelegan" lebih ''cepat'' (ia sampai pada HALT dengan langkah lebih sedikit).
[[Analisis algoritma]]
<ref>
cf Knuth 1973:7 (Vol. I), and his more-detailed analyses on pp. 1969:294-313 (Vol II).
</ref>
mengindikasikan kenapa hal tersebut terjadi: "Elegan" melakukan pengujian kondisi ''dua'' kali disetiap pengulangan pengurangan, sementara "inelegan" hanya sekali.
Bila algoritma (biasanya) membutuhkan banyak pengulangan, ''secara rata-rata'' lebih banyak waktu yang terbuang saat melakukan tes "B = 0?" yang hanya diperlukan saat sisa sudah dihitung.
'''Bisakah algoritma ditingkatkan?''': Bila programmer sudah menilai sebuah program "cocok" dan "efektif" -- yaitu, ia menghitung fungsi yang ditujukan oleh penulisnya -- maka pertanyaannya menjadi, bisakah ditingkatkan?
Kepadatan dari "inelegan" bisa ditingkatkan dengan menghilangkan 5 langkah.
Tapi Chaitin membuktikan bahwa memadatkan algoritma tidak bisa diotomatiskan dengan algoritma generalisasi;
<ref>
Kesalahan terjadi saat sebuah algoritma mencoba memadatkan dirinya sendiri.
Keberhasilan akan memecahkan [[permasalahan perhentian]].
</ref>
tapi, ia bisa dilakukan secara [[heuristik]], misalnya dengan pencarian menyeluruh (contohnya bisa ditemukan di [[berang-berang sibuk]]), coba dan gagal, kecerdasan, kedalaman, penggunaan [[penalaran induktif]], dll.
Bisa diamati bahwa langkah 4, 5, dan 6 dilang pada langkah 11, 12, dan 13.
Pembandingan dengan "Elegan" menyediakan petunjuk langkah-langkah tersebut dengan langkah 2 dan 3 dapat dihilangkan.
Hal ini mengurangi jumlah instruksi dasar dari 13 menjadi 8, yang membuatnya "lebih elegan" dari "Elegan" dengan 9 langkah.
Kecepatan "Elegan" bisa ditingkatkan dengan memindahkan tes B=0? keluar dari pengulangan.
Perubahan ini memerlukan penambahan 3 instruksi (B=0?, A=0?, GOTO).
Sekarang "Elegant" menghitung contoh-angka lebih cepat;
untuk setiap angka pada A, B dan R, S hal ini selalu merupakan kasus yang membutuhkan analisis yang mendalam.
== Analisis Algoritma ==
{{Main|Analisis algoritma}}
Sangat penting untuk mengetahui berapa banyak sumber tertentu (seperti waktu dan tempat penyimpanan) secara teoritis diperlukan untuk sebuah algoritma.
Metode-metode telah dikembangkan untuk [[analisis algoritma]] untuk mendapatkan jawaban kuantitatif (estimasi);
sebagai contohnya, algoritma pengurutan di atas memerlukan waktu O(''n''), menggunakan [[notasi O besar]] dengan ''n'' sebagai panjang deret (yang akan diurut).
Setiap saat algoritma hanya perlu mengingat dua nilai: nilai terbesar yang ditemukan, dan posisinya sekarang dideretan input.
Oleh karena itu dikatakan memiliki kebutuhan ruang ''O(1)'', jika ruang yang dibutuhkan untuk menyimpan angka masukan tidak dihitung, atau O(''n'') jika dihitung.
Algoritma berbeda mungkin menyelesaikan pekerjaan yang sama dengan kumpulan instruksi yang berbeda dengan waktu, ruang, atau '[[efisiensi algoritmik|usaha]]' lebih sedikit atau banyak dari yang lain.
Sebagai contohnya, algoritma [[pencairan binari]] biasanya mengungguli pencarian berderet secara [[pencarian paksa|paksa]] bila digunakan untuk [[tabel pencarian]] pada deret terurut.
=== Formal lawan empiris ===
{{Main|Algoritma empiris|Profiling (pemrograman komputer)|Optimisasi program}}
[[analisis algoritma|Analisis dan kajian algoritma]] adalah bidang dari ilmu komputer, dan biasanya dilakukan secara abstrak tanpa menggunakan [[bahasa pemrograman]] tertentu atau implementasi.
Dalam artian, analisis algoritma mirup dengan bidang matematika lainnya yang mana fokus pada properti yang mendasari algoritma dan bukan pada implementasi tertentu.
Biasanya [[pseudokode]] digunakan pada analisis karena merupakan representasi paling umum dan sederhana.
Namun, pada akhirnya, kebanyakan algoritma diimplementasikan di perangkat keras / lunak tertentu dan [[efisiensi algoritmik]] mereka akhirnya diuji menggunakan kode yang sebenarnya.
Untuk solusi dari sebuah masalah, efisiensi dari algoritma tertentu mungkin tidak terlalu berpengaruh (kecuali n sangat besar) tapi bagi algoritma yang dirancang untuk kecepatan interaktif, komersial, atau penggunaan ilmiah jangka panjang ia bisa saja kritikal.
Meningkatkan n dari kecil ke n yang besar biasanya menunjukan ketakefisienan algoritma yang tidak berbahaya.
Pengujian empiris berguna karena bisa membuka interaksi tak terduga yang mempengaruhi performa.
[[Benchmark (komputasi)|Benchmark]] bisa digunakan untuk membandingkan potensi kenaikan sebelum/sesudah dari algoritma setelah optimisasi program dilakukan.
==== Percepatan FFT ====
{{Main|Efisiensi algoritmik}}
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada algoritma yang "sudah terkenal", inovasi penting terbaru, berkaitan dengan algoritma [[Transformasi Fourier Cepat|FFT]] (banyak digunakan di bidang pemrosesan gambar), bisa menurunkan waktu pemrosesan dengan faktor sebesar 10.000.
Akibat dari percepatan ini membolehkan, sebagai contohnya, perangkat komputasi portabel (dan perangkat lainnya) menggunakan tenaga lebih sedikit
<ref name="Hassanieh12">
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price
, "[http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf ACM-SIAM Symposium On Discrete Algorithms (SODA)]
, Kyoto, January 2012.
Lihat juga [http://groups.csail.mit.edu/netmit/sFFT/ sFFT Web Page].
</ref>
== Klasifikasi ==
Ada berbagai cara untuk mengklasifikasikan algoritma, tiap-tiapnya memiliki manfaatnya sendiri.
=== Dengan implementasi ===
Salah satu cara mengklasifikasikan algoritma yaitu dengan cara implementasi.
* '''Rekursi''' atau '''iterasi''': Sebuah [[algoritma rekursi]] yaitu algoritma yang memanggil dirinya sendiri berulang kali sampai kondisi tertentu tercapai, yang merupakan metode umum bagi [[pemrograman fungsional]].
Algoritma [[Iterasi|iteratif]] menggunakan konstruksi berulang seperti [[Pengulangan program|pengulangan]] dan terkadanga struktur data tambahan seperti [[Tumpukan (struktur data)|tumpukan]] untuk menyelesaikan permasalahan.
Beberapa permasalahan secara alami cocok dengan satu implementasi atau lainnya.
Sebagai contoh, [[Menara Hanoi]] dikenal dengan implementasi rekursif.
Setiap versi rekursif memiliki kesamaan (tapi bisa lebih atau kurang kompleks) dengan versi iteratif, dan sebaliknya.
* '''Logical''': Sebuah algoritma bisa dilihat sebagai [[Penalaran deduktif|logika deduksi]] terkontrol. Pernyataan ini diekspresikan sebagai: '''Algoritma = logika + kontrol'''. <ref>Kowalski 1979</ref>
Komponen logika mengekspresikan aksioma yang bisa digunakan dalam komputasi dan komponen kontrol menentukan cara deduksi digunakan pada aksioma.
Ini merupakan dasar dari paradigma [[pemrograman logika]].
Dalam bahasa pemrograman logika murni komponen kontrol adalah tetap dan algoritma ditentukan dengan memberikan hanya komponen logikanya.
Daya tarik dari pendekatan ini adalah [[Semantik formal dari bahasa pemrograman|semantik]] elegan: sebuah perubahan dalam aksioma memiliki perubahan dalam algortima.
* '''Serial''' atau ''paralel'' atau '''terdistribusi''': Algoritma biasanya dibicarakan dengan asumsi bahwa komputer menjalankan satu instruksi algoritma setiap waktu.
Komputer tersebut terkadang disebut dengan komputer serial.
[[Rancang algoritma|Rancangan algoritma]] untuk lingkungan tersebut disebut dengan algoritma serial, terbalik dengan [[algoritma paralel]] atau [[algoritma terdistribusi]].
Algoritma paralel memanfaatkan arsitektur komputer yang mana beberapa prosesor bisa mengerjakan masalah di waktu yang sama, selain itu algoritma terdistribusi memanfaatkan banyak mesin yang terhubung dengan [[Jaringan komputer|jaringan]].
Algoritma paralel atau terdistribusi membagi permasalahan menjadi banyak sub-masalah simetris atau asimetris dan mengumpulkan hasilnya kembali.
Konsumsi sumber pada algoritma tersebut tidak hanya perputaran prosesor disetiap prosesor tapi juga daya komunikasi antara prosesor.
Algoritma pengurutan bisa diparalelkan secara efisien, tapi biaya komunikasinya sangat mahal.
Algoritma iteratif secara umum bisa diparalelkan.
Beberapa permasalahan tidak ada algoritma paralelnya, dan disebut dengan permasalahan serial lahiriah.
* '''Deterministik''' atau '''non-deterministik''': [[Algoritma deterministik]] menyelesaikan masalah dengan keputusan yang tepat disetiap langkah dari algoritama sedangkan [[algoritma non-deterministik]] menyelesaikan masalah lewat penerkaan walaupun penerkaan biasanya lebih akurat dengan menggunakan [[heuristik]].
* '''Tepat''' atau '''perkiraan''': Bila banyak algoritma sampai pada solusi yang tepat, [[algoritma perkiraan]] mencari sebuah perkiraan yang terdekat dengan solusi benarnya.
Perkiraan bisa menggunakan baik strategi deterministik atau acak.
Algoritma seperti itu memiliki nilai guna untuk banyak permasalahan sulit.
* '''[[Algoritma quantum]]''' berjalan di model realistik dari [[komputasi quantum]].
Istilah ini biasanya digunakan untuk algoritma yang tampak pada dasarnya quantum, atau menggunakan beberapa fitur penting komputasi quantum seperti [[superposisi quantum]] atau [[belitan quantum]].
== Paradigma secara rancangan ==
Cara lain mengklasifikasikan algoritma adalah dengan metodologi rancangannya atau paradigma.
Ada sejumlah paradigma, tiap-tiapnya berbeda dari yang lain.
Lebih lanjut, setiap kategori tersebut mengikutkan banyak tipe algoritma yang berbeda.
BEberapa paradigma umum yang sering ditemukan termasuk:
* '''[[Pencarian paksa|paksa]]''' atau '''pencarian mendalam'''.
Ini merupakan metoda naif mencoba setiap kemungkinan solusi untuk melihat yang terbaik.
<ref>{{cite book
| last1 = Carroll
| first1 = Sue
| last2 = Daughtrey
| first2 = Taz
| title = Fundamental Concepts for the Software Quality Engineer
| url = http://books.google.com/?id=bz_cl3B05IcC&pg=PA282
| date = July 4, 2007
| publisher = American Society for Quality
| isbn = 978-0-87389-720-4
| pages = 282 et seq. }}</ref>
* '''Membagi dan menaklukan'''. [[Algoritma bagi dan takluk]] secara berulang mengurangi instansi jumlah masalah menjadi satu atau lebih kecil instasi masalah yang sama (biasanya secara [[rekursif]]) sampai instansi cukup kecil diselesaikan dengan mudah.
Salah satu contoh bagi dan takluk adalah [[mergesort|pengurutan gabung]].
Pengurutan dapat dilakukan disetiap segmen data setelah membagi data menjadi segmen-segmen dan urutan seluruh data bisa didapat pada fase takluk dengan menggabungkan segmen-segmen.
Variasi sederhana dari bagi-dan-takluk disebut '''algoritma kurang dan takluk''', yang menyelesaikan sub-masalah yang sama dan menggunakan solusi dari sub-masalah tersebut untuk menyelesaikan masalah yang lebih besar.
Bagi dan takluk membagi permasalahan menjadi banyak sub-masalah dan sehingga tahap takluk lebih kompleks daripada algoritma kurang-dan-taklukan.
Sebuah contoh dari algoritma kurang-dan-taklukan adalah [[algoritma pencarian binari]].
* '''[[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, [[algoritma Floyd-Warshall]], jalan terpendek ke tujuan dari sebuah vertex dalam [[grafik (matematika)|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 matematis|tabel]] dari submasalah yang telah diselesaikan, pemrograman dinamis mengurangi eksponensial dari banyak permasalahan menjadi kompleksitas polinomial.
* '''Metoda rakus'''. Sebuah [[algoritma rakus]] mirip dengan [[pemrograman dinamis|algoritma pemrograman dinamis]], tapi 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. Metoda 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. Algoritma ini tidak terlalu mendalam, dan tidak memberikan jawaban yang akurat terhadap banyak permasalahan. Tapi bila ia bekerja, ia menjadi metoda yang paling cepat. Algoritma rakus paling terkenal adalah menemukan rentang pohon minimal seperti pada [[pengkodean Huffman|Pohon Huffman]], [[Algoritma Kruskal|Kruskal]], [[Algoritma Prim|Prim]], [[Algoritma Sollin|Sollin]].
* '''Pemrograman Linear'''. Saat menyelesaikan sebuah masalah menggunakan [[pemrograman linear]], [[ketidaksamaan (matematika)|ketidaksamaan]] khusus mengikutkan input ditemukan dan percobaan dilakukan untuk memaksimalkan (atau meminimalkan) beberapa fungsi linear dari input. Banyak masalah (seperti [[Permasalahan alur maksimum|alur maksimum]] untuk grafik terarah) bisa diselesaikan dengan cara pemrograman linear, dan kemudian diselesaikan dengan algoritma 'umum'' seperti [[algoritma simplex]]. Jenis pemrograman linear yang lebih kompleks disebut dengan pemrograman integer, yang mana ruang lingkup solusi dibatasi oleh [[integer]].
* '''[[Reduksi (kompleksitas)|Reduksi]]'''. Teknik ini menyelesaikan masalah sulit dengan mengubahnya menjadi permasalahan yang lebih diketahui yang mana kita (berharap) memiliki algoritma [[asimptotikal optimal]]. Tujuannya yaitu untuk menemukan sebuah algoritma reduksi yang [[teori kompleksitas komputasi|kompleksitas]]nya tidak didominasi oleh algoritma hasil reduksi. Sebagai contoh, [[algoritma 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''.
* '''Cari dan enumerasi'''. Banyak masalah (seperti bermain [[catur]]) bisa dimodelkan sebagai masalah danan [[teori grafik|grafik]]. Sebuah [[algoritma eksplorasi grafik]] menentukan aturan-aturan untuk bergerak disekitar grafik dan berguna bagi masalah tersebut. Kategori ini juga mengikutkan [[algoritma pencarian]], enumerasi [[batas dan cabang]] dan [[backtracking]].
# [[Algoritma pengacakan]] yaitu yang membuat pilihan secara acak (atau pseudo-acak); untuk beberapa masalah, pada kenyataannya bisa dibuktikan bahwa solusi tercepat harus mengikutkan beberapa [[keacakan]]. Ada dua kelas besar dari algoritma ini:
## [[Algoritma Monte Carlo]] mengembalikan jawaban yang benar dengan probabilitas-tinggi. Misalnya, [[RP (kompleksitas)|RP]] adalah sub-klas dari algoritma ini yang berjalan dalam [[waktu polinomial]])
## [[Algoritma Las Vegas]] selalu mengembalikan jawaban yang benar, tapi waktu prosesnya adalah hanya terikat secara probabilistik, misalnya [[Waktu Probabilistik Polinomial Galat-Nol|ZPP]].
## Dalam [[masalah optimisasi]], algoritma heuristik tidak mencoba menemukan solusi optimal, tapi solusi terdekat yang mana waktu atau sumber dayanya terbatas. Algoritma ini tidak praktis untuk menemukan solusi yang sempurna. Salah satu contoh dari ini yaitu algoritma [[pencarian lokal (optimisasi)|pencarian lokal]], [[pencarian tabu]], atau [[simulasi penguatan]], sebuah kelompok dari algoritma probabilistik heuristik yang memiliki beragam solusi dari sebuah masalah dengan sejumlah keacakan. Istilah "simulasi penguatan" mengiaskan istilah metalurgi yang artinya pemanasan dan pendinginan besi untuk mendapatkan kebebasan dari cacat. Tujuan dari perbedaan acak adalah untuk menemukan solusi yang mendekati secara global melainkan yang secara lokal, idenya adalah elemen acak berkurang saat algoritma mencapai solusi. [[Algoritma pendekatan]] adalah algoritma heuristik yang menambahkan beberapa ikatan pada galat. [[Algoritma genetik]] mencoba menemukan solusi dari permasalahan dengan meniru proses [[evolusi]] biologis, dengan perputaran mutasi acak menghasilkan generasi yang sukses dari "solusi". Maka, mereka meniru reproduksi dan "seleksi alam". Dalam [[pemrograman genetik]], pendekatan ini dikembangkan ke algoritma, dengan menganggap algoritma itu sendiri sebagai "solusi dari sebuah masalah.
=== Berdasarkan bidang kajian ===
{{Lihat juga|Daftar algoritma}}
Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan algoritma yang efisien. Masalah yang berkaitan di satu bidang terkadang dipelajari bersama. Beberapa contoh yaitu [[algoritma pencarian]], [[algoritma penggabungan]], [[analisis numerik|algoritma numerik]], [[teori grafik|algoritma grafik]], [[algoritma deret]], [[geometri komputasi|algoritma komputasi geometri]], [[kombinatorial|algoritma kombinatorial]], [[algoritmas medis]], [[mesin belajar]], [[kriptografi]], algoritma [[kompresi data]] dan [[penguraian|teknik penguraian]].
Terkadang bidang-bidang tersebut saling tumpang tindih, dan perkembangan algoritma di satu bidang bisa meningkatkan bidang lainnya yang terkadang tidak berkaitan. Sebagai contohnya, pemrograman dinamis ditemukan untuk optimisasi konsumsi sumber daya dalam industri, tapi sekarang digunakan untuk menyelesaikan sejumlah besar permasalahan dalam banyak bidang.
=== Berdasarkan kompleksitas ===
{{Lihat juga|kelas kompleksitas|Kompleksitas parameterisasi}}
Algoritma bisa diklasifikasikan berdasarkan jumlah waktu yang dibutuhkan untuk selesai dibandingkan dengan ukuran inputnya. Ada berbagai varietas: beberapa algoritma 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 algoritama dengan kompleksitas yang berbeda, sementara permasalahan yang lain bisa saja tidak memiliki algoritma atau tidak diketahui algoritmanya yang efisien. Ada juga pemetaan dari beberapa algoritma terhadap permasalahan lain. Karena itu, lebih cocok untuk mengklasifikasikan permasalahan itu sendiri bukannya algoritma menjadi kelas-kelas yang sama berdasarkan kompleksitas dari kemungkinan algoritma terbaik baginya.
Burgin (2005, p. 24) menggunakan definisi algoritma secara umum yang melonggarkan kebutuhan bersama yang keluaran dari algoritma yang menjalankan sebuah fungsi harus ditentukan setelah sejumlah langkah. Dia mendefinisikan kelas super-rekursif dari algoritma sebagai "sebuah kelas algoritma 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 metoda [[hiperkomputasi]].
== Algoritma berkelanjutan ==
Kata sifat "berkelanjutan" bila diterapkan pada kata "algoritma" bisa berarti:
# Sebuah algoritma beroperasi pada data yang merepresentasikan kuantitas yang berkelanjutan, walaupun data tersebut direpresentasikan oleh pendekatan diskrit -- seperti algoritma yang dipelajari dalam [[analisis numerik]]; atau
# Sebuah algoritma dalam bentuk dari [[persamaan diferensial]] yang beroperasi secara berkelanjutan terhadap data, berjalan dalam sebuah [[komputer analog]].
<ref>{{cite book
| author = Tsypkin
| title = Adaptation and learning in automatic systems
| url = http://books.google.com/?id=sgDHJlafMskC&pg=PA54
| year = 1971
| publisher = Academic Press
| isbn = 978-0-08-095582-7
| page = 54 }}</ref>
== Isu legalitas ==
:''Lihat juga: [[Paten perangkat lunak]] untuk pendahuluan umum dari paten pada perangkat lunak, termasuk algoritma untuk diimplementasikan pada komputer.''
Algoritma biasanya tidak dipatenkan. Di Amerika Serikat, sebuah klaim yang terdiri hanya dari manipulasi sederhana dari konsep abstrak, angka, atau sinyal tidak berarti suatu "process" (SPTO 2006), dan oleh karena itu algoritma tidak bisa dipatenkan (sebagaimana dalam [[Gottschalk v. Benson]]).
Namun, penerapan praktis dari algoritma terkadang dipatenkan.
Sebagai contohnya, dalam [[Diamond v. Diehr]], aplikasi dari algoritma [[umpan-balik]] sederhana untuk membantu dalam menyembuhkan [[karet sintetis]] dianggap dapat dipatenkan.
[[Debat paten perangkat lunak|Mematenkan perangkat lunak]] sangat kontroversial, dan ada paten yang mengikutkan algoritma yang sangat dikritisi, terutama algoritma [[kompresi data]], seperti [[Graphics Interchange Format|Format Grafik]]nya [[Unisys]].
Sebagai tambahan, beberapa algoritma kriptografi memiliki batasan ekspor (lihat [[ekspor dari kriptografi]]).
== Etimologi ==
Kata ''"Algoritma"'', atau ''"[[Algorisma]]"'' pada versi penulisan lain, datang dari nama [[al-Khwarizmi]]. dieja dalam Arab klasik sebagai Al-Khwarithmi. Al-khwarizmi adalah [[matematikawan]], [[ahli astronomi]], [[ahli geografi]] dari [[orang Persia|Persia]] dan sarjana [[House of Wisdom]] di [[Baghdad]], yang arti namanya ''"penduduk asli [[Khwarezm]]"'', sebuah kota yang merupakan bagian dari [[Wilayah Iran]] pada masanya dan sekarang [[Uzbekistan]]
{{sfn|Toomer|1990|loc={{citation not found}}}}.
<ref name="Hogendijk">{{cite journal
|first=Jan P.
|last=Hogendijk
|title=al-Khwarzimi
|journal=Pythagoras
|volume=38
|issue=2
|year=1998
|pages=4–5
|url=http://www.kennislink.nl/web/show?id=116543
|ref=harv}}
{{Dead link |date=March 2010
}}</ref>
<ref name="Oaks">{{cite web
|first=Jeffrey A.
|last= Oaks
|url=http://facstaff.uindy.edu/~oaks/MHMC.htm
|title=Was al-Khwarizmi an applied algebraist?
|publisher=[[University of Indianapolis]]
|accessdate=May 30, 2008
}}</ref>
Sekitar tahun 825, dia menulis risalah dalam bahasa Arab, yang diterjemahkan dalam [[Latin]] pada abad ke-12 dengan judul ''Algoritmi de numero Indorum''.
Judul ini artinya "Algoritmi pada bilangan India", dimana "Algoritmi" adalah pelatinan penerjemah dari nama Al-Khwarizmi.
<ref>{{cite book
| last = Brezina
| first = Corona
| title = Al-Khwarizmi: The Inventor Of Algebra
| url = http://books.google.com/?id=955jPgAACAAJ
| year = 2006
| publisher = The Rosen Publishing Group
| isbn = 978-1-4042-0513-0
}}</ref>
Al-Khwarizmi dulunya adalah matematikawan yang paling banyak dibaca di Eropa pada akhir Abad Pertengahan, pada umum lewat bukunya yang lain, [[Al-Jabr|Aljabar]].
<ref>[http://www-history.mcs.st-and.ac.uk/Extras/Boyer_Foremost_Text.html Foremost mathematical texts in history], according to [[Carl B. Boyer]].</ref>
Pada akhir abad pertengahan, ''algorismus'', perubahan dari namanya, berarti "sistem bilangan desimal" yang masih merupakan arti dari kata Inggris moderen [[algorism]].
Pada abad ke-17 Prancis kata tersebut berubah, tapi tidak maknanya, menjadi ''algorithme''.
Inggris mengadopsi Prancis setelahnya, tapi tidak pada akhir abad ke-19 lah "Algorithm" mengambil makna dari kata Inggris masa sekarang.
<ref>Etymology of algorithm at [http://dictionary.reference.com/browse/algorithm Dictionary.Reference.com]</ref>
== Sejarah: Perkembangan dari kata "algoritma" ==
=== Asal mula ===
Kata algoritma datang dari nama matematikawan muslim Persia abad ke-9 [[al-Khwarizmi|Abu Abdullah Muhammad ibnu Musa Al-Khwarizmi]], yang hasil kerjanya dibangun dari matematikawan India abad ke-7 [[Brahmagupta]].
Kata algorisma awalnya mengacu hanya pada aturan-aturan dalam melakukan aritmatika menggunakan bilangan Hindu-Arab namun berkembang lewat penerjemahan Latin Eropa dari nama Al-Khwarizmi menjadi algoritma pada abad ke-18.
Penggunaan kata tersebut berkembang mengikutkan semua prosedur untuk menyelesaikan masalah atau melakukan unit kegiatan.
<ref>{{cite web
|url=http://www.scriptol.com/programming/algorithm-history.php
|title=History of Algorithms and Algorithmics
|publisher=Scriptol.com
|date=
|accessdate=November 7, 2012
}}</ref>
=== Simbol diskrit dan yang dapat dibedakan ===
'''Penanda-penghitung''': Untuk mencatat hewan gembalaan, kumpulan biji dan uang mereka orang dahulu menggunakan penghitung: akumulasi batu atau tanda yang ditoreh pada tongkat, atau membuat simbol diskrit di kerang.
Sampai orang Babilonia dan Mesir menggunakan tanda dan simbol, pada akhirnya [[bilangan Roma]] dan [[abakus]] berkembang (Dilson, p. 16-41).
Penanda penghitung muncul dalam [[sistem bilangan operan]] aritmatika digunakan dalam [[mesin Turing]] dan komputasi [[mesin Post-Turing]].
=== Manipulasi simbol sebagai "penampung" bilangan: aljabar ===
Karya dari [[matematika Yunani|Geometer Yunani]] kuno ([[algoritma Euklid]]), [[Daftar matematikawan India|matematikawan India]] [[Brahmagupta]], dan [[matematika Islam|matematikawan Persia]] [[Muhammad ibnu Musa al-Khwarizmi|Al-Khwarizmi]] (yang darinya isitlah "[[algorism]]" dan "algoritma" diturunkan), dan matematikawan Eropa Barat memuncak dalam notasi [[Gottfried Leibniz|Leibniz]] dari [[rasiosinator kalkulus]] (sekitar 1680-an):
{{quote|Abad yang baik dan setengah lebih maju dari masanya, Leibniz mengajukan logika aljabar, sebuah aljabar yang akan menentukan aturan-aturan untuk memanipulasi konsep logika dengan cara yang aljabar biasa menentukan aturan untuk manipulasi angka.<ref>Davis 2000:18</ref>}}
=== Rancangan mekanis dengan tingkat diskrit ===
'''Jam''': Bolter memuji penemuan [[jam]] gaya-berat sebagai "Kunci penemuan [dari Eropa di Abad Pertengahan]]", khususnya pada [[ambang pelarian]]
<ref>Bolter 1984:24</ref>
yang menyediakan kita dengan tik dan tak dari jam mekanis.
"Mesin otomatis yang akurat"
<ref>Bolder 1984:26</ref>
mengarah langsung pada "[[teori otomata|otomata]] mekanis" dimulai pada abad ke-13 dan terakhir pada "mesin komputasi" -- [[motor berbeda]] dan [[motor analitik]] dari [[Charles Babbage]] dan bangsawan [[Ada Lovelace]], pertengahan abad ke-19.
<ref>Bolter 1984:33–34, 204–206.</ref>
Lovelace dikreditkan sebagai yang pertama menciptakan algoritma yang ditujukan untuk diproses di komputer -- motor analitis Babbage, perangkat pertama yang dianggap [[komputer]] [[Turing-sempurna]] sebenarnya bukan hanya sebuah [[kalkulator]] -- dan terkadang dikenal "programmer pertama dalam sejarah", walaupun implementasi penuh dari perangkat Babbage kedua tidak terealisasi sampai beberapa dekade setelah masanya.
'''Mesin logika 1870 - [[Stanley Jevons]]' "sempoa logika" dan "mesin logika"''': Masalah teknisnya adalah untuk mengurangi [[persamaan boolean]] bila ditampilkan dalam sebuah bentuk yang pada masa sekarang dikenal sebagai [[pemetaan Karnaugh]].
Jevons (1880) pertama menjelaskan "sempoa" sederhana dari "potongan kayu dilengkapi dengan penyemat, dibuat supaya bagian atau kelas kombinasi [logika]] manapun dapat dipilih secara mekanis ... Baru-baru ini Saya telah mengurangi sistem menjadi bentu yang secara sempurna mekanis, dan membuatnya mewujudkan keseluruhan proses inferensi tak langsung dalam apa yang disebut sebuah '''Mesin Logika'''"
Mesinnya dilengkapi dengan "beberapa tangkai kayu yang bisa dipindahkan" dan "di bawah ada 21 kunci seperti pada piano [dll] ...".
Dengan mesin ini dia dapat menganalis sebuah "[[silogisme]] atau argumen logika sederhana apapun".
<ref>All quotes from W. Stanley Jevons 1880 ''Elementary Lessons in Logic: Deductive and Inductive'', Macmillan and Co., London and New York. Republished as a googlebook; cf Jevons 1880:199–201. Louis Couturat 1914 ''the Algebra of Logic'', The Open Court Publishing Company, Chicago and London. Republished as a googlebook; cf Couturat 1914:75–76 gives a few more details; interestingly he compares this to a typewriter as well as a piano. Jevons states that the account is to be found at Jan . 20, 1870 ''The Proceedings of the Royal Society''.</ref>
'''Mesin tenun Jacquard, kartu berlobangnya Hollerith, telegraf dan telepon -- penyiaran elektromekanis''': Bell dan Newell (1971) mengindikasikan bahwa [[mesin tenun Jacquard]] (1801), pelopor dari [[kartu Hollerith]] (kartu berlobang, 1887), dan "teknologi alih telepon" adalah akar dari sebuah pohon yang mengarah pada perkembangan dari komputer pertama.
<ref>Bell and Newell diagram 1971:39, cf. Davis 2000</ref>
Pada pertengahan abad ke-19 [[telegraf]], pelopor dari telepon, digunakan diseluruh dunia, pengkodean diskrit dan pembedaan huruf sebagai "titik dan strip".
Pada akhir abad ke-19 [[pita telegraf]] (sekitar 1870-an) digunakan, sebagaimana juga kartu Hollerith pada sensus Amerika 1890.
Kemudian muncullah [[teleprinter]] (sekitar 1910-an) dengan kerta-berlobang menggunakan [[kode Baudot]] di pita.
'''Jaringan alih-telepon''' dari [[penyiaran]] elektromekanis (ditemukan 1835) adalah karya dair [[George Stibitz]] (1937), penemu dari perangkat penghitungan digital.
Saat bekerja di laboratorium Bell, dia mengamati "beratnya" penggunaan kalkulator mekanis dengan geligi.
"Dia pulang ke rumah pada suatu malam 1937 berniat untuk menguji idenya ... Saat mengatik selesai, Stibitz telah membangun perangkat hitung digital".
<ref>* Melina Hill, Valley News Correspondent, ''A Tinkerer Gets a Place in History'', Valley News West Lebanon NH, Thursday March 31, 1983, page 13.</ref>
Davis (2000) mengamati pentingnya penyiaran elektromekanis (dengan "keadaan binari"-nya ''buka'' dan ''tutup''):
: Hanya dengan perkembangan, dimulai sejak 1930-an, dari kalkulator elektromekanis menggunakan penggantian elektris, sehingga mesin yang dibuat memiliki ruang lingkup yang dibayangkan Babbage." <ref> Davis 2000:14</ref>
=== Matematika selama abad 19 sampai pertengahan abad 20 ===
'''Symbol dan aturan''': Dengan cepat berkembangnya matematika dari [[George Boole]] (1847, 1854), [[Gottlob Frege]] (1897), dan [[Giuseppe Peano]] (1888-1889) mengurangi aritmatika menjadi serangkaian simbol dimanipulasi oleh aturan-aturan. ''The Principles of arithmetic, presented by a new method''-nya Peano (1888) adalah "usaha pertama mengaksiomakan matematika dalam sebuah bahasa simbolik".
<ref>van Heijenoort 1967:81ff</ref>
Tapi Heijenoort memberi pujian pada Frege (1879): Frege "merupakan karya tulis paling penting mengenai logika. ... yang mana kita lihat sebuah "'bahasa formula', yaitu sebuah ''lingua characterica'', sebuah bahasa ditulis dengan simbol-simbol khusus, "untuk berpikir murni", yaiut, bebas dari hiasan retorikal ... dibangun dari simbol-simbol tertentu yang dimanipulasi menurut aturan-aturan terbatas".
<ref>van Heijenoort's commentary on Frege's ''Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought'' in van Heijenoort 1967:1</ref>
Karya dari Frege lebih lanjut disederhanakan dan diperkuat oleh [[Alfred North Whitehead]] dan [[Bertrand Russell]] dalam [[Principia Mathematical]] (1910-1913).
'''Paradoks''': Pada masa yang sama sejumlah paradoks yang mengganggu muncul dalam literatur, pada khususnya [[paradoks Burali-Forti]] (1987), [[paradoks Russell]] (1902-03), dan [[Paradoks Richard]].
<ref>Dixon 1906, cf. Kleene 1952:36–40</ref>
Hasilnya mengarah ke makalah [[Kurt Godel]] (1931) -- dia secara khusus merujuk paradoks pembohong -- yang mengurangi aturan dari [[rekursi]] pada angka.
'''Penghitungan Efektif''': Dalam usaha untuk menyelesaikan [[Entscheidungsproblem]] yang didefinisikan oleh Hilbert tahun 1928, matematikawan pertama mendefinisikan apa arti dari "metoda efektif" atau "kalkulasi efektif" (misalnya, sebuah kalkulasi yang akan sukses).
Dalam waktu yang cepat hal berikut muncul: [[kalkulus-λ]] oleh [[Alonzo Church]], [[Stephen Kleene]], dan [[J.B. Rosser]]
<ref>
cf. footnote in Alonzo Church 1936a in Davis 1965:90 and 1936b in Davis 1965:110
</ref>
definisi dari "rekursi umum" yang benar-benar diasah dari karya Godel berdasarkan saran dari [[Jacquard Herbrand]] (cf. kuliah Godel di Princeton tahun 1934) dan penyederhaan selanjutnya oleh Kleene.
<ref>
Kleene 1935–6 in Davis 1965:237ff, Kleene 1943 in Davis 1965:255ff
</ref>
Church membuktikan
<ref>Church 1936 in Davis 1965:88ff</ref>
bahwa Entscheidungsproblem tidak terpecahkan, definisi [[Emil Post]] tentang penghitungan efektif yaitu sebagai pekerja yang tanpa berpikir mengikuti suatu daftar instruksi untuk bergerak ke kiri atau kanan lewat sederetan ruangan dan bersamaan dengan itu bisa menandai atau menghapus kertas atau mengamati kertas dan membuat pilihan ya-tidak tentang instruksi selanjutnya.
<ref>cf. "Formulation I", Post 1936 in Davis 1965:289–290</ref>
Pembuktian Alan Turing bahwa Entscheidungsproblem tidak terpecahkan dengan menggunakan "sebuah mesin [otomatis]"-nya
<ref>Turing 1936–7 in Davis 1965:116ff</ref>
dengan efek yang mirip dengan "formulasi"-nya Post, definisi [[J. Barkley Rosser]] tentang "metoda efektif" dalam makna "sebuah mesin".
<ref>Rosser 1939 in Davis 1965:226</ref>
Proposal [[S. C. Kleene]] dari pelopor "[[Tesis Church]]" yang disebutnya "Thesis I",
<ref>Kleene 1943 in Davis 1965:273–274</ref>
dan beberapa tahun kemudian Kleene menamakan tesisnya "Tesis Church"
<ref>Kleene 1952:300, 317</ref>
dan mengajukan "Tesis Turing".
<ref>Kleene 1952:376</ref>
=== Emil Post (1936) dan Alan Turing (1936-37, 1939) ===
Berikut adalah kebetulan yang luar biasa dari dua orang yang tidak tahu satu sama lain tapi mendeskripsikan proses orang-sebagai-komputer mengerjakan komputasi -- dan mereka menghasilkan definisi yang mirip.
[[Emil Post]] (1936) mendeskripsikan aksi dari sebuah "komputer" (manusia) sebagai berikut:
:"... dua konsep ikut serta: yaitu sebuah ''simbol ruang'' dimana pekerjaan mengarah dari masalah ke jawaban dilakukan, dan ''sekumpulan arahan'' yang baku dan tidak bisa diubah.
Simbol ruangnya yaitu
:"sederetan dua arah tak terbatas dari ruang atau kotak... penyelesai masalah atau pekerja harus berjalan dan bekerja di simbol ruang ini, dengan bisanya masuk, dan beroperasi dengan satu kotak dalam satu waktu... sebuah kotak memiliki dua kemungkinan kondisi, yaitu, kosong atau belum ditandai, dan dengan adanya tanda tunggal disana, katakanlah garis vertikal.
:"Satu kotak dibiarkan dan disebut sebagai titik awal. ...sebuah masalah tertentu diberikan dalam bentuk simbolik dengan sejumlah kotak terbatas [yaitu, INPUT] ditandai dengan coretan. Begitu juga jawabannya [yaitu, OUTPUT] diberikan dalam bentuk simbolik dari suatu konfigurasi dari kotak-kotak yang ditandai....
:"Sekumpulan arahan bisa digunakan untuk permasalahan umum menentukan proses determistik saat diterapkan pada setiap masalah tertentu. Proses ini hanya berhenti bila datang arahan dengan tipe (C ) [yaitu, STOP]". <ref>Turing 1936–7 in Davis 1965:289–290</ref> Lihat lebih lanjut pada [[mesin post-Turing]] [[File:Alan Turing.jpg|thumb|200px|Alan Turing's statue at [[Bletchley Park]].]] Karya [[Alan Turing]] <ref>Turing 1936 in Davis 1965, Turing 1939 in Davis 1965:160</ref> mendahului Stibitz (1937); tidak diketahui apakah Stibitz tahu dengan karya Turing. Biografi Turing percaya bahwa Turing menggunakan model seperti-mesin-ketik diturunkan dari ketertarikan pada masa muda: "Alan memiliki impian menemukan mesin ketik pada saat muda; Ibu Turing memiliki sebuah mesin ketik; dan dia mungkin memulainya dengan menanyakan pada dirinya sendiri apa maksudnya dengan menyebut sebuah mesin ketik dengan 'mekanikal'". <ref>Hodges, p. 96</ref> Dengan lazimnya kode Morse dan telegraf, mesin pita telegraf, dan mesin-ketik jarak jauh kita bisa menyimpulkan bahwa semua itu berpengaruh.
Turing -- model dari komputasinya sekarang dikenal dengan [[mesin Turing]] -- memulai, sebagaimana Post, dengan analisa dari komputer manusia yang ia sederhanakan menjadi sekumpulan gerakan dasar sederhana dan "keadaan pikiran".
Tapi dia terus maju selangkah ke depan dan membuat sebuah mesin sebagai model dari komputasi angka.
<ref>Turing 1936–7:116</ref>
:"Menghitung biasanya dilakukan dengan menulis simbol tertentu di atas kertas. Misalkan kertas tersebut dibagi menjadi segi empat seperti buku aritmatika anak-anak.... Saya asumsikan bahwa komputasi dilakukan pada kertas satu dimensi, yaitu, di pita yang dibagi dalam persegi. Juga misalkan bahwa jumlah simbol yang akan dicetak terbatas....
:"Perilaku dari komputer disetiap waktu ditentukan oleh simbol yang diobservasinya, dan "keadaan pikiran"-nya pada waktu tersebut. Juga bisa diasumsikan bahwa ada batas B sebagai jumlah simbol atau persegi yang mana komputer dapat amati dalam satu waktu. Jika ia ingin mengamati lebih, ia harus menggunakan pengamatan beriringan. Kita juga memisalkan bahwa jumlah keadaan pikiran yang diperlukan disini adalah terbatas...
:"Mari kita bayangkan bahwa operasi yang dilakukan oleh komputer akan dipecah menjadi 'operasi-operasi sederhana' yang sangat mendasar sehingga tidak mudah membayangkannya untuk dibagi lebih jauh." <ref name="Turing 1936-7 in Davis 1965:136">Turing 1936–7 in Davis 1965:136</ref>
Reduksi Turing menghasilkan hal berikut:
:"Operasi sederhana haruslah mengikutkan:
::"(a) Perubahan dari simbol pada salah satu persegi yang sedang diamati
::"(b) Perubahan dari salah satu persegi diamati terhadap persegi lainnya di antara L persegi dari salah satu yang sebelumnya diamati.
"Bisa saja beberapa dari perubahan tersebut menyebabkan perubahan keadaan pikiran. Operasi tunggal paling umum oleh karena itu harus diambil jadi salah satu hal berikut:
::"(A) Suatu kemungkinan perubahan (a) dari simbol bersamaan dengan suatu perubahan dari keadaan pikiran.
::"(B) Suatu kemungknian perubahan (b) dari persegi yang diamati, bersama dengan kemungkinan perubahan dari keadaan pikiran"
:"Kita sekarang mungkin sudah bisa membentuk sebuah mesin untuk melakukan pekerjaan dari komputer tersebut." <ref name="Turing 1936-7 in Davis 1965:136"/>
Beberapa tahun kemudian, Turing mengembangkan analisanya (tesis, secara definisi) dengan ekspresi kuat berikut:
:"Sebuah fungsi dikatakan "bisa dihitung secara efektif" jika nilainya bisa ditemukan dengan proses yang murni mekanis.
Walau sangat mudah menangkap ide ini, namun ia membutuhkan beberapa definisi matematikan terbatas yang bisa diekspresikan . . . [dia mendiskusikan sejarah dari definisi seperti di atas dengan menghormati Godel, Herbrand, Kleen, Church, Turing dan Post] ... Kita mungkin gunakan pernyataan tersebut secara harfiah, memahami murni dengan proses mekanis yang mana dapat dilakukan oleh sebuah mesin. Memungkinkan untuk memberikan deskripsi matematis, dalam beberapa bentuk normal, dari struktur mesin tersebut. Perkembangan dari ide ini mengarah pada definisi penulis dari sebuah fungsi yang dapat dihitung, dan untuk mengidentifikasi komputibilitas † dengan penghitungan yang efektif . . . .
::"† Kita boleh menggunakan ekspresi "fungsi hitung" untuk mengartikan sebuah fungsi yang dapat dihitung oleh sebuah mesin, dan kita biarkan "secara efektif dapat dihitung" mengacu pada ide intuitif tanpa definisi tertentu dengan salah satu dari definisi tersebut". <ref>Turing 1939 in Davis 1965:160</ref>
=== J. B. Rosser (1939) dan S. C. Kleene (1943) ===
'''[[J. Barkley Rosser]]''' mendefinisikan sebuah 'metoda [matematis] efektif' dalam cara berikut (penebalan ditambahkan):
:"'Metoda efektif' digunakan di sini bukan makna khusus dari sebuah metoda yang setiap langkahnya secara tepat ditentukan dan pasti menghasilkan jawaban dalam sejumlah langkah yang terbatas.
Dengan pengertian khusus ini, tiga definisi berbeda telah diajukan sampai sekarang. [catatan kakinya #5; lihat diskusinya di bawah].
Yang paling sederhana (karena Post dan Turing) menyatakan intinya bahwa '''sebuah metoda efektif menyelesaikan sekumpulan permasalahan hanya ada jika seseorang bisa membuat sebuah mesin yang akan menyelesaikan setiap masalah dari sekumpulan masalah tanpa campur tangan manusia kecuali memasukan pertanyaan dan (nantinya) membaca jawabannya'''.
Ketiga definisi tersebut sama, jadi tidak masalah yang mana yang digunakan.
Lebih lanjut, fakta bahwa ketiganya sama adalah argumen yang sangat kuat untuk kebenaran dari salah satunya." (Rosser 1939:225-6)
Catatan kaki Rosser #5 merujuk karya dari (1) Church dan Kleene dan definisi dari λ-definabiliti, secara khusus Church menggunakannya dalam ''An Unsolvable Problem of Elementary Number Theory''-nya (1936);
(2) Herbrand dan Godel dan penggunaan rekursi mereka terutama Godel menggunakannya dalam makalah terkenalnya ''On Formally Undecidable Propositions of Principia Mathematica and Related Systems I'' (1931);
dan (3) Post (1936) dan Turing (1936-7) dalam model mekanisme komputasi mereka.
'''[[Stephen C. Kleene]]''' didefinisikan sebagai "Thesis I" nya yang terkenal yang dikenal sebagai [[tesis Church-Turing]].
Tapi dia melakukan hal tersebut dalam konteks berikut (penebalan dari aslinya):
:"12. '''Teori-teori algoritma'''... Dalam menyiapkan sebuah teori algoritma yang komplit, apa yang kita lakukan adalah mendeskripsikan sebuah prosedur, yang dapat dilakukan untuk setiap kumpulan nilai dari variabel-variabel tunggal, yang mana prosedur berhenti dan dengan cara tersebut dari hasilnya kita bisa membaca sebuah jawaban tertentu, "ya" atau tidak", untuk pertanyaan "apakah nilai predikat benar?"" (Kleene 1943:273)
=== Sejarah setelah 1950 ===
Sejumlah usaha telah diarahkan keperbaikan lebih jauh dari definisi dari "algoritma", dan aktivitas tersebut masih sedang berjalan karena isu-isu yang mengelilingi, terutama, [[fondasi matematika]] (khususnya [[tesis Church-Turing]]) dan [[filsafat pikiran]] (khususnya argumen menyangkut [[kecerdasan buatan]]).
Lebih lanjut, lihat [[karakterisasi algoritma]].
== Lihat juga ==
<div style="-moz-column-count:3; column-count:3;">
* [[Mesin abstrak]]
* [[Rekayasa algoritma]]
* [[Komposisi algoritmik]]
* [[Sintesis algoritmik]]
* [[Algoritma trading]]
* [[Sampah masuk, sampah keluar]]
* ''[[Pendahuluan untuk Algoritma]]''
* [[Daftar topik algoritma umum]]
* [[Daftar publikasi penting dalam ilmu komputer teoritis#Algoritma | Daftar publikasi penting dalam ilmu komputer teoritis - Algoritma]]
* [[Numerical Mathematics Consortium]]
* [[Teori komputasi]]
** [[Teori komputabilitas]]
** [[Teori kompleksitas Komputasi]]
</div>
== Catatan ==
{{Reflist|30em}}
== Referensi ==
{{refbegin|30em}}
* Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, ''Transactions of the American Mathematical Society'' 92, pp. 85–105
* Bell, C. Gordon and Newell, Allen (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. ISBN 0-07-004357-4.
* {{Cite journal|author1-link=Andreas Blass|first1=Andreas|last1=Blass|author2-link=Yuri Gurevich|first2=Yuri|last2=Gurevich|year=2003|url=http://research.microsoft.com/~gurevich/Opera/164.pdf|title=Algorithms: A Quest for Absolute Definitions|journal= Bulletin of European Association for Theoretical Computer Science|volume= 81}} Includes an excellent bibliography of 56 references.
* {{cite book| last1 = Boolos| first1 = George| last2 = Jeffrey| first2 = Richard| title = Computability and Logic| edition = 4th| year = 1974, 1999| publisher = Cambridge University Press, London| isbn = 0-521-20402-X| ref = harv| author1-link = George Boolos| author2-link = Richard Jeffrey }}: cf. Chapter 3 ''Turing machines'' where they discuss "certain enumerable sets not effectively (mechanically) enumerable".
* {{cite book| last = Burgin| first = Mark| title = Super-Recursive Algorithms| year = 2004| publisher = Springer| isbn = 978-0-387-95569-8 }}
* Campagnolo, M.L., [[Cris Moore|Moore, C.]], and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In ''Proc. of the 4th Conference on Real Numbers and Computers'', Odense University, pp. 91–109
* {{Cite journal|last=Church|first=Alonzo|authorlink=Alonzo Church|title=An Unsolvable Problem of Elementary Number Theory|journal=The American Journal of Mathematics|volume=58|pages= 345–363|year=1936a|doi=10.2307/2371045|issue=2|jstor=2371045}} Reprinted in ''The Undecidable'', p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (''The Undecidable'') where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.
* {{Cite journal|last=Church|first=Alonzo|authorlink=Alonzo Church|title=A Note on the Entscheidungsproblem|journal=The Journal of Symbolic Logic|volume=1|year=1936b|pages=40–41|doi=10.2307/2269326|issue=1|jstor=2269326}} {{cite journal|last=Church|first=Alonzo|title=Correction to a Note on the Entscheidungsproblem|journal=The Journal of Symbolic Logic|volume=1|year=1936|pages=101–102|doi=10.2307/2269030|issue=3|jstor=2269030}} Reprinted in ''The Undecidable'', p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
* {{cite book| last = Daffa'| first = Ali Abdullah al-| title = The Muslim contribution to mathematics| year = 1977| publisher = Croom Helm| location = London| isbn = 0-85664-464-1 }}
* {{cite book| last = Davis| first = Martin| authorlink = Martin Davis| title = The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions| year = 1965| publisher = Raven Press| location = New York| isbn = 0-486-43228-9 }} Davis gives commentary before each article. Papers of [[Gödel]], [[Alonzo Church]], [[Alan Turing|Turing]], [[J. Barkley Rosser|Rosser]], [[Kleene]], and [[Emil Post]] are included; those cited in the article are listed here by author's name.
* {{cite book| last = Davis| first = Martin| authorlink = Martin Davis| title = Engines of Logic: Mathematicians and the Origin of the Computer| year = 2000| publisher = W. W. Nortion| location = New York| isbn = 0-393-32229-7 }} Davis offers concise biographies of [[Gottfried Leibniz|Leibniz]], [[George Boole|Boole]], [[Gottlob Frege|Frege]], [[Georg Cantor|Cantor]], [[David Hilbert|Hilbert]], Gödel and Turing with [[John von Neumann|von Neumann]] as the show-stealing villain. Very brief bios of [[Joseph-Marie Jacquard]], [[Babbage]], [[Ada Lovelace]], [[Claude Shannon]], [[Howard Aiken]], etc.
* {{DADS|algorithm|algorithm}}
* {{cite book| last = Dennett| first = Daniel| authorlink = Daniel Dennett| title = Darwin's Dangerous Idea| year = 1995| publisher = Touchstone/Simon & Schuster| location = New York| isbn = 0-684-80290-2 }}
* [[Yuri Gurevich]], [http://research.microsoft.com/~gurevich/Opera/141.pdf ''Sequential Abstract State Machines Capture Sequential Algorithms''], ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77–111. Includes bibliography of 33 sources.
* {{Cite journal|last=Kleene C.|first=Stephen|authorlink=Stephen Kleene |title=General Recursive Functions of Natural Numbers|journal=Mathematische Annalen|volume=112|pages=727–742|year=1936
| doi = 10.1007/BF01565439|issue=5}} Presented to the American Mathematical Society, September 1935. Reprinted in ''The Undecidable'', p. 237ff. Kleene's definition of "general recursion" (known now as mu-recursion) was used by Church in his 1935 paper ''An Unsolvable Problem of Elementary Number Theory'' that proved the "decision problem" to be "undecidable" (i.e., a negative result).
* {{Cite journal|last=Kleene C.|first=Stephen|authorlink=Stephen Kleene |title= Recursive Predicates and Quantifiers|journal=American Mathematical Society Transactions|volume=54|pages=41–73|year=1943 |doi= 10.2307/1990131|issue=1|jstor=1990131}} Reprinted in ''The Undecidable'', p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis"(Kleene 1952:317) (i.e., the [[Church thesis]]).
* {{cite book| last = Kleene| first = Stephen C.| authorlink = Kleene| title = Introduction to Metamathematics| edition = Tenth Edition 1991| year = First Edition 1952| publisher = North-Holland Publishing Company| isbn = 0-7204-2103-9 }} Excellent—accessible, readable—reference source for mathematical "foundations".
* {{cite book| last = Knuth| first = Donald| authorlink = Donald Knuth| title = Fundamental Algorithms, Third Edition| year = 1997| publisher = Addison–Wesley| location = Reading, Massachusetts| isbn = 0-201-89683-4 }}
* {{Cite book|last=Knuth|first=Donald|authorlink=Donald Knuth|title=Volume 2/Seminumerical Algorithms, The Art of Computer Programming First Edition|publisher=Addison–Wesley|location=Reading, Massachusetts|year=1969|isbn= }}
* Kosovsky, N. K. ''Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms'', LSU Publ., Leningrad, 1981
* {{Cite journal|last=Kowalski|first=Robert|authorlink=Robert Kowalski|title=Algorithm=Logic+Control|journal=[[Communications of the ACM]]|volume=22|issue=7|pages=424–436|year=1979|doi=10.1145/359131.359136}}
* [[A. A. Markov]] (1954) ''Theory of algorithms''. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
* {{cite book| last = Minsky| first = Marvin| authorlink = Marvin Minsky| title = Computation: Finite and Infinite Machines| edition = First| year = 1967| publisher = Prentice-Hall, Englewood Cliffs, NJ| isbn = 0-13-165449-7 }} Minsky expands his "...idea of an algorithm—an effective procedure..." in chapter 5.1 ''Computability, Effective Procedures and Algorithms. Infinite machines."
* {{Cite journal|last=Post|first=Emil|authorlink=Emil Post|title=Finite Combinatory Processes, Formulation I |journal=The Journal of Symbolic Logic |volume=1 |year=1936 |pages=103–105 |doi=10.2307/2269031 |issue=3 |jstor=2269031}} Reprinted in ''The Undecidable'', p. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called [[Church–Turing thesis]].
* {{Cite book|last=Rogers, Jr|first=Hartley|title=Theory of Recursive Functions and Effective Computability|publisher=The MIT Press|year=1987|isbn=0-262-68052-1 (pbk.)}}
* {{Cite journal|last=Rosser|first=J.B.|authorlink=J.B. Rosser|title=An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem|journal=Journal of Symbolic Logic|volume= 4 |year=1939}} Reprinted in ''The Undecidable'', p. 223ff. Herein is Rosser's famous definition of "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (p. 225–226, ''The Undecidable'')
* {{Cite book|last=Scott|first=Michael L.|title=Programming Language Pragmatics |edition=3rd |publisher=Morgan Kaufmann Publishers/Elsevier|year=2009|isbn=978-0-12-374514-9}}
* {{cite book| last = Sipser| first = Michael| title = Introduction to the Theory of Computation| year = 2006| publisher = PWS Publishing Company| isbn = 0-534-94728-X }}
* {{Cite book|last=Stone|first=Harold S.|title=Introduction to Computer Organization and Data Structures|edition=1972|publisher=McGraw-Hill, New York|isbn=0-07-061726-0|year=1972}} Cf. in particular the first chapter titled: ''Algorithms, Turing Machines, and Programs''. His succinct informal definition: "...any sequence of instructions that can be obeyed by a robot, is called an ''algorithm''" (p. 4).
* {{cite book| last = Tausworthe| first = Robert C| title = Standardized Development of Computer Software Part 1 Methods| year = 1977| publisher = Prentice-Hall, Inc.| location = Englewood Cliffs NJ| isbn = 0-13-842195-1 }}
* {{Cite journal|last=Turing|first=Alan M.|authorlink=A. M. Turing|title=On Computable Numbers, With An Application to the Entscheidungsproblem|journal=[[Proceedings of the London Mathematical Society]], Series 2|volume=42|pages= 230–265 |year=1936–7|doi=10.1112/plms/s2-42.1.230 }}. Corrections, ibid, vol. 43(1937) pp. 544–546. Reprinted in ''The Undecidable'', p. 116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK.
* {{Cite journal|last=Turing|first=Alan M.|authorlink=A. M. Turing|title=Systems of Logic Based on Ordinals|journal=Proceedings of the London Mathematical Society, Series 2|volume=45|pages=161–228|year=1939|doi=10.1112/plms/s2-45.1.161}} Reprinted in ''The Undecidable'', p. 155ff. Turing's paper that defined "the oracle" was his PhD thesis while at Princeton USA.
* [[United States Patent and Trademark Office]] (2006), [http://www.uspto.gov/web/offices/pac/mpep/documents/2100_2106_02.htm ''2106.02 **>Mathematical Algorithms: 2100 Patentability''], Manual of Patent Examining Procedure (MPEP). Latest revision August 2006
=== Referensi tambahan ===
* {{cite book| last = Bolter| first = David J.| title = Turing's Man: Western Culture in the Computer Age| edition = 1984| year = 1984| publisher = The University of North Carolina Press, Chapel Hill NC| isbn = 0-8078-1564-0 }}, ISBN 0-8078-4108-0 pbk.
* {{cite book| last = Dilson| first = Jesse| authorlink = Dilson| title = The Abacus| edition = (1968,1994)| year = 2007| publisher = St. Martin's Press, NY| isbn = 0-312-10409-X }}, ISBN 0-312-10409-X (pbk.)
* {{cite book| last = van Heijenoort| first = Jean| authorlink = van Heijenoort| title = From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931| edition = (1967)| year = 2001| publisher = Harvard University Press, Cambridge, MA| isbn = 0-674-32449-8 }}, 3rd edition 1976[?], ISBN 0-674-32449-8 (pbk.)
* {{cite book| last = Hodges| first = Andrew| title = Alan Turing: The Enigma| edition = (1983)| year = 1983| publisher = Simon and Schuster, New York| isbn = 0-671-49207-1 }}, ISBN 0-671-49207-1. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
{{refend}}
== Bacaan lebih lanjut ==
{{refbegin}}
* {{cite book| author = Jean Luc Chabert| title = A History of Algorithms: From the Pebble to the Microchip| year = 1999| publisher = Springer Verlag| isbn = 978-3-540-63369-3 }}
* {{cite book| title = Algorithmics.: The Spirit of Computing.| year = 2004| publisher = Addison-Wesley| isbn = 978-0-321-11784-7 }}
* [[Donald Knuth|Knuth, Donald E.]] (2000). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. Stanford, California: Center for the Study of Language and Information.
* Knuth, Donald E. (2010). ''[http://www-cs-faculty.stanford.edu/~uno/da.html Selected Papers on Design of Algorithms]''. Stanford, California: Center for the Study of Language and Information.
* {{cite book| last = Berlinski| first = David| title = The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer| year = 2001| publisher = Harvest Books| isbn = 978-0-15-601391-8 }}
* {{cite book|author = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein| title = Introduction To Algorithms, Third Edition| year = 2009| publisher = MIT Press | isbn =978-0262033848 }}
{{refend}}
== Tautan luar ==
{{wiktionary}}
{{wikibooks|Algorithma}}
{{WVD}}
* {{springer|title=Algorithm|id=p/a011780}}
* {{dmoz|Computers/Algorithms/|Algorithms}}
* {{MathWorld | urlname=Algorithm | title=Algorithm}}
* [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures]—[[National Institute of Standards and Technology]]
* [http://www.softpanorama.org/Algorithms/index.shtml Algorithms and Data Structures by Dr Nikolai Bezroukov]
; Algorithm repositories
* [http://www.cs.sunysb.edu/~algorith/ The Stony Brook Algorithm Repository]—[[State University of New York at Stony Brook]]
* [http://www.netlib.org/ Netlib Repository]—[[University of Tennessee]] and [[Oak Ridge National Laboratory]]
* [http://calgo.acm.org/ Collected Algorithms of the ACM]—[[Association for Computing Machinery]]
* [http://www-cs-staff.stanford.edu/~knuth/sgb.html The Stanford GraphBase]—[[Stanford University]]
* [http://www.combinatorica.com/ Combinatorica]—[[University of Iowa]] and [[State University of New York at Stony Brook]]
* [http://www.algorithmic-solutions.com/ Library of Efficient Datastructures and Algorithms (LEDA)]—previously from [[Max-Planck-Institut für Informatik]]
* [http://www.keithschwarz.com/interesting/ Archive of Interesting Code]
* [http://allmyalgorithms.org A semantic wiki to collect, categorize and relate all algorithms and data structures]
; Lecture notes
* [http://compgeom.cs.uiuc.edu/~jeffe//teaching/algorithms/ Algorithms Course Materials]. Jeff Erickson. [[University of Illinois]].
; Community
* [https://plus.google.com/communities/101392274103811461838 Algorithms] on [[Google+]]
[[Kategori:Algoritma| ]]
[[Kategori:Logika matematika]]
[[Kategori:Ilmu komputer teoritis]]
| 