Algoritma dalam bahasa formal yang didefinisikan dengan baik untuk menghitung 1

ASAL KATA

‘Algoritma’ muncul dari ‘Algoritmi’, bentuk Latin dari al-Khwarizmi, matematikawan, ahli astronomi, dan ahli geografi dari Persia

Dalam matematika dan ilmu komputer, algoritma adalah prosedur langkah-demi-langkah untuk penghitungan. Algoritma digunakan untuk penghitungan, pemrosesan data, dan penalaran otomatis.

Algoritma adalah metode efektif diekspresikan sebagai rangkaian terbatas dari instruksi-instruksi yang telah didefinisikan dengan baik untuk menghitung sebuah fungsi. Dimulai dari sebuah kondisi awal dan input awal (mungkin kosong), instruksi-instruksi tersebut menjelaskan sebuah komputasi yang, bila dieksekusi, diproses lewat sejumlah urutan kondisi terbatas yang terdefinisi dengan baik, yang pada akhirnya menghasilkan “keluaran”  dan berhenti di kondisi akhir. Transisi dari satu kondisi ke kondisi selanjutnya tidak harus deterministik. Beberapa algoritma, dikenal dengan algoritma pengacakan, menggunakan masukan acak.

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 algoritma 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” atau “metode efektif“. 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 Post pada tahun 1936, dan Mesin Turing-nya Alan Turing pada tahun 1936-7 dan 1939. Dari definisi formal dari algoritma di atas, berkaitan dengan konsep intuituf, masih tetap ada masalah yang menantang.

Diagram alur dari sebuah algoritma (Algoritma Euclid) untuk menghitung faktor persekutuan terbesar (f.p.k.) dari dua angka a dan b dalam lokasi bernama A dan B. Algoritma dijalankan dengan pengurangan berturut-turut dalam dua pengulangan: JIKA pengujian B >= A menghasilkan “ya” (atau benar) (lebih akuratnya angka b dalam lokasi B lebih besar atau sama dengan angka a dalam lokasi A) MAKA, algoritma menentukan B ← B – A (artinya angka b – a menggantikan b sebelumnya). Hal yang sama, JIKA A > B, MAKA A ← A – B. Proses tersebut berhenti saat (isi dari) B adalah 0, menghasilkan f.p.k. dalam A. (Algoritma tersebut diambil dari Scott 2009:13; simbol dan gaya penggambaran dari Tausworthe 1977).

DEFINISI INFORMAL

Definisi informalnya bisa berarti “sekumpulan aturan yang secara tepat menentukan seurutan operasi” yang mengikutkan semua program komputer, termasuk program yang tidak melakukan perhitungan numerik. Secara umum, sebuah program hanyalah sebuah algoritma jika ia akan berhenti nantinya.

Sebuah contoh prototipikal dari suatu algoritma adalah algoritma Euclid untuk menentukan bilangan pembagi terbesar dari dua integer sebagai contohnya (ada contoh yang lain) dijelaskan dengan diagram alur di atas dan sebagai contoh di bagian lanjut.

Boolos & Jeffrey (1974, 1999) memberikan sebuah makna informal dari kata algoritma dalam persamaan berikut:

Tidak ada manusia yang dapat menulis begitu cepat, atau begitu lama, atau begitu kecil (“kecil, dan lebih kecil tanpa batas … anda mungkin mencoba menulis di atas molekul, atom, elektron”) untuk mencatat semua anggota dari kumpulan bilangan tak terbatas dengan menuliskan namanya, bergantian, dalam suatu notasi. Tapi manusia bisa melakukan sesuatu yang sama bergunanya, pada kasus kumpulan bilangan tak terbatas: Mereka dapat memberikan instruksi jelas untuk menentukan anggota ke-n dari set, untuk n terbatas acak. Instruksi tersebut diberikan secara eksplisit, dalam bentuk yang dapat diikuti oleh mesin penghitung, atau oleh manusia yang mampu melakukan hanya operasi-operasi dasar dengan simbol-simbol.

Suatu “bilangan tak-terbatas” adalah bilangan yang elemen-elemenya bisa berkorespondensi satu-ke-satu dengan integer. Maka, Boolos dan Jeffrey mengatakan bahwa sebuah algoritma berarti instruksi bagi sebuah proses yang “membuat” keluaran integer dari sebuah “masukan” acak integer yang, secara teori, bisa sangat besar. Maka sebuah algoritma dapat berupa persamaan aljabar seperti y = m + n — dua variabel masukan m dan n yang menghasikan keluaran y. Tapi berbagai penulis yang mencoba mendefinisikan persamaan tersebut mengatakan bahwa kata algoritma mengandung lebih dari itu, sesuatu yang kurang lebih (untuk contoh penjumlahan):

Konsep dari algoritma juga digunakan untuk mendefinisikan notasi dari desidabilitas. Notasi tersebut adalah pusat untuk menjelaskan bagaimana sistem formal berasal dari sejumlah kecil aksioma dan aturan. Dalam logika, waktu dari sebuah algoritma untuk selesai tidak dapat dihitung, karena tidak berelasi dengan dimensi fisik kita. Dari ketidakpastian tersebut, yang mengkarakteristikan pekerjaan yang sedang berjalan, timbulah ketidak-tersediannya definisi algoritma yang sesuai dengan konkret (pada tingkat tertentu) dan penggunaan secara abstrak dari istilah tersebut.

FORMALISASI

Algoritma sangat penting bagi cara komputer mengolah data. Banyak program komputer mengandung algoritma memberikan rincian pada instruksi khusus yang komputer harus lakukan (dengan urutan tertentu) untuk menjalankan pekerjaan tertentu, seperti menghitung gaji karyawan atau mencetak kartu rapor siswa. Maka, sebuah algoritma bisa dianggap sebagai urutan operasi yang bisa disimulasikan oleh sebuah sistem Turing-lengkap. Penulis yang mendukung tesis ini termasuk Minsky (1967), Savage (1987), dan Gurevich (2000):

Minsky: “Tapi kita juga menjaga, dengan Turing … bahwa setiap prosedur yang “secara alami” disebut efektif, bisa dinyatakan oleh mesin (sederhana). Walaupun tampaknya ekstrim, alasan tersebut … sukar disanggah”.

Gurevich: “… argumen informal Turing untuk menyokong tesis ini membenarkan tesis yang lebih kuat: setiap algoritma bisa disimulasikan oleh sebuah mesin Turing … menurut Savage [1987], sebuah algoritma adalah sebuah proses penghitungan yang ditentukan oleh sebuah mesin Turing”.

Biasanya, bila sebuah algoritma dihubungkan dengan pengolahan informasi, data dibaca dari sumber masukan, ditulis ke perangkat keluaran, dan/atau disimpan untuk pengolahan selanjutnya. Data simpanan dianggap sebagai bagian dari keadaan internal dari entitas yang melakukan algoritma. Pada praktiknya, keadaan tersebut disimpan pada satu atau lebih struktur data.

Untuk beberapa proses komputasi, algoritma harus ditentukan secara teliti , dijabarkan dengan cara ia bakal berlaku untuk semua kemungkinan yang dapat timbul. Yaitu, setiap langkah tambahan harus secara sistematis dihadapi, kasus-per-kasus. Kriteria bagi setiap kasus harus jelas (dan bisa dihitung).

Karena sebuah algoritma adalah kumpulan dari langkah-langkah yang tepat, urutan dari komputasi selalu penting bagi berfungsinya algoritma. Instruksi biasanya diasumsikan terdaftar secara eksplisit, dan dijelaskan dimulai “dari atas” dan terus “ke bawah“, sebuah gambaran yang dijelaskan secara formal oleh alur kontrol

Sejauh ini, diskusi tentang formalisasi algoritma telah mengasumsikan premis dari pemrograman imperatif. Hal ini merupakan konsepsi umum, yang mencoba menjelaskan sebuah pekerjaan dalam makna diskrit dan “mekanis“. Keunikan dari konsepsi formalisasi algoritma adalah operasi penetapan, mengatur nilai dari sebuah variabel. Ia berasal dari intuisi “ingatan” sebagai kertas buram. Contoh operasi penetapan tersebut ada di bawah.

Untuk konsepsi yang lain dari apa yang membentuk sebuah algoritma lihat pemrograman fungsional dan pemrograman logika.

MENGGAMBARKAN ALGORITMA

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

Ada banyak macam kemungkinan representasi dan seseorang dapat mengekspresikan sebuah program mesin Turing sebagai urutan dari tabel-tabel mesin, sebagai diagram alur dan bagan drakon, atau sebagai bentuk kode mesin atau kode assembly dasar yang dikenal “kumpulan lipat empat”.

Representasi dari algoritma dapat dikelompokan ke dalam tiga tingkatan dari deskripsi mesin Turing.

Sebagai contoh dari algoritma sederhana “Penjumlahan m+n” dijelaskan dalam tiga tingkatan tersebut.

IMPLEMENTASI

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