Algoritma

Menggambarkan algoritmeSunting

Algoritme dapat digambarkan dengan banyak notasi, termasuk bahasa alamiah, pseudokode, diagram alur, bagan drakon, bahasa pemrograman atau tabel kontrol(diproses oleh penerjemah). Ekspresi bahasa alamiah terhadap algoritme condong lebih banyak dan rancu, dan jarang digunakan untuk algoritme yang kompleks dan teknis. Pseudokode, diagram alur, bagan drakon, dan tabel kontrol adalah cara yang terstruktur untuk menggambarkan algoritme yang mencegah banyaknya kerancuan pada pernyataan-pernyataan bahasa alamiah. Bahasa pemrograman ditujukan untuk mengekspresikan algoritme dalam sebuah bentuk yang dapat dieksekusi oleh komputer, tetapi sering kali digunakan sebagai suatu cara untuk menentukan atau mendokumentasikan algoritme.

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 algoritme dapat dikelompokan ke dalam tiga tingkatan dari deskripsi mesin Turing: ^[23]

1 Deskripsi tingkat-tinggi

"... ditujukan untuk menjelaskan algoritme, menghiraukan rincian implementasi. Pada tingkat ini kita tidak perlu menyebutkan bagaimana mesin mengatur perangkat pita atau kepala pita rekam."

2 Deskripsi implementasi

"... digunakan untuk menjelaskan cara mesin Turing menggunakan kepalanya dan cara menyimpan data. Pada tingkat ini kita tidak memberikan secara rinci kondisi atau fungsi transisi."

3 Deskripsi formal

Lebih rinci, "tingkat paling rendah", menjelaskan "tabel kondisi" dari mesin Turing.

Sebagai contoh dari algoritme sederhana "Penjumlahan m+n" dijelaskan dalam tiga tingkatan tersebut lihat contoh algoritme.

ImplementasiSunting

Kebanyakan algoritme ditujukan untuk diimplementasikan sebagai program komputer. Namun, algoritme juga diimplementasikan dengan tujuan lain, seperti dalam jaringan saraf biologis (sebagai contohnya, otak manusia yang mengimplementasikan aritmetika atau sebuah serangga yang melihat makanan), dalam sirkuit elektris, atau dalam sebuah perangkat mekanis.

Algoritme komputerSunting

Contoh diagram alur dari struktur Bohm-Jacopini: URUTAN (segi empat), WHILE-DO dan IF-THEN-ELSE. Ketiga struktur dibentuk dari kondisi primitif GOTO ( IF test=true THEN GOTO step xxx ) (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 algoritme pada dasarnya adalah instansi dari logikaditulis dalam perangkat lunak oleh pengembang perangkat lunak supaya efektif untuk komputer yang "ditargetkan" untuk mesin tertentu untuk menghasilkan keluarandari masukan yang diberikan (kemungkinan nul).

Program yang "elegan" (padat), program yang "baik" (cepat): Pernyataan dari "sederhana dan elegan" muncul secara informal dalam buku Knuth dan dalam Chaitin:

Knuth: "... kita menginginkan algoritme yang baik dalam definisi estetika sederhana. Salah satu kriterianya ... adalah waktu yang dibutuhkan untuk berjalannya algoritme ... Kriteria yang lain adalah adaptasi dari algoritme ke komputer, kesederhanaan dan elegan, dll"^[24]

Chaitin: "... sebuah program adalah 'elegan, maksud saya adalah ia merupakan program terkecil untuk menghasilkan keluaran."^[25]

Chaitin membuka definisinya dengan: "Saya akan perlihatkan bahwa anda tidak dapat membuktikan sebuah program adalah 'elegan'"—bukti tersebut akan menyelesaikan permasalahan perhentian (ibid).

Algoritme terhadap fungsi yang dapat dihitung oleh algoritme: Untuk sebuah fungsi bisa ada beberapa algoritme. Hal ini benar, bahkan tanpa mengembangkan kumpulan instruksi yang ada bagi programmer. Rogers mengamati bahwa "Sangat ... penting untuk membedakan antara pengertian algoritme, misalnya prosedur dan pernyataan fungsi yang dihitung oleh algoritme, misalnya pemetaan hasil dari prosedur. Fungsi yang sama bisa memiliki beberapa algoritme berbeda". ^[26]

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 algoritme Euclid bisa dilihat di bawah.

Komputer (dan komputor), model dari komputasi: Sebuah komputer (atau manusia "komputor" ^[27] ) adalah tipe terbatas dari mesin, sebuah "perangkat mekanis deterministik diskrit" ^[28] yang secara buta mengikuti instruksinya ^[29]. Model primitif dari Melzak dan Lambek ^[30] mereduksi pemikiran tersebut menjadi empat elemen: (i) diskrit, lokasi yang bisa dibedakan, (ii) diskrit, penghitung yang tak bisa dibedakan ^[31] (iii) sebuah agen, dan (iv) sebuah daftar instruksi yang efektif relatif terhadap kemampuan dari agen. ^[32]

Minsky menjelaskan variasi yang lebih sesuai dari model "abacus"-nya Lambek dalam "Basis Komputabilitas Paling Sederhana". ^[33]Mesin Minsky memproses secara berurutan lewat lima (atau enam tergantung bagaimana seseorang menghitungnya) instruksi kecuali baik sebuah kondisi IF-THEN GOTO atau GOTO tak bersyarat mengubah alur program keluar dari urutan. Selain HALT, mesin Minsky mengikutkan tiga operasi penetapan(penggantian, substitusi): ^[34] ZERO (misalnya, isi dari lokasi diganti oleh 0: L ← 0), SUCCESSOR (misalnya, L ← L+1), dan DECREMENT (misalnya, L ← L-1). ^[35] Jarang seorang programer harus menulis "kode" dengan kumpulan instruksi terbatas. Tapi Minsky memperlihatkan (sebagaimana Melzak dan Lambek) bahwa mesinnya adalah Turing komplet dengan hanya empat tipeinstruksi utama: GOTO kondisional, GOTO tak bersyarat, penetapan/penggantian/substitusi, dan HALT. ^[36]

Simulasi dari sebuah algoritme: bahasa komputer (komputor): Knuth menganjurkan pembaca bahwa "cara terbaik untuk belajar algoritme dalah mencobanya ... langsung ambil pulpen dan kertas dan bekerja lewat contoh". ^[37] Lalu bagaimana dengan simulasi atau eksekusi yang sebenarnya? Programmer harus menerjemahkan algoritme ke dalam bahasa yang mana simulator/komputer/komputor dapat mengeksekusi secara efektif. Stone memberikan contoh dari hal ini: saat menghitung akar dari persamaan kuadrat si komputor harus tahu bagaimana mendapatkan akar kuadrat. Jika tidak maka supaya algoritme dapat efektif ia harus menyediakan sejumlah aturan untuk mengekstrak akar kuadrat. ^[38]

Hal ini berarti programer harus tahu sebuah "bahasa" yang efektif relatif terhadap target pada agen komputasi (komputer/komputor).

Lalu model apa yang seharusnya digunakan untuk simulasi? Van Emde Boas mengamati "bahkan bila kita mendasari teori kompleksitas dengan mesin abstrak bukannya mesin kongkrit, kesembarangan dari pemilihan model masih tetap ada. Pada titik itulah mulainya pemikiran simulasi". ^[39]Bila kecepatan yang dihitung, jumlah instruksi berpengaruh. Sebagai contohnya, subprogram dalam algoritme Euclid untuk menghitung sisa akan berjalan lebih cepat jika programmer memiliki instruksi "modulus" (sisa pembagian) bukannya dengan pengurangan (atau lebih parah: hanya "penurunan").

Pemrograman terstuktur, struktur kanonikal: Menurut Tesis Church-Turing setiap algoritme bisa dihitung dengan sebuah model yang dikenal Turing komplet, dan menurut demonstrasi Minsky kekomplitan Turing membutuhkan hanya empat tipe instruksi—GOTO bersyarat, GOTO tak bersyarat, penetapan, HALT. Kemeny dan Kurtz mengamati bahwa saat penggunaan GOTO tak bersyarat yang "tak disiplin" dan IF-THEN GOTO bersyarat bisa menghasilkan "kode spageti" seorang programer bisa menulis program terstruktur menggunakan instruksi tersebut; di lain sisi "juga memungkinkan, dan tidak begitu sulit, untuk menulis sebuah program terstruktur yang buruk dalam sebuah bahasa terstruktur". ^[40] Tausworthe menambahkan tiga struktur kanon Bohm-Jacopini: ^[41] SEQUENCE, IF-THEN-ELSE, dan WHILE-DO, dengan dua lagi: DO-WHILE dan CASE. ^[42] Keuntungan dari program terstruktur adalah ia cocok dengan pembuktian kebenaran menggunakan induksi matematika. ^[43]

Simbol diagram alur^[44]: Pembantu grafik yang disebut diagram alur memberikan suatu cara untuk menjelaskan dan mendokumentasikan sebuah algoritme (dan program komputer). Seperti alur program dari mesin Minsky, sebuah diagram alur selalu mulai dari atas dan terus ke bawah. Simbol utamanya hanya 4: arah panah memperlihatkan alur program, segi empat (SEQUENCE, GOTO), wajik (IF-THEN-ELSE), dan titik (OR). Struktur kanonikal Bohm-Jacopini dibuat dari bentuk-bentuk primitif tersebut. Sub-struktur bisa "bersarang" dalam segi empat hanya jika jalan keluar tunggal terjadi pada super-struktur. Simbol dan penggunaannya untuk membangun struktur kanonikal diperlihatkan dalam diagram.

ContohSunting

Info lebih lanjut: Contoh algoritme

Contoh AlgoritmeSunting

Animasi dari algoritme quicksortmengurutkan larik dari nilai acak. Batang merah menandakan elemen pivot; pada awal animasi, elemen paling kanan dipilih sebagai pivot.

Salah satu dari algoritme sederhana adalah menemukan bilangan terbesar dalam sebuah deretan angka (tak berurut). Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tetapi hanya sekali. Dari hal ini munculah algoritme sederhana, yang bisa dinyatakan dalam kalimat bahasa deskripsi tingkat-tinggi, sebagai:

Deskripsi tingkat-tinggi:

1. Jika tidak ada angka dalam deret makan tidak ada bilangan terbesar.
2. Asumsikan item pertama dalam deret adalah yang terbesar.
3. Untuk setiap sisa angka dalam deret, jika angka tersebut besar dari angka terbesar sekarang, anggap angka tersebut menjadi yang terbesar dalam deret.
4. Bila tidak ada lagi angka yang tersisa pada deret untuk diperiksa, anggap angka terbesar sekarang menjadi angka yang terbesar dalam deret.

Deskripsi (Quasi-)formal: Ditulis dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, berikut ini adalah kode formal dari algoritme dalam pseudokodeatau 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.

Algoritme EuclidSunting

Info lebih lanjut: Algoritme Euklid

Contoh diagram dari algoritme Euclid dari T.L. Health 1908 dengan rincian tambahan. Euclid tidak sampai pada penghitungan ketiga dan tidak memberikan contoh numeris. Nocomachus memberikan contoh dari 49 dan 21: "Saya mengurangi yang kecil dari yang besar; 28 adalah yang kiri; kemudian saya kurangi lagi 21 (hal ini memungkinkan); tersisa 7, tetapi 7 tidak bisa dikurangi dari 7." Heath berkomentar bahwa, "Kalimat terakhir terdengar aneh, tetapi maknanya sangat jelas, begitu juga makna dari kalimat tentang mengakhiri 'dengan satu dan angka yang sama'."(Heath 1908:300).

Algoritme Euclid muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari Elements. ^[45] Euclid mengajukan permasalahan: "Ambil dua angka bukan prima, untuk mencari bilangan pembagi terbesar". Dia menentukan "Sebuah angka [merupakan] besaran yang terdiri dari unit-unit": angka penghitung, integer positif kecuali 0. Dan "mengukur" adalah menempatkan ukuran panjang terkecil s dengan tepat (q kali) di antara ukuran terpanjang l sampai sisa r lebih kecil dari panjang terkecil s. ^[46] Dalam dunia modern, sisa r = l - q*s, q sebagai hasil bagi, atau sisa r adalah "modulus", bagian sisa-integer yang tersisa setelah pembagian. ^[47]

Supaya metode Euclid berhasil, panjang awalnya harus memenuhi dua kebutuhan: (i) panjangnya tidak 0, DAN (ii) hasil pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka adalah hasil pengurangan dari yang terbesar (cara lain, keduanya bisa sama sehingga pengurangan menghasilkan 0).

Pembuktian asli Euclid mengikutkan kebutuhan yang ketiga: kedua panjang bukanlah bilangan prima. Euclid menentukan hal ini supaya dia bisa membentuk sebuah bukti reductio ad absurdum bahwa dua pembagi dua angka adalah yang terbesar. ^[48]Walau algoritme Nicomachus sama dengan Euclid, bila kedua bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi terbesar. Jadi untuk lebih jelasnya algoritme berikut adalah algoritme Nicomachus.

ContohSunting

Ekspresi grafik dari algoritme Euclid menggunakan contoh dengan 1599 dan 650.

1599 = 650*2 + 299
650 = 299*2 + 52
299 = 52*5 + 39
52 = 39*1 + 13
39 = 13*3 + 0

Bahasa komputer untuk algoritme EuclidSunting

Hanya beberapa tipe instruksi yang dibutuhkan untuk mengeksekusi algoritme—beberapa tes logika (GOTO bersyarat), GOTO tak bersyarat, penetapan (penggantian), dan pengurangan.

• Sebuah lokasi disimbolkan dengan huruf besar, misalnya, S, A, dll.
• Kuantitas beragam (angka) dalam sebuah lokasi ditulis dengan huruf kecil dan (biasanya) dihubungkan dengan nama lokasi. Sebagai contohnya, lokasi L pada awal bisa mengandung angka l = 3009.

Program yang kurang elegan (inelegan) untuk algoritme EuclidSunting

"Inelegan" adalah terjemahan dari versi Knuth terhadap algoritme berdasarkan pengulangan-sisa mengganti pembagian (atau instruksi "modulus"). Diambil dari Knuth 1973:2-4. Bergantung pada kedua angka "Inelegan" bisa menghitung f.p.k dengan sedikit langkah daripada "elegan".

Algoritme berikut disebut sebagai versi Euclid dan Nichomachus 4-langkah-nya Knuth, tetapi bukannya menggunakan pembagi untuk menentukan sisa ia menggunakan pengurangan berturut-turut dari panjang terkecil s dari sisa panjang r sampai r kurang dari s. Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:

INPUT:

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 di R kurang dari panjang terkecil s pada S, kurangi angka s dalam S berulang kali dari sisa panjang r dalam R.

7 IF S > R THEN
   selesai mengukur jadi
   GOTO 10
 ELSE
   ukur lagi,
8 R ← R - S
9 [Pengulangan-sisa]:
   GOTO 7.

E2: [Apakah sisa 0?]: APAKAH (i) pengukuran terakhir adalah sama dan sisa di R adalah 0 program dapat berhenti, ATAU (ii) algoritme harus terus jalan: hasil pengukuran meninggalkan sisa di R kurang dari 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 untuk mengukur angka terkecil sebelumnya s:; L sebagai lokasi sementara.

11 L ← S
12 R ← S
13 S ← L
14 [Ulang proses pengukuran]:
   GOTO 7

OUTPUT:

15 [Selesai. S berisi faktor persekutuan terbesar]:
   PRINT S

DONE:

16 HALT, END, STOP.

Klik disini