Definisi Algoritma, Algoritma adalah: Sejarah dan Pengertian Algoritma
Diagram alur dari sebuah algoritme (Algoritme Euclid) buat menghitung faktor komplotan terbesar (f.P.B.) menurut dua angka a & b dalam lokasi bernama A dan B. Algoritme dijalankan menggunakan pengurangan berturut-turut dalam dua pengulangan: JIKA pengujian B >= A membentuk "ya" (atau benar) (lebih akuratnya angka b dalam lokasi B lebih akbar atau sama menggunakan nomor a pada lokasi A) MAKA, algoritme memilih B ← B - A (ialah nomor b - a menggantikan b sebelumnya). Hal yg sama, JIKA A > B, MAKA A ← A - B. Proses tadi berhenti ketika (isi menurut) B adalah 0, membuat f.P.K. Dalam A. (Algoritme tadi diambil dari Scott 2009:13; simbol & gaya penggambaran menurut Tausworthe 1977).
Dalam matematika dan ilmu komputer, algoritme merupakan mekanisme langkah-demi-langkah buat penghitungan. Algoritme digunakan untuk penghitungan, pemrosesan data, & penalaran otomatis.
Algoritme adalah metode efektif diekspresikan menjadi rangkaian terbatas dari instruksi-instruksi yg sudah didefinisikan dengan baik buat menghitung sebuah fungsi. Dimulai menurut sebuah syarat awal dan input awal (mungkin kosong), instruksi-instruksi tersebut menyebutkan sebuah komputasi yg, jika dihukum, diproses lewat sejumlah urutan syarat terbatas yg terdefinisi dengan baik, yang dalam akhirnya membentuk "keluaran" & berhenti pada kondisi akhir. Transisi menurut satu syarat ke syarat selanjutnya nir wajib deterministik; beberapa algoritme, dikenal menggunakan algoritme pengacakan, menggunakan masukan acak.
Walaupun algorism-nya al-Khawarizmi dirujuk sebagai aturan anggaran melakukan aritmetika memakai bilangan Hindu-Arab & solusi sistematis & persamaan kuadrat, sebagian formalisasi yang nantinya menjadi algoritme modern dimulai dengan bisnis untuk memecahkan perseteruan keputusan (Entscheidungsproblem) yang diajukan oleh David Hilbert dalam tahun 1928. Formalisasi selanjutnya dilihat menjadi bisnis buat memilih "penghitungan efektif" atau "metode efektif"; formalisasi tadi mengikutkan Godel-Herbrand-Kleene fungsi rekursif-nya Kurt Godel - Jacques Herbrand - Stephen Cole Kleene dalam tahun 1930, 1934, & 1935, kalkulus lambda-nya Alonzo Church pada tahun 1936, "Formulasi 1"-nya Emil Post dalam tahun 1936, & Mesin Turing-nya Alan Turing dalam tahun 1936-7 dan 1939. Dari definisi formal berdasarkan algoritme pada atas, berkaitan dengan konsep intuituf, masih tetap ada masalah yg menantang.
Asal Kata
'Algoritme' timbul dari 'Algoritmi', bentuk Latin dari al-Khwarizmi, matematikawan, pakar astronomi, & ahli geografi berdasarkan Persia.
Definisi Informal
Definisi informalnya mampu berarti "sekumpulan anggaran yang secara tepat memilih seurutan operasi". yang mengikutkan semua program komputer, termasuk acara yg tidak melakukan perhitungan numerik. Secara generik, sebuah program hanyalah sebuah algoritme apabila ia akan berhenti nantinya.
Sebuah model prototipikal menurut suatu algoritme merupakan algoritme Euclid untuk memilih sapta pembagi terbesar berdasarkan dua integer; sebagai misalnya (ada contoh yg lain) dijelaskan menggunakan diagram alur di atas dan sebagai model di bagian lanjut.
(Boolos & Jeffrey 1974, 1999) menaruh sebuah makna informal menurut kata algoritme pada persamaan berikut:
"Tidak terdapat manusia yg bisa menulis begitu cepat, atau begitu lama , atau begitu mini ("mini , & lebih kecil tanpa batas ... Anda mungkin mencoba menulis di atas molekul, atom, elektron") buat mencatat semua anggota dari formasi bilangan tak terbatas menggunakan menuliskan namanya, bergantian, pada suatu notasi. Tapi insan mampu melakukan sesuatu yg sama bergunanya, dalam masalah formasi sapta tidak terbatas: Mereka bisa menaruh instruksi kentara untuk menentukan anggota ke-n berdasarkan set, buat n terbatas acak. Instruksi tadi diberikan secara eksplisit, dalam bentuk yang dapat diikuti oleh mesin penghitung, atau sang insan yg bisa melakukan hanya operasi-operasi dasar dengan simbol-simbol."
Suatu "sapta tidak-terbatas" merupakan bilangan yang elemen-elemenya sanggup berkorespondensi satu-ke-satu dengan integer. Maka, Boolos & Jeffrey mengungkapkan bahwa sebuah algoritme berarti instruksi bagi sebuah proses yg "menciptakan" keluaran integer berdasarkan sebuah "masukan" rambang integer yang, secara teori, bisa sangat akbar. Maka sebuah algoritme dapat berupa persamaan aljabar seperti y = m + n -- 2 variabel masukan m & n yg menghasikan keluaran y. Tapi banyak sekali penulis yang mencoba mendefinisikan persamaan tersebut mengungkapkan bahwa kata algoritme mengandung lebih dari itu, sesuatu yg sekitar (buat contoh penjumlahan):
Instruksi rinci dan tepat (dalam bahasa yang dipahami oleh "personal komputer ")[16] buat proses yg cepat, efisien, "baik" yang memilih "pergerakan" berdasarkan "komputer" (mesin atau manusia, dibekali menggunakan informasi dan kemampuan internal yang diharapkan) buat menemukan, dekode, & lalu mengolah masukan integer/simbol m dan n, simbol + dan = ... & "secara efektif" membuat, dalam waktu yg "masuk akal", keluaran integer y dalam tempat dan format tertentu.
Konsep menurut algoritme pula dipakai buat mendefinisikan notasi dari desidabilitas. Notasi tersebut merupakan sentra buat mengungkapkan bagaimana sistem formal dari berdasarkan sejumlah mini aksioma & anggaran. Dalam nalar, ketika menurut sebuah algoritme untuk selesai tidak dapat dihitung, karena nir berelasi dengan dimensi fisik kita. Dari ketidakpastian tadi, yang mengkarakteristikan pekerjaan yang sedang berjalan, timbulah ketidak-tersediannya definisi algoritme yg sinkron menggunakan nyata (pada tingkat eksklusif) dan penggunaan secara abstrak menurut istilah tadi.
Formalisasi
Algoritme sangat penting bagi cara personal komputer mengolah data. Banyak program komputer mengandung algoritme menaruh rincian dalam instruksi spesifik yang personal komputer harus lakukan (dengan urutan tertentu) buat menjalankan pekerjaan eksklusif, seperti menghitung honor karyawan atau mencetak kartu rapor siswa. Maka, sebuah algoritme bisa dianggap menjadi urutan operasi yg mampu disimulasikan sang sebuah sistem Turing-lengkap. Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):
Minsky: "Tapi kita pula menjaga, dengan Turing ... Bahwa setiap prosedur yg "secara alami" disebut efektif, bisa dinyatakan sang mesin (sederhana). Walaupun sepertinya ekstrem, alasan tersebut ... Sukar disanggah".
Gurevich: "... Argumen informal Turing buat menyokong tesis ini membenarkan tesis yg lebih kuat: setiap algoritme mampu disimulasikan sang sebuah mesin Turing ... Dari Savage [1987], sebuah algoritme merupakan sebuah proses penghitungan yg dipengaruhi sang sebuah mesin Turing".
Biasanya, bila sebuah algoritme dihubungkan menggunakan pengolahan kabar, data dibaca dari sumber masukan, ditulis ke perangkat keluaran, dan/atau disimpan buat pengolahan selanjutnya. Data simpanan dianggap sebagai bagian menurut keadaan internal dari entitas yg melakukan algoritme. Pada praktiknya, keadaan tersebut disimpan dalam satu atau lebih struktur data.
Untuk beberapa proses komputasi, algoritme harus ditentukan secara teliti: dijabarkan dengan cara beliau bakal berlaku buat seluruh kemungkinan yang dapat muncul. Yaitu, setiap langkah tambahan wajib secara sistematis dihadapi, perkara-per-perkara; Kriteria bagi setiap perkara harus jelas (dan bisa dihitung).
Lantaran sebuah algoritme adalah deretan dari langkah-langkah yang sempurna, urutan berdasarkan komputasi selalu krusial bagi berfungsinya algoritme. Instruksi umumnya diasumsikan terdaftar secara eksplisit, & dijelaskan dimulai "menurut atas" & terus "ke bawah", sebuah gambaran yang dijelaskan secara formal oleh alur kontrol
Sejauh ini, diskusi tentang formalisasi algoritme telah mengasumsikan premis dari pemrograman imperatif. Hal ini merupakan konsepsi generik, yg mencoba menyebutkan sebuah pekerjaan pada makna diskrit dan "mekanis". Keunikan dari konsepsi formalisasi algoritme merupakan operasi penetapan, mengatur nilai dari sebuah variabel. Ia asal berdasarkan intuisi "ingatan" sebagai kertas buram. Contoh operasi penetapan tadi ada pada bawah.
Untuk konsepsi yg lain dari apa yg menciptakan sebuah algoritme lihat pemrograman fungsional dan pemrograman akal.
Menggambarkan algoritme
Algoritme dapat digambarkan dengan banyak notasi, termasuk bahasa alamiah, pseudokode, diagram alur, bagan drakon, bahasa pemrograman atau tabel kontrol (diproses sang penerjemah). Ekspresi bahasa alamiah terhadap algoritme condong lebih poly dan tidak wajar, & jarang dipakai buat algoritme yg kompleks dan teknis. Pseudokode, diagram alur, bagan drakon, & tabel kontrol merupakan cara yg terstruktur untuk mendeskripsikan algoritme yg mencegah banyaknya kerancuan pada pernyataan-pernyataan bahasa alamiah. Bahasa pemrograman ditujukan untuk mengekspresikan algoritme dalam sebuah bentuk yang bisa dihukum oleh personal komputer , namun seringkali kali dipakai sebagai suatu cara untuk memilih atau mendokumentasikan algoritme.
Ada banyak macam kemungkinan representasi & seorang dapat mengekspresikan sebuah acara mesin Turing sebagai urutan berdasarkan tabel-tabel mesin (lihat lebih lanjut pada mesin kondisi-terbatas, tabel transisi kondisi & tabel kontrol), sebagai diagram alur & bagan drakon (lihat lebih lanjut di diagram syarat), atau menjadi bentuk kode mesin atau kode assembly dasar yg dikenal "perpaduan lipat empat" (lihat lebih lanjut pada mesin Turing).
Representasi menurut algoritme dapat dikelompokan ke dalam tiga strata berdasarkan pelukisan mesin Turing:
1 Deskripsi tingkat-tinggi
"... Ditujukan buat menjelaskan algoritme, menghiraukan rincian implementasi. Pada tingkat ini kita tidak perlu mengungkapkan bagaimana mesin mengatur perangkat pita atau ketua pita rekam."
2 Deskripsi implementasi
"... Dipakai buat menjelaskan cara mesin Turing memakai kepalanya dan cara menyimpan data. Pada taraf ini kita tidak memberikan secara rinci kondisi atau fungsi transisi."
tiga Deskripsi formal
Lebih rinci, "taraf paling rendah", menyebutkan "tabel kondisi" berdasarkan mesin Turing.
Sebagai contoh berdasarkan algoritme sederhana "Penjumlahan m+n" dijelaskan dalam 3 strata tadi lihat contoh algoritme.
Implementasi
Kebanyakan algoritme ditujukan buat diimplementasikan sebagai program personal komputer . Namun, algoritme pula diimplementasikan menggunakan tujuan lain, misalnya dalam jaringan saraf biologis (sebagai misalnya, otak insan yg mengimplementasikan aritmetika atau sebuah serangga yg melihat kuliner), dalam sirkuit elektris, atau dalam sebuah perangkat mekanis.
Algoritma Komputer
Dalam sistem personal komputer , sebuah algoritme pada dasarnya merupakan instansi dari logika ditulis pada software oleh pengembang software supaya efektif untuk personal komputer yg "ditargetkan" buat mesin tertentu buat membuat keluaran berdasarkan masukan yang diberikan (kemungkinan nul).
Program yg "elegan" (padat), acara yg "baik" (cepat): Pernyataan menurut "sederhana dan elegan" timbul secara informal dalam kitab Knuth & dalam Chaitin:
Knuth: "... Kita menginginkan algoritme yg baik pada definisi keindahan sederhana. Salah satu kriterianya ... Adalah ketika yang diperlukan buat berjalannya algoritme ... Kriteria yg lain adalah adaptasi menurut algoritme ke personal komputer , kesederhanaan & elegan, dll"
Chaitin: "... Sebuah acara adalah 'elegan, maksud aku merupakan ia adalah acara terkecil buat membuat keluaran."
Chaitin membuka definisinya dengan: "Saya akan perlihatkan bahwa anda nir bisa menandakan sebuah acara merupakan 'elegan'" bukti tadi akan menyelesaikan perseteruan perhentian (ibid).
Algoritme terhadap fungsi yg dapat dihitung sang algoritme: Untuk sebuah fungsi bisa ada beberapa algoritme. Hal ini benar, bahkan tanpa berbagi perpaduan instruksi yg terdapat bagi programmer. Rogers mengamati bahwa "Sangat ... Penting buat membedakan antara pengertian algoritme, contohnya mekanisme dan pernyataan fungsi yg dihitung oleh algoritme, contohnya pemetaan output dari prosedur. Fungsi yg sama bisa mempunyai beberapa algoritme tidak sama".
Sayangnya ada pertukaran antara kebaikan (kecepatan) & elegan (kepadatan) sebuah acara yang elegan bisa melakukan lebih banyak langkah buat merampungkan sebuah komputasi daripada yang kurang elegan. Sebuah model yang memakai algoritme Euclid sanggup dipandang pada bawah.
Komputer (dan komputor), model berdasarkan komputasi: Sebuah personal komputer (atau manusia "komputor" ) adalah tipe terbatas dari mesin, sebuah "perangkat mekanis deterministik diskrit" yang secara buta mengikuti instruksinya . Model primitif berdasarkan Melzak & Lambek mereduksi pemikiran tadi menjadi empat elemen: (i) diskrit, lokasi yang bisa dibedakan, (ii) diskrit, penghitung yang tak bisa dibedakan (iii) sebuah agen, dan (iv) sebuah daftar instruksi yang efektif relatif terhadap kemampuan menurut agen.
Minsky mengungkapkan variasi yg lebih sesuai menurut contoh "abacus"-nya Lambek dalam "Basis Komputabilitas Paling Sederhana". Mesin Minsky memproses secara berurutan lewat lima (atau enam tergantung bagaimana seorang menghitungnya) instruksi kecuali baik sebuah kondisi IF-THEN GOTO atau GOTO tidak bersyarat mengganti alur program keluar menurut urutan.
Selain HALT, mesin Minsky mengikutkan tiga operasi penetapan (penggantian, substitusi): ZERO (misalnya, isi menurut lokasi diganti oleh 0: L ← 0), SUCCESSOR (misalnya, L ← L+1), & DECREMENT (misalnya, L ← L-1). Jarang seorang programer wajib menulis "kode" dengan kumpulan instruksi terbatas. Tapi Minsky memperlihatkan (sebagaimana Melzak & Lambek) bahwa mesinnya adalah Turing komplet menggunakan hanya empat tipe instruksi utama: GOTO kondisional, GOTO tak bersyarat, penetapan/penggantian/substitusi, & HALT.
Simulasi menurut sebuah algoritme: bahasa personal komputer (komputor): Knuth menganjurkan pembaca bahwa "cara terbaik buat belajar algoritme dalah mencobanya ... Langsung ambil pulpen dan kertas dan bekerja lewat model".
Lalu bagaimana dengan simulasi atau hukuman yang sebenarnya? Programmer harus menerjemahkan algoritme ke dalam bahasa yg mana simulator/personal komputer /komputor dapat mengeksekusi secara efektif. Stone menaruh model dari hal ini: waktu menghitung akar menurut persamaan kuadrat si komputor wajib memahami bagaimana menerima akar kuadrat. Apabila tidak maka agar algoritme bisa efektif ia wajib menyediakan sejumlah aturan buat mengekstrak akar kuadrat.
Hal ini berarti programer wajib tahu sebuah "bahasa" yg efektif nisbi terhadap sasaran pada agen komputasi (komputer/komputor).
Lalu contoh apa yang seharusnya dipakai untuk simulasi? Van Emde Boas mengamati "bahkan bila kita mendasari teori kompleksitas menggunakan mesin tak berbentuk bukannya mesin kongkrit, kesembarangan berdasarkan pemilihan contoh masih permanen ada. Pada titik itulah mulainya pemikiran simulasi".
Jika kecepatan yang dihitung, jumlah instruksi berpengaruh. Sebagai misalnya, subprogram pada algoritme Euclid buat menghitung sisa akan berjalan lebih cepat bila programmer mempunyai instruksi "modulus" (residu pembagian) bukannya dengan pengurangan (atau lebih parah: hanya "penurunan").
Pemrograman terstuktur, struktur kanonikal: Menurut Tesis Church-Turing setiap algoritme mampu dihitung dengan sebuah contoh yang dikenal Turing komplet, & dari demonstrasi Minsky kekomplitan Turing membutuhkan hanya empat tipe instruksi GOTO bersyarat, GOTO tidak bersyarat, penetapan, HALT. Kemeny & Kurtz mengamati bahwa waktu penggunaan GOTO tak bersyarat yg "tidak disiplin" dan IF-THEN GOTO bersyarat mampu membentuk "kode spageti" seseorang programer mampu menulis acara terstruktur menggunakan instruksi tersebut; di lain sisi "jua memungkinkan, & nir begitu sulit, buat menulis sebuah acara terstruktur yg tidak baik pada sebuah bahasa terstruktur".
Tausworthe menambahkan tiga struktur kanon Bohm-Jacopini: SEQUENCE, IF-THEN-ELSE, & WHILE-DO, menggunakan 2 lagi: DO-WHILE dan CASE. Keuntungan menurut acara terstruktur merupakan dia cocok dengan pembuktian kebenaran menggunakan induksi matematika.
Simbol diagram alur: Pembantu grafik yang diklaim diagram alur memberikan suatu cara buat menyebutkan dan mendokumentasikan sebuah algoritme (dan program komputer).
Seperti alur program berdasarkan mesin Minsky, sebuah diagram alur selalu mulai menurut atas dan terus ke bawah. Simbol utamanya hanya 4: arah panah menerangkan alur program, segi empat (SEQUENCE, GOTO), wajik (IF-THEN-ELSE), & titik (OR). Struktur kanonikal Bohm-Jacopini dibuat dari bentuk-bentuk primitif tersebut. Sub-struktur bisa "bersarang" dalam segi empat hanya apabila jalan keluar tunggal terjadi dalam super-struktur. Simbol & penggunaannya buat membangun struktur kanonikal diperlihatkan dalam diagram.
Contoh Algoritma
Salah satu dari algoritme sederhana adalah menemukan bilangan terbesar pada sebuah kumpulan nomor (tidak berurut). Solusinya membutuhkan inspeksi setiap nomor pada deret, namun hanya sekali. Dari hal ini munculah algoritme sederhana, yang mampu dinyatakan dalam kalimat bahasa pelukisan taraf-tinggi, menjadi:
Deskripsi tingkat-tinggi:
- apabila tidak terdapat angka pada deret makan tidak terdapat bilangan terbesar.
- Asumsikan item pertama pada deret merupakan yg terbesar.
- Untuk setiap residu angka pada deret, bila angka tersebut besar dari angka terbesar kini , anggap nomor tadi sebagai yang terbesar dalam deret.
- Jika tidak terdapat lagi angka yg tersisa dalam deret buat diperiksa, anggap nomor terbesar kini sebagai nomor yang terbesar dalam deret.
Deskripsi (Quasi-)formal: Ditulis pada kalimat yang lebih dekat menggunakan bahasa taraf-tinggi menurut program personal komputer , ini dia adalah kode formal berdasarkan algoritme pada pseudokode atau kode pijin:
Algoritma LargestNumber
Masukan: Deret angka L.
Keluaran: Angka terbesar dalam daftar L.
terbesar ← Lnull
untuk setiap item dalam L, lakukan
jika item > terbesar, maka
terbesar ← item
kembalikan terbesar
- "←" adalah singkatan untuk "diubah menjadi". Misalnya, "terbesar ← item" artinya nilai dari terbesar diubah menjadi nilai dari item.
- "kembalikan" mengakhiri algoritma dan mengeluarkan nilai kembalian.
Algoritma euclid
Contoh diagram berdasarkan algoritme Euclid menurut T.L. Health 1908 dengan rincian tambahan. Euclid tidak sampai dalam penghitungan ketiga dan nir memberikan contoh numeris. Nocomachus menaruh model berdasarkan 49 dan 21: "Saya mengurangi yg mini berdasarkan yang besar ; 28 adalah yg kiri; kemudian saya kurangi lagi 21 (hal ini memungkinkan); tersisa 7, namun 7 tidak sanggup dikurangi berdasarkan 7." Heath berkomentar bahwa, "Kalimat terakhir terdengar aneh, tetapi maknanya sangat jelas, begitu juga makna menurut kalimat mengenai mengakhiri 'menggunakan satu & nomor yang sama'."(Heath 1908:300).
Algoritme Euclid ada sebagai Proposisi II pada Book VII ("Elementary Number Theory") menurut Elements. [45] Euclid mengajukan pertarungan: "Ambil 2 nomor bukan prima, buat mencari sapta pembagi terbesar". Dia memilih "Sebuah angka [merupakan] besaran yang terdiri berdasarkan unit-unit": nomor penghitung, integer positif kecuali 0. Dan "mengukur" merupakan menempatkan berukuran panjang terkecil s dengan sempurna (q kali) di antara berukuran terpanjang l sampai residu r lebih mini berdasarkan panjang terkecil s. [46] Dalam global modern, residu r = l - q*s, q menjadi output bagi, atau sisa r adalah "modulus", bagian sisa-integer yg tersisa selesainya pembagian.
Supaya metode Euclid berhasil, panjang awalnya wajib memenuhi dua kebutuhan: (i) panjangnya tidak 0, DAN (ii) output pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka merupakan output pengurangan berdasarkan yang terbesar (alternatif, keduanya mampu sama sebagai akibatnya pengurangan membuat 0).
Pembuktian orisinil Euclid mengikutkan kebutuhan yg ketiga: ke 2 panjang bukanlah sapta prima. Euclid memilih hal ini agar dia sanggup membangun sebuah bukti reductio ad absurdum bahwa 2 pembagi 2 nomor adalah yang terbesar. [48] Walau algoritme Nicomachus sama menggunakan Euclid, bila ke 2 bilangan prima maka membentuk nomor "1" buat bilangan pembagi terbesar. Jadi buat detail algoritme berikut adalah algoritme Nicomachus.
Contoh:
1599 = 650*2 + 299
650 = 299*2 + 52
299 = 52*5 + 39
52 = 39*1 + 13
39 = 13*3 + 0
Bahasa personal komputer buat algoritme Euclid
Hanya beberapa tipe instruksi yg diperlukan buat mengeksekusi algoritme—beberapa tes nalar (GOTO bersyarat), GOTO tak bersyarat, penetapan (penggantian), & pengurangan.
Sebuah lokasi disimbolkan menggunakan huruf besar , misalnya, S, A, dll.
Kuantitas beragam (angka) dalam sebuah lokasi ditulis menggunakan alfabet mini dan (umumnya) dihubungkan menggunakan nama lokasi. Sebagai contohnya, lokasi L pada awal bisa mengandung angka l = 3009.
Program yg kurang elegan (inelegan) buat algoritme Euclid Sunting
Algoritme berikut disebut sebagai versi Euclid dan Nichomachus 4-langkah-nya Knuth, namun bukannya menggunakan pembagi buat menentukan sisa ia menggunakan pengurangan berturut-turut berdasarkan panjang terkecil s dari sisa panjang r sampai r kurang menurut s. Deskripsi taraf-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi menurut Knuth 1973:dua-4:
INPUT:
1 [Kedalam dua lokasi L dan S taruh angka l dan s yang merepresentasikan kedua panjang]:
INPUT L, S
2 [Inisialisasi R: buat supaya sisa panjang r sama dengan panjang awal l]
R ← L
E0: [Pastikan r ≥ s.]
3 [Pastikan angka terkecil dari kedua angka ada dalam S dan yang terbesar di R]:
IF R > S THEN
isi dari L adalah angka terbesar jadi lewati langkah 4, 5 dan 6:
GOTO step 6
ELSE
tukar isi R dan S.
4 L ← R (langkah pertama ini berlebih, tetapi berguna untuk diskusi nanti).
5 R ← S
6 S ← L
E1: [Cari sisa]: Sampai sisa panjang r pada R kurang dari panjang terkecil s pada S, kurangi angka s dalam S berulang kali dari sisa panjang r pada R.
7 IF S > R THEN
selesai mengukur jadi
GOTO 10
ELSE
ukur lagi,
8 R ← R - S
9 [Pengulangan-sisa]:
GOTO 7.
E2: [Apakah sisa 0?]: APAKAH (i) pengukuran terakhir adalah sama & sisa di R merupakan 0 acara bisa berhenti, ATAU (ii) algoritme wajib terus jalan: output pengukuran meninggalkan residu di R kurang menurut angka pengukuran dalam S.
10 IF R = 0 THEN
selesai jadi
GOTO langkah 15
ELSE
lanjut ke langkah 11,
E3: [Interchange s dan r]: Sulitnya algoritme Euclid. Menggunakan sisa r buat mengukur angka terkecil sebelumnya s:; L menjadi lokasi ad interim.
11 L ← S
12 R ← S
13 S ← L
14 [Ulang proses pengukuran]:
GOTO 7
OUTPUT:
15 [Selesai. S berisi faktor persekutuan terbesar]:
PRINT S
DONE:
16 HALT, END, STOP.Program elegan buat algoritme Euclid
Versi algoritme Euclid berikut hanya membutuhkan 6 instruksi inti buat melakukan 13 langkah dalam solusi "inelegan"; parahnya, "inelegan" membutuhkan tipe instruksi lebih banyak. Diagram alur menurut "elegan" bisa dilihat pada permukaan artikel ini. Dalam bahasa Basic (tak terstruktur) langkahnya diberi nomor , & instruksi LET [] = [] adalah instruksi penetapan disimbolkan dengan ←.
5 REM Algoritme 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 2 pengulangan, pengulangan A > B yang menghitung A ← A - B, & pengualang B ≤ A yg menghitung B ← B - A. Hal ini bekerja lantaran, ketika yang dikurang M lebih mini pengurang S ( Selisih = pengurang - yang_di_kurang ), yang_dikurang bisa menjadi s (panjang pengukuran yang baru) & pengurang sanggup menjadi r yang baru (panjang yg akan diukur); dengan istilah lain "arti" berdasarkan pengurangan dibalik.
Menguji algoritme Euclid Sunting
Apakah algoritme berjalan seperti yg penulis inginkan? Beberapa masalah uji cukup memilih fungsi inti. Sumber pertama [49] menggunakan 3009 dan 884. Knuth menyarankan 40902, 24140. Kasus menarik lainnya yaitu 2 angka nisbi prima 14157 dan 5950.
Tapi masalah pengecualian harus teridentifikasi dan diuji. Apakah "inelegan" berjalan benar waktu R > S, S > R, R = S? Sama juga menggunakan "Elegan": B > A, A > B, A = B? (Semuanya sahih). Apa yg terjadi jika salah satu bilangan nol, atau keduanya nol? ("Inelegan" terus berjalan dalam ke 2 perkara; "elegan" terus berjalan waktu A = 0.) Apa yang terjadi jika angka negatif dimasukan? Angka desimal? Bila nomor masukan, contohnya domain berdasarkan fungsi yg dihitung sang algoritme/acara, mengikutkan hanya integer positif termasuk 0, maka kegagalan dalam nol mengindikasikan bahwa algoritme (dan program instansiasinya) merupakan sebuah fungsi parsial bukannya fungsi total. Kesalahan yang populer karena eksepsi adalah kegagalan roket Ariane V.
Bukti menurut kebenaran program memakai induksi matematika: Knuth mendemonstrasikan penggunaan induksi matematika buat versi "pengembangan" dari algoritme Euclid, & dia mengajukan "metode umum yang dipakai buat menandakan validitas berdasarkan setiap algoritme." Tausworthe mengajukan bahwa sebuah pengukuran dari kompleksitas berdasarkan sebuah acara adalah panjang menurut verifikasi kebenarannya.
Menghitung & meningkatkan algoritme Euclid
Elegan (kepadatan) versus kebaikan (kecepatan): Dengan hanya 6 instruksi dasar, "Elegan" merupakan kentara pemenang dibandingkan dengan instruksi "inelegan" menggunakan 13 instruksi. Namun, "inelegan" lebih cepat (beliau hingga pada HALT menggunakan langkah lebih sedikit). Analisis algoritme mengindikasikan kenapa hal tersebut terjadi: "Elegan" melakukan pengujian kondisi dua kali disetiap pengulangan pengurangan, ad interim "inelegan" hanya sekali. Jika algoritme (umumnya) membutuhkan banyak pengulangan, secara rata-rata lebih poly waktu yang terbuang ketika melakukan tes "B = 0?" yg hanya diharapkan waktu residu telah dihitung.
Bisakah algoritme ditingkatkan?: Jika programmer sudah menilai sebuah program "cocok" & "efektif" yaitu, ia menghitung fungsi yang ditujukan oleh penulisnya maka pertanyaannya sebagai, bisakah ditingkatkan?
Kepadatan berdasarkan "inelegan" bisa ditingkatkan menggunakan menghilangkan 5 langkah. Tapi Chaitin membuktikan bahwa memadatkan algoritme tidak sanggup diotomatiskan menggunakan algoritme generalisasi; kan tetapi, ia sanggup dilakukan secara heuristik, contohnya dengan pencarian menyeluruh (contohnya mampu ditemukan di Berang sibuk), coba dan gagal, kecerdasan, kedalaman, penggunaan penalaran induktif, dll. Bisa diamati bahwa langkah 4, lima, & 6 diulang dalam langkah 11, 12, & 13. Pembandingan dengan "Elegan" menyediakan petunjuk langkah-langkah tersebut menggunakan langkah 2 & tiga dapat dihilangkan. Hal ini mereduksi jumlah instruksi dasar berdasarkan 13 sebagai 8, yg membuatnya "lebih elegan" dari "Elegan" dengan 9 langkah.
Kecepatan "Elegan" bisa ditingkatkan menggunakan memindahkan tes B=0? Keluar berdasarkan pengulangan. Perubahan ini memerlukan penambahan 3 instruksi (B=0?, A=0?, GOTO). Sekarang "Elegant" menghitung contoh-nomor lebih cepat; buat setiap angka pada A, B dan R, S hal ini selalu adalah perkara yg membutuhkan analisis yg mendalam.
Analisis Algoritma
Sangat penting untuk mengetahui berapa banyak sumber tertentu (seperti waktu dan tempat penyimpanan) secara teoretis diperlukan untuk sebuah algoritme. Metode-metode telah dikembangkan untuk analisis algoritme untuk mendapatkan jawaban kuantitatif (estimasi); sebagai contohnya, algoritme pengurutan di atas memerlukan waktu O(n), menggunakan notasi O besar dengan n sebagai panjang deret (yang akan diurut). Setiap saat algoritme 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.
Algoritme berbeda mungkin menyelesaikan pekerjaan yang sama dengan kumpulan instruksi yang berbeda dengan waktu, ruang, atau 'usaha' lebih sedikit atau banyak dari yang lain. Sebagai contohnya, algoritme pencairan binari biasanya mengungguli pencarian berderet secara paksa bila digunakan untuk tabel pencarian pada deret terurut.
Formal lawan empiris
!Artikel utama untuk bagian ini adalah: Algoritme empiris, Profiling (pemrograman komputer), dan Optimisasi program
Analisis dan kajian algoritme adalah bidang dari ilmu komputer, dan biasanya dilakukan secara abstrak tanpa menggunakan bahasa pemrograman tertentu atau implementasi. Dalam artian, analisis algoritme mirip dengan bidang matematika lainnya yang mana fokus pada properti yang mendasari algoritme dan bukan pada implementasi tertentu.
Biasanya pseudokode digunakan pada analisis karena merupakan representasi paling umum dan sederhana. Namun, pada akhirnya, kebanyakan algoritme diimplementasikan di perangkat keras / lunak tertentu dan efisiensi algoritmik mereka akhirnya diuji menggunakan kode yang sebenarnya. Untuk solusi dari sebuah masalah, efisiensi dari algoritme tertentu mungkin tidak terlalu berpengaruh (kecuali n sangat besar) tetapi bagi algoritme 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 algoritme yang tidak berbahaya.
Pengujian empiris berguna karena bisa membuka interaksi tak terduga yang mempengaruhi performa. Benchmark bisa digunakan untuk membandingkan potensi kenaikan sebelum/sesudah algoritme setelah optimisasi program dilakukan.
Efisiensi eksekusi
fisiensi algoritmik
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada algoritme yang sudah teruji, inovasi terbaru, berkaitan dengan algoritme FFT (banyak digunakan di bidang pemrosesan gambar), bisa menurunkan waktu pemrosesan dengan faktor sampai 1.000 untuk aplikasi seperti pencitraan medis.
Secara umum, peningkatan kecepatan bergantung pada properti khusus dari permasalahan, yang mana sangat umum pada aplikasi praktis. 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 algoritme yaitu dengan cara implementasi.
Rekursi atau iterasi
Sebuah algoritme rekursi yaitu algoritme yang memanggil dirinya sendiri berulang kali sampai kondisi tertentu tercapai, ini merupakan metode umum bagi pemrograman fungsional. Algoritme iteratif menggunakan konstruksi berulang seperti pengulangan dan terkadang struktur data tambahan seperti 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 algoritme bisa dilihat sebagai logika deduksi terkontrol. Pernyataan ini diekspresikan sebagai: Algoritme = logika + kontrol. 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 algoritme ditentukan dengan memberikan hanya komponen logikanya. Daya tarik dari pendekatan ini adalah semantik elegan: sebuah perubahan dalam aksioma memiliki perubahan dalam algoritme.
Serial, paralel atau terdistribusi
Algoritme biasanya dibicarakan dengan asumsi bahwa komputer menjalankan satu instruksi algoritme setiap waktu. Komputer tersebut terkadang disebut dengan komputer serial. Rancangan algoritme untuk lingkungan tersebut disebut dengan algoritme serial, terbalik dengan algoritme paralel atau algoritme terdistribusi. Algoritme paralel memanfaatkan arsitektur komputer yang mana beberapa prosesor bisa mengerjakan masalah di waktu yang sama, selain itu algoritme terdistribusi memanfaatkan banyak mesin yang terhubung dengan jaringan.
Algoritme paralel atau terdistribusi membagi permasalahan menjadi banyak sub-masalah simetris atau asimetris dan mengumpulkan hasilnya kembali. Konsumsi sumber pada algoritme tersebut tidak hanya perputaran prosesor disetiap prosesor tetapi juga daya komunikasi antara prosesor. Algoritme pengurutan bisa diparalelkan secara efisien, tetapi biaya komunikasinya sangat mahal. Algoritme iteratif secara umum bisa diparalelkan. Beberapa permasalahan tidak ada algoritme paralelnya, dan disebut dengan permasalahan serial lahiriah.
Deterministik atau non-deterministik
Algoritme deterministik menyelesaikan masalah dengan keputusan yang tepat disetiap langkah dari algoritme sedangkan algoritme non-deterministik menyelesaikan masalah lewat penerkaan walaupun penerkaan biasanya lebih akurat dengan menggunakan heuristik.
Tepat atau perkiraan
Bila banyak algoritme sampai pada solusi yang tepat, algoritme perkiraan mencari sebuah perkiraan yang terdekat dengan solusi benarnya. Perkiraan bisa menggunakan baik strategi deterministik atau acak. Algoritme seperti itu memiliki nilai guna untuk banyak permasalahan sulit.
Algoritme quantum
Berjalan di model realistik dari komputasi quantum. Istilah ini biasanya digunakan untuk algoritme yang tampak pada dasarnya quantum, atau menggunakan beberapa fitur penting komputasi quantum seperti superposisi quantum atau belitan quantum.
Paradigma secara rancangan
Cara lain mengklasifikasikan algoritme merupakan menggunakan metodologi rancangannya atau paradigma. Ada sejumlah kerangka berpikir, tiap-tiapnya tidak selaras menurut yang lain. Lebih lanjut, setiap kategori tersebut mengikutkan banyak tipe algoritme yg tidak sinkron. Beberapa kerangka berpikir generik termasuk:
Pencarian paksa atau pencarian mendalam
Ini adalah metode naif mencoba setiap kemungkinan solusi buat melihat yang terbaik.
Membagi & menaklukan (Divide and conqueror)
Algoritme bagi & takluk secara berulang mereduksi instansi jumlah masalah menjadi satu atau lebih kecil instasi perkara yang sama (umumnya secara rekursif) sampai instansi cukup kecil diselesaikan dengan gampang.
Salah satu model bagi & takluk adalah pengurutan gabung. Pengurutan dapat dilakukan disetiap segmen data selesainya membagi data sebagai segmen-segmen & urutan semua data mampu didapat dalam fase takluk menggunakan menggabungkan segmen-segmen. Variasi sederhana berdasarkan bagi-dan-takluk diklaim algoritme kurang & takluk, yg menuntaskan sub-masalah yg sama & memakai solusi menurut sub-kasus tadi buat menuntaskan kasus yang lebih akbar. Bagi & takluk membagi konflik sebagai banyak sub-masalah & sebagai akibatnya tahap takluk lebih kompleks daripada algoritme kurang-&-taklukan. Sebuah contoh dari algoritme kurang-dan-taklukan adalah algoritme pencarian binari.
Pencarian dan enumerasi
Banyak perkara (misalnya bermain catur) mampu dimodelkan sebagai perkara dalam grafik. Sebuah algoritme eksplorasi grafik menentukan aturan-aturan buat berkiprah disekitar grafik & bermanfaat bagi kasus tadi. Kategori ini juga mengikutkan algoritme pencarian, enumerasi batas dan cabang & backtracking.
Algoritme pengacakan
Algoritme ini menciptakan pilihan secara acak (atau pseudo-rambang). Ia sangat bermanfaat buat menemukan solusi perkiraan buat perkara dimana solusi yang niscaya nir mudah (lihat metode heuristik pada bawah). Untuk beberapa perkara, diketahui bahwa asumsi tercepat harus mengikutkan beberapa pengacakan.
Apakah algoritme pengacakan menggunakan kompleksitas ketika polinomial bisa sebagai algoritme tercepat untuk beberapa perkara masih menjadi pertanyaan terbukan yg dikenal sebagai Masalah P versus NP. Ada dua kelas akbar menurut algoritme ini:
- Algoritme Monte Carlo mengembalikan jawaban yg benar menggunakan probabilitas-tinggi. Misalnya, RP adalah sub-klas dari algoritme ini yg berjalan pada waktu polinomial).
- Algoritme Las Vegas selalu mengembalikan jawaban yang sahih, tetapi saat prosesnya merupakan hanya terikat secara probabilistik, misalnya ZPP.
Reduksi
Teknik ini menuntaskan kasus sulit dengan mengubahnya sebagai pertarungan yang lebih diketahui yg mana kita (berharap) mempunyai algoritme asimptotikal optimal. Tujuannya yaitu untuk menemukan sebuah algoritme reduksi yang kompleksitasnya nir didominasi oleh algoritme hasil reduksi. Sebagai contoh, algoritme seleksi buat menemukan rata-homogen dalam daftar tidak terurut mengikutkan mengurutkan daftar (bagian yg paling mahal) & menarik elemen paling tengah dalam daftar terurut (bagian yg paling gampang). Teknik ini juga diketahui menggunakan ubah dan taklukan.
Perseteruan optimisasi
Pemrograman Linear
Saat mencari solusi optimal terhadap sebuah fungsi linear yg terikat persamaan linear & ketidaksamaan konstrain, batasan berdasarkan pertarungan bisa digunakan secara langsung buat menghasilkan solusi optimal.
Ada algoritme yang dapat memecahkan setiap perseteruan pada kategori ini, seperti algoritme simpleks yg populer. Perseteruan yang bisa diselesaikan dengan pemrograman linear termasuk permasalahan alur maksimum untuk grafik terarah). Jika sebuah kasus menjadi tambahan membutuhkan satu atau lebih jawaban haruslah integer maka dia diklasifikan pada pemrograman integer. Algoritme pemrograman linear bisa menuntaskan masalah misalnya itu apabila bisa dibuktikan bahwa semua batasan buat nilai integer adalah tidak sahih, yaitu solusi memenuhi batasan tersebut. Pada perkara generik, algoritme yg dikhususkan atau algoritme yang menemukan solusi asumsi dipakai, bergantung pada kesulitan dari pertarungan.
Pemrograman bergerak maju
Bila sebuah masalah menampakan substruktur optimal, ialah solusi optimal terhadap sebuah masalah bisa direkonstruksi menurut solusi optimal ke sub-masalah, dan submasalah tumpang-tindih, merupakan sub-masalah yang sama dipakai buat merampungkan poly instasi perkara berbeda, pendekatan tercepat disebut pemrograman dinamis menghindari penghitungan solusi yang sudah dikomputasi. Sebagai model, algoritme Floyd-Warshall, jalan terpendek ke tujuan dari sebuah vertex pada grafik berbobot sanggup ditemukan menggunakan menggunakan jalan terpendek ke tujuan berdasarkan seluruh simpul yg berdekatan. Pemrograman bergerak maju dan memoisasi berpadanan. Perbedaan utama antara pemrograman bergerak maju & bagi-dan-taklukan merupakan submasalah kurang lebih independen dalam bagi-&-taklukan, sementara submasalah tumpang tindik pada pemrograman bergerak maju.
Perbedaaan antara pemrograman dinamis dan rekursi eksklusif merupakan pada 'caching' atau memoisasi berdasarkan pemanggialan rekursif. Saat submasalah independen dan tidak ada pengulangan, memoisasi nir membantu sama sekali; makanya pemrograman bergerak maju bukalanh solusi buat semua perseteruan kompleks. Dengan memakai memoisasi atau tabel berdasarkan submasalah yang telah diselesaikan, pemrograman dinamis mereduksi eksponensial dari poly konflik sebagai kompleksitas polinomial.
Metode rakus
Sebuah algoritme rakus mirip menggunakan algoritme pemrograman bergerak maju, tetapi perbedaannya adalah solusi menurut submasalah nir wajib diketahui pada setiap termin; melainkan pilihan yang "rakus" sanggup dibentuk menggunakan melihat apa yang terbaik buat ketika tersebut.
Metode rakus menyebarkan solusi menggunakan kemungkinan keputusan yg terbaik (bukan menggunakan keputusan yang terdapat) pada tahap algoritmis dari optimasi lokal yg terdapat kini & keputusan yang terbaik (bukan semua kemungkinan keputusan) yang dibuat pada langkah sebelumnya. Algoritme ini tidak terlalu mendalam, dan tidak memberikan jawaban yg akurat terhadap poly pertarungan. Tapi jika beliau bekerja, dia sebagai metode yang paling cepat. Algoritme rakus paling populer adalah menemukan rentang pohon minimal seperti dalam Pohon Huffman, Kruskal, Prim, Sollin.
Metode heuristik
Dalam perkara optimisasi, algoritme heuristik bisa dipakai buat menemukan suatu solusi yang terdekat menggunakan solusi optimal apabila andai kata menemukan solusi optimal nir mudah. Algoritme ini bekerja dengan mendekati sedikit-sedikit ke solusi optimal saat dia berjalan. Secara prinsipnya, bila dijalankan tanpa batas ketika, beliau akan menemukan solusi optimal.
Kebaikan mereka adalah mereka dapat menemukan suatu solusi sangat dekat dengan solusi optimal dalam waktu yang relatif sangat pendek. Algoritme tadi termasuk pencarian lokal, pencarian tabu, simulasi pelunakan, dan algoritme genetik. Beberapa berdasarkan mereka, misalnya simuasi pelunakan, merupakan algoritme non-deterministik ad interim yang lainnya, misalnya pencarian tabu, adalah deterministik. Saat batas menurut keliru dari solusi non-optimal diketahui, algoritme kemudia dikategorikan sebagai algoritme pendekatan.
Berdasarkan bidang kajian
Setiap bidang sains memiliki permasalahannya sendiri dan membutuhkan algoritme yang efisien. Masalah yg berkaitan pada satu bidang terkadang dipelajari bersama. Beberapa contoh yaitu algoritme pencarian, algoritme penggabungan, algoritme numerik, algoritme grafik, algoritme deret, algoritme komputasi geometri, algoritme kombinatorial, algoritmas medis, mesin belajar, kriptografi, algoritme kompresi data dan teknik penguraian.
Terkadang bidang-bidang tersebut saling tumpang tindih, & perkembangan algoritme pada satu bidang bisa menaikkan bidang lainnya yang terkadang tidak berkaitan. Sebagai misalnya, pemrograman dinamis ditemukan untuk optimisasi konsumsi asal daya pada industri, namun kini digunakan buat merampungkan sejumlah besar konflik pada poly bidang.
Berdasarkan kompleksitas
Algoritme sanggup diklasifikasikan berdasarkan jumlah saat yang dibutuhkan buat selesai dibandingkan menggunakan ukuran inputnya. Ada berbagai varietas: beberapa algoritme selesai dalam ketika linear nisbi terhadap berukuran input, beberapa selesai dalam jumlah waktu yang eksponensial atau lebih buruh, & beberapa berhenti.
Sebagai tambahan, beberapa kasus sanggup mempunyai banyak sekali algoritme menggunakan kompleksitas yang tidak sama, sementara pertarungan yg lain mampu saja tidak mempunyai algoritme atau tidak diketahui algoritmanya yg efisien. Ada jua pemetaan berdasarkan beberapa algoritme terhadap konflik lain. Karena itu, lebih cocok buat mengklasifikasikan perseteruan itu sendiri bukannya algoritme menjadi kelas-kelas yg sama dari kompleksitas dari kemungkinan algoritme terbaik baginya.
Burgin (2005, p. 24) menggunakan definisi algoritme secara umum yang melonggarkan kebutuhan beserta yg keluaran berdasarkan algoritme yg menjalankan sebuah fungsi wajib ditentukan setelah sejumlah langkah. Dia mendefinisikan kelas super-rekursif dari algoritme sebagai "sebuah kelas algoritme yang mana memungkinkan buat menghitung fungsi yg tidak sanggup dihitung oleh mesin Turing manapun" (Burgin 2005, p. 107). Hal ini berkaitan dekat dengan kajian dari metode hiperkomputasi.
Berdasarkan tipe evaluatif
Untuk menjaga keseimbangan saat mengintegrasikan mesin ke dalam rakyat, seseorang bisa mengklasifikasikan algoritme dari tipe menurut penilaian yang mereka lakukan. Sejumlah filsuf sudah berhipotesis bahwa masyarakat diuntungkan berdasarkan keragaman evaluatif seperti mereka diuntungkan keragaman jender dan tipe darah (contohnya, Dean 2012, Sober & Wilson 1998) Hertzke & McConkey 1998, & Bellah 1985). Teknologi dapat mengancam ekosistem moral tersebut seperi spesies invasif bila dia mengganggu adonan keragaman.
Wallach & Allen (2008) mengklasifikasikan algoritme penghasil-keputusan sebagai tiga tipe evaluatif: Algoritme bottom-up menciptakan penilaian nir terprediksi bagi pemrogram (misalnya, perangkat lunak yg berevolusi). Yang lainnya (top-down) dibagi menjadi deontologikal (yg dapat bergantung pada implementasi aturan pemrograman) lawan consequensialis (yg mengandalkan dalam memaksimalkan asumsi pemrograman). Sebagai contohnya, sebuah kalkulator baku termasuk deontologikal, ad interim mesin pembelajaran buat perdagangan saham termasuk consequensialis.
Santos-Lang mengganti nama deontologikal dan consequensialis sebagai kelas "institusional" dan "negosiator" menggunakan tujuan buat menghindari implikasi bahwa semua teori-teori etika deontologikal dan consequensialis sanggup diimplementasikan sebagai algoritme, dan membagi kelas bottom-up menjadi "pengganggu" (algoritme yg tidak terprediksi karena menggunakan generator pengacakan) versus "relasional" (algoritme yang nir terprediksi lantaran impak jaringan). Seorang mutator dalam komputasi evolusioner sanggup menjadi contoh berdasarkan pengganggu, sementara kelas 3 atau 4 dari otomata sellular adalah model menurut mesin relasional.
Santos-Lang mencatat bahwa algoritme terkadang mempunyai subkomponen berdasarkan tipe lainnya. Sebagai misalnya, negosiator perdagangan saham sanggup mengimplementasikan sebuah algoritme genetik, & memiliki mutator pengganggu, & mutator mampu mempunyai subkomponen institusional & relasional, seluruh komputasi merupakan relasional pada tingkat di jajaran kimiawi (Santos-Lang 2014).
Algoritme berkelanjutan
Kata sifat "berkelanjutan" apabila diterapkan dalam istilah "algoritme" sanggup berarti:
Sebuah algoritme beroperasi pada data yang merepresentasikan kuantitas yg berkelanjutan, walaupun data tersebut direpresentasikan sang pendekatan diskrit misalnya algoritme yang dipelajari pada analisis numerik; atau
Sebuah algoritme pada bentuk berdasarkan persamaan diferensial yg beroperasi secara berkelanjutan terhadap data, berjalan pada sebuah personal komputer analog.
Isu legalitas
Algoritme umumnya tidak dipatenkan. Di Amerika Serikat, sebuah klaim yang terdiri hanya dari manipulasi sederhana berdasarkan konsep abstrak, angka, atau frekuwensi tidak berarti suatu "process" (SPTO 2006), dan oleh karenanya algoritme tidak bisa dipatenkan (sebagaimana dalam Gottschalk v. Benson). Tetapi, penerapan praktis menurut algoritme terkadang dipatenkan. Sebagai misalnya, pada Diamond v.
Diehr, pelaksanaan menurut algoritme umpan-balik sederhana buat membantu dalam menyembuhkan karet sintetis dipercaya bisa dipatenkan. Mematenkan aplikasi sangat kontroversial, & terdapat paten yang mengikutkan algoritme yang sangat dikritisi, terutama algoritme kompresi data, misalnya Format Grafiknya Unisys.
Sebagai tambahan, beberapa algoritme kriptografi memiliki batasan ekspor (lihat ekspor berdasarkan kriptografi).
Etimologi
Kata "Algoritme", atau "Algorisma" dalam versi penulisan lain, datang berdasarkan nama al-Khwarizmi. Dieja dalam Arab klasik menjadi Al-Khwarithmi. Al-khwarizmi (bahasa Persia: خوارزمي, 780-850) merupakan matematikawan, pakar astronomi, pakar geografi menurut Persia dan sarjana House of Wisdom di Baghdad, yang arti namanya "penduduk orisinil Khwarezm", sebuah kota yg merupakan bagian dari Wilayah Iran pada masanya dan kini Uzbekistan.
Sekitar tahun 825, beliau menulis selebaran pada bahasa Arab, yg diterjemahkan pada Latin pada abad ke-12 dengan judul Algoritmi de numero Indorum. Judul ini artinya "Algoritmi dalam bilangan India", di mana "Algoritmi" merupakan pelatinan penerjemah menurut nama Al-Khwarizmi. Al-Khwarizmi dulunya merupakan matematikawan yang paling banyak dibaca di Eropa pada akhir Abad Pertengahan, pada generik lewat bukunya yg lain, Aljabar.
Pada akhir abad pertengahan, algorismus, perubahan berdasarkan namanya, berarti "sistem sapta desimal" yg masih merupakan arti dari istilah Inggris terbaru algorism. Pada abad ke-17 Prancis kata tadi berubah, namun tidak maknanya, menjadi algorithme. Inggris mengadopsi Prancis setelahnya, tetapi tidak dalam akhir abad ke-19 lah "Algorithm" mengambil makna menurut kata Inggris masa kini .
Etimologi cara lain menjamin berasal mulanya dari istilah algebra (aljabar) menurut makna abad pertengahan "aritmetika Arab" & arithmos kata Yunani untuk nomor (yang secara harfiah berarti "sapta Arab" atau "perhitungan Arab"). Karya algoritme Al-Kharizmi bukan berbentuk seperti pada masa modern sekarang tetapi menjadi tipe menurut 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 & persamaan kuadrat). Dalam makna tersebut, algoritima dikenal pada Eropa jauh sebelum Al-Kharizmi. Algoritme paling tua yang dikenal kini merupakan Algoritme Euklid (lihat pula Pengembangan algoritme Euklid). Sebelum ditemukan kata algorithm orang Yunani menyebutnya anthyphairesis secara harfiah berarti anti-substraksi atau substraksi timbal-kembali (buat bacaan lebih lanjut disini dan ini. Algoritme dikenal sang orang Yunani berabad sebelum Euclid.
Bukannya istilah algebra orang Yunani menggunakan kata arithmetica(ἀριθμητική, yaitu dalam karya Diophantus yang dikenal "bapak berdasarkan Aljabar" - lihat jua artikel Wikipedia persamaan Diophantine dan Eudoxos).
Sejarah: Perkembangan berdasarkan kata "algoritme"
Asal mula
Kata algoritme datang dari nama matematikawan Persia abad ke-9 Abu Abdullah Muhammad ibnu Musa Al-Khwarizmi, yang output kerjanya dibangun menurut matematikawan India abad ke-7 Brahmagupta.
Kata algorisma awalnya mengacu hanya dalam aturan-aturan dalam melakukan aritmetika memakai bilangan Hindu-Arab namun berkembang lewat penerjemahan Latin Eropa menurut nama Al-Khwarizmi menjadi algoritme pada abad ke-18. Penggunaan istilah tadi berkembang mengikutkan seluruh mekanisme buat menyelesaikan perkara atau melakukan unit aktivitas.
Simbol diskrit dan yang dapat dibedakan
Penanda-penghitung: Untuk mencatat hewan gembalaan, perpaduan biji & uang mereka orang dahulu memakai penghitung: akumulasi batu atau pertanda yang ditoreh dalam tongkat, atau membuat simbol diskrit di kerang. Sampai orang Babilonia & Mesir memakai pertanda & simbol, pada akhirnya bilangan Roma & abakus berkembang (Dilson, p. 16-41). Penanda penghitung muncul dalam sistem bilangan operan aritmetika dipakai pada mesin Turing dan komputasi mesin Post-Turing.
Manipulasi simbol sebagai "penampung" bilangan: aljabar Sunting
Karya dari Geometer Yunani antik (algoritme Euklid), matematikawan India Brahmagupta, & matematikawan Persia Al-Khwarizmi (yang darinya isitlah "algorism" & "algoritme" diturunkan), dan matematikawan Eropa Barat memuncak pada notasi Leibniz berdasarkan rasiosinator kalkulus (kurang lebih 1680-an):
Abad yang baik dan 1/2 lebih maju berdasarkan masanya, Leibniz mengajukan nalar aljabar, sebuah aljabar yg akan memilih anggaran-aturan buat memanipulasi konsep nalar dengan cara yang aljabar biasa memilih anggaran buat manipulasi angka.
Rancangan mekanis dengan tingkat diskrit
Jam: Bolter memuji inovasi jam gaya-berat menjadi "Kunci inovasi menurut Eropa pada Abad Pertengahan", khususnya pada ambang pelarian menyediakan kita menggunakan tik & tak berdasarkan jam mekanis. "Mesin otomatis yang akurat" menunjuk pribadi dalam "otomata mekanis" dimulai pada abad ke-13 & terakhir dalam "mesin komputasi" motor tidak sama dan motor analitik dari Charles Babbage & bangsawan Ada Lovelace, pertengahan abad ke-19.
Lovelace dikreditkan sebagai yg pertama membangun algoritme yg ditujukan buat diproses pada personal komputer motor analitis Babbage, perangkat pertama yang dianggap personal komputer Turing-paripurna sebenarnya bukan hanya sebuah kalkulator dan terkadang dikenal "programmer pertama pada sejarah", walaupun implementasi penuh berdasarkan perangkat Babbage kedua nir terlaksana hingga beberapa dasa warsa sesudah masanya.
Mesin nalar 1870 - Stanley Jevons "sempoa logika" dan "mesin nalar": Masalah teknisnya adalah untuk mereduksi persamaan boolean jika ditampilkan pada sebuah bentuk yang dalam masa kini dikenal menjadi pemetaan Karnaugh.
Jevons (1880) pertama menyebutkan "sempoa" sederhana menurut "rabat kayu dilengkapi menggunakan penyemat, dibuat supaya bagian atau kelas kombinasi akal manapun bisa dipilih secara mekanis ... Baru-baru ini Saya telah mereduksi sistem sebagai bentuk yang secara sempurna mekanis, & membuatnya mewujudkan holistik proses inferensi tak langsung pada apa yang disebut sebuah Mesin Logika" Mesinnya dilengkapi menggunakan "beberapa tangkai kayu yg sanggup dipindahkan" & "di bawah ada 21 kunci misalnya pada piano [dll] ...". Dengan mesin ini dia bisa menganalis sebuah "silogisme atau argumen nalar sederhana apapun".
Mesin tenun Jacquard, kartu berlobangnya Hollerith, telegraf dan telepon -- penyiaran elektromekanis: Bell & Newell (1971) menandakan bahwa mesin tenun Jacquard (1801), pelopor berdasarkan kartu Hollerith (kartu berlobang, 1887), & "teknologi alih telepon" merupakan akar dari sebuah pohon yang mengarah dalam perkembangan menurut komputer pertama.
Pada pertengahan abad ke-19 telegraf, pelopor berdasarkan telepon, digunakan diseluruh global, pengkodean diskrit & pembedaan huruf sebagai "titik & strip". Pada akhir abad ke-19 pita telegraf (kurang lebih 1870-an) digunakan, sebagaimana jua kartu Hollerith dalam sensus Amerika 1890. Kemudian muncullah teleprinter (kurang lebih 1910-an) menggunakan kerta-berlobang menggunakan kode Baudot pada pita.
Jaringan alih-telepon berdasarkan penyiaran elektromekanis (ditemukan 1835) merupakan karya dair George Stibitz (1937), penemu dari perangkat penghitungan digital. Saat bekerja pada laboratorium Bell, dia mengamati "beratnya" penggunaan kalkulator mekanis dengan geligi. "Dia pergi ke tempat tinggal dalam suatu malam 1937 berniat buat menguji idenya ... Saat mengatik terselesaikan, Stibitz telah menciptakan perangkat hitung digital".
Davis (2000) mengamati pentingnya penyiaran elektromekanis (dengan "keadaan binari"-nya buka & tutup):
Hanya dengan perkembangan, dimulai semenjak 1930-an, berdasarkan kalkulator elektromekanis memakai penggantian elektris, sehingga mesin yang dibentuk mempunyai ruang lingkup yang dibayangkan Babbage.
"Matematika selama abad 19 hingga pertengahan abad 20 Sunting
Simbol & aturan: Dengan cepat berkembangnya matematika berdasarkan George Boole (1847, 1854), Gottlob Frege (1897), & Giuseppe Peano (1888-1889) mereduksi aritmetika menjadi serangkaian simbol dimanipulasi oleh anggaran-anggaran. The Principles of arithmetic, presented by a new method-nya Peano (1888) merupakan "bisnis pertama mengaksiomakan matematika pada sebuah bahasa simbolik".
Tapi Heijenoort memberi kebanggaan pada Frege (1879): Frege "adalah karya tulis paling krusial tentang nalar. ... Yang mana kita lihat sebuah "'bahasa formula', yaitu sebuah lingua characterica, sebuah bahasa ditulis menggunakan simbol-simbol spesifik, "buat berpikir murni", yaiut, bebas dari hiasan retorikal ... Dibangun berdasarkan simbol-simbol tertentu yang dimanipulasi dari aturan-aturan terbatas". Karya dari Frege lebih lanjut disederhanakan & diperkuat oleh Alfred North Whitehead & Bertrand Russell pada Principia Mathematical (1910-1913).
Paradoks: Pada masa yang sama sejumlah lawan asas yg mengganggu ada pada literatur, pada khususnya lawan asas Burali-Forti (1987), paradoks Russell (1902-03), dan Paradoks Richard. Hasilnya menunjuk ke makalah Kurt Godel (1931) -- dia secara spesifik merujuk lawan asas suka berbohong yg mereduksi aturan dari rekursi pada angka.
Penghitungan Efektif: Dalam usaha buat menyelesaikan perseteruan keputusan yang didefinisikan oleh Hilbert tahun 1928, matematikawan pertama mendefinisikan apa arti dari "metode efektif" atau "kalkulasi efektif" (contohnya, sebuah kalkulasi yang akan sukses). Dalam waktu yang cepat hal berikut ada: kalkulus-λ sang Alonzo Church, Stephen Kleene, dan J.B. Rosser definisi menurut "rekursi generik" yang sahih-sahih diasah dari karya Godel berdasarkan saran dari Jacquard Herbrand (cf. Kuliah Godel di Princeton tahun 1934) & penyederhaan selanjutnya sang Kleene.
Church menandakan bahwa perseteruan keputusan tidak terpecahkan, definisi Emil Post tentang penghitungan efektif yaitu sebagai pekerja yg tanpa berpikir mengikuti suatu daftar instruksi buat beranjak ke arah kiri atau kanan lewat sederetan ruangan dan bersamaan menggunakan itu sanggup menandai atau menghapus kertas atau mengamati kertas & menciptakan pilihan ya tidak mengenai instruksi selanjutnya.
Pembuktian Alan Turing bahwa permasalahan keputusan nir terpecahkan menggunakan menggunakan "sebuah mesin [otomatis]"-nya menggunakan imbas yang seperti dengan "formulasi"-nya Post, definisi J. Barkley Rosser tentang "metode efektif" pada makna "sebuah mesin". Proposal S. C. Kleene dari pelopor "Tesis Church" yang disebutnya "Thesis I", & beberapa tahun kemudian Kleene menamakan tesisnya "Tesis Church" dan mengajukan "Tesis Turing".
Emil Post (1936) dan Alan Turing (1936-37, 1939)
Berikut merupakan kebetulan yg luar biasa berdasarkan dua orang yg tidak saling mengenal tetapi menggambarkan sebuah proses orang-sebagai-personal komputer mengerjakan perhitungan & mereka membentuk definisi yang mirip.
Emil Post (1936) menggambarkan aksi dari sebuah "personal komputer " (manusia) sebagai berikut:
"... Dua konsep ikut serta: yaitu sebuah simbol ruang dimana pekerjaan yang menunjuk menurut perkara ke jawaban dilakukan, & sekumpulan arahan yg standar dan nir bisa diubah.
Simbol ruangnya yaitu
"sederetan 2 arah tidak terbatas menurut ruang atau kotak... Penyelesai kasus atau pekerja wajib berjalan dan bekerja di simbol ruang ini, dengan bisanya [si pekerja] masuk, & beroperasi dengan satu kotak dalam satu saat... Sebuah kotak memiliki dua kemungkinan syarat, yaitu, kosong atau belum ditandai, dan dengan adanya tanda tunggal disana, katakanlah garis vertikal.
"Satu kotak dibiarkan dan disebut sebagai titik awal. ...Sebuah kasus eksklusif diberikan dalam bentuk simbolik dengan sejumlah kotak terbatas [yaitu, INPUT] ditandai dengan coretan. Begitu jua jawabannya [yaitu, OUTPUT] diberikan dalam bentuk simbolik menurut suatu konfigurasi menurut kotak-kotak yg ditandai....
"Sekumpulan arahan sanggup digunakan buat permasalahan generik memilih proses determistik waktu diterapkan pada setiap masalah eksklusif. Proses ini hanya berhenti jika datang arahan dengan tipe (C ) [yaitu, STOP]". Lihat lebih lanjut dalam mesin post-Turing.
Turing model menurut komputasinya kini dikenal dengan mesin Turing memulai, sebagaimana Post, menggunakan analisis menurut personal komputer manusia yang ia sederhanakan menjadi sekumpulan gerakan dasar sederhana & "keadaan pikiran". Tapi beliau terus maju selangkah ke depan & membuat sebuah mesin menjadi contoh berdasarkan komputasi angka.
"Menghitung biasanya dilakukan menggunakan menulis simbol eksklusif di atas kertas. Misalkan kertas tadi dibagi menjadi segi empat misalnya kitab aritmetika anak-anak.... Saya asumsikan bahwa komputasi dilakukan dalam kertas satu dimensi, yaitu, di pita yg dibagi pada persegi. Juga misalkan bahwa jumlah simbol yang akan dicetak terbatas....
"Perilaku berdasarkan personal komputer disetiap saat dipengaruhi oleh simbol yang diobservasinya, dan "keadaan pikiran"-nya dalam saat tadi. Juga bisa diasumsikan bahwa terdapat batas B menjadi jumlah simbol atau persegi yang mana personal komputer dapat amati dalam satu saat. Apabila dia ingin mengamati lebih, beliau wajib memakai pengamatan beriringan. Kita juga memisalkan bahwa jumlah keadaan pikiran yang diperlukan disini adalah terbatas...
"Mari kita bayangkan bahwa operasi yg dilakukan sang komputer akan dipecah menjadi 'operasi-operasi sederhana' yg sangat mendasar sehingga tidak mudah membayangkannya untuk dibagi lebih jauh."
Reduksi Turing menghasilkan hal berikut:
"Operasi sederhana haruslah mengikutkan:
"(a) Perubahan berdasarkan simbol pada salah satu persegi yg sedang diamati
"(b) Perubahan menurut salah satu persegi diamati terhadap persegi lainnya pada antara L persegi dari keliru satu yang sebelumnya diamati.
"Bisa saja beberapa dari perubahan tersebut menyebabkan perubahan keadaan pikiran. Operasi tunggal paling generik sang karena itu wajib diambil jadi galat satu hal berikut:
"(A) Suatu kemungkinan perubahan (a) berdasarkan simbol bersamaan dengan suatu perubahan berdasarkan keadaan pikiran.
"(B) Suatu kemungknian perubahan (b) menurut persegi yang diamati, beserta menggunakan kemungkinan perubahan dari keadaan pikiran".
"Kita kini mungkin sudah sanggup membangun sebuah mesin untuk melakukan pekerjaan menurut personal komputer tersebut."
Beberapa tahun kemudian, Turing mengembangkan analisanya (tesis, secara definisi) dengan ekspresi bertenaga berikut:
"Sebuah fungsi dikatakan "mampu dihitung secara efektif" jika nilainya sanggup ditemukan menggunakan proses yang murni mekanis.
Walau sangat gampang menangkap ilham 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 pakai pernyataan tersebut secara harfiah, memahami murni dengan proses mekanis yang mana bisa dilakukan sang sebuah mesin.
Memungkinkan buat menaruh deskripsi matematis, pada beberapa bentuk normal, menurut struktur mesin tersebut. Perkembangan dari inspirasi ini menunjuk pada definisi penulis menurut sebuah fungsi yg bisa dihitung, dan buat mengidentifikasi komputibilitas † dengan penghitungan yg efektif . . . .
"† Kita boleh menggunakan aktualisasi diri "fungsi hitung" buat mengartikan sebuah fungsi yang dapat dihitung oleh sebuah mesin, dan kita abaikan "secara efektif bisa dihitung" mengacu pada wangsit intuitif tanpa definisi eksklusif menggunakan galat satu dari definisi tadi".
J. B. Rosser (1939) dan S. C. Kleene (1943)
J. Barkley Rosser mendefinisikan 'metode [matematis] efektif' dengan cara berikut (kemiringan dibubuhi):
"'Metode efektif' diklaim sebagai metode yg spesial yang mana setiap langkahnya secara tepat dipengaruhi dan pasti membentuk jawaban dalam sejumlah langkah yang terbatas. Dengan pengertian khusus ini, 3 definisi tidak sama sudah diajukan hingga sekarang. [catatan kakinya #5; lihat diskusinya di bawah]. Yang paling sederhana (karena Post & Turing) menyatakan pada dasarnya bahwa sebuah metode efektif menuntaskan sekumpulan pertarungan hanya ada bila seseorang mampu menciptakan sebuah mesin yg akan merampungkan setiap masalah dari sekumpulan kasus tanpa campur tangan insan kecuali memasukan pertanyaan dan (nantinya) membaca jawabannya. Ketiga definisi tersebut sama, jadi nir kasus yg mana yg digunakan. Lebih lanjut, fakta bahwa ketiganya sama merupakan argumen yg sangat kuat buat kebenaran dari salah satunya.
" (Rosser 1939:225-6)
Catatan kaki Rosser #lima merujuk karya berdasarkan (1) Church dan Kleene & definisi dari definabiliti-λ, secara khusus Church menggunakannya pada 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) pada model mekanisme komputasi mereka.
Stephen C. Kleene didefinisikan menjadi "Thesis I"-nya yang populer yang dikenal menjadi tesis Church-Turing. Tapi dia melakukan hal tersebut pada konteks berikut (penebalan berdasarkan aslinya):
"12. Teori-teori algoritme... Dalam menyiapkan sebuah teori algoritme yang komplet, apa yg kita lakukan adalah menggambarkan sebuah prosedur, yg dapat dilakukan buat setiap formasi nilai berdasarkan variabel-variabel tunggal, yang mana prosedur berhenti dan menggunakan cara tersebut dari hasilnya kita sanggup membaca sebuah jawaban eksklusif, "ya" atau tidak", buat pertanyaan "apakah nilai predikat sahih?"" (Kleene 1943:273).
Sejarah selesainya 1950
Sejumlah usaha telah diarahkan buat memperbaiki lebih lanjut definisi dari "algoritme", & aktivitas tersebut masih terus berjalan lantaran info-info yang mengelilinginya, terutama, fondasi matematika (khususnya tesis Church-Turing) & filsafat pikiran (khususnya argumen menyangkut kecerdasan protesis). Lebih lanjut, lihat karakterisasi algoritme.
Komentar
Posting Komentar