Sejarah Algoritma

algorism = proses menghitung dengan angka arab
algorist = orangnya / manusianya
berasal dari penulis buku Arab yang terkenal, yaitu Abu Ja’far Muhammad ibnu Musa al-Khuwarizmi.

tahun 1950, algoritma pertama kali di gunakan pada “Algoritma Euclidean (Euclid’s algorithm)“.
Euclid, matematikawan Yunani (lahir 350 SM), buku Element menuliskan langkah-langkah untuk menemukan pembagi bersama terbesar (common greatest divisor atau gcd), dari dua buah bilangan bulat, m dan n.
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
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 sbb :

  1. 80 di bagi 12 = 6, sisa 8    ( atau 80 = 6 * 12 + 8 )
  2. 12 di bagi 8 = 1, sisa 4       (atau 12 = 1 * 8 + 4)
  3. 8 di bagi 4 = 2, sisa 0         (atau 8 = 4 * 2 + 0)

Pembagian terkahir menghasilkan 0, maka sisa pembagian terakhir sebelum 0, yaitu 4, menjadi gcd(80,12). Jadi gcd(80,12) = gcd(12,8) = gcd(8,4) = gcd(4,0) =4.

Proses mencari gcd dari 80 dan 12 juga dapat di ilustrasikan dalam diagram berikut ini :

euclidean

Salah satu versi algoritma Eucledean :

ALGORITMA Euclidean
{Diberikan dua buah bilangan bulat tak negatif m dan n (m lebih kecil atau tidak sama dengan n).
 Algoritma Euclidean mencari pembagi terbesar, gcd , dari kedua bilangan tsb,
 yaitu bilangan bulat positif terbesar yang habis membagi m dan n}
1. Jika n = 0 maka
   m adalah jawabannya;
   stop.
   tetapi jika n tidak = 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.