Algoritma: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Cahyogunadi (bicara | kontrib) Perbaikan Tag: halaman dengan galat kutipan Menghilangkan referensi VisualEditor |
Tidak ada ringkasan suntingan Tag: halaman dengan galat kutipan VisualEditor Suntingan perangkat seluler Suntingan peramban seluler |
||
(27 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:Euclid flowchart 1.png |jmpl
Dalam [[matematika]] dan [[ilmu komputer]], '''algoritma'''
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
==
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 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 "
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
<ref>
Stone secara sederhana membutuhkan "harus berhenti dalam sejumlah langkah" (Stone 1973:7-8).
</ref>
Sebuah contoh prototipikal dari suatu
{{Harvtxt|Boolos|Jeffrey|1974, 1999}} memberikan sebuah makna informal dari kata
<blockquote>
Baris 63 ⟶ 51:
Suatu "bilangan tak-terbatas" adalah bilangan yang elemen-elemenya bisa berkorespondensi satu-ke-satu dengan integer.
Maka, Boolos dan Jeffrey mengatakan bahwa sebuah
Maka sebuah
Tapi berbagai penulis yang mencoba mendefinisikan persamaan tersebut mengatakan bahwa kata
: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
Konsep dari ''
Notasi tersebut adalah pusat untuk menjelaskan bagaimana [[sistem formal]] berasal dari sejumlah kecil [[aksioma]] dan aturan.
Dalam [[logika]], waktu dari sebuah
Dari ketidakpastian tersebut, yang mengkarakteristikan pekerjaan yang sedang berjalan, timbulah ketidak-tersediannya definisi ''
== Formalisasi ==
Banyak [[program komputer]] mengandung
Maka, sebuah
Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):
<blockquote>
Baris 87 ⟶ 75:
<blockquote>
Gurevich: "... argumen informal Turing untuk menyokong tesis ini membenarkan tesis yang lebih kuat: setiap
<ref>
Gurevich 2000:1, 3
Baris 93 ⟶ 81:
</blockquote>
Biasanya, bila sebuah
Data simpanan dianggap sebagai bagian dari keadaan internal dari entitas yang melakukan
Pada praktiknya, keadaan tersebut disimpan pada satu atau lebih [[struktur data]].
Untuk beberapa proses komputasi,
Yaitu, setiap langkah tambahan harus secara sistematis dihadapi, kasus-per-kasus;
Kriteria bagi setiap kasus harus jelas (dan bisa dihitung).
Karena sebuah
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
Hal ini merupakan konsepsi umum, yang mencoba menjelaskan sebuah pekerjaan dalam makna diskrit dan "mekanis".
Keunikan dari konsepsi formalisasi
Ia berasal dari intuisi "[[ingatan]]" sebagai kertas buram.
Contoh operasi penetapan tersebut ada di bawah.
Untuk konsepsi yang lain dari apa yang membentuk sebuah
=== Menggambarkan
Ekspresi bahasa alamiah terhadap
Pseudokode, diagram alur, bagan drakon, dan tabel kontrol adalah cara yang terstruktur untuk menggambarkan
Bahasa pemrograman ditujukan untuk mengekspresikan
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
<ref>Sipser 2006:157</ref>
; '''1 Deskripsi tingkat-tinggi'''
: "... ditujukan untuk menjelaskan
; '''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."
Baris 130 ⟶ 118:
: Lebih rinci, "tingkat paling rendah", menjelaskan "tabel kondisi" dari mesin Turing.
Sebagai contoh dari
== Implementasi ==
Kebanyakan
Namun,
==
[[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
''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
:Chaitin: "... sebuah program adalah 'elegan'', maksud saya adalah ia merupakan program terkecil untuk menghasilkan keluaran."<ref>Chaitin 2005:32</ref>
Baris 150 ⟶ 138:
Chaitin membuka definisinya dengan: "Saya akan perlihatkan bahwa anda tidak dapat membuktikan sebuah program adalah 'elegan'"—bukti tersebut akan menyelesaikan [[permasalahan perhentian]] (ibid).
''
Hal ini benar, bahkan tanpa mengembangkan kumpulan instruksi yang ada bagi programmer.
Rogers mengamati bahwa "Sangat ... penting untuk membedakan antara pengertian ''
Fungsi yang sama bisa memiliki beberapa
<ref>
Rogers 1987:1-2
Baris 159 ⟶ 147:
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
''Komputer (dan komputor), model dari komputasi'': Sebuah komputer (atau manusia "komputor"
Baris 213 ⟶ 201:
</ref>
''Simulasi dari sebuah
<ref>Knuth 1973:4</ref>
Lalu bagaimana dengan simulasi atau eksekusi yang sebenarnya?
Programmer harus menerjemahkan
Stone memberikan contoh dari hal ini: saat menghitung akar dari persamaan kuadrat si komputor harus tahu bagaimana mendapatkan akar kuadrat.
Jika tidak maka supaya
<ref>
Strone 1972:5. Metode untuk mendapatkan akar tidaklah biasa: lihat [[Metode untuk menghitung akar kuadrat]].
Baris 240 ⟶ 228:
</ref>
Bila kecepatan yang dihitung, jumlah instruksi berpengaruh.
Sebagai contohnya, subprogram dalam
''Pemrograman
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".
Baris 256 ⟶ 244:
</ref>
''Simbol diagram alur<ref>cf Tausworthe 1977</ref>'': Pembantu grafik yang disebut [[diagram alur]] memberikan suatu cara untuk menjelaskan dan mendokumentasikan sebuah
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).
Baris 264 ⟶ 252:
== Contoh ==
{{Further2|[[Contoh
=== Contoh
[[Berkas:Sorting quicksort anim.gif |jmpl| Animasi dari [[
Salah satu dari
Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tetapi hanya sekali.
Dari hal ini munculah
''Deskripsi tingkat-tinggi:''
Baris 280 ⟶ 268:
''Deskripsi (Quasi-)formal:''
Ditulis dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, berikut ini adalah kode formal dari
{{algorithm-begin|name=LargestNumber}}
Baris 293 ⟶ 281:
{{algorithm-end}}
===
{{Further2|[[
[[Berkas:Euclid's algorithm Book VII Proposition 2 2.png | 250px|jmpl|kiri| Contoh diagram dari
<ref>
Heath 1908:300; Hawking's Dover 2005 edisi diambil dari Heath.
Baris 314 ⟶ 302:
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
</ref>
Baris 326 ⟶ 314:
Euclid mengungkapkan pertanyaan ini dalam Proposisi 1 nya.
</ref>
Walau
Jadi untuk lebih jelasnya
==== Contoh ====
[[File:Euclids-algorithm-example-1599-650.gif | 350px |jmpl|ka| Ekspresi grafik dari
<syntaxhighlight lang="text" highlight="1,5">
Baris 341 ⟶ 329:
</syntaxhighlight>]]
==== Bahasa komputer untuk
Hanya beberapa ''tipe'' instruksi yang dibutuhkan untuk mengeksekusi
* 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
[[File:Euclid's algorithm Inelegant program 1.png|jmpl|163px|ka|"Inelegan" adalah terjemahan dari versi Knuth terhadap
Diambil dari Knuth 1973:2-4.
Bergantung pada kedua angka "Inelegan" bisa menghitung f.p.k dengan sedikit langkah daripada "elegan".]]
Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:
Baris 383 ⟶ 371:
GOTO [[#7|7]].
'''E2: [Apakah sisa 0?]''': APAKAH (i) pengukuran terakhir adalah sama dan sisa di R adalah 0 program dapat berhenti, ATAU (ii)
{{vanchor|10|el10}} IF R = 0 THEN
selesai jadi
Baris 390 ⟶ 378:
lanjut ke langkah [[#11|11]],
'''E3: [Interchange ''s'' dan ''r'']''': Sulitnya
{{vanchor|11|el11}} L ← S
{{vanchor|12|el12}} R ← S
Baris 405 ⟶ 393:
{{vanchor|16|el16}} HALT, END, STOP.
==== Program elegan untuk
Versi
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 [[
6 PRINT "Masukan dua integer besar dari 0"
10 INPUT A,B
Baris 427 ⟶ 415:
dengan kata lain "arti" dari pengurangan dibalik.
=== Menguji
Apakah
Beberapa kasus uji cukup menentukan fungsi inti.
Sumber pertama
Baris 451 ⟶ 439:
Apa yang terjadi bila angka ''negatif'' dimasukan?
Angka desimal?
Bila angka masukan, misalnya [[domain (matematika)|domain]] dari fungsi yang dihitung oleh
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
<ref>
Knuth 1973:13-18. Dia memuji "formulasi pembuktian-
</ref>
Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari pembuktian kebenarannya.
Baris 463 ⟶ 451:
</ref>
=== Menghitung dan meningkatkan
''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
<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
''Bisakah
Kepadatan dari "inelegan" bisa ditingkatkan dengan menghilangkan 5 langkah.
Tapi Chaitin membuktikan bahwa memadatkan
<ref>
Kesalahan terjadi saat sebuah
Keberhasilan akan memecahkan [[permasalahan perhentian]].
</ref>
Baris 492 ⟶ 480:
untuk setiap angka pada A, B dan R, S hal ini selalu merupakan kasus yang membutuhkan analisis yang mendalam.
== Analisis
{{Main|Analisis
Sangat penting untuk mengetahui berapa banyak sumber tertentu (seperti waktu dan tempat penyimpanan) secara teoretis diperlukan untuk sebuah
Metode-metode telah dikembangkan untuk [[analisis
sebagai contohnya,
Setiap saat
Oleh karena itu dikatakan memiliki kebutuhan ruang ''O(1)'', jika ruang yang dibutuhkan untuk menyimpan angka masukan tidak dihitung, atau O(''n'') jika dihitung.
Sebagai contohnya,
=== Formal lawan empiris ===
{{Main|
[[analisis
Dalam artian, analisis
Biasanya [[pseudokode]] digunakan pada analisis karena merupakan representasi paling umum dan sederhana.
Namun, pada akhirnya, kebanyakan
Untuk solusi dari sebuah masalah, efisiensi dari
Meningkatkan n dari kecil ke n yang besar biasanya menunjukan ketak efisienan
Pengujian empiris berguna karena bisa membuka interaksi tak terduga yang mempengaruhi performa.
[[Benchmark (komputasi)|Benchmark]] bisa digunakan untuk membandingkan potensi kenaikan sebelum/sesudah
==== Efisiensi eksekusi ====
{{Main|Efisiensi algoritmik}}
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada
<ref>{{cite web
| title=Better Math Makes Faster Data Networks
Baris 538 ⟶ 526:
== Klasifikasi ==
Salah satu cara mengklasifikasikan
; Rekursi atau iterasi
: Sebuah [[
; Logical
: Sebuah
; Serial, paralel atau terdistribusi
:
; Deterministik atau non-deterministik
: [[
; Tepat atau perkiraan
: Bila banyak
; [[
: Berjalan di model realistik dari [[komputasi quantum]]. Istilah ini biasanya digunakan untuk
== Paradigma secara rancangan ==
Cara lain mengklasifikasikan
Ada sejumlah paradigma, tiap-tiapnya berbeda dari yang lain.
Lebih lanjut, setiap kategori tersebut mengikutkan banyak tipe
Beberapa paradigma umum termasuk:
Baris 579 ⟶ 567:
; Membagi dan menaklukan (''Divide and conqueror'')
: [[
; Pencarian dan enumerasi
: Banyak masalah (seperti bermain [[catur]]) bisa dimodelkan sebagai masalah dalam [[teori grafik|grafik]]. Sebuah [[
; [[
:
# [[
# [[
▲# [[Algoritme Monte Carlo]] mengembalikan jawaban yang benar dengan probabilitas-tinggi. Misalnya, [[RP (kompleksitas)|RP]] adalah sub-klas dari algoritme ini yang berjalan dalam [[waktu polinomial]])
▲# [[Algoritme Las Vegas]] selalu mengembalikan jawaban yang benar, tetapi waktu prosesnya adalah hanya terikat secara probabilistik, misalnya [[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
=== 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
[[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]].
; [[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, [[
; Metode rakus
: Sebuah [[
; Metode heuristik
: Dalam [[masalah optimisasi]], [[
=== Berdasarkan bidang kajian ===
{{Lihat pula|Daftar
Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan
Terkadang bidang-bidang tersebut saling tumpang tindih, dan perkembangan
=== Berdasarkan kompleksitas ===
Baris 630 ⟶ 606:
{{Lihat pula|kelas kompleksitas|Kompleksitas parameterisasi}}
Burgin (2005, p. 24) menggunakan definisi
=== Berdasarkan tipe evaluatif ===
Baris 638 ⟶ 614:
{{Lihat pula|Keragaman evaluatif}}
Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam masyarakat, seseorang bisa mengklasifikasikan
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
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
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
Sebagai contohnya, negosiator perdagangan saham bisa mengimplementasikan sebuah
==
Kata sifat "berkelanjutan" bila diterapkan pada kata "
* Sebuah
* Sebuah
<ref>{{cite book
|author = Tsypkin
Baris 665 ⟶ 641:
== Isu legalitas ==
:''Lihat pula: [[Paten perangkat lunak]] untuk pendahuluan umum dari paten pada perangkat lunak, termasuk
Namun, penerapan praktis dari
Sebagai contohnya, dalam [[Diamond v. Diehr]], aplikasi dari
[[Debat paten perangkat lunak|Mematenkan perangkat lunak]] sangat kontroversial, dan ada paten yang mengikutkan
Sebagai tambahan, beberapa
== Etimologi ==
Kata ''"
<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.
Baris 717 ⟶ 674:
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
Dalam makna tersebut, algoritima dikenal di Eropa jauh sebelum Al-Kharizmi.
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 }}.
<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 "
=== 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 ===
Baris 749 ⟶ 698:
=== Manipulasi simbol sebagai "penampung" bilangan: aljabar ===
Karya dari [[matematika Yunani|Geometer Yunani]] kuno ([[
{{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>}}
Baris 761 ⟶ 710:
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
''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]].
Baris 870 ⟶ 819:
''[[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
=== Sejarah setelah 1950 ===
Sejumlah usaha telah diarahkan untuk memperbaiki lebih lanjut definisi dari "
Lebih lanjut, lihat [[karakterisasi
== Lihat juga ==
Baris 882 ⟶ 831:
* [[Pemerintahan algoritmik]]
* [[Mesin abstrak]]
* [[Rekayasa
* [[Komposisi algoritmik]]
* [[Sintesis algoritmik]]
* [[
* [[Sampah masuk, sampah keluar]]
* ''[[Pendahuluan untuk
* [[Daftar topik
* [[Daftar publikasi penting dalam ilmu komputer teoretis#
* [[Numerical Mathematics Consortium]]
* [[Teori komputasi]]
Baris 905 ⟶ 854:
* {{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
Baris 914 ⟶ 863:
{{wiktionary}}
{{wikibooks|Algorithma}}
* {{id}} [http://www.abstrak.web.id/
* {{en}} {{springer|title=Algorithm|id=p/a011780}}
* {{dmoz|Computers/Algorithms/|Algorithms}}
Baris 921 ⟶ 870:
* {{en}} [http://www.softpanorama.org/Algorithms/index.shtml Algorithms and Data Structures by Dr Nikolai Bezroukov]
[[Kategori:
[[Kategori:Logika matematika]]
[[Kategori:Ilmu komputer teoretis]]
|