Algoritma: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Menolak perubahan teks terakhir (oleh 180.214.232.87) dan mengembalikan revisi 8107105 oleh Relly Komaruzaman |
k Membatalkan 1 suntingan by 2404:8000:1025:2E9:A0F3:D6FC:3A89:FF6D (bicara) (TW) Tag: Pembatalan halaman dengan galat kutipan |
||
| (125 revisi perantara oleh 78 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:Euclid flowchart 1.png |jmpl| [[Diagram alur]] dari sebuah algoritma ([[Algoritma Euklides]]) untuk menghitung faktor persekutuan terbesar (f.p.b.) dari dua angka ''a'' dan ''b'' dalam lokasi bernama A dan B. Algoritma dijalankan dengan pengurangan berturut-turut dalam dua pengulangan: JIKA pengujian B >= A menghasilkan "ya" (atau benar) (lebih akuratnya ''angka'' ''b'' dalam lokasi B lebih besar atau sama dengan ''angka'' ''a'' dalam lokasi A) MAKA, algoritma menentukan B ← B - A (artinya angka ''b'' - ''a'' menggantikan ''b'' sebelumnya). Hal yang sama, JIKA A > B, MAKA A ← A - B. Proses tersebut berhenti saat (isi dari) B adalah 0, menghasilkan f.p.k. dalam A. (Algoritma tersebut diambil dari Scott 2009:13; simbol dan gaya penggambaran dari Tausworthe 1977).]]
Dalam [[matematika]] dan [[ilmu komputer]], '''algoritma''' adalah rangkaian terbatas dari instruksi-instruksi yang rumit, biasanya digunakan untuk menyelesaikan atau menjalankan suatu kelompok masalah [[komputasi]] tertentu. Algoritma digunakan sebagai spesifikasi untuk melakukan perhitungan dan pemrosesan [[data]]. Algoritma yang lebih mutakhir dapat melakukan [[deduksi]] otomatis (disebut sebagai penalaran otomatis) dan menggunakan tes matematis dan logis untuk mengarahkan eksekusi kode melalui berbagai rute (disebut sebagai pengambilan keputusan otomatis). Penggunaan karakteristik manusia sebagai deskriptor mesin secara metaforis telah dipraktekkan oleh [[Alan Turing]] dengan terminologi seperti "memory", "search" dan "stimulus".<ref>Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. Information: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247</ref>
Sebaliknya, [[heuristika]] adalah pendekatan untuk pemecahan masalah komputasi yang mungkin tidak sepenuhnya terspesifikasi atau tidak menjamin hasil yang benar atau optimal, terutama dalam ranah masalah komputasi yang mana tidak ada hasil yang benar atau optimal yang terdefinisi dengan baik.<ref>David A. Grossman, Ophir Frieder, ''Information Retrieval: Algorithms and Heuristics'', 2nd edition, 2004, {{isbn|1402030045}}</ref>
Sebagai metode yang efektif, algoritma dapat diekspresikan dalam jumlah ruang dan waktu yang terbatas,<ref>"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).</ref> dan dalam bahasa formal yang terdefinisi dengan baik<ref>Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).</ref> untuk menghitung suatu [[Fungsi (matematika)|fungsi]].<ref>"an algorithm is a procedure for computing a ''function'' (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).</ref> Dimulai dari tataran awal dan input awal (bisa jadi kosong),<ref>"An algorithm has [[zero]] or more inputs, i.e., [[Quantity|quantities]] which are given to it initially before the algorithm begins" (Knuth 1973:5).</ref> instruksi-instruksi yang ada menggambarkan sebuah komputasi yang, ketika dieksekusi, berjalan melalui sejumlah tataran dengan jumlah terhingga yang terdefinisi dengan baik,<ref>"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method{{'"}} (Knuth 1973:5).</ref> yang pada akhirnya menghasilkan "output"<ref>"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).</ref> dan berakhir pada tataran final akhir. Transisi dari satu tataran ke tataran berikutnya tidak selalu bersifat menentukan; beberapa algoritma, yang dikenal sebagai algoritma acak, menggabungkan input acak.<ref>Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2).</ref>
== Sejarah ==
Konsep algoritma telah ada sejak zaman prasejarah. Algoritma [[Aritmetika|aritmatika]], seperti algoritma divisi, digunakan oleh matematikawan [[Babilonia (kota kuno)|Babilonia]] kuno sekitar tahun 2500 [[SM]] dan matematikawan [[Mesir Kuno|Mesir]] sekitar tahun 1550 SM. Matematikawan [[Yunani Kuno|Yunani]] kemudian juga menggunakan algoritma pada 240 SM sebagaimana yang terdapat pada [[Tapis Eratosthenes]] untuk menemukan bilangan prima, dan [[Algoritma Euklides|Algoritma Euklides]] untuk menemukan pembagi persekutuan terbesar dari dua bilangan.<ref name="Cooke2005">{{cite book|last=Cooke|first=Roger L.|date=2005|title=The History of Mathematics: A Brief Course|url=https://archive.org/details/historyofmathema0000cook_o3g3|publisher=John Wiley & Sons|isbn=978-1-118-46029-0}}</ref> Matematikawan Arab seperti [[al-Kindi]] pada abad ke-9 menggunakan algoritma kriptografi untuk pemecahan kode, berdasarkan analisis frekuensi.
Kata algoritma berasal dari nama matematikawan [[Persia]] abad ke-9, [[Muḥammad bin Mūsā al-Khawārizmī|Muḥammad bin Mūsā al-Khwārizmī]], yang [[nisbah]]-nya (yang mengidentifikasikannya sebagai seseorang yang berasal dari [[Khwarezmia]]) dilatinkan sebagai Algoritmi (bahasa Persia yang diarabkan: الخوارزمی sekitar: 780-850).<ref>{{cite web|title=Al-Khwarizmi biography|url=http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Khwarizmi.html|website=www-history.mcs.st-andrews.ac.uk|archive-url=https://web.archive.org/web/20190802091553/http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Khwarizmi.html|archive-date=August 2, 2019|access-date=May 3, 2017|url-status=live}}</ref><ref>{{cite web|title=Etymology of algorithm|url=http://chambers.co.uk/search/?query=algorithm&title=21st|website=Chambers Dictionary|archive-url=https://web.archive.org/web/20190331204600/https://chambers.co.uk/search/?query=algorithm&title=21st|archive-date=March 31, 2019|access-date=December 13, 2016|url-status=live}}</ref> Namanya bermakna 'yang berasal dari (daerah) [[Khwarezmia]]', sebuah daerah yang dulunya merupakan bagian dari [[Iran Raya]] dan sekarang sebagai bagian dari [[Uzbekistan]].<ref name="Hogendijk2">{{cite journal|last=Hogendijk|first=Jan P.|year=1998|title=al-Khwarzimi|url=http://www.kennislink.nl/web/show?id=116543|journal=Pythagoras|volume=38|issue=2|pages=4–5|archive-url=https://web.archive.org/web/20090412193516/http://www.kennislink.nl/web/show?id=116543|archive-date=April 12, 2009|url-status=dead}}</ref><ref name="Oaks2">{{cite web|last=Oaks|first=Jeffrey A.|title=Was al-Khwarizmi an applied algebraist?|url=http://facstaff.uindy.edu/~oaks/MHMC.htm|publisher=[[University of Indianapolis]]|archive-url=https://web.archive.org/web/20110718094835/http://facstaff.uindy.edu/~oaks/MHMC.htm|archive-date=July 18, 2011|access-date=May 30, 2008|url-status=dead|df=mdy-all}}</ref> Sekitar tahun 825, Al-Khwarizmi menulis sebuah risalah [[Bahasa Arab|berbahasa Arab]] tentang [[sistem angka Hindu-Arab]], yang diterjemahkan ke dalam [[bahasa Latin]] selama abad ke-12. Naskah ini dimulai dengan frasa Dixit Algorizmi ('Maka berkatalah Al-Khwarizmi'), di mana "Algorizmi" di sini adalah [[Latinisasi]] penerjemah akan nama Al-Khwarizmi.<ref>{{cite book|last=Brezina|first=Corona|year=2006|url=https://books.google.com/books?id=955jPgAACAAJ|title=Al-Khwarizmi: The Inventor Of Algebra|publisher=The Rosen Publishing Group|isbn=978-1-4042-0513-0}}</ref> Bukunya yang bernama Aljabar menjadi salah satu buku matematikawan yang paling banyak dibaca di Eropa pada abad pertengahan.<ref>[http://www-history.mcs.st-and.ac.uk/Extras/Boyer_Foremost_Text.html Foremost mathematical texts in history] {{Webarchive|url=https://web.archive.org/web/20110609224820/http://www-history.mcs.st-and.ac.uk/Extras/Boyer_Foremost_Text.html|date=June 9, 2011}}, according to [[Carl B. Boyer]].</ref> Dalam bahasa Latin abad pertengahan, kata ''algorismus,'' yang merupakan pengadaptasian dari namanya, menjadi kata yang bermakna "sistem bilangan desimal".<ref>{{Citation|title=algorismic|url=https://www.thefreedictionary.com/algorismic|work=The Free Dictionary|access-date=2019-11-14|archive-url=https://web.archive.org/web/20191221200124/https://www.thefreedictionary.com/algorismic|archive-date=December 21, 2019|url-status=live}}</ref> Pada abad ke-15, di bawah pengaruh kata Yunani ἀριθμός (arithmos), 'angka' (lih. 'aritmatika'), kata Latin-nya diubah menjadi algorithmus.<ref>''[[Oxford English Dictionary]]'', Third Edition, 2012 [http://www.oed.com/view/Entry/4959 ''s.v.'']</ref> Dalam [[bahasa Inggris]], kata algorithm pertama kali digunakan pada sekitar tahun 1230 dan kemudian oleh [[Geoffrey Chaucer|Chaucer]] pada 1391. Bahasa Inggris mengadopsi istilah tersebut dari [[bahasa Prancis]], akan tetapi baru pada abad ke-19 lah kata "algorithm" mulai memiliki makna seperti sekarang yang ada dalam bahasa Inggris modern.<ref>{{Cite journal|last=Mehri|first=Bahman|date=2017|title=From Al-Khwarizmi to Algorithm|journal=Olympiads in Informatics|volume=11|issue=2|pages=71–74|doi=10.15388/ioi.2017.special.11}}</ref>
Matematika [[India]] pada awalnya sebagian besar berbentuk algoritmik. Algoritma yang mewakili tradisi matematika India berkisar dari Śhulba Sūtrā dari beberapa abad sebelum masehi hingga teks-teks abad pertengahan dari Sekolah Kerala akan Astronomi dan Matematika.<ref>{{cite book|last1=Sriram|first1=M. S.|date=2005|title=Contributions to the History of Indian Mathematics|publisher=Springer|isbn=978-93-86279-25-5|editor1-last=Emch|editor1-first=Gerard G.|page=153|language=en|chapter=Algorithms in Indian Mathematics|editor2-last=Sridharan|editor2-first=R.|editor3-last=Srinivas|editor3-first=M. D.|chapter-url=https://books.google.com/books?id=qfJdDwAAQBAJ&pg=PA153}}</ref>
Pemakaian awal lainnya dari kata ini berasal dari tahun 1240, dalam sebuah [[Transmisi manual|manual]] berjudul Carmen de Algorismo yang disusun oleh Alexandre de Villedieu. Yang kalimatnya diawali dengan:
{{blockquote|''Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.''}}
yang bermakna:
{{blockquote|Algorisme adalah ilmu yang saat ini kita gunakan untuk menghitung dengan angka-angka India, yang jumlahnya ada dua kali lima (sepuluh).}}
Puisi ini panjangnya beberapa ratus baris dan merangkum ilmu menghitung dengan angka-angka yang diadopsi dari [[India]].<ref>{{Cite web|title=Abu Jafar Muhammad ibn Musa al-Khwarizmi|url=http://members.peak.org/~jeremy/calculators/alKwarizmi.html|website=members.peak.org|archive-url=https://web.archive.org/web/20190821232118/http://members.peak.org/~jeremy/calculators/alKwarizmi.html|archive-date=August 21, 2019|access-date=2019-11-14|url-status=live}}</ref>
Formalisasi parsial dari konsep algoritma modern dimulai dengan upaya untuk memecahkan ''Entscheidungsproblem'' (masalah pengambilan keputusan) yang diajukan oleh [[David Hilbert]] pada tahun 1928. Formalisasi selanjutnya dibingkai sebagai upaya untuk mendefinisikan "kalkulabilitas efektif"<ref>Kleene 1943 in Davis 1965:274</ref> atau "metode efektif".<ref>Rosser 1939 in Davis 1965:225</ref> Formalisasi tersebut termasuk fungsi rekursif [[Kurt Gödel|Gödel]]-Herbrand-Kleene pada tahun 1930, 1934 dan 1935, kalkulus lambda Alonzo Church pada tahun 1936, Formulasi 1 Emil Post pada tahun 1936, dan [[mesin Turing]]-nya [[Alan Turing]] pada tahun 1936-37 dan 1939.
== Definisi informal ==
{{about||penjelasan lebih rinci dari berbagai sudut pandang mengenai definisi "algoritma" |Karakterisasi Algoritma }}
Definisi informalnya bisa berarti "sekumpulan aturan yang secara tepat menentukan seurutan operasi".
<ref>Stone 1973:4</ref>
yang mengikutkan semua program komputer, termasuk program yang tidak melakukan perhitungan numerik.
Secara umum, sebuah program hanyalah sebuah algoritma jika ia akan berhenti nantinya.
<ref>
Stone secara sederhana membutuhkan "harus berhenti dalam sejumlah langkah" (Stone 1973:7-8).
</ref>
Sebuah contoh prototipikal dari suatu algoritma adalah [[algoritma Euclid]] untuk menentukan bilangan pembagi terbesar dari dua integer; sebagai contohnya (ada contoh yang lain) dijelaskan dengan [[diagram alur]] di atas dan sebagai contoh di bagian lanjut.
{{Harvtxt|Boolos|Jeffrey|1974, 1999}} memberikan sebuah makna informal dari kata algoritma dalam persamaan berikut:
<blockquote>
Tidak ada manusia yang dapat menulis begitu cepat, atau begitu lama, atau begitu kecil ("kecil, dan lebih kecil tanpa batas ... anda mungkin mencoba menulis di atas molekul, atom, elektron") untuk mencatat semua anggota dari kumpulan bilangan tak terbatas dengan menuliskan namanya, bergantian, dalam suatu notasi.
Tapi manusia bisa melakukan sesuatu yang sama bergunanya, pada kasus kumpulan bilangan tak terbatas: Mereka dapat memberikan ''instruksi jelas untuk menentukan anggota ke-'''n''' dari set'', untuk ''n'' terbatas acak.
Instruksi tersebut diberikan secara eksplisit, dalam bentuk yang ''dapat diikuti oleh mesin penghitung'', atau oleh ''manusia yang mampu melakukan hanya operasi-operasi dasar dengan simbol-simbol.''
<ref>
Boolos and Jeffrey 1974, 1999:19
</ref>
</blockquote>
Suatu "bilangan tak-terbatas" adalah bilangan yang elemen-elemenya bisa berkorespondensi satu-ke-satu dengan integer.
Maka, Boolos dan Jeffrey mengatakan bahwa sebuah algoritma berarti instruksi bagi sebuah proses yang "membuat" keluaran integer dari sebuah "masukan" ''acak'' integer yang, secara teori, bisa sangat besar.
Maka sebuah algoritma dapat berupa persamaan aljabar seperti '''y = m + n''' -- dua variabel masukan '''m''' dan '''n''' yang menghasikan keluaran '''y'''.
Tapi berbagai penulis yang mencoba mendefinisikan persamaan tersebut mengatakan bahwa kata algoritma mengandung lebih dari itu, sesuatu yang kurang lebih (untuk contoh penjumlahan):
:Instruksi rinci dan tepat (dalam bahasa yang dipahami oleh "komputer")<ref>cf Stone 1972:5</ref> untuk proses yang cepat, efisien, "baik"<ref>Knuth 1973:7 menyatakan: "Pada praktiknya kita tidak hanya menginginkan algoritma, kita menginginkan algoritam yang ''baik'' ... salah satu kriteria dari kebaikannya adalah lama waktu yang digunakan untuk menjalankan algoritma ... kriteria lainnya adalah kemampuan adaptasi dari algoritma ke komputer, kesederhanaan dan elegan, dll."</ref> yang menentukan "pergerakan" dari "komputer" (mesin atau manusia, dibekali dengan informasi dan kemampuan internal yang dibutuhkan)<ref>cf Stone 1973:6</ref> untuk menemukan, dekode, dan kemudian mengolah masukan integer/simbol '''m''' dan '''n''', simbol '''+''' dan '''=''' ... dan "secara efektif"<ref>Stone 1973:7-8 menyatakan bahwa harus ada, "... sebuah prosedur yang robot [yaitu komputer] bisa ikuti supaya dapat menentukan secara tepat bagaimana mengikuti instruksi tersebut." Stone menambahkan keterbatasan dari proses, dan kepastian (tidak memiliki kerancuan pada instruksi) pada definisi tersebut.</ref> menghasilkan, dalam waktu yang "masuk akal",<ref>Knuth, loc. cit</ref> keluaran integer '''y''' pada tempat dan format tertentu.
Konsep dari ''algoritma'' juga digunakan untuk mendefinisikan notasi dari [[desidabilitas (logika)|desidabilitas]].
Notasi tersebut adalah pusat untuk menjelaskan bagaimana [[sistem formal]] berasal dari sejumlah kecil [[aksioma]] dan aturan.
Dalam [[logika]], waktu dari sebuah algoritma untuk selesai tidak dapat dihitung, karena tidak berelasi dengan dimensi fisik kita.
Dari ketidakpastian tersebut, yang mengkarakteristikan pekerjaan yang sedang berjalan, timbulah ketidak-tersediannya definisi ''algoritma'' yang sesuai dengan konkret (pada tingkat tertentu) dan penggunaan secara abstrak dari istilah tersebut.
== Formalisasi ==
Algoritma sangat penting bagi cara komputer mengolah data.
Banyak [[program komputer]] mengandung algoritma memberikan rincian pada instruksi khusus yang komputer harus lakukan (dengan urutan tertentu) untuk menjalankan pekerjaan tertentu, seperti menghitung gaji karyawan atau mencetak kartu rapor siswa.
Maka, sebuah algoritma bisa dianggap sebagai urutan operasi yang bisa disimulasikan oleh sebuah sistem [[Kelengkapan Turing|Turing-lengkap]].
Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):
<blockquote>
Minsky: "Tapi kita juga menjaga, dengan Turing ... bahwa setiap prosedur yang "secara alami" disebut efektif, bisa dinyatakan oleh mesin (sederhana).
Walaupun tampaknya ekstrem, alasan tersebut ... sukar disanggah".
<ref name="Minsky 1967:105">
'''Minsky''' 1967:105</ref>
</blockquote>
<blockquote>
Gurevich: "... argumen informal Turing untuk menyokong tesis ini membenarkan tesis yang lebih kuat: setiap algoritma bisa disimulasikan oleh sebuah mesin Turing ... menurut Savage [1987], sebuah algoritma adalah sebuah proses penghitungan yang ditentukan oleh sebuah mesin Turing".
<ref>
Gurevich 2000:1, 3
</ref>
</blockquote>
Biasanya, bila sebuah algoritma dihubungkan dengan pengolahan informasi, data dibaca dari sumber masukan, ditulis ke perangkat keluaran, dan/atau disimpan untuk pengolahan selanjutnya.
Data simpanan dianggap sebagai bagian dari keadaan internal dari entitas yang melakukan algoritma.
Pada praktiknya, keadaan tersebut disimpan pada satu atau lebih [[struktur data]].
Untuk beberapa proses komputasi, algoritma harus ditentukan secara teliti: dijabarkan dengan cara ia bakal berlaku untuk semua kemungkinan yang dapat timbul.
Yaitu, setiap langkah tambahan harus secara sistematis dihadapi, kasus-per-kasus;
Kriteria bagi setiap kasus harus jelas (dan bisa dihitung).
Karena sebuah algoritma adalah kumpulan dari langkah-langkah yang tepat, urutan dari komputasi selalu penting bagi berfungsinya algoritma.
Instruksi biasanya diasumsikan terdaftar secara eksplisit, dan dijelaskan dimulai "dari atas" dan terus "ke bawah", sebuah gambaran yang dijelaskan secara formal oleh ''[[alur kontrol]]''
Sejauh ini, diskusi tentang formalisasi algoritma telah mengasumsikan premis dari [[pemrograman imperatif]].
Hal ini merupakan konsepsi umum, yang mencoba menjelaskan sebuah pekerjaan dalam makna diskrit dan "mekanis".
Keunikan dari konsepsi formalisasi algoritma adalah [[operasi penetapan]], mengatur nilai dari sebuah variabel.
Ia berasal dari intuisi "[[ingatan]]" sebagai kertas buram.
Contoh operasi penetapan tersebut ada di bawah.
Untuk konsepsi yang lain dari apa yang membentuk sebuah algoritma lihat [[pemrograman fungsional]] dan [[pemrograman logika]].
=== Menggambarkan algoritma ===
Algoritma dapat digambarkan dengan banyak notasi, termasuk [[bahasa alamiah]], [[pseudokode]], [[diagram alur]], [[DRAKON|bagan drakon]], [[bahasa pemrograman]] atau [[tabel kontrol]] (diproses oleh [[penerjemah (komputasi)|penerjemah]]).
Ekspresi bahasa alamiah terhadap algoritma condong lebih banyak dan rancu, dan jarang digunakan untuk algoritma yang kompleks dan teknis.
Pseudokode, diagram alur, bagan drakon, dan tabel kontrol adalah cara yang terstruktur untuk menggambarkan algoritma yang mencegah banyaknya kerancuan pada pernyataan-pernyataan bahasa alamiah.
Bahasa pemrograman ditujukan untuk mengekspresikan algoritma dalam sebuah bentuk yang dapat dieksekusi oleh komputer, tetapi sering kali digunakan sebagai suatu cara untuk menentukan atau mendokumentasikan algoritma.
Ada banyak macam kemungkinan representasi dan seseorang dapat mengekspresikan sebuah program [[mesin Turing]] sebagai urutan dari tabel-tabel mesin (lihat lebih lanjut di [[mesin kondisi-terbatas]], [[tabel transisi kondisi]] dan [[tabel kontrol]]), sebagai diagram alur dan bagan drakon (lihat lebih lanjut di [[diagram kondisi]]), atau sebagai bentuk [[kode mesin]] atau [[kode assembly]] dasar yang dikenal "kumpulan lipat empat" (lihat lebih lanjut di [[mesin Turing]]).
Representasi dari algoritma dapat dikelompokan ke dalam tiga tingkatan dari deskripsi mesin Turing:
<ref>Sipser 2006:157</ref>
; '''1 Deskripsi tingkat-tinggi'''
: "... ditujukan untuk menjelaskan algoritma, menghiraukan rincian implementasi. Pada tingkat ini kita tidak perlu menyebutkan bagaimana mesin mengatur perangkat pita atau kepala pita rekam."
; '''2 Deskripsi implementasi'''
: "... digunakan untuk menjelaskan cara mesin Turing menggunakan kepalanya dan cara menyimpan data. Pada tingkat ini kita tidak memberikan secara rinci kondisi atau fungsi transisi."
; '''3 Deskripsi formal'''
: Lebih rinci, "tingkat paling rendah", menjelaskan "tabel kondisi" dari mesin Turing.
Sebagai contoh dari algoritma sederhana "Penjumlahan m+n" dijelaskan dalam tiga tingkatan tersebut lihat [[contoh algoritma]].
== Implementasi ==
Kebanyakan algoritma ditujukan untuk diimplementasikan sebagai [[program komputer]].
Namun, algoritma juga diimplementasikan dengan tujuan lain, seperti dalam [[jaringan saraf]] biologis (sebagai contohnya, [[otak manusia]] yang mengimplementasikan [[aritmetika]] atau sebuah serangga yang melihat makanan), dalam [[sirkuit elektris]], atau dalam sebuah perangkat mekanis.
== Algoritma komputer ==
[[Berkas:Euclid's algorithm structured blocks 1.png |jmpl|ka|493x493px|Contoh diagram alur dari [[Teorema program terstruktur|struktur Bohm-Jacopini]]: URUTAN (segi empat), WHILE-DO dan IF-THEN-ELSE. Ketiga struktur dibentuk dari kondisi primitif GOTO (<code> IF ''test''=true THEN GOTO step xxx </code>) (wajik), GOTO tak bersyarat (segi empat), berbagai operator penetapan (segi empat), dan HALT (bujursangkar). Memasukan struktur tersebut ke dalam blok-penetapan menghasilkan diagram yang kompleks (cf Tausworthe 1977:100,114).]]
Dalam [[sistem komputer]], sebuah algoritma pada dasarnya adalah instansi dari [[logika]] ditulis dalam [[perangkat lunak]] oleh pengembang perangkat lunak supaya efektif untuk komputer yang "ditargetkan" untuk mesin tertentu untuk menghasilkan ''keluaran'' dari ''masukan'' yang diberikan (kemungkinan nul).
''Program yang "elegan" (padat), program yang "baik" (cepat)'': Pernyataan dari "sederhana dan elegan" muncul secara informal dalam buku Knuth dan dalam Chaitin:
:Knuth: "... kita menginginkan algoritma yang ''baik'' dalam definisi estetika sederhana. Salah satu kriterianya ... adalah waktu yang dibutuhkan untuk berjalannya algoritma ... Kriteria yang lain adalah adaptasi dari algoritma ke komputer, kesederhanaan dan elegan, dll"<ref>Knuth 1973:7</ref>
:Chaitin: "... sebuah program adalah 'elegan'', maksud saya adalah ia merupakan program terkecil untuk menghasilkan keluaran."<ref>Chaitin 2005:32</ref>
Chaitin membuka definisinya dengan: "Saya akan perlihatkan bahwa anda tidak dapat membuktikan sebuah program adalah 'elegan'"—bukti tersebut akan menyelesaikan [[permasalahan perhentian]] (ibid).
''Algoritma terhadap fungsi yang dapat dihitung oleh algoritma'': Untuk sebuah fungsi bisa ada beberapa algoritma.
Hal ini benar, bahkan tanpa mengembangkan kumpulan instruksi yang ada bagi programmer.
Rogers mengamati bahwa "Sangat ... penting untuk membedakan antara pengertian ''algoritma'', misalnya prosedur dan pernyataan ''fungsi yang dihitung oleh algoritma'', misalnya pemetaan hasil dari prosedur.
Fungsi yang sama bisa memiliki beberapa algoritma berbeda".
<ref>
Rogers 1987:1-2
</ref>
Sayangnya ada pertukaran antara kebaikan (kecepatan) dan elegan (kepadatan) -- sebuah program yang elegan bisa melakukan lebih banyak langkah untuk menyelesaikan sebuah komputasi daripada yang kurang elegan.
Sebuah contoh yang menggunakan algoritma Euclid bisa dilihat di bawah.
''Komputer (dan komputor), model dari komputasi'': Sebuah komputer (atau manusia "komputor"
<ref>
Dalam esainya "Calculations by Man and Machine: Conceptual Analysis" Seig 2002:390 memuji perbedaan ini oleh Robin Gandy, cf Wilfred Seig, dll., 2002 ''Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman'', Association for Symbolic Logic, A. K Peters Ltd, Natick, MA.
</ref>
)
adalah tipe terbatas dari mesin, sebuah "perangkat mekanis deterministik diskrit"
<ref>
cf gandy 1980:126, robin gandy ''church's thesis and principles for mechanisms'' appearing on pp. 123–148 in j. barwise et al. 1980 ''the kleene symposium'', north-holland publishing company.
</ref>
yang secara buta mengikuti instruksinya.<ref>
Sebuah "robot": "Sebuah komputer adalah sebuah robot yang melakukan setiap tugas yang dapat dijelaskan sebagai urutan dari instruksi." cf Stone 1972:3
</ref>
Model primitif dari Melzak dan Lambek
<ref>
"abacus"-nya Lambek adalah "sejumlah lokasi tak terbatas yang bisa dihitung (lubang, kabel, dll.) berikut dengan persediaan penghitung yang tak terbatas (kerikil, remah roti, dll).
Lokasinya bisa dibedakan, penghitungnya tidak".
Lubangnya memiliki kapasitas tak terbatas, dan digerakan oleh agen yang memahami dan mampu menjalankan sejumlah instruksi" (Lambek 1961:295).
Lambek mengacu Melzak yang mendefinisikan mesin-Q nya sebagai "sejumlah lokasi yang besar tanpa batas ... persediaan penghitung yang tanpa batas yang terdistribusi di antara lokasi-lokasi tersebut, sebuah program, dan sebuah operator yang tujuan satu-satunya yaitu menjalankan program." (Melzak 1961:283).
B-B-J (loc. cit.) menambahkan syarat bahwa lubang tersebut "mampu menyimpan sejumlah batu" (p. 46).
Melzak dan Lambek muncul di ''The Canadian Mathematical Bulletin'', vol. 4, no. 3, September 1961.
</ref>
mereduksi pemikiran tersebut menjadi empat elemen: (i) diskrit, ''lokasi'' yang bisa dibedakan,
(ii) diskrit, ''penghitung'' yang tak bisa dibedakan
<ref>
Jika tidak ada kebingungan yang dihasilkan, kata "penghitung" bisa dihiraukan, dan sebuah lokasi bisa dikatakan mengandung sebuah "angka".
</ref>
(iii) sebuah agen, dan
(iv) sebuah daftar instruksi yang ''efektif'' relatif terhadap kemampuan dari agen.
<ref>
"Kita mengatakan bahwa instruksi adalah ''efektif'' bila ada sebuah prosedur yang robot dapat ikuti supaya dapat menentukan secara tepat bagaimana mematuhi instruksi." (Stone 1972:6)
</ref>
Minsky menjelaskan variasi yang lebih sesuai dari model "abacus"-nya Lambek dalam "Basis [[Komputabilitas]] Paling Sederhana".
<ref>
cf Minsky 1967: Chapter 11 "Computer models" and Chapter 14 "Very Simple Bases for Computability" pp. 255–281 in particular
</ref>
[[Mesin Minsky]] memproses secara berurutan lewat lima (atau enam tergantung bagaimana seseorang menghitungnya) instruksi kecuali baik sebuah kondisi IF-THEN GOTO atau GOTO tak bersyarat mengubah alur program keluar dari urutan.
Selain HALT, mesin Minsky mengikutkan tiga operasi ''penetapan'' (penggantian, substitusi):
<ref>cf Knuth 1973:3.</ref>
ZERO (misalnya, isi dari lokasi diganti oleh 0: L ← 0), SUCCESSOR (misalnya, L ← L+1), dan DECREMENT (misalnya, L ← L-1).
<ref>
Tapi selalu diikuti oleh IF-THEN untuk menghindari pengurangan yang tidak sesuai.
</ref>
Jarang seorang programer harus menulis "kode" dengan kumpulan instruksi terbatas.
Tapi Minsky memperlihatkan (sebagaimana Melzak dan Lambek) bahwa mesinnya adalah [[Turing komplet]] dengan hanya empat ''tipe'' instruksi utama: GOTO kondisional, GOTO tak bersyarat, penetapan/penggantian/substitusi, dan HALT.
<ref>
Namun, beberapa instruksi penetapan berbeda (misalnya, DECREMENT, INCREMENT, dan ZERO/CLEAR/EMPTY untuk mesin Minsky) juga dibutuhkan untuk kekomplitan-Turing;
spesifikasi lengkapnya tergantung kepada perancang.
GOTO tak bersyarat cukup mudah; ia dapat dibentuk dengan menginisialisasi suatu lokasi tertentu dengan nol, misalnya, instruksi "Z ← 0";
oleh karena itu instruksi IF Z=0 THEN GOTO xxx adalah tak bersyarat.
</ref>
''Simulasi dari sebuah algoritma: bahasa komputer (komputor)'': Knuth menganjurkan pembaca bahwa "cara terbaik untuk belajar algoritma dalah mencobanya ... langsung ambil pulpen dan kertas dan bekerja lewat contoh".
<ref>Knuth 1973:4</ref>
Lalu bagaimana dengan simulasi atau eksekusi yang sebenarnya?
Programmer harus menerjemahkan algoritma ke dalam bahasa yang mana simulator/komputer/komputor dapat mengeksekusi ''secara efektif''.
Stone memberikan contoh dari hal ini: saat menghitung akar dari persamaan kuadrat si komputor harus tahu bagaimana mendapatkan akar kuadrat.
Jika tidak maka supaya algoritma dapat efektif ia harus menyediakan sejumlah aturan untuk mengekstrak akar kuadrat.
<ref>
Strone 1972:5. Metode untuk mendapatkan akar tidaklah biasa: lihat [[Metode untuk menghitung akar kuadrat]].
</ref>
Hal ini berarti programer harus tahu sebuah "bahasa" yang efektif relatif terhadap target pada agen komputasi (komputer/komputor).
Lalu model apa yang seharusnya digunakan untuk simulasi?
Van Emde Boas mengamati "bahkan bila kita mendasari [[Teori kompleksitas komputasi|teori kompleksitas]] dengan mesin abstrak bukannya mesin kongkrit, kesembarangan dari pemilihan model masih tetap ada.
Pada titik itulah mulainya pemikiran ''simulasi''".
<ref>
{{cite book
|last = Leeuwen
|first = Jan
|title = Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A
|url = http://books.google.com/?id=-X39_rA3VSQC
|year = 1990
|publisher = Elsevier
|isbn = 978-0-444-88071-0
|page = 85}}
</ref>
Bila kecepatan yang dihitung, jumlah instruksi berpengaruh.
Sebagai contohnya, subprogram dalam algoritma Euclid untuk menghitung sisa akan berjalan lebih cepat jika programmer memiliki instruksi "modulus" (sisa pembagian) bukannya dengan pengurangan (atau lebih parah: hanya "penurunan").
''Pemrograman terstruktur, struktur kanonikal'': Menurut [[Tesis Church-Turing]] setiap algoritma bisa dihitung dengan sebuah model yang dikenal [[Turing komplet]], dan menurut demonstrasi Minsky kekomplitan Turing membutuhkan hanya empat tipe instruksi—GOTO bersyarat, GOTO tak bersyarat, penetapan, HALT.
Kemeny dan Kurtz mengamati bahwa saat penggunaan GOTO tak bersyarat yang "tak disiplin" dan IF-THEN GOTO bersyarat bisa menghasilkan "[[kode spageti]]" seorang programer bisa menulis program terstruktur menggunakan instruksi tersebut;
di lain sisi "juga memungkinkan, dan tidak begitu sulit, untuk menulis sebuah program terstruktur yang buruk dalam sebuah bahasa terstruktur".
<ref>[[John G. Kemeny]] and [[Thomas E. Kurtz]] 1985 ''Back to Basic: The History, Corruption, and Future of the Language'', Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0.
</ref>
Tausworthe menambahkan tiga [[Teorema program terstruktur|struktur kanon Bohm-Jacopini]]:
<ref>Tausworthe 1977:101</ref>
SEQUENCE, IF-THEN-ELSE, dan WHILE-DO, dengan dua lagi: DO-WHILE dan CASE.
<ref>Tausworthe 1977:142</ref>
Keuntungan dari program terstruktur adalah ia cocok dengan [[pembuktian kebenaran]] menggunakan [[induksi matematika]].
<ref>
Knuth 1973 bagian 1.2.1, dikembangkan oleh Tausworthe 1977 di halaman 100ff dan Bab 9.1
</ref>
''Simbol diagram alur<ref>cf Tausworthe 1977</ref>'': Pembantu grafik yang disebut [[diagram alur]] memberikan suatu cara untuk menjelaskan dan mendokumentasikan sebuah algoritma (dan program komputer).
Seperti alur program dari mesin Minsky, sebuah diagram alur selalu mulai dari atas dan terus ke bawah.
Simbol utamanya hanya 4: arah panah memperlihatkan alur program, segi empat (SEQUENCE, GOTO), wajik (IF-THEN-ELSE), dan titik (OR).
Struktur kanonikal Bohm-Jacopini dibuat dari bentuk-bentuk primitif tersebut.
Sub-struktur bisa "bersarang" dalam segi empat hanya jika jalan keluar tunggal terjadi pada super-struktur.
Simbol dan penggunaannya untuk membangun struktur kanonikal diperlihatkan dalam diagram.
== Contoh ==
{{Further2|[[Contoh algoritma]]}}
=== Contoh Algoritma ===
[[Berkas:Sorting quicksort anim.gif |jmpl| Animasi dari [[algoritma quicksort]] mengurutkan larik dari nilai acak. Batang merah menandakan elemen pivot; pada awal animasi, elemen paling kanan dipilih sebagai pivot.]]
Salah satu dari algoritma sederhana adalah menemukan bilangan terbesar dalam sebuah deretan angka (tak berurut).
Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tetapi hanya sekali.
Dari hal ini munculah algoritma sederhana, yang bisa dinyatakan dalam kalimat bahasa deskripsi tingkat-tinggi, sebagai:
''Deskripsi tingkat-tinggi:''
# Jika tidak ada angka dalam deret makan tidak ada bilangan terbesar.
# Asumsikan item pertama dalam deret adalah yang terbesar.
# Untuk setiap sisa angka dalam deret, jika angka tersebut besar dari angka terbesar sekarang, anggap angka tersebut menjadi yang terbesar dalam deret.
# Bila tidak ada lagi angka yang tersisa pada deret untuk diperiksa, anggap angka terbesar sekarang menjadi angka yang terbesar dalam deret.
''Deskripsi (Quasi-)formal:''
Ditulis dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, berikut ini adalah kode formal dari algoritma dalam [[pseudokode]] atau [[kode pijin]]:
{{algorithm-begin|name=LargestNumber}}
Masukan: Deret angka ''L''.
Keluaran: Angka terbesar dalam daftar ''L''.
''terbesar'' ← ''L''<sub>null</sub>
'''untuk setiap''' ''item'' '''dalam''' ''L'', '''lakukan'''
'''jika''' ''item'' > ''terbesar'', '''maka'''
''terbesar'' ← ''item''
'''kembalikan''' ''terbesar''
{{algorithm-end}}
=== Algoritma Euclid ===
{{Further2|[[Algoritma Euklid]]}}
[[Berkas:Euclid's algorithm Book VII Proposition 2 2.png | 250px|jmpl|kiri| Contoh diagram dari algoritma Euclid dari T.L. Health 1908 dengan rincian tambahan. Euclid tidak sampai pada penghitungan ketiga dan tidak memberikan contoh numeris. Nocomachus memberikan contoh dari 49 dan 21: "Saya mengurangi yang kecil dari yang besar; 28 adalah yang kiri; kemudian saya kurangi lagi 21 (hal ini memungkinkan); tersisa 7, tetapi 7 tidak bisa dikurangi dari 7." Heath berkomentar bahwa, "Kalimat terakhir terdengar aneh, tetapi maknanya sangat jelas, begitu juga makna dari kalimat tentang mengakhiri 'dengan satu dan angka yang sama'."(Heath 1908:300).]]
Algoritma [[Euclid]] muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari ''[[Euclid's Elements|Elements]]''.
<ref>
Heath 1908:300; Hawking's Dover 2005 edisi diambil dari Heath.
</ref>
Euclid mengajukan permasalahan: "Ambil dua angka bukan prima, untuk mencari bilangan pembagi terbesar".
Dia menentukan "Sebuah angka [merupakan] besaran yang terdiri dari unit-unit": angka penghitung, integer positif kecuali 0.
Dan "mengukur" adalah menempatkan ukuran panjang terkecil ''s'' dengan tepat (''q'' kali) di antara ukuran terpanjang ''l'' sampai sisa ''r'' lebih kecil dari panjang terkecil ''s''.
<ref>
"'Biarkan CD, mengukur BF, meninggalkan FA kurang darinya.'
Hal ini merupakan singkatan cerdik untuk mengatakan, ukur pada BA panjang yang sama dengan CD sampai titik F sehingga sisa panjang FA kurang dari CD;
dengan kata lain, misalkan BF adalah yang kelipatan terbesar dari CD yang terdapat dalam BA"
(Heath 1908:297)
</ref>
Dalam dunia modern, sisa ''r = l - q*s'', ''q'' sebagai hasil bagi, atau sisa ''r'' adalah "modulus", bagian sisa-integer yang tersisa setelah pembagian.
<ref>
Untuk percobaan moden menggunakan pembagian dalam algoritma lihat Hardy dan Wright 1979:180, Knuth 1973:2 (Volume 1), ditambah diskusi tentang algoritma Euclid dalam Knuth 1969:293-297 (Volume 2).
</ref>
Supaya metode Euclid berhasil, panjang awalnya harus memenuhi dua kebutuhan:
(i) panjangnya tidak 0, DAN
(ii) hasil pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka adalah hasil pengurangan dari yang terbesar (cara lain, keduanya bisa sama sehingga pengurangan menghasilkan 0).
Pembuktian asli Euclid mengikutkan kebutuhan yang ketiga: kedua panjang bukanlah bilangan prima.
Euclid menentukan hal ini supaya dia bisa membentuk sebuah bukti [[reductio ad absurdum]] bahwa dua pembagi dua angka adalah yang ''terbesar''.
<ref>
Euclid mengungkapkan pertanyaan ini dalam Proposisi 1 nya.
</ref>
Walau algoritma Nicomachus sama dengan Euclid, bila kedua bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi terbesar.
Jadi untuk lebih jelasnya algoritma berikut adalah algoritma Nicomachus.
==== Contoh ====
[[File:Euclids-algorithm-example-1599-650.gif | 350px |jmpl|ka| Ekspresi grafik dari algoritma Euclid menggunakan contoh dengan 1599 dan 650.
<syntaxhighlight lang="text" highlight="1,5">
9778 = 650*2 + 299
650 = 299*2 + 52
299 = 52*5 + 39
52 = 39*1 + 13
39 = 13*3 + 0
</syntaxhighlight>]]
==== Bahasa komputer untuk algoritma Euclid ====
Hanya beberapa ''tipe'' instruksi yang dibutuhkan untuk mengeksekusi algoritma—beberapa tes logika (GOTO bersyarat), GOTO tak bersyarat, penetapan (penggantian), dan pengurangan.
* Sebuah ''lokasi'' disimbolkan dengan huruf besar, misalnya, S, A, dll.
* Kuantitas beragam (angka) dalam sebuah lokasi ditulis dengan huruf kecil dan (biasanya) dihubungkan dengan nama lokasi. Sebagai contohnya, lokasi L pada awal bisa mengandung angka ''l'' = 3009.
==== Program yang kurang elegan (inelegan) untuk algoritma Euclid ====
[[File:Euclid's algorithm Inelegant program 1.png|jmpl|163px|ka|"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, tetapi 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''':
{{vanchor|1|el1}} [Kedalam dua lokasi L dan S taruh angka ''l'' dan ''s'' yang merepresentasikan kedua panjang]:
INPUT L, S
{{vanchor|2|el2}} [Inisialisasi R: buat supaya sisa panjang ''r'' sama dengan panjang awal ''l'']
R ← L
'''E0: [Pastikan ''r'' ≥ ''s''.]'''
{{vanchor|3|el3}} [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|4]], [[#5|5]] dan [[#6|6]]:
GOTO step [[#6|6]]
ELSE
tukar isi R dan S.
{{vanchor|4|el4}} L ← R (langkah pertama ini berlebih, tetapi berguna untuk diskusi nanti).
{{vanchor|5|el5}} R ← S
{{vanchor|6|el6}} 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.
{{vanchor|7|el7}} IF S > R THEN
selesai mengukur jadi
GOTO [[#10|10]]
ELSE
ukur lagi,
{{vanchor|8|el8}} R ← R - S
{{vanchor|9|el9}} [Pengulangan-sisa]:
GOTO [[#7|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.
{{vanchor|10|el10}} IF R = 0 THEN
selesai jadi
GOTO langkah [[#15|15]]
ELSE
lanjut ke langkah [[#11|11]],
'''E3: [Interchange ''s'' dan ''r'']''': Sulitnya algoritma Euclid. Menggunakan sisa ''r'' untuk mengukur angka terkecil sebelumnya ''s'':; L sebagai lokasi sementara.
{{vanchor|11|el11}} L ← S
{{vanchor|12|el12}} R ← S
{{vanchor|13|el13}} S ← L
{{vanchor|14|el14}} [Ulang proses pengukuran]:
GOTO [[#7|7]]
'''OUTPUT''':
{{vanchor|15|el15}} [Selesai. S berisi faktor persekutuan terbesar]:
PRINT S
'''DONE''':
{{vanchor|16|el16}} 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 ←.
5 REM [[Algoritma 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
''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.
Hal ini bekerja karena, saat yang dikurang M lebih kecil pengurang S ( Selisih = pengurang - yang_di_kurang ), yang_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/program, mengikutkan hanya integer positif termasuk 0, maka kegagalan pada nol mengindikasikan bahwa algoritma (dan program [[instansi (ilmu komputer)|instansiasinya]]) adalah sebuah [[fungsi parsial]] bukannya [[fungsi total]].
Kesalahan yang terkenal karena eksepsi 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 "formulasi pembuktian-algoritma dalam makan asersi dan induksi" 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 metode Knuth di bab 9.1 dari ''Formal Proofs'' (pages 288–298).
</ref>
Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari pembuktian 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" dengan 13 instruksi.
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 sibuk]]), coba dan gagal, kecerdasan, kedalaman, penggunaan [[penalaran induktif]], dll.
Bisa diamati bahwa langkah 4, 5, dan 6 diulang pada langkah 11, 12, dan 13.
Pembandingan dengan "Elegan" menyediakan petunjuk langkah-langkah tersebut dengan langkah 2 dan 3 dapat dihilangkan.
Hal ini mereduksi 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 teoretis 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 mirip 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) tetapi 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 ketak efisienan 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 algoritma setelah optimisasi program dilakukan.
==== Efisiensi eksekusi ====
{{Main|Efisiensi algoritmik}}
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada algoritma yang sudah teruji, inovasi terbaru, berkaitan dengan algoritma [[Transformasi Fourier Cepat|FFT]] (banyak digunakan di bidang pemrosesan gambar), bisa menurunkan waktu pemrosesan dengan faktor sampai 1.000 untuk aplikasi seperti pencitraan medis.
<ref>{{cite web
| title=Better Math Makes Faster Data Networks
| author=Gillian Conahan
| date=January 2013
| url=http://discovermagazine.com/2013/jan-feb/34-better-math-makes-faster-data-networks#.URAnVieX98F
| publisher=discovermagazine.com}}</ref>
Secara umum, peningkatan kecepatan bergantung pada properti khusus dari permasalahan, yang mana sangat umum pada aplikasi praktis.
<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)] {{Webarchive|url=https://web.archive.org/web/20130704180806/http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf |date=2013-07-04 }}
, Kyoto, January 2012.
Lihat juga [http://groups.csail.mit.edu/netmit/sFFT/ sFFT Web Page].</ref>
Percepatan dengan tingkat seperti itu membolehkan perangkat komputasi yang sering menggunakan pemrosesan gambar (seperti kamera digital dan peralatan medis) menghabiskan daya yang lebih sedikit.
== Klasifikasi ==
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, ini merupakan metode umum bagi [[pemrograman fungsional]]. Algoritma [[Iterasi|iteratif]] menggunakan konstruksi berulang seperti [[Pengulangan program|pengulangan]] dan terkadang 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 algoritma.
; Serial, 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 pada 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 tetapi juga daya komunikasi antara prosesor. Algoritma pengurutan bisa diparalelkan secara efisien, tetapi 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 algoritma 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 termasuk:
; [[Pencarian paksa]] atau pencarian mendalam
: Ini merupakan metode 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 (''Divide and conqueror'')
: [[Algoritma bagi dan takluk]] secara berulang mereduksi 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]].
; Pencarian dan enumerasi
: Banyak masalah (seperti bermain [[catur]]) bisa dimodelkan sebagai masalah dalam [[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]]
: Algoritma 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]].<ref>Misalnya, [[volume]] dari suatu [[politop kompleks]] (dijelaskan menggunakan sebuah keanggotaan oracle) dapat diperkirakan sampai keakuratan yang tinggi dengan mengacak algoritma waktu polinomial, bukan dengan deterministik; lihat {{citation|last1=Dyer|first1=Martin|last2=Frieze|first2=Alan|last3=Kannan|first3=Ravi|date=January 1991|doi=10.1145/102782.102783|issue=1|journal=J. ACM|location=New York, NY, USA|pages=1–17|publisher=ACM|title=A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies|volume=38}}.</ref> Apakah algoritma pengacakan dengan [[P (kompleksitas)|kompleksitas waktu polinomial]] bisa menjadi algoritma tercepat untuk beberapa masalah masih menjadi pertanyaan terbukan yang dikenal sebagai [[Masalah P versus NP]]. 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, tetapi waktu prosesnya adalah hanya terikat secara probabilistik, misalnya [[Waktu Probabilistik Polinomial Galat-Nol|ZPP]].
; [[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|kompleksitasnya]] 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''.
=== Permasalahan optimisasi ===
; 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 algoritma yang dapat memecahkan setiap permasalahan dalam kategori ini, seperti [[algoritma simpleks]] yang terkenal.<ref>
[[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref> 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]]. Algoritma 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, algoritma yang dikhususkan atau algoritma 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, [[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 mereduksi eksponensial dari banyak permasalahan menjadi kompleksitas polinomial.
;
: Sebuah [[algoritma rakus]] mirip dengan [[pemrograman dinamis|algoritma 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. Algoritma ini tidak terlalu mendalam, dan tidak memberikan jawaban yang akurat terhadap banyak permasalahan. Tapi bila ia bekerja, ia menjadi metode 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]].
; Metode heuristik
: Dalam [[masalah optimisasi]], [[algoritma heuristik]] bisa digunakan untuk menemukan suatu solusi yang terdekat dengan solusi optimal jika seandainya menemukan solusi optimal tidak praktis. Algoritma 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. Algoritma tersebut termasuk [[pencarian lokal (optimisasi)|pencarian lokal]], [[pencarian tabu]], [[simulasi pelunakan]], dan [[algoritma genetik]]. Beberapa dari mereka, seperti simuasi pelunakan, adalah algoritma non-deterministik sementara yang lainnya, seperti pencarian tabu, adalah deterministik. Saat batas dari galat dari solusi non-optimal diketahui, algoritma kemudia dikategorikan sebagai [[algoritma pendekatan]].
===
{{Lihat pula|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, tetapi sekarang digunakan untuk menyelesaikan sejumlah besar permasalahan dalam banyak bidang.
=== Berdasarkan kompleksitas ===
{{Lihat pula|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 algoritma 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 metode [[hiperkomputasi]].
=== Berdasarkan tipe evaluatif ===
{{Lihat pula|Keragaman evaluatif}}
Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam masyarakat, seseorang bisa mengklasifikasikan algoritma 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 & Wilson 1998) Hertzke & McConkey 1998, dan Bellah 1985).
Teknologi dapat mengancam ekosistem moral tersebut seperi [[spesies invasif]] jika ia mengganggu campuran keragaman.
Wallach & Allen (2008) mengklasifikasikan algoritma pembuat-keputusan menjadi tiga tipe evaluatif: Algoritma bottom-up membuat penilaian tidak terprediksi bagi pemrogram (misalnya, perangkat lunak yang berevolusi).
Yang lainnya (top-down) dibagi menjadi [[etika deontologikal|deontologikal]] (yang dapat bergantung pada implementasi aturan pemrograman) lawan [[Konsekuensialism|consequensialis]] (yang mengandalkan pada memaksimalkan perkiraan pemrograman).
Sebagai contohnya, sebuah kalkulator standar termasuk deontologikal, sementara [[mesin pembelajaran]] untuk perdagangan saham termasuk consequensialis.
Santos-Lang mengganti nama deontologikal dan consequensialis menjadi kelas "institusional" dan "negosiator" dengan tujuan untuk menghindari implikasi bahwa semua teori-teori etika deontologikal dan consequensialis bisa diimplementasikan sebagai algoritma, dan membagi kelas bottom-up menjadi "[[Etika pengganggu|pengganggu]]" (algoritma yang tidak terprediksi karena menggunakan generator pengacakan) lawan "[[Etika peran|relasional]]" (algoritma yang tidak terprediksi karena efek jaringan).
Seorang mutator dalam [[komputasi evolusioner]] bisa menjadi contoh dari pengganggu, sementara kelas 3 atau 4 dari [[otomata sellular]] adalah contoh dari mesin relasional.
Santos-Lang mencatat bahwa algoritma terkadang memiliki subkomponen dari tipe lainnya.
Sebagai contohnya, negosiator perdagangan saham bisa mengimplementasikan sebuah algoritma genetik, dan memiliki mutator pengganggu, dan mutator bisa memiliki subkomponen institusional dan relasional, semua komputasi adalah relasional pada tingkat di jajaran kimiawi (Santos-Lang 2014).
== 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 pula: [[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 Grafiknya]] [[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 ({{lang-fa|خوارزمي}}, 780-850) 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]].
<ref name="Hogendijk">{{cite journal|last=Hogendijk|first=Jan P.|year=1998|title=al-Khwarzimi|url=http://www.kennislink.nl/web/show?id=116543|dead-url=yes|format=|journal=Pythagoras|volume=38|issue=2|pages=4–5|issn=0033–4766|archive-url=https://web.archive.org/web/20080319024147/http://www.kennislink.nl/web/show?id=116543|archive-date=2008-03-19|access-date=2014-08-28|ref=harv}}</ref>
<ref name="Oaks">{{cite web|last=Oaks|first=Jeffrey A.|title=Was al-Khwarizmi an applied algebraist?|url=http://facstaff.uindy.edu/~oaks/MHMC.htm|publisher=[[University of Indianapolis]]|archive-url=https://www.webcitation.org/5uGLbfttF?url=http://facstaff.uindy.edu/~oaks/MHMC.htm|archive-date=2010-11-15|dead-url=yes|accessdate=2008-05-30}}</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", di mana "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 modern [[algorism]].
Pada abad ke-17 Prancis kata tersebut berubah, tetapi tidak maknanya, menjadi ''algorithme''.
Inggris mengadopsi Prancis setelahnya, tetapi 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>
Etimologi alternatif mengklaim asal mulanya dari istilah ''algebra'' (aljabar) dari makna abad pertengahan "aritmetika Arab" dan ''arithmos'' istilah Yunani untuk angka (yang secara harfiah berarti "bilangan Arab" atau "perhitungan Arab").
Karya algoritma Al-Kharizmi bukan berbentuk seperti pada masa modern sekarang tetapi sebagai tipe dari pengulangan kalkulus (disini disebutkan bahwa karya fundamentalnya yang dikenal sebagai [[algebra]] pada awalnya berjudul "[[Buku Ringkasan tentang Kalkulasi dengan Penyempurnaan dan Pengimbangan]]" menjelaskan tipe-tipe dari pengulangan perhitungan dan [[persamaan kuadrat]]).
Dalam makna tersebut, algoritima dikenal di Eropa jauh sebelum Al-Kharizmi.
Algoritma paling tua yang dikenal sekarang adalah [[Algoritma Euklid]] (lihat juga [[Pengembangan algoritma Euklid]]).
Sebelum ditemukan istilah ''algorithm'' orang Yunani menyebutnya ''anthyphairesis'' secara harfiah berarti anti-substraksi atau substraksi timbal-balik (untuk bacaan lebih lanjut [[David Fowler (matematikawan)|disini]] dan [http://livetoad.org/Courses/Documents/bb63/Notes/continued_fractions.pdf ini] {{Webarchive|url=https://web.archive.org/web/20131103100608/http://livetoad.org/Courses/Documents/bb63/Notes/continued_fractions.pdf |date=2013-11-03 }}.
Algoritma dikenal oleh orang Yunani berabad sebelum
<ref>Becker O (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B 2: 311–333.</ref>
Euclid.
Bukannya kata ''algebra'' orang Yunani menggunakan istilah ''arithmetica''(ἀριθμητική, yaitu dalam karya [[Diophantus]] yang dikenal "[[Arithmetica|bapak dari Aljabar]]" - lihat juga artikel Wikipedia [[persamaan Diophantine]] dan [[Eudoxus dari Cnidus|Eudoxos]]).
== Sejarah: Perkembangan dari kata "algoritma" ==
=== Asal mula ===
Bukti terawal tentang algoritma ditemukan dalam matematika [[Babilonia (kota kuno)|Babilonia]] di [[Mesopotamia]] kuno (saat ini merupakan bagian dari [[Irak]]). Sebuah tablet tanah liat [[Sumeria]] yang ditemukan di Shuruppak dekat [[Bagdad|Baghdad]] dan berasal dari sekitar tahun 2500 SM menjelaskan algoritma divisi yang paling awal.<ref name="Springer Science & Business Media">{{cite book|last1=Chabert|first1=Jean-Luc|date=2012|title=A History of Algorithms: From the Pebble to the Microchip|publisher=Springer Science & Business Media|isbn=9783642181924|pages=7–8}}</ref> Selama dinasti Hammurabi sekitar 1800-1600 SM, tablet tanah liat Babilonia menjabarkan algoritma untuk rumus-rumus komputasi.<ref>{{cite journal|last1=Knuth|first1=Donald E.|date=1972|title=Ancient Babylonian Algorithms|url=http://steiner.math.nthu.edu.tw/disk5/js/computer/1.pdf|journal=Commun. ACM|volume=15|issue=7|pages=671–677|doi=10.1145/361454.361514|issn=0001-0782|archive-url=https://web.archive.org/web/20121224100137/http://steiner.math.nthu.edu.tw/disk5/js/computer/1.pdf|archive-date=2012-12-24|s2cid=7829945|url-status=dead}}</ref> Algoritma juga digunakan dalam astronomi Babilonia. Tablet tanah liat Babilonia menguraikan dan menggunakan prosedur algoritmik untuk menghitung waktu dan tempat peristiwa astronomi yang signifikan.<ref>{{Citation|last=Aaboe|first=Asger|author-link=Asger Aaboe|date=2001|title=Episodes from the Early History of Astronomy|publisher=Springer|place=New York|pages=40–62|isbn=978-0-387-95136-2}}</ref>
Algoritma untuk aritmatika juga ditemukan dalam matematika Mesir kuno, yang terdapat pada Papirus Matematika Rhind yang berasar dari sekitar tahun 1550 SM.<ref name="Springer Science & Business Media2" /> Algoritma kemudian digunakan dalam matematika [[Periode Helenistik|Helenistik]] kuno. Dua contohnya adalah [[Tapis Eratosthenes]], yang dijelaskan dalam Pengenalan Aritmatika oleh [[Nicomachus]],<ref>{{cite web|last=Ast|first=Courtney|title=Eratosthenes|url=http://www.math.wichita.edu/history/men/eratosthenes.html|publisher=Wichita State University: Department of Mathematics and Statistics|archive-url=https://web.archive.org/web/20150227150653/http://www.math.wichita.edu/history/men/eratosthenes.html|archive-date=February 27, 2015|access-date=February 27, 2015|url-status=live}}</ref><ref name="Cooke20052" />{{rp|Ch 9.2}} dan [[Algoritma Euklides|Algoritma Euklides]], yang pertama kali dipaparkan dalam Euclid's Elements (sekitar 300 SM).<ref name="Cooke20052" />{{rp|Ch 9.1}}
=== 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]] aritmetika 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 pada 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 mereduksi [[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 mereduksi sistem menjadi bentuk 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 ===
''Simbol dan aturan'': Dengan cepat berkembangnya matematika dari [[George Boole]] (1847, 1854), [[Gottlob Frege]] (1897), dan [[Giuseppe Peano]] (1888-1889) mereduksi aritmetika 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 mereduksi aturan dari [[rekursi]] pada angka.
''Penghitungan Efektif'': Dalam usaha untuk menyelesaikan [[permasalahan keputusan]] yang didefinisikan oleh Hilbert tahun 1928, matematikawan pertama mendefinisikan apa arti dari "metode 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 permasalahan keputusan 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 permasalahan keputusan 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 "metode 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 saling mengenal tetapi mendeskripsikan sebuah proses orang-sebagai-komputer mengerjakan perhitungan—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 yang 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 [si pekerja] 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]] [[Berkas:Alan Turing.jpg|jmpl|200px|Patung Alan Turing di [[Taman Bletchley]].]] Karya [[Alan Turing]]<ref>Turing 1936 in Davis 1965, Turing 1939 in Davis 1965:160</ref> mendahului karya dari Stibitz (1937); tidak diketahui apakah Stibitz mengetahui karya Turing. Biografinya Turing percaya bahwa Turing menggunakan model seperti-mesin-ketik diturunkan dari ketertarikannya 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 pada waktu itu kita bisa menyimpulkan bahwa semua itu memberikan pengaruh.
Turing—model dari komputasinya sekarang dikenal dengan [[mesin Turing]]—memulai, sebagaimana Post, dengan analisis 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 aritmetika 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 analisisnya (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 'metode [matematis] efektif' dengan cara berikut (kemiringan ditambahkan):
:"'Metode efektif' disebut sebagai metode yang spesial yang mana 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 metode 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 komplet, 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 untuk memperbaiki lebih lanjut definisi dari "algoritma", dan aktivitas tersebut masih terus berjalan karena isu-isu yang mengelilinginya, terutama, [[fondasi matematika]] (khususnya [[tesis Church-Turing]]) dan [[filsafat pikiran]] (khususnya argumen menyangkut [[kecerdasan buatan]]).
Lebih lanjut, lihat [[karakterisasi algoritma]].
== Lihat juga ==
{{colbegin|3}}
* [[Pemerintahan algoritmik]]
* [[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 teoretis#Algoritma|Daftar publikasi penting dalam ilmu komputer teoretis - Algoritma]]
* [[Numerical Mathematics Consortium]]
* [[Teori komputasi]]
** [[Teori komputabilitas]]
** [[Teori kompleksitas Komputasi]]
{{colend}}
== Referensi ==
{{Reflist|30em}}
== Bacaan lanjutan ==
{{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 book|last=Bellah|first=Robert Neelly|year=1985|authorlink=Robert N. Bellah|title=Habits of the Heart: Individualism and Commitment in American Life|location=Berkeley|isbn=978-0-520-25419-0|publisher=University of California Press|url= http://books.google.com/books?id=XsUojihVZQcC|ref=harv}}
* {{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|url = https://archive.org/details/computabilitylog0000bool_r8y9|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.
{{refend}}
== Pranala luar ==
{{wiktionary}}
{{wikibooks|Algorithma}}
* {{id}} [http://www.abstrak.web.id/pengertian_algoritma/ Pengertian Algoritma]{{Pranala mati|date=Februari 2021 |bot=InternetArchiveBot |fix-attempted=yes }}
* {{en}} {{springer|title=Algorithm|id=p/a011780}}
* {{dmoz|Computers/Algorithms/|Algorithms}}
* {{MathWorld | urlname=Algorithm | title=Algorithm}}
* {{en}} [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures]—[[National Institute of Standards and Technology]]
* {{en}} [http://www.softpanorama.org/Algorithms/index.shtml Algorithms and Data Structures by Dr Nikolai Bezroukov]
[[Kategori:Algoritma| ]]
[[Kategori:Logika matematika]]
[[Kategori:Ilmu komputer teoretis]]
| |||