Sejarah ALGORITMA

Sejarah ALGORITMA

   Algoritma adalah jantung ilmu komputer atau informatika. Banyak cabang dari ilmu komputer yang diacu dalam terminologi algoritma, misalnya algoritma perutean (routing) pesan di dalam jaringan komputer, algoritma brensenham untuk menggambar garis lurus (bidang grafika komputer), algoritma Knuth-Morris-Pratt untuk mencari suatu pola di dalam teks (bidang information retrievel), dan sebagainya.

   Ditinjau dari asal usul kata, kata "algoritma" sendiri mempunyai sejarah yang cukup aneh. Kata ini tidak muncul di dalam kamus Webster sampai akhir tahun 1957. Orang hanya menemukan kata algorism yang berarti proses meghitung angka Arab. Anda dikatakan algorist jika anda menggunakan angka Arab. Para ahli bahasa berusaha menemukan asal kata algorism ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal muasal kata tersebut. Kata algorism berasal dari nama penulis buku Arab yang terkenal, yaitu Abu Ja'far Muhammad ibnu Musa al-Khuwarizmi (al-Khuwarizmi dibaca orang Barat menjadi algorism). Al-Khuwarizmi menulis buku yang berjudul Kitab al jabar wal-muqabala, yang artinya "Buku pemugaran dan pengurangan" (The book of restoration and reduction). Dari judul buku itu kita juga memperoleh akar kata "aljabar" (algebra). Perubahan dari kata algorism menjadi algorithm muncul karena kata algorism sering dikelirukan dengan arithmetic, sehingga akhiran -sm berubah menjadi -thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang sudah biasa/lumrah, maka lambat laun kata algorithm berangsur-angsur diapaki sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna aslinya. Dalam bahasa Indonesia, kata algorithm diserap menjadi "algoritma".
   Pada tahun 1950, kata algoritma pertama kali digunakan pada "algoritma Euclidean" (Euclid's algorithm). Euclid, seorang matematikawan Yunani (lahir pada tahun 350 M), dalam bukunya yang berjudul Element menuliskan langkah-langkah untuk menemukan pembagi bersama terbesar (common greatest divisor atau gcd), dari dua buah bilangan bulat, m dan n. (tentu saja Euclid tidak menyebut metodenya itu sebagai algoritma, baru di abad modernlah orang-orang menyebut metodenya itu sebagai "algoritma Euclidean"). Pembagi bersama terbesar dari dua buah bilangan bulat tak-negatif adalah bilangan bulat positif terbesar yang habis membagi kedua bilangan tersebut.

Misalnya, m=80 dan n=12 Semua faktor pembagi 80 adalah

          1,2,4,5,8,10,16,20,40,80

dan semua faktor pembagi 12 adalah

          1,2,3,4,6,12

maka gcd(80,12) = 4. Langkah - langkah mencari gcd(80,12) dengan algoritma Euclidean sebagai berikut:

          80 dibagi 12 hasilnya = 6 sisa = 8          (atau: 80 = 6.12+8)
          12 dibagi 8 hasilnya = 1, sisa = 4           (atau: 12 = 1.8+4)
          8 dibagi 4 hasilnya   = 2, sisa = 0            (atau: 8 = 4.2+0)

Karena pembagian yang terakhir menghasilkan 0, maka sisa pembagian terakhir sebelum 0, yaitu 4, menjadi gcd(80,12). Jadi, gcd(80,12) = gcd(12,8) = gcd(4,0) = 4. Proses mencari gcd dari 80 dan 12 juga dapat diilustrasikan dalam diagram berikut:

                                                                          

Terdapat beberapa versi algoritma Euclidean, salah satu versinya dituliskan dibawah ini.

ALGORITMA Euclidean: {Diberikan dua buah bilangan bulat tak-negatif m dan n ( m ≥ n). Algoritma Euclidean mencari pembagi bersama terbesar, gcd, dari kedua bilangan tersebut, yaitu bilangan bulat positif terbesar yang habis membagi m dan n.} 1. Jika n = 0 maka m adalah jawabannya ; stop. tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2. Bagilah m dengan n dan misalkan r adalah sisanya. 3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.

Dengan menggunakan algoritma Euclidean ini, kita dapat menghitung gcd dari dua bilangan bulat sembarang secara sistematis.

Contoh-contoh algoritma yang sudah dijelaskan di atas memberi dua pesan penting. Pertama, sebuah algoritma harus benar. Kedua, algoritma harus berhenti, dan setelah berhenti, algoritma memberi hasil yang benar.
Menurut Donald E. Knuth dalam bukunya yang berjudul The Art of Computer Programming, sebuah algoritma harus mempunyai lima ciri penting:
1.  Algoritma harus berhenti setelah mengerjakan sejumlah langkah terbatas. Sebagai contoh, tinjau kembali algoritma Euclidean. Pada langkah 1, jika n=0, algoritma berhenti. Jika n ≠ 0, maka nilai n selalu berkurang sebagai akibat langkah 2 dan 3, dan pada akhirnya nilai n=0. Program yang tidak pernah berhenti mengindikasikan bahwa program tersebut berisi algoritma yang salah.
2.  Setiap langkah harus didefinisikan dengan tepat dan tidak berarti-dua (ambiguous). Pembaca harus mengerti apa yang dimaksud dengan "m dan n adalah bilangan bulat tak-negatif". Contoh lainnya, pernyataan "bagilah p dengan sejumlah beberapa buah bilangan bulat positif" dapat bermakna ganda. Berapakah yang dimaksud dengan "beberapa"?
Algoritma menjadi jelas jika langkah tersebut ditulis "bagilah p dengan 10 buah bilangan bulat positif"
3. Algoritma memiliki nol atau lebih masukan (input). Masukan ialah besaran yang diberikan kepada algoritma untuk diproses. Algoritma Euclidean mempunyai dua buah masukan, m dan n.
4. Algoritma mempunyai nol atau lebih keluaran (output). Keluaran dapat berupa pesan atau besaran yang memiliki hubungan dengan masukan. Algoritma Euclidean mempunyai satu keluaran, yaitu m pada langkah 1, yang merupakan pembagi bersama terbesar dari kedua masukannya.
5. Algoritma harus sangkil (effective). Setiap langkah harus sederhana sehinggan dapat dikerjakan dalam sejumlah waktu yang masuk akal.