Contoh Algoritma dalam Matematika

1. Algoritma Euclid: Mencari Faktor Persekutuan Terbesar (FPB)

Salah satu algoritma tertua dan paling elegan yang masih digunakan hingga kini adalah Algoritma Euclid. Algoritma ini bertujuan untuk menemukan Faktor Persekutuan Terbesar (FPB) dari dua bilangan bulat positif. FPB adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan tersebut tanpa sisa.

Ide dasar di balik algoritma ini adalah bahwa FPB dari dua bilangan tidak berubah jika bilangan yang lebih besar dikurangi dengan bilangan yang lebih kecil. Proses ini diulang sampai kedua bilangan sama, dan bilangan inilah yang merupakan FPB-nya. Versi yang lebih efisien menggunakan operasi modulo (sisa pembagian).

Langkah-langkah Algoritma Euclid (menggunakan modulo):

1. Diberikan dua bilangan bulat positif, katakanlah a dan b, dengan a > b.
2. Hitung sisa dari pembagian a oleh b. Misalkan sisa ini adalah r.
3. Jika r = 0, maka b adalah FPB dari a dan b. Selesai.
4. Jika r ≠ 0, ganti a dengan b, dan b dengan r.
5. Ulangi dari langkah 2.

Contoh: Mencari FPB dari 48 dan 18.

• Langkah 1: a = 48, b = 18.
• Langkah 2: 48 ÷ 18 = 2 dengan sisa 12 (r = 12).
• Langkah 3: r ≠ 0. Ganti a = 18, b = 12.
• Langkah 2: 18 ÷ 12 = 1 dengan sisa 6 (r = 6).
• Langkah 3: r ≠ 0. Ganti a = 12, b = 6.
• Langkah 2: 12 ÷ 6 = 2 dengan sisa 0 (r = 0).
• Langkah 3: r = 0. Maka FPB adalah 6.

Algoritma Euclid sangat efisien dan merupakan dasar untuk banyak algoritma lain dalam teori bilangan.

2. Algoritma Pencarian (Search Algorithms)

Dalam matematika dan ilmu komputer, pencarian adalah proses menemukan elemen tertentu dalam sebuah kumpulan data. Ada berbagai algoritma pencarian, yang paling umum adalah pencarian linear dan pencarian biner.

a. Pencarian Linear

Ini adalah algoritma yang paling sederhana. Kita memeriksa setiap elemen dalam daftar secara berurutan sampai elemen yang dicari ditemukan atau daftar habis.

Contoh: Mencari angka 5 dalam daftar [2, 8, 5, 1, 9].

1. Periksa elemen pertama: 2 ≠ 5.
2. Periksa elemen kedua: 8 ≠ 5.
3. Periksa elemen ketiga: 5 = 5. Ditemukan!

Pencarian linear cocok untuk daftar yang tidak terurut atau daftar yang sangat kecil. Namun, untuk daftar yang besar, efisiensinya menjadi sangat rendah.

b. Pencarian Biner

Algoritma ini jauh lebih efisien, tetapi memerlukan daftar yang sudah terurut. Ide dasarnya adalah membagi daftar menjadi dua bagian berulang kali.

Langkah-langkah Pencarian Biner:

1. Diberikan daftar terurut dan elemen yang dicari.
2. Periksa elemen tengah dari daftar.
3. Jika elemen tengah cocok dengan yang dicari, pencarian selesai.
4. Jika elemen yang dicari lebih kecil dari elemen tengah, ulangi pencarian di separuh bagian kiri daftar.
5. Jika elemen yang dicari lebih besar dari elemen tengah, ulangi pencarian di separuh bagian kanan daftar.
6. Jika daftar habis tanpa menemukan elemen, maka elemen tersebut tidak ada dalam daftar.

Contoh: Mencari angka 15 dalam daftar terurut [2, 5, 8, 12, 15, 18, 22].

• Daftar: [2, 5, 8, 12, 15, 18, 22]. Elemen tengah adalah 12. 15 > 12. Cari di separuh kanan.
• Daftar sisa: [15, 18, 22]. Elemen tengah adalah 18. 15 < 18. Cari di separuh kiri.
• Daftar sisa: [15]. Elemen tengah adalah 15. 15 = 15. Ditemukan!

Pencarian biner secara drastis mengurangi jumlah perbandingan yang diperlukan, membuatnya sangat cepat untuk kumpulan data yang besar.

3. Algoritma Pengurutan (Sorting Algorithms)

Algoritma pengurutan digunakan untuk mengatur elemen-elemen dalam sebuah daftar ke dalam urutan tertentu (misalnya, naik atau turun). Ada banyak algoritma pengurutan yang berbeda, masing-masing dengan kelebihan dan kekurangannya sendiri dalam hal efisiensi dan kompleksitas.

a. Bubble Sort

Salah satu algoritma pengurutan yang paling mudah dipahami. Algoritma ini berulang kali menukar elemen yang berdekatan jika berada dalam urutan yang salah. Proses ini diulangi sampai tidak ada lagi pertukaran yang terjadi, yang menandakan bahwa daftar telah terurut.

Contoh: Mengurutkan [5, 1, 4, 2, 8] secara menaik.

• Iterasi 1: [1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] (elemen terbesar, 8, "menggelembung" ke akhir)
• Iterasi 2: [1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] (elemen kedua terbesar, 5, "menggelembung")
• Iterasi 3: [1, 2, 4, 5, 8] (tidak ada pertukaran)

Meskipun mudah dipahami, Bubble Sort tidak efisien untuk daftar besar.

b. Merge Sort

Ini adalah algoritma pengurutan yang lebih efisien, menggunakan pendekatan "divide and conquer" (bagi dan taklukkan). Algoritma ini membagi daftar menjadi sub-daftar yang lebih kecil hingga setiap sub-daftar hanya berisi satu elemen (yang secara trivial terurut), kemudian menggabungkan kembali sub-daftar tersebut dalam urutan yang benar.

Meskipun proses penggabungan (merge) mungkin tampak rumit, secara konseptual algoritma ini memecah masalah besar menjadi masalah-masalah kecil yang dapat dikelola, kemudian menggabungkan solusinya.