Analysis and Design Algorithm

Oleh

Putri Harliana, ST, [Link]

 Introduction to Analysis of Algorithm
History of Algorithm
Algoritma Setelah abad ke-9 oleh:
Ilmuan ini menulis buku Abu Jafar Muhammad Ibnu Musu
yang berjudul Al-Khowarizmi.
Al Jabar Wal-Muqabala

Algorism oleh orang barat

Buku Pemugaran The book of
dan Pengurangan restoration and Algorism Algorithm
reduction

Karena kata algorism sering Diterapkan

Indonesia untuk metode
dikelirukan oleh arithmetic, sebut
sehingga akhiran -sm berubah perhitungan
Algoritma (komputasi)
menjadi -thm
Pengertian Algoritma
• Urutan logis langkah-langkah penyelesaian masalah yang
disusun secara sistematis.
• Metode khusus yang dirancang untuk memecahakan beberapa
jenis masalah.
• Serangkaian langkah-langkah yang terbatas dimana masing-
masing dari langkah-langkah tesebut membutuhkan satu atau
banyak operasi.
• Prosedur langkah-demi-langkah yang terbatas untuk mencapai
hasil yang diinginkan.
• Sebuah prosedur komputasi yang mentransformasikan
sejumlah input menjadi output.
 Contoh-contoh Algoritma dalam kehidupan sehari-hari

Contoh langkah dalam

Proses Algoritma
Algoritma
1. Membuat kue Resep kue Masukkan telur kedalam wajan,
kocok sampai mengembang
Gunting kain dari pinggir kiri
2. Membuat pakaian pola pakaian bawah ke arah kanan sejauh 5
cm
3. Peraktikum reaksi kimia Panduan Campurkan 10 ml H2SO4
praktikum dengan 15 NaOH
Sambungkan komponen A
4. Merakit mobil Panduan merakit
dengan komponen B
Pukul 15.00: tidur siang, pukul
5. Kegiatan sehari-hari Jadwal harian
16.00: membuat PR
6. Memainkan musik Papan not balok Not balok
Panduan Tekan nomor 888 masukkan
7. Mengisi voucher kartu
pengisian nomor voucher 14 digit
Design Algoritma
• Pengetahuan merancang yang akan membantu
seseorang untuk membuat algoritma yang bagus.

Analysis Algoritma
• Mengacu kepada proses penentuan berapa banyak waktu
komputasi dan penyimpanan algoritma akan perlukan.
• Tantangan yang terkadang memerlukan keterampilan
matematika.
Problem Solving
• Algoritma mempunyai beberapa strategi yang digunakan untuk
mencari solusi dari beberapa permasalahan yang muncul.
Secara umum strategi tersebut dikelompokkan sebagai berikut:

1. Penyelesaian Langsung (direct solution strategies)

-> Algoritma Brute force
-> Algoritma Greedy

2. Penyelesaian berbasis pencarian pada ruang

status (state-space based strategies)
-> Algoritma Back Tracking
-> Algoritma Branch and Bound
Pemecahan Masalah

3. Penyelesaian Atas-Bawah (top-down solution

strategies)
-> Algoritma Divide and Conquer

4. Penyelesaian Bawah-Atas (bottom-up solution

strategies)
-> Algoritma Dynamic Programming
Definisi dari beberapa strategi algoritma

• Divide and conquer

teknik membagi masalah menjadi beberapa masalah dari
masalah yang semula dan memecahkan (menyelesaikan)
masalah-masalah tersebut dengan cara menggabungkan
solusi dari masing-masing masalah hingga menghasilkan
solusi dari masalah yang semula (utama)
• The Greedy
Metode yang menggunakan beberapa teknik seperti selection
sort, knapsack problem, minimum spanning tree dan shortest
path untuk memecahkan masalah pada algoritma.
Brute Force
Merupakan suatu algoritma yang kurang bagus (inefficient)
untuk memecahkan suatu permasalahan karena memiliki
langkah-langkah banyak sehingga membutuhkan konsumsi
waktu lama.

Branch and Bound

Merupakan suatu algoritma yang menggunakan metode
untuk pencarian di dalam ruang yang menghasilakan solusi
secara sistematis
Dynamic Programming
suatu teknik yang menggambarkan proses pemecahan
masalah dengan mencari keputusan terbaik dari keputusan-
keputusan yang ada.

Backtracking
Algoritma berbasis DFS digunakan untuk mencari solusi
dari persoalan yang dimunculkan pada algoritma. Teknik ini
merupakan perbaikan dari Brute-Froce Algoritma, yaitu
mencari solusi persoalan diantara semua kemungkinan
solusi yang ada.
Algoritma Bruteforce
• Definisi Bruteforce

 Brute force adalah sebuah pendekatan yang lempang

(straightforward) untuk memecahkan suatu masalah,
biasanya didasarkan pada pernyataan masalah (problem
statement) dan definisi konsep yang dilibatkan.
 Algoritma brute force memecahkan masalah dengan
sangat sederhana, langsung dan dengan cara yang jelas
(obvious way).
 Algoritma Bruteforce
Contoh-contoh masalah yang dipecahkan secara
Brute Force:

1. Menghitung an (a > 0, n adalah bilangan bulat tak-

negatif)
an = a x a x … x a (n kali) , jika n > 0
an = 1 , jika n = 0
Algoritma: kalikan 1 dengan a sebanyak n kali
2. Menghitung n! (n bilangan bulat tak-negatif)
n! = 1 × 2 × 3 × … × n , jika n > 0
=1 , jika n = 0
Algoritma: kalikan n buah bilangan, yaitu 1, 2, 3, …, n,
bersama-sama
Algoritma Bruteforce
Algoritma Kalikan 1 dengan a sebanyak n kali
function pangkat(input a, n : integer)integer
{ Menghitung an, a > 0 dan n bilangan bulat tak-negatif
Masukan: a, n
Keluaran: nilai perpangkatan.
}
Deklarasi
k, hasil ,n, a: integer

Algoritma:
hasil1
for k1 to n do
hasilhasil * a
endfor
return hasil
Algoritma Bruteforce
Algoritma: kalikan n buah bilangan, yaitu: 1,2,3,…,n,
bersama – sama.

function faktorial(input n : integer)integer

{ Menghitung n!, n bilangan bulat tak-negatif
Masukan: n
Keluaran: nilai faktorial dari n.
}
Deklarasi
k, fak ,n: integer

Algoritma:
fak1
for k1 to n do
fakfak * k
endfor
return fak
 Algoritma Bruteforce

3. Mengalikan dua buah matrik yang berukuran n × n.

Misalkan C = A × B dan elemen-elemen matrik dinyatakan

sebagai cij, aij, dan bij

Algoritma: hitung setiap elemen hasil perkalian satu per satu,

dengan cara mengalikan dua vektor yang panjangnya n.
Algoritma Bruteforce
Algoritma: hitung setiap elemen hasil perkalian satu per satu,
dengan cara mengalikan dua vektor yang panjangnya n.

procedure PerkalianMatriks(input A, B : Matriks,

input n : integer,
output C : Matriks)
{ Mengalikan matriks A dan B yang berukuran n × n, menghasilkan
matriks C yang juga berukuran n × n
Masukan: matriks integer A dan B, ukuran matriks n
Keluaran: matriks C
}

Deklarasi
i, j, k : integer

Algoritma
for i1 to n do
for j1 to n do
C[i,j]0 { inisialisasi penjumlah }
for k  1 to n do
C[i,j]C[i,j] + A[i,k]*B[k,j]
endfor
endfor
endfor
 Algoritma Bruteforce
4. Menemukan semua faktor dari bilangan bulat n
selain dari 1 dan n itu sendiri.
Definisi: Bilangan bulat a adalah faktor dari bilangan
bulat b jika a habis membagi b.
procedure CariFaktor(input n : integer)
{ Mencari faktor dari bilangan bulat n selain 1 dan n itu sendiri.
Masukan: n
Keluaran: setiap bilangan yang menjadi faktor n dicetak.
}
Deklarasi
k : integer

Algoritma:
k1
ketemu  false
for k2 to n - 1 do
if n mod k = 0 then
write(k)
endif
endfor
Algoritma Bruteforce
• Karakteristik Algoritma Brute Force
 Algoritma brute force umumnya tidak cerdas dan tidak mangkus,
karena ia membutuhkan jumlah langkah yang besar dalam
penyelesaiannya. Kadang-kadang algoritma brute force disebut juga
algoritma naif (naïve algorithm).
 Algoritma brute force seringkali merupakan pilihan yang kurang
disukai karena ketidakmangkusannya itu, tetapi dengan mencari pola-
pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan
membantu kita menemukan algoritma yang lebih cerdas dan mangkus.
 Untuk masalah yang ukurannya kecil, kesederhanaan brute force
biasanya lebih diperhitungkan daripada ketidakmangkusannya.
Algoritma brute force sering digunakan sebagai basis bila
membandingkan beberapa alternatif algoritma yang mangkus.
Algoritma Bruteforce
 Algoritma brute force seringkali lebih mudah diimplementasikan
daripada algoritma yang lebih canggih, dan karena
kesederhanaannya, kadang-kadang algoritma brute force dapat lebih
mangkus (ditinjau dari segi implementasi).
 Algoritma Bruteforce
Contoh-contoh Algoritma Brute Force Lainnya
1. Mencari elemen terbesar
Persoalan: Diberikan sebuah himpunan yang beranggotakan n
buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan
sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan
tersebut.

• Asumsikan a1 sebagai elemen tebesar sementara. Simpan a1 ke dalam maks.

• Bandingkan maks dengan elemen a2. Jika a2 lebih besar dari maks, maka
nilai maks diganti dengan a2.
• Ulangin lankah 2 untuk elemen-elemen berikutnya (a3,a4,…….,an).
• Berhenti jika tidak ada lagi elemen yang dibandingkan. Dalam hal ini, maks
berisi nilai dari elemen terbesar.
Algoritma Bruteforce
#include <stdio.h>
void main() Program Bahasa C
{
int A[5],i,maks;
clrscr();
for(i=0;i<5;i++)
{ printf("masukkan nilai A[%i] = ",i+1);
scanf("%i",&A[i]);
}
maks=A[0];
for(i=1;i<=4;i++)
{
if (A[i] > maks)
{ maks=A[i]; }
}
printf("\n\nNilai Maximum = %i",maks);
getch();
}
Algoritma Bruteforce

procedure CariElemenTerbesar(input a1, a2, ..., an : integer,

output maks : integer)
{ Mencari elemen terbesar di antara elemen a1, a2, ..., an. Elemen
terbesar akan disimpan di dalam maks.
Masukan: a1, a2, ..., an
Keluaran: maks
}
Deklarasi
k : integer

Algoritma:
maksa1
for k2 to n do
if ak > maks then
maksak
endif
endfor
 Algoritma Bruteforce
2. Sequential Search

Persoalan: Diberikan n buah bilangan bulat yang

dinyatakan sebagai a1, a2, …, an. Carilah apakah x terdapat
di dalam himpunan bilangan bulat tersebut. Jika x
ditemukan, maka lokasi (indeks) elemen yang bernilai x
disimpan di dalam peubah idx. Jika x tidak terdapat di
dalam himpunan tersebut, maka idx diisi dengan nilai 0.
 Algoritma Bruteforce
Contah: Program pencarian beruntun
(sequential search or linear search)
#include <stdio.h> i=0;
void main() while(i<10)
{ {
int i,A[10],x,idx; if(A[i]!=x)
clrscr(); { i++;
if(i==10)
i=0; { idx=0;
while(i<10) printf("\nNilai x=%i
{ tidak ditemukan!!",x);
printf("Masukkan nilai A[%i] = ",i+1); }
scanf("%i",&A[i]); }
i++; else
} {
printf("\nnilai A[%i]=%i",i+1,A[i]);
printf("\nMasukan nilai x = "); idx=A[i];
scanf("%i",&x); printf("\nNilai x=%i ditemukan!!",idx);
break; }
}
getch();
}
Algoritma Bruteforce
procedure PencarianBeruntun(input a1, a2, ..., an : integer,
x : integer,
output idx : integer)
{ Mencari x di dalam elemen a1, a2, ..., an. Lokasi (indeks elemen)
tempat x ditemukan diisi ke dalam idx. Jika x tidak ditemukan, maka
idx diisi dengan 0.
Masukan: a1, a2, ..., an
Keluaran: idx
}
Deklarasi
k : integer

Algoritma:
k1
while (k < n) and (ak  x) do
k  k + 1
endwhile
{ k = n or ak = x }

if ak = x then { x ditemukan }
idxk
else
idx 0 { x tidak ditemukan }
endif
 Algoritma Bruteforce
3. Algoritma mempertukar nilai dari dua
variable peubah
Program Bahasa C
#include <stdio.h> Algoritma
Deklarasi
void main()
temp : integer
{
x : integer
int temp,x,y;
y : integer
clrscr();
x =10;
Algoritma
y =8;
x  10
temp=x;
y8
x=y;
temp  x
y=temp;
xy
printf(“\nX = %i”,x);
y  temp
printf(“\nY = %i”,y);
write (x)
getch();
write (y)
}
Algoritma Bruteforce
4. Bubble Sort

Apa metode yang paling lempang dalam memecahkan

masalah pengurutan?,

Jawabnya adalah algoritma pengurutan bubble sort.

Algoritma bubble sort mengimplementasikan teknik

brute force dengan jelas sekali.
Algoritma Bruteforce

procedure BubbleSort (input/output L : TabelInt, input n : integer)

{ Mengurutkan tabel L[1..N] sehingga terurut menaik dengan metode
pengurutan bubble sort.
Masukan : Tabel L yang sudah terdefenisi nilai-nilainya.
Keluaran: Tabel L yang terurut menaik sedemikian sehingga
L[1]  L[2]  …  L[N].
}
Deklarasi
i : integer { pencacah untuk jumlah langkah }
k : integer { pencacah,untuk pengapungan pada setiap
langkah }
temp : integer { peubah bantu untuk pertukaran }

Algoritma:
for i  1 to n - 1 do
for k  n downto i + 1 do
if L[k] < L[k-1] then
{pertukarkan L[k] dengan L[k-1]}
temp  L[k]
L[k]  L[k-1]
L[k-1]  temp
endif
endfor
endfor
 Algoritma Bruteforce
5. Menghitung nilai
function polinom(input x0 : real)real
polinom secara { Menghitung nilai p(x) pada x = x0. Koefisien-koefisein polinom sudah
disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi.
brute force Masukan: x0
Keluaran: nilai polinom pada x = x0.
}
Deklarasi
Persoalan: Hitung i, j : integer
p, pangkat : real
nilai polinom
Algoritma:
p0
p(x) = anxn + an- for in downto 0 do
pangkat1
1xn-1 + … + a1x + for j1 to i do {hitung xi }
pangkatpangkat * x0
a0 endfor
pp + ai * pangkat
endfor
return p
pada titik x = x0.
Algoritma Bruteforce
• Kekuatan dan Kelemahan Metode Brute Force
Kekuatan:
 Metode brute force dapat digunakan untuk memecahkan hampir
sebagian besar masalah (wide applicability).

 Metode brute force sederhana dan mudah dimengerti.

 Metode brute force menghasilkan algoritma yang layak untuk beberapa

masalah penting seperti pencarian, pengurutan, pencocokan string,
perkalian matriks.

 Metode brute force menghasilkan algoritma baku (standard) untuk

tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan,
menentukan elemen minimum atau maksimum di dalam tabel (list).
Algoritma Bruteforce
Kelemahan:
 Metode brute force jarang menghasilkan algoritma yang mangkus.

 Beberapa algoritma brute force lambat sehingga tidak dapat

diterima.

 Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya.

 Ken Thompson (salah seorang penemu Unix) mengatakan: “When in

doubt, use brute force”, faktanya kernel Unix yang asli lebih
menyukai algoritma yang sederhana dan kuat (robust) daripada
algoritma yang cerdas tapi rapuh.
Terima Kasih..
Referensi

• Rinaldi Munir, Diktat Kuliah Strategi Algoritmik, 193, 2005.