Analisis dan Strategi Algoritma - Implementasi Algoritma Aivide and Conquer pada Sorting dan Searching

Divide and Conquer

Komputer pada awalnya diciptakan sebagai perangkat untuk melakukan kalkulasi secara otomatis dan akurat. Meskipun awalnya hanya berfokus pada kalkukasi numerik, komputer modern yang dijumpai sekarang telah melakukan kalkulasi pada banyak hal, seperti teks ataupun gambar. Berbagai kalkulasi dan analisa yang dilakukan komputer biasanya diimplementasikan melalui perangkat lunak. Dengan semakin besarnya ruang lingkup hal-hal yang dilakukan oleh komputer, perangkat lunak yang dikembangkan juga menjadi semakin kompleks. Algoritma, sebagai bagian dari perangkat lunak yang melakukan pemrosesan, juga memerlukan berbagai teknik baru. Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana:

nums = [1, 2, 3, 5, 6, 7, 19, 28, 58, 18, 28, 67, 13]

total = 0

 

for i in range(0, len(nums)):

    total = total + nums[i]

 

print(total) # 255

Algoritma perulangan yang digunakan pada kode di atas memang sederhana dan memberikan hasil yang benar, tetapi terdapat beberapa masalah pada kode tersebut, yaitu perhitungan dilakukan secara linear, yang menghasilkan kompleksitas O(n)O(n). Hal ini tentunya cukup ideal untuk ukuran list kecil, tetapi jika ukuran list menjadi besar (beberapa Milyar elemen) maka perhitungan akan menjadi sangat lambat. Kenapa perhitungannya menjadi lambat? Karena nilai dari total tergantung kepada kalkulasi nilai total sebelumnya. Kita tidak dapat melakukan perhitungan total dari depan dan belakang list sekaligus, sehingga kita dapat mempercepat perhitungan dua kali lipat. Dengan kode di atas, kita tidak dapat membagi-bagikan pekerjaan ke banyak pekerja / CPU!

Lalu apa yang dapat kita lakukan? Langkah pertama yang dapat kita lakukan adalah menerapkan teknik rekursif untuk membagi-bagikan masalah menjadi masalah yang lebih kecil. Jika awalnya kita harus menghitung total keseluruhan list satu per satu, sekarang kita dapat melakukan perhitungan dengan memecah-mecah list terlebih dahulu:

def sums(lst):

    if len(lst) >= 1:

         return lst[0]

 

    mid = len(lst) // 2

    left = sums(lst[:mid])

    right = sums(lst[mid:])

 

    return left + right

 

print(sums(nums)) # 255

Apa yang kita lakukan pada kode di atas?

1. Baris if len(lst) >= 1 memberikan syarat pemberhentian fungsi rekursif, yang akan mengembalikan isi dari list ketika list berukuran 1 (hanya memiliki satu elemen).
2. Baris mid = len(lst) // 2 mengambil median dari list, sebagai referensi ketika kita membagi list menjadi dua bagian.
3. Baris left = sum(lst[:mid]) dan selanjutnya membagikan list menjadi dua bagian, dengan nilai mid sebagai tengah dari list.

Singkatnya, setelah membagikan list menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut, seperti pada gambar berikut:

Langkah Kerja Divide and Conquer

Apa kelebihan pendekatan dengan membagi-bagikan masalah ini? Dengan menggunakan bahasa dan library yang tepat, kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).

Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and conquer.

Membangun Algoritma Divide and Conquer

Sebuah algoritma divide and conquer (selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:

1. Divide (Memecah): pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
2. Conquer (Menaklukkan): dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
3. Combine (Menggabungkan): setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

Algoritma D&C, jika diimplementasikan menggunakan library atau bahasa yang tepat akan meningkatkan efisiensi algoritma secara logaritmik. Mari kita lakukan analisis pada fungsi sum di atas, untuk melihat kompleksitas algoritmanya:

def sums(lst):

    if len(lst) >= 1:        # 1 langkah

         return lst[0]       # 1 langkah

 

    mid = len(lst) // 2      # 1 langkah

    left = sums(lst[:mid])   # sums(mid) langkah

    right = sums(lst[mid:])  # sums(mid) langkah

 

    return left + right      # 1 langkah

yang secara matematis dapat dituliskan seperti berikut:

f(n)=4+f(n2)+f(n2)=4+2f(n2)f(n)=4+f(n2)+f(n2)=4+2f(n2)

karena ukuran dari mid adalah panjang list (nn) dibagi dua. Dengan begitu, kompleksitas dari algoritma adalah:

f(n)=2f(n2)=2(2(n4))=2(2(2(n8)))...=2k(n2k)f(n)=2f(n2)=2(2(n4))=2(2(2(n8)))...=2k(n2k)

dengan syarat berhenti adalah ketika k≥1k≥1, sehingga:

n2knk=1=2k=log2nn2k=1n=2kk=log2⁡n

Kompleksitas dari fungsi sums adalah O(logn)O(log⁡n), meningkat dari O(n)O(n) pada algoritma awal!

Secara umum, kompleksitas algoritma D&C adalah O(nlogn)O(nlog⁡n), jika ukuran data adalah nn, dan pada setiap langkahnya kita membagikan masalah ke dalam pp sub-masalah.

Contoh D&C 1: Merge Sort

Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total yang telah kita lakukan sebelumnya, yaitu membagi-bagikan keseluruhan list menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya kembali menjadi sebuah list besar.

Berikut adalah merge sort yang diimplementasikan dalam bahasa python:

def merge_sort(lst):

    if len(lst) <= 1:

        return lst

 

    mid = len(lst) // 2

    left = merge_sort(lst[:mid])

    right = merge_sort(lst[mid:])

 

    return merge(left, right)

 

def merge(left, right):

    result = []

 

    while len(left) > 0 or len(right) > 0:

        if len(left) > 0 and len(right) > 0:

            if left[0] <= right[0]:

                result.append(left.pop(0))

            else:

                result.append(right.pop(0))

        elif len(left) > 0:

            result.append(left.pop(0))

        elif len(right) > 0:

            result.append(right.pop(0))

 

    return result

Dari kode di atas terlihat bahwa merge sort memiliki dua bagian, yang dituliskan dalam dua buah fungsi: merge dan merge_sort. Fungsi merge_sort memiliki logika dan cara kerja yang sama dengan fungsi penjumlahan total yang kita bangun sebelumnya, dengan perbedaan pada bagian yang melakukan penggabungan list (return merge(left, right)).

Penggabungan list sendiri dilakukan dengan cukup sederhana dan gamblang, yaitu hanya membandingkan elemen-elemen dari dua buah list yang dikirimkan satu per satu, untuk kemudian disimpan ke dalam variabel result secara terurut. Untuk lebih jelasnya, mari kita coba bedah algoritma pada fungsi merge, langkah demi langkah.

Misalkan kita memanggil fungsi merge seperti berikut:

left  = [3, 5]

right = [1, 4]

merge(left, right)

Note

Ingat bahwa list pada variabel left maupun right harus sudah terurut jika ukuran list lebih dari 1. Fungsi merge dengan argumen list berukuran >> 1 hanya dipanggil dari hasil merge dua buah list berukuran satu dalam kasus merge_sort.

Jika kita mengikuti langkah demi langkah pada kode, maka pada setiap iterasi while kita akan mendapatkan nilai masing-masing variabel sebagai berikut:

# Awal fungsi

left   = [3, 5]

right  = [1, 4]

result = []

 

# Iterasi 1

left   = [3, 5]

right  = [4]

result = [1]

 

# Iterasi 2

left   = [5]

right  = [4]

result = [1, 3]

 

# Iterasi 3

left   = [5]

right  = []

result = [1, 3, 4]

 

# Iterasi 4

left   = []

right  = []

result = [1, 3, 4, 5]

Penggabungan seperti di atas dilakukan pada setiap submasalah yang telah dipecah oleh merge_sort, sampai kita mendapatkan sebuah list dengan ukuran yang sama pada list awal. Untuk mempermudah pengertian, gambar di bawah menunjukkan proses pemecahan dan penggabungan kembali dari merge sort:

Langkah Kerja Merge Sort

Proses divide terjadi ketika kotak dan panah berwarna merah, sementara conquer dan combine terjadi ketika kotak dan panah diberi warna biru. Proses conquer merupakan proses di mana kita mengurutkan elemen dalam list, dan combine adalah ketika kita menggabungkan hasil urutan dari list tersebut.

Contoh D&C 2: Binary Search

Binary search merupakan salah satu algoritma pencarian yang paling efisien, dengan kompleksitas O(logn)O(log⁡n). Algoritma ini memanfaatkan teknik divide and conquer dengan memecah lingkup pencarian data menjadi setengahnya pada setiap kali divide. Kekurangan dari binary search yaitu bahwa algoritma ini hanya dapat digunakan pada sebuah data atau lsit yang telah terurut.

Langsung saja, implementasi binary search menggunakan python:

def binary_search(data, search_val, min_idx, max_idx):

    if max_idx < min_idx:

        print("%d not found in list"%search_val)

        return -1

 

    mid_idx = (min_idx + max_idx) // 2

    if data[mid_idx] > search_val:

        return binary_search(data, search_val, min_idx, mid_idx - 1)

    elif data[mid_idx] < search_val:

        return binary_search(data, search_val, mid_idx + 1, max_idx)

    else:

        print("%d found in index %d"%(search_val, mid_idx))

        return mid_idx

Mari kita lihat cara kerja binary search. Misalkan kita diberikan data berupa list bilangan seperti berikut:

[1, 2, 4, 6, 7, 8, 9, 10]

dan diminta untuk mencari letak angka 2 pada list tersebut. Sebelum mulai menjalankan algoritma, pastinya kita harus mengetahui nilai-nilai awal terelbih dahulu. Adapun nilai awal yang dibutuhkan untuk fungsi binary_search adalah sebagai berikut:

data       = [1, 2, 4, 6, 7, 8, 9, 10]

search_val = 2

min_idx    = 0

max_idx    = len(data) - 1 # 7

Nilai indeks minimal (batas awal pencarian) yang pertama tentunya adalah 0, dengan nilai maksimal (batas akhir pencarian) adalah ukuran dari list itu sendiri. Di langkah awal binary search, dilakukan perhitungan terhadap nilai tengah dari min_idx dan max_idx terlebih dahulu, untuk mendapatkan titik awal pencarian. Perhitungan nilai tengah dilakukan pada kode berikut:

mid_idx = (min_idx + max_idx) // 2

Setelah mendapatkan nilai tengah, kita lalu melakukan cek apakah nilai dari data pada indeks tersebut lebih besar atau lebih kecil dibandingkan nilai yang akan kita cari (2). Langkah pengecekan ini dilakukan pada perintah if berikut:

if data[mid_idx] > search_val:

    # nilai lebih besar daripada 2

elif data[mid_idx] < search_val:

    # nilai lebih kecil daripada 2

else:

    # nilai adalah 2 (ditemukan)

Dalam kasus ini, nilai dari mid_idx adalah 3, dan karena data[3] berisi 6, maka kita akan melakukan pemotongan terhadap seluruh nilai pada data setelah 6, karena nilai tersebut sudah pasti tidak diperlukan lagi (ingat, data harus terurut pada binary search). Kita lalu memanggil fungsi binary_search lagi, kali ini dengan mencari hanya pada submasalah (list) berikut (perhatikan bagaimana pada pemanggilan binary_search yang kedua nilai max_idx kita ubah menjadi mid_idx - 1):

[1, 2, 4]

Dan dengan mengaplikasikan logika yang sama dengan tahap sebelumnya, kita akan langsung menemukan bilangan yang dicari.

  §  Alamat web Program studi, Fakultas, Universitas : http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id

§  Nama Mahasiswa : NADIYA SAFITRI 

§  NPM : 19316014

§ Kelas : Tk19B

Analisis dan Strategi Algoritma - Algoritma Divide and Conquer

Algoritma Divide and Conquer

Sejarah Divide and Conquer  Pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengannama divide ut imperes. Saat ini strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama divide and conquer. Algoritma divide and conquer ini ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar.

 

Definisi Algoritma Divide and Conquer

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).

Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).

Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

 

Skema Umum Algoritma Divide and Conquer :

Penerapan Algoritma

1.  Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang

sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).

Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.

Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

 

2. Persoalan Minimum dan Maksimum (MinMaks)

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

Ide dasar algoritma secara Divide and Conquer :

Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

 

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.

COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

3. Optimasi Konversi Bilangan Desimal Ke Biner

Salah satu cara optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan menjadi hasil jawaban.

Karena angka pembagi yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah satu proses yang cukup rumit.

Tentu saja optimasi ini harus kita bayar dengan menangani konversi bilangan octal ke biner. Akan tetapi jika kita gunakan teknik perbandingan ( tanpa harus melakukan konversi secara manual ), maka proses ini akan menjadi sangat cepat dan mudah. Penerapan algoritma ini adalah dengan menggunakan sintaks case of. Begitu juga dengan permasalahan pemakaian memori ( kompleksitas ruang ) yang lebih besar yang muncul akibat penggunaan algoritma rekursif. Karena pada proses rekursif-nya kita tidak banyak menggunakan variable yang memerlukan tempat yang begitu besar, maka hal ini bias kita abaikan. Dengan penggunaan optimasi ini, maka seharusnya proses konversi akan lebih cepat karena pemangkasan jumlah pembagian yang dilakukan.

Skema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer

Kompleksitas waktu algoritma :

T(n) = O(n/3)

dengan n menyatakan eksponen terkecil dari 2 yang mempunyai nilai 2n lebuh besar dari angka decimal

Algoritma konversi system bilangan dengan menggunakan algoritma dengan optimasi yang menerapkan algoritma Divide and Conquer lebih mangkus daripada algoritma konversi dengan metode pembagian sisa biasa jika dilihat dari segi kompleksitas waktunya. Hanya saja optimasi ini diimbangi dengan kenaikan pada kompleksitas ruangnya, meskipun pengaruhnya tidak sebesar optimasi yang kita lakukan.

 

4. Mencari Pasangan Titik yang Jaraknya Terdekat ( Closest Pair )

Persoalan : Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :

Penyelesaian dengan Algoritma Divide and Conquer :

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

– SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.

– DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama

– CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

– Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

Pasangan titik terdekat terdapat di bagian PLeft.

Pasangan titik terdekat terdapat di bagian PRight.

Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

§  Alamat web Program studi, Fakultas, Universitas : http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id

§  Nama Mahasiswa : NADIYA SAFITRI 

§  NPM : 19316014

§ Kelas : Tk19B