Nama Guru : Ikbal Ramdani, A.md.kom
Sekolah : SMK Cimahi Cicantayan
Dalam matematika dan ilmu komputer, algoritme adalah prosedur langkah-demi-langkah untuk penghitungan. Algoritme digunakan untuk penghitungan, pemrosesan data, dan penalaran otomatis.
Algoritme adalah metode efektif diekspresikan sebagai rangkaian terbatas [1] dari instruksi-instruksi yang telah didefinisikan dengan baik [2] untuk menghitung sebuah fungsi.[3] Dimulai dari sebuah kondisi awal dan input awal (mungkin kosong),[4] instruksi-instruksi tersebut menjelaskan sebuah komputasi yang, bila dieksekusi, diproses lewat sejumlah urutan kondisi terbatas [5] yang terdefinisi dengan baik, yang pada akhirnya menghasilkan "keluaran" [6] dan berhenti di kondisi akhir. Transisi dari satu kondisi ke kondisi selanjutnya tidak harus deterministik; beberapa algoritme, dikenal dengan algoritme pengacakan, menggunakan masukan acak.[7]
Walaupun algorism-nya al-Khawarizmi dirujuk sebagai aturan-aturan melakukan aritmetika menggunakan bilangan Hindu-Arab dan solusi sistematis dan persamaan kuadrat, sebagian formalisasi yang nantinya menjadi algoritme modern dimulai dengan usaha untuk memecahkan permasalahan keputusan(Entscheidungsproblem) yang diajukan oleh David Hilbert pada tahun 1928. Formalisasi selanjutnya dilihat sebagai usaha untuk menentukan "penghitungan efektif" [8] atau "metode efektif"; [9] formalisasi tersebut mengikutkan Godel-Herbrand-Kleene fungsi rekursif-nya Kurt Godel - Jacques Herbrand - Stephen Cole Kleene pada tahun 1930, 1934, dan 1935, kalkulus lambda-nya Alonzo Church pada tahun 1936, "Formulasi 1"-nya Emil Postpada tahun 1936, dan Mesin Turing-nya Alan Turing pada tahun 1936-7 dan 1939. Dari definisi formal dari algoritme di atas, berkaitan dengan konsep intuituf, masih tetap ada masalah yang menantang.
Dalam sistem komputer, sebuah algoritme pada dasarnya adalah instansi dari logika ditulis dalam perangkat lunak oleh pengembang perangkat lunak supaya efektif untuk komputer yang "ditargetkan" untuk mesin tertentu untuk menghasilkan keluaran dari masukan yang diberikan (kemungkinan nul).
Program yang "elegan" (padat), program yang "baik" (cepat): Pernyataan dari "sederhana dan elegan" muncul secara informal dalam buku Knuth dan dalam Chaitin:
- Knuth: "... kita menginginkan 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 tipe instruksi 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 kebenaranmenggunakan 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.
Komentar