BAB 2 TINJAUAN PUSTAKA
2.1 Konsep Dasar Algoritma Algoritma adalah kumpulan instruksi atau perintah yang dibuat secara jelas dan sistematis berdasarkan urutan yang logis (logika) untuk penyelsaian suatu masalah. French, C.S (1948) menyatakan sejumlah konsep yang mempunyai relevansi dengan masalah rancangan program yaitu kemampuan komputer, kesulitan dan ketepatan. Knuth (1973) menyatakan algoritma fundamental. Untuk keperluan matematika dan program komputer metode yang sering digunakan yaitu : [3] 1. Diagram Alir (Flowchart) 2. Kode Semu (Pseudocode) 3. Algoritma Fundamental. Knuth (1973) menyatakan 5 komponen utama dalam algoritma yaitu finiteness, definiteness, input, output, dan effectiveness. Sehingga dalam merancang sebuah algoritma ada 3 komponen yang harus ada yaitu : 1. Komponen masukan (input) Komponen ini biasanya terdiri dari pemilihan variabel, jenis variabel, tipe variabel, konstanta dan parameter (dalam fungsi). 2. Komponen keluaran (output) Komponen ini merupakan tujuan dari perancangan algoritma dan program. Permasalahan yang diselesaikan dalam algoritma dan program harus ditampilkan
Universitas Sumatera Utara
dalam komponen keluaran. Karakteristik keluaran yang baik adalah benar (menjawab) permasalahan dan tampilan yang ramah (user friendly). 3. Komponen Proses (Proccesing) Komponen ini merupakan bagian utama dan terpenting dalam merancang sebuah algoritma. Dalam bagian ini terdapat logika masalah , logika algoritma (sintaksis dan semantik), rumusan, metode (rekursi, perbandingan, penggabungan, pengurangan dan lain-lain). Flowchart
Konsep Logika
Format Algoritma
Pseudocode
Matematika
Algoritma Fundamental, 1973
Gambar 2.1. Struktur Hubungan dan Jenis Algoritma
2.2 Defenisi Analisis Algoritma Algoritma tidak selalu memberikan hasil terbaik yang mungkin diperoleh,maka diharapkan adanya suatu evaluasi mutu hasil dari algoritma tersebut (Liu, C.L, 1995, P271). Sekali sebuah algoritma diberikan kepada sebuah permasalahan dan dijamin akan memberikan hasil yang diharapkan, maka langkah penting selanjutnya adalah menentukan besar biaya yang diperlukan algoritma tersebut untuk memeroleh hasil itu. Proses inilah yang disebut dengan analisis algoritma.
Universitas Sumatera Utara
Ukuran biaya eksekusi suatu algoritma yang paling sering digunakan adalah lamanya waktu diperlukan. Namun juga masih ada ukuran-ukuran lainnya, misalnya besarnya memori yang diperlukan untuk mengeksekusi algoritma tersebut (Liu, C.L, 1995, P 272) [11]. Maksud dilakukannya analisis algoritma (Horowitz, Elis dan Sartaj Sahni, 1978, p1) adalah untuk : 1. Memenuhi aktivitas intelektual 2. Meramalkan suatu hal yang akan terjadi atau yang akan didapat algoritma tersebut. 3. Mengetahui efektifitas suatu algoritma dibanding dengan algoritma yang lain untuk persoalan yang sama.
2.3 Kompleksitas Waktu Algoritma Dan Masalah Algoritma tidak selalu memberikan hasil terbaik yang mungkin diperoleh maka diharapkan adanya suatu evaluasi mutu hasil dari algoritma tersebut (Liu, C.L, 1995, p271). Sekali sebah algoritma diberikan kepada sebuah permasalahan dan dijamin akan memberikan hasil yang diharapkan, maka langkah penting selanjutnya adalah menentukan besar biaya yang diperlukan algoritma tersebut untuk memperoleh hasil itu. Proses inilah yang disebut analisis algoritma (Weiss, Mark Allen,p149). [11] Ukuran biaya eksekusi suatu algoritma yang paling sering digunakan adalah lamanya waktu diperlukan. Namun juga masih ada ukuran-ukuran lainnya, misalnya besarnya memori yang diperlukan untuk mengeksekusi algoritma tersebut (Liu, C.L, 1995, p272). Dua buah algoritama yang berbeda dapat digunakan memecahkan masalah yang sama dan mungkin saj mempunyai kompleksitas waktu (time complexity) yang sangat berbeda (Liu. C.L, 1995, P277). Kompleksitas waktu algoritma terbaik untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu (time complexity of problem) (Liu, C.L, 1995, p277).
Universitas Sumatera Utara
2.3.1 Big O(O) Notasi big O pertama kali diperkenalkan oleh seorang teoritis bilangan bernama Paul Bachmann pada tahun 1894, didalam buku keduanya yang berjudul Analytische Zahlentheorie (“analytic number teory”). Dalam teori kompleksitas komputasi, notasi big O sering digunakan untuk menjelaskan bagaimana ukuran data masukan mempengaruhi sebuah kegunaan algoritma dari sumber daya komputasi (biasanya running time atau memori). Definisi pertama dalam pengukuran kompleksitas suatu masalah adalah Big O (Weiss dan Mark Allen, 1996, p161). Definisi : T(n) = O(f(n)), jika ada konstanta positif c dan ketika n >
dimana T(n) < c(f(n)),
. T(n) = O(f(n)), artinya T(n) berorde paling besar f(n) bila terdapat
konstanta c dan
sehingga T(n) <= c(f(n)) untuk n >=
2.3.2 Big Omega (Ω) Defenisi kedua dalam pengukuran kompleksitas suatu masalah adalah Big Omega. (Weiss dan Mark Allen, 1996, p161). Definisi : T(n) = Ω(f(n)), jika ada konstanta positif c dan
dimana T(n) > c(F(n)),
ketika N >
Universitas Sumatera Utara
2.3.3 Big Theta (ɵ)
Definisi ketiga dalam pengukuran kompleksitas suatu masalah adalah Big Theta. (Weiss dan Mark Allen, 1996, p161). Definisi : T(n)= ɵ (f(n)), jika dan hanya jika T(n) = O(f(n)) dan T(n) = Ω(f(n)) Suatu algoritma dikatakan anggota Θ(h(n)) jika algoritma itu adalah anggota O(h(n)) +
dan anggota Ω(h(n)). Contoh : Karena T(n) = anggota Ω(
), maka T(n) adalah anggota Θ(
adalah angota O(
) dan
). [2]
Contoh : For i ← 1 to n do For j ← 1 to i do For k ← j to n do a ← a + 1 end for end for end for Nilai O-besar, Ω-besar, dan Θ-besar dari algoritma di atas adalah sebagai berikut : Untuk i = 1, Untuk j = 1, jumlah perhitungan = n kali Untuk i = 2, Untuk j = 1, jumlah perhitungan = n kali Untuk j = 2, jumlah perhitungan = n–1 kali … Untuk i = n, Untuk j = 1, jumlah perhitungan = n kali Untuk j = 2, jumlah perhitungan = n –1 kali
Universitas Sumatera Utara
... Untuk j = n, jumlah perhitungan = 1 kali. T(n) =
+
+
+ ... + 1
= n(n + 1)(2n + 1)/6 =
+
+ 1.
Diperoleh T(n) ≤ 3untuk n ≥ 4 dan T(n) ≥ 2 = O(
) = Ω(
) = Θ(
untuk n ≥ 1. Sehingga diperoleh : T(n)
).
2.4 Algoritma Greedy Algoritma Greedy merupakan metode yang paling umum digunakan untuk memecahkan masalah optimasi. Permasalahan optimasi adalah persoalan mencari solusi optimum yaitu maksimasi dan minimasi. Algoritma ini memecahkan masalah langkah per langkah, pada setiap langkah : 1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan dengan perinsip “take what you can get now!”. 2. Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global. Contoh permasalahan optimasi adalah seperti masalah penukaran uang. Misalnya sejumlah uang senilai 32. Tukarkan dengan koin-koin uang (1, 5, 10, 25) yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukara tersebut?. Berikut adalah cara-cara penukaran koin yang didapat.
Universitas Sumatera Utara
32 = 1+1+1+…+1
(32 koin)
32 = 5+5+5+5+10+1+1
(7 koin)
32 = 10+10+10+1+1
(5 koin)
32 = 25+5+1+1
(4 koin)
Jumlah minimum penukaran uang sebanyak 4 koin. Keuntungan Greedy adalah dengan pengambilan pilihan terbaik disetiap langkah (optimum lokal) diharapkan akan mendapatkan optimum global. Bila algoritma Greedy optimum, maka keomptimalannya dapat dibuktikan secara matematis. Meskipun begitu, Greedy tidak selalu memperoleh solusi optimum untuk keseluruhan masalah dikarenakan Greedy tidak melakukan operasi secara exhaustive search kepada semua data dan seringkali tidak mementingkan solusi optimum [6]. Dalam pencarian kartu tertinggi pada kartu, implementasi Greedy diletakkan pada kartu yang diurutkan secara descending dengan selection sort. Berikut contohnya : 1. 5 kartu yang terpilih secara random
2. Kartu di urutkan berdasarkan nilai dan corak dari maximum ke minimum (selection sort). Sehingga didapat kartu tertinggi paling kiri.
Universitas Sumatera Utara
2.5 Algoritma Brute Force Brute Force adalah sebuah pendekatan yang lempang (straight forward) untuk memecahan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan defenisi konsep yang dilibatkan. Algoritma Brute Force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way). [7] Kelebihan algoritma Brute Force adalah cara berpikir yang mudah karna langsung pada pernyataan masalah. Algoritma ini dapat digunakan untuk memecahkan hampir sebagian masalah (wide applicability). Disamping itu Brute Force juga menghasilkan algoritma baku (standar) untuk tugas-tugas komputasi seperti penjumalahan dan perkalian n buah bilanagan. Kekurangan dari algoritma ini tentunya adalah butuh banyak jumlah langkah dalam menyelesaikan suatu masalah sehingga butuh banyak memori dan resource yang besar dan waktu yang lama sehingga jarang menghasilkan algoritma yang mangkus. Berikut adalah contoh implementasi algoritma Brute Force dalam pencarian kartu tertinggi pada kartu remi : 1. 5 kartu yang terpilih secara random dan dieksekusi langsung.
2. Pencarian kartu tertinggi dilakukan mulai dari kanan sampai semua kartu habis dibandingkan. Jika nilai dan corak lebih besar akan di swap. Jika lebih kecil tidak akan dilakukan swap.
Universitas Sumatera Utara
Sesuai dengan aturan permainan poker, urutan nilai kartu remi dari nilai terkecil ke nilai terbesar adalah 2, 3, 4, 5, 6, 7, 8, 9, 10, J(Jack), Q(Queen), K(King), As. Jika dalam pencarian kartu tertinggi terdapat nilai yang sama maka akan dipilih corak mana yang lebih tinggi. Sehingga corak kartu poker dalam pencarian kartu tertinggi disini berlaku. Berikut adalah kelas corak kartu dari tertinggi sampai terendah : [4]
1. Sekop 2. Hati 3. Keriting 4. Wajik
Universitas Sumatera Utara
