lecture note graf & algoritma - official site of...
TRANSCRIPT
Lecture Note
Logika & Algoritma
Jurusan Manajemen Informatika
Fakultas Ilmu Komputer & Teknologi Informasi
Universitas Gunadarma
Logika & Algoritma Halaman 2 dari 99 halaman RAT
Pertemuan ke-1
Teori Dasar Graf
Kelahiran Teori Graf
Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss, bernama
Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg pada tahun
1736. Di Kota Konigsberg (sekarang bernama Kalilingrad, di Uni Soviet) mengalir
sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut terdapat dua buah
pulau. Dari kedua pulau tersebut terdapat jembatan yang menghubungi ke tepian
sungai dan diantara kedua pulau. Jumlah jembatan tersebut adalah 7 buah seperti
gambar berikut :
Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat tersebut
pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat menikmati daerah
tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni bermula dari satu
tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka berusaha untuk
memperoleh rute yang sesuai dengan keinginan tersebut, dengan selalu mencoba
Sungai Pregel
di Kalilingrad
(Uni Soviet)
A
B
C D
Logika & Algoritma Halaman 3 dari 99 halaman RAT
menjalaninya. Setelah mencoba berkali-kali dan karena sudah cukup lama tidak
diperoleh rutenya, akhirnya penduduk tersebut mengirim surat kepada Euler. Euler
dapat memecahkan masalah tersebut, yakni bahwa perjalanan / rute yang diinginkan
(yakni berawal dari suatu tempat, melalui ketujuh jembatan tepat satu kali, dan kembali
ke tempat semula) tidak mungkin dicapai.
Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg
tersebut seperti gambar berikut :
Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan
sebagai titik dan jembatan disajikan sebagai ruas garis. Euler mengemukakan
teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang
kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan
banyaknya garis yang datang pada setiap titik (derajat simpul) adalah genap.
Problema & Model Graf
Secara umum, langkah-langkah yang perlu dilalui dalam penyelesaian suatu masalah
dengan bantuan komputer adalah sebagai berikut :
Problema Model Yang Tepat Algoritma Program Komputer
A
C D
B
Logika & Algoritma Halaman 4 dari 99 halaman RAT
Contoh problema graf :
1. Petugas kantor telepon yang ingin mengumpulkan koin-koin dari telepon umum.
Berangkat dari kantor & kembali ke kantornya lagi.
Yang diharapkan suatu rute perjalanan dengan waktu minimal.
Masalah di atas dikenal sebagai Travelling Salesman Problem
Sebagai contoh :
Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Tetangga Terdekat
(yakni menggunakan Metode Greedy)
= Kantor
8
11 7
12 9 11 9
11 10 8
1
3 4
2
5
* waktu dalam menit
1
Logika & Algoritma Halaman 5 dari 99 halaman RAT
2. Perancangan Lampu Lalu Lintas.
Yang diharapkan pola lampu lalu lintas dengan jumlah fase minimal.
Sebagai contoh :
Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Pewarnaan Graf (juga
dikenal sebagai Graph Coloring, yakni menggunakan Metode Greedy)
Graf Secara Formal
Sebuah Graf G mengandung 2 himpunan :
(1). Himp. V, yang elemennya disebut simpul
Vertex / point / titik / node
(2). Himp. E, yang merupakan pasangan tak terurut dari simpul-simpul, disebut ruas
C D
B E
A
F
A
A
B
B
A
D
D
F B
F
F C
E
C
E
C
E
B
C
E
Logika & Algoritma Halaman 6 dari 99 halaman RAT
Edge / rusuk / sisi
Sehingga sebuah graf dinotasikan sebagai G ( V, E )
Contoh :
G ( V, E )
V = { A, B, C, D }
E = { ( A, B ), ( B, C ), ( C, D ), ( D, A ), ( B, D ) }
Secara Geometri :
Tidak ada ketentuan khusus dalam penyajian graf secara geometri, seperti dimana dan
bagaimana menyajikan simpul dan ruas. Berikut contoh penyajian Graf yang sama,
tetapi disajikan berbeda.
e2
e3 e1 e5
e4 C D
A B
terdiri dari 4 simpul dan 5 ruas
C
A
D
A
A
B
A
D B
C
D B
C
Logika & Algoritma Halaman 7 dari 99 halaman RAT
Beberapa istilah lain dalam graf :
Berdampingan
simpul U dan V disebut berdampingan bila terdapat ruas (U,V)
Order
banyaknya simpul
Size
banyaknya ruas
Self-loop (loop) / Gelung
ruas yang menghubungkan simpul yang sama ( sebuah simpul )
Ruas sejajar / berganda
ruas-ruas yang menghubungkan 2 simpul yang sama
Sebuah graf dikatakan multigraf bila graf tersebut mengandung ruas sejajar atau
gelung. Sedangkan graf yang tidak mengandung ruas sejajar atau gelung dikenal
sebagai graf sederhana, atau yang disebut graf. Adapun contoh multigraf adalah
sebagai berikut.
Subgraf
G‘(V‘, E‘) adalah Subgraf dari G (V, E) bila : V‘ V dan E‘ E
Apabila E‘ mengandung semua ruas di E yang kedua ujungnya di V‘ , maka
G‘ adalah Subgraf yang dibentuk oleh V‘ (Spanning Subgraph)
A
A A
e2
w
12 A
e3
e4 e1
e5
e6
Multigraf
Logika & Algoritma Halaman 8 dari 99 halaman RAT
Contoh :
Graf berlabel
Graf berlabel/ berbobot adalah graf yang setiap ruasnya mempunyai nilai/bobot berupa
bilangan non negatif.
Contoh :
e2
e3 e1 e5
e4 C D
A B
G :
e5 e1
A B
D
G’ :
G’ subgraf dari G
e2
e5 e1
A B
D
G’ :
G’ spanning subgrapf dari G
B D F
C G E
H A
3
19
8
13
3
3
4
2 2 2
12
6
3
Logika & Algoritma Halaman 9 dari 99 halaman RAT
Isomorfisma
G (V,E) dan G* (V*,E*) adalah 2 buah Graf.
f : V V * suatu fungsi satu-satu dan pada, sedemikian sehingga (u,v) adalah ruas
dari G jika dan hanya jika (f (u),f(v)) adalah ruas dari G *
Maka f disebut fungsi yang isomorfisma dan G & G * adalah graf-graf yang isomorfis
Contoh :
Graf yang berbentuk huruf A & R, X & K, F & T, dan V & Z, di bawah ini adalah
isomorfis.
Homomorfis
Jika G* dan G** diperoleh dari G dengan membagi beberapa ruas dari G oleh
penambahan beberapa simpul pada ruas tersebut, maka kedua graf G* dan G**
disebut homomorfis
Logika & Algoritma Halaman 10 dari 99 halaman RAT
Contoh :
Operasi pada Graf
Berdasarkan definisi graf (yang terdiri dari 2 himpunan) dan operasi pada himpunan,
maka pada graf juga dapat dilakukan operasi-operasi. Bila diketahui 2 buah graf :
G1(V1,E1) dan G2(V2,E2), maka :
1. Gabungan G1 G2 adalah graf dengan himpunan V nya = V1 V2 dan himpunan E
nya = E1 E2
2. Irisan G1 G2 adalah graf dengan himpunan V nya = V1 V2 dan himpunan E nya =
E1 E2
3. Selisih G1 - G2 adalah graf dengan himpunan V nya = V1 dan himpunan E nya = E1 -
E2
Sedangkan Selisih G2 – G1 adalah graf dengan himpunan V nya = V2 dan himpunan
E nya = E2 – E1
4. Penjumlahan Ring G1 G2 adalah graf yang dihasilkan dari
(G1 G2) – (G1 G2) atau (G1 - G2) (G2 - G1)
G G* G**
Logika & Algoritma Halaman 11 dari 99 halaman RAT
Contoh :
C D
B A
E
e2 e4
e1
e3
e6 e5
e7 e8
A
F
D
e1 B
C
e4 e2
e10
e3
e9
D
A e1 B
C
e4 e2
e3 C D
B A
E
e2 e4
e1
e3
e6 e5
e7 e8
e10 e9
C D
B A
E
e6 e5
e7 e8
C D
e10 e9
C D
B A
E
e6 e5
e7 e8
e10 e9
G1 G2
G1 G2 G1 G2
G1 G2
G1 - G2 G2 – G1
Logika & Algoritma Halaman 12 dari 99 halaman RAT
Graf Null / Hampa
Ada beberapa pengertian tentang graf null/hampa. Di sini akan dipakai pengertian
bahwa suatu graf dikatakan graf null/hampa bila graf tersebut tidak mengandung ruas.
Contoh :
Suatu graf G dikatakan dikomposisikan menjadi K dan L bila G = K L dan K L =
Contoh :
Penghapusan / Deletion
Penghapusan dapat dilakukan pada simpul ataupun ruas.
1) Penghapusan Simpul .
G L
K
D
A
A
A
B
B
B
C
C
C D
G :
V1
V3
V2
V dan
E =
Logika & Algoritma Halaman 13 dari 99 halaman RAT
Notasinya : G – {V}
Contoh :
Penghapusan Simpul V2
2) Penghapusan Ruas .
Notasinya : G – {e}
Contoh :
Penghapusan Ruas e3
Pemendekan / Shorting
Pemendekan/Shorting adalah menghapus simpul yang dihubungkan oleh 2 ruas
(simpul berderajat 2), lalu menghubungkan titik-titik ujung yang lain dari kedua ruas
tersebut.
Contoh :
V1 V1 V2
V3 V4
V5
V6 V7 V7 V6
V5
V4 V3
e1 e1
e2 e2 e3 e4 e4
e5 e5
Logika & Algoritma Halaman 14 dari 99 halaman RAT
pemendekan terhadap simpul A dan C
Derajat Graf
Derajat graf adalah jumlah dari derajat simpul-simpulnya. Sedangkan derajat simpul
adalah banyaknya ruas yang incidence (terhubung) ke simpul tersebut.
Contoh :
d (A) = 2
d (B) = 5
d (C) = 3
d (D) = 3
d (E) = 1
d (F) = 0
+
Σ = 14 = 2 x Size
B
C
F
E D
A
A
D D C
B B
Logika & Algoritma Halaman 15 dari 99 halaman RAT
Berdasarkan derajat simpul, sebuah simpul dapat disebut :
Simpul Ganjil, bila derajat simpulnya merupakan bilangan ganjil
Simpul Genap, bila derajat simpulnya merupakan bilangan genap
Simpul Bergantung / Akhir, bila derajat simpulnya adalah 1
Simpul Terpencil, bila derajat simpulnya adalah 0
Keterhubungan
Dalam keterhubungan sebuah graf, akan dikenal beberapa istilah-istilah berikut :
1. Walk : barisan simpul dan ruas
2. Trail : Walk dengan ruas yang berbeda
3. Path / Jalur : Walk dengan simpul yang berbeda
4. Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2
Contoh :
1) A, B, C, D, E, F, C, A, B, D, C Walk
2) A, B, C, D, E, F, C, A Trail
3) A, B, C, A Cycle
4) A, B, D, C, B, D, E Walk
5) A, B, C, D, E, C, F Trail
6) A, B, D, C, E, D Trail
7) A, B, D, E, F, C, A Cycle
8) C, E, F Path
E D
A
B
F C
b
d
h
e
g c k
f
a
Logika & Algoritma Halaman 16 dari 99 halaman RAT
9) B, D, C, B Cycle
10) C, A, B, C, D, E, C, F, E Trail
11) A, B, C, E, F, C, A Trail
Graf yang tidak mengandung cycle disebut dengan Acyclic
Contoh :
Suatu graf G disebut terhubung jika untuk setiap 2 simpul dari graf terdapat jalur yang
menghubungkan kedua simpul tersebut.
Subgraf terhubung suatu graf disebut komponen dari G bila subgraf tersebut tidak
terkandung dalam subgraf terhubung lain yang lebih besar.
Jarak antara 2 simpul dalam graf G adalah panjang jalur terpendek antara ke-2 simpul
tersebut.
Diameter suatu graf terhubung G adalah maksimum jarak antara simpul-simpul G.
Ada Subgraf S dari graf terhubung G, yang bila kita ambil / pindahkan dari G, akan
menyebabkan G tidak terhubung .
Kalau tidak ada Subgraf sejati R dari S, yang pemindahannya juga menyebabkan G
tidak terhubung, maka S disebut Cut-Set dari G.
Graf Regular
Sebuah graf dikatakan graf regular bila derajat setiap simpulnya sama.
Logika & Algoritma Halaman 21 dari 99 halaman RAT
Pertemuan ke-2
Teori Dasar Graf (Lanjutan)
Matriks dan Graf
Untuk menyelesaikan suatu permasalahan model graf dengan bantuan komputer, maka
graf tersebut disajikan dalam bentuk matriks. Matriks-matriks yang dapat menyajikan
model graf tersebut antara lain :
Matriks Ruas
Matriks Adjacency
Matriks Incidence
Sebagai contoh, untuk graf seperti di bawah ini :
Maka,
Matriks Ruas :
V4 V5
V2 V3
V1
e6
e5
e4
e3
e2
e1
e8
e7
1 2
1 3
1 4
1 5
2 3
3 4
3 5
4 5
n x 2
Logika & Algoritma Halaman 22 dari 99 halaman RAT
Atau :
Matriks Adjacency :
Matriks Incidence :
Graf Planar
Sebuah graf dikatakan graf planar bila graf tersebut dapat disajikan (secara geometri)
tanpa adanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa adanya ruas
yang berpotongan disebut dengan penyajian planar/map/peta.
Contoh :
1 1 1 1 2 3 3 4
2 3 4 5 3 4 5 5
2 x n
V1 V2 V3 V4 V5
V1 0 1 1 1 1
V2 1 0 1 0 0
V3 1 1 0 1 1
V4 1 0 1 0 1
V5 1 0 1 1 0
e1 e2 e3 e4 e5 e6 e7 e8
V1 1 1 0 1 1 0 0 0
V2 1 0 1 0 0 0 0 0
V3 0 1 1 0 0 1 1 0
V4 0 0 0 1 0 1 0 1
V5 0 0 0 0 1 0 1 1
Graf Planar
K4
Penyajian Planar
Logika & Algoritma Halaman 23 dari 99 halaman RAT
Graf yang termasuk planar antara lain :
Tree / Pohon
Kubus
Bidang Empat
Bidang Delapan Beraturan
Tree / Pohon
Kubus
Bidang Empat
Bidang Delapan Beraturan
Logika & Algoritma Halaman 24 dari 99 halaman RAT
Pada penyajian planar/map, dikenal istilah region. Derajat dari suatu region adalah
panjang walk batas region tersebut
Contoh :
d ( r1 ) = 3
d ( r2 ) = 3
d ( r3 ) = 5
d ( r4 ) = 4
d ( r5 ) = 3
+
Σ = 18 = 2 x SIZE
Region dengan batasnya gelung, maka d (r) = 1
Region dengan batasnya ruas sejajar, maka d (r) = 2
Formula Euler untuk Graf Planar
Untuk Graf Planar berlaku Formula Euler berikut :
V – E + R = 2
Dimana p = jumlah simpul dan q = jumlah ruas
r1
r4
r5
r2
r3
A B
C
D
F E
Logika & Algoritma Halaman 25 dari 99 halaman RAT
Graf Non-Planar
Sebuah graf yang tidak dapat disajikan (secara geometri) tanpa adanya ruas yang
berpotongan dikenal sebagai graf non planar.
Contoh :
K3,3
Utility Graph K5 = Bintang
Teorema Kuratowski ( 1930 )
Suatu graf adalah Non-Planar jika dan hanya jika mengandung subgraf yang
Homomorfis ke K3,3 atau ke K5
Pewarnaan Graf
Pewarnaan graf adalah pemberian warna terhadap simpul-simpul graf dimana 2 buah
simpul yang berdampingan tidak boleh mempunyai warna yang sama.
G berwarna n artinya graf tersebut menggunakan n warna.
Bilangan kromatis dari G = K(G) adalah jumlah minimum warna yang dibutuhkan.
Algoritma yang dapat digunakan untuk mendapatkan bilangan kromatis dari sebuah
graf adalah Algoritma Welch-Powell.
Adapun langkah-langkahnya adalah :
1. Urutkan simpul-simpul berdasarkan derajatnya.
Dari besar ke kecil.
2. Warnai.
Logika & Algoritma Halaman 26 dari 99 halaman RAT
Contoh :
Langkah 1 :
urutan simpulnya dari besar ke kecil adalah : E, C, G, A, B, D, F, H
Langkah 2 :
mewarnai :
warna Merah : E, A
warna Putih : C, D, H
warna Biru : G, B, F
Sehingga bilangan kromatis graf di atas adalah 3.
Teorema :
Pernyataan berikut adalah ekivalen :
(1) G berwarna 2
(2) G adalah bipartisi
(3) Setiap sirkuit dalam G mempunyai panjang genap
Graf Lengkap k dengan n simpul membutuhkan n warna
G
A B C
D
E F
H
Logika & Algoritma Halaman 27 dari 99 halaman RAT
Teorema :
Suatu graf planar G adalah berwarna 5
Pewarnaan Region
Pewarnaan region dapat dilakukan (seperti pemberian warna pada wilayah-wilayah di
peta) dengan cara membuat dual dari map tersebut. Gambarkan sebuah simpul baru
pada masing-masing region suatu map M, kemudian buat sebuah ruas yang
menghubungkan simpul pada 2 buah region yang berdampingan bila terdapat ruas
sebagai batas / persekutuan kedua region tersebut. Buatlah tanpa adanya ruas baru
yang berpotongan, maka akan terbentuk suatu map M*, yang disebut dual dari map M.
Setelah Dualnya terbentuk, dapar dilakukan pewarnaan terhadap simpul-simpulnya.
Simpul-simpul tersebut mewakili region sebelumnya, sehingga warna yang digunakan
untuk suatu simpul berarti warna yang dapat digunakan untuk pewarnaan region yang
diwakilinya.
Teorema : suatu map M adalah berwarna 5
Setiap graf planar adalah berwarna (simpul) 4
Dibuktikan oleh Apple & Haken (1976) – 2000 Graf, jutaan kasus.
Logika & Algoritma Halaman 28 dari 99 halaman RAT
Pertemuan ke-3
Pohon (Tree)
Pohon
Tree atau pohon adalah graf terhubung yang tidak mengandung sirkuit.
Untuk itu perlu diingat kebali bahwa :
Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G
selalu terdapat jalur yang menghubungkan kedua simpul tersebut.
Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul
dua.
Contoh :
Sifat :
Logika & Algoritma Halaman 29 dari 99 halaman RAT
Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur
diantara setiap pasang simpul dari Graf G.
Teorema :
Suatu Graf G dengan n buah simpul adalah Pohon jika :
(1) G terhubung dan tak mengandung sirkuit, atau
(2) G tidak mengandung sirkuit dan mempunyai n-1 buah ruas, atau
(3) G mempunyai n-1 buah ruas dan terhubung
Pohon Rentangan
Suatu spanning tree atau pohon rentangan adalah suatu subgraf dari graf G yang
mengandung semua simpul dari G, dan merupakan suatu pohon.
Contoh :
Contoh :
GRAF G SPANNING TREE
n simpul n simpul
m ruas n – 1 ruas
m – ( n – 1)
BRANCH
(CABANG)
CHORD
Keterangan
Branch
Chord
Logika & Algoritma Halaman 31 dari 99 halaman RAT
Pohon Rentangan Minimal
Apabila G suatu Graf berbobot (Suatu Network); maka pohon rentangan minimal dari
graf adalah pohon rentangan dengan jumlah bobot terkecil.
Minimal spanning tree
Contoh :
Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut :
Solin
Kruskal
Prim’s
SOLIN
1. Urutkan ruas dari G menurut bobotnya; dari besar ke kecil.
2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan; dengan
ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi
tidak terhubung.
.
. .
.
.
.
. . .
11
19
10
13
16
15
9 18
14
12
8 17
Logika & Algoritma Halaman 32 dari 99 halaman RAT
KRUSKAL
1. Urutkan ruas dari G menurut bobotnya; dari kecil ke besar.
2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan; dengan
ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.
PRIM’S
= Kruskal + menjaga graf tetap terhubung
Untuk mencari pohon rentangan maksimal, dapat dilakukan dengan dengan cara
merubah bobot tiap ruas menjadi – (bobot yang lama)
Definisi :
Hutan atau foresi adalah graf yang tidak mengandung sirkuit.
Pohon adalah hutan yang terhubung
Contoh :
Logika & Algoritma Halaman 33 dari 99 halaman RAT
Pertemuan ke-4
Berbagai Jenis Pohon (Tree)
Pohon Berakar
Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yang
dirancang/ditunjuk sebagai akar (root) dari R. Seperti diketahui bahwa hanya terdapat
satu jalur antara r dengan simpul lain v pada pohon pohon tersebut. Panjang jalur
antara r dengan simpul v disebut level atau kedalaman simpul v. Simpul bukan akar,
yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun
disebut cabang (branch).
Berikut ini contoh pohon berakar.
Contoh :
Suatu pohon dapat dijadikan suatu pohon berakar cukup dengan mengangkat salah
satu simpul sebagai akar. Dengan adanya akar, setiap ruas dari pohon seolah-olah
mempunyai arah, yang bermula dari akar tersebut. Simpul u dikatakan mendahului
simpul v jika jalur dari akar r ke v melalui u. Dikatakan u mendahului langsung v bila u
R
b c
d e f g
a
h i j
Logika & Algoritma Halaman 34 dari 99 halaman RAT
mendahului v serta simpul u dan v berdampingan. Pada contoh di atas, a mendahului d,
mendahului e, dan mendahului h.
Suatu pohon berakar dapat digunakan untuk menelusurisemua kemungkinan dari
kejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara.
Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree)
dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree).
Pohon Binar
Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini
biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan
hirarkikal antara elemen-elemen mereka.
Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary.
Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan
terdiri dari sebuah himpunan hingga elemen yang disebut simpul (node), sedemikian
sehingga :
a. T adalah hampa (disebut pohon null) atau
b. T mengandung simpul R yang dipilih (dibedakan dari yang lain), disebut
akar (root) dari T, dan simpul sisanya membentuk 2 pohon binar (subpohon
kiri dan subpohon kanan dari R) T1 dan T2 yang saling lepas.
Perhatikan bahwa pendefinisian pohon binar di atas adalah rekursif. Jika T1 tidak
hampa, maka simpul akarnya disebut suksesor kiri dari R. Hal serupa untuk akar dari
T2 (tidak hampa) disebut suksesor kanan dari R.
Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagian
paling atas. Sedangkan suksesor kiri digambarkan sebagai garis ke kiri bawah dan
suksesor kanan sebagai garis ke kanan bawah.
Contoh :
Logika & Algoritma Halaman 35 dari 99 halaman RAT
Pohon Sintaks
Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebih
dahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu :
SI KUCING KECIL MENENDANG BOLA BESAR
Gambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohon
sintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Dari
pelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya,
atau telah benar tata bahasanya.
Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :
A
C
G D E F
I
B
H
J K
Logika & Algoritma Halaman 36 dari 99 halaman RAT
KALIMAT
Besar
Predikat Subyek
Bola Menendang Kecil Si Kucing
Obyek
Kata
Keadaan
Kata
Benda
Kata
Kerja
Kata
Keadaan
Kata
Sandang
Kata
Benda
Logika & Algoritma Halaman 37 dari 99 halaman RAT
Pertemuan ke-5
Graf Berarah
Graf Berarah
Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran
(flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan
konsep graf tak berarah.
Suatu graf berarah (Directed Graph, yang dikenal sebagai Digraf) D terdiri dari 2
himpunan :
(1). Himp. V, yang elemennya disebut simpul
Vertex / point / titik / node
(2). Himp. A, yang merupakan pasangan terurut dari simpul-simpul, disebut ruas
berarah
Arc / arkus
Sehingga sebuah digraf dinotasikan sebagai D ( V, A )
Contoh :
Sebuah graf berarah D(V,A), dengan :
1. V = { 1, 2, 3, 4 }
2. A = { (1,4), (2,1), (2,1), (4,2), (4,3), (2,3), (2,2) }
Arc (2,2) disebut gelung (self-loop), sedangkan arc (2,2) muncul 2 kali, disebut arc
sejajar atau arc berganda.
4
3
2
1
Logika & Algoritma Halaman 38 dari 99 halaman RAT
Apabila arc suatu graf berarah mempunyai suatu bobot, graf berarah tersebut
dinamakan suatu jaringan atau network.
Beberapa Pengertian dalam graf berarah :
Derajat ke luar (out degree) suatu simpul adalah banyaknya arc yang mulai /
keluar dari simpul tersebut.
Derajat ke dalam (in degree) suatu simpul adalah banyaknya arc yang berakhir /
masuk ke simpul tersebut.
Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul
berderajat ke luar = 0 disebut muara (sink).
Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf
berarah, dimana harus sesuai dengan arah arc. Kalau tidak sesuai dengan arah
arc-nya, maka disebut sebagai semi walk, semi path atau semi trail.
Pada graf berarah terdapat 3 pengertian keterhubungan, yakni :
Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari D.
Terhubung unilateral, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari
u ke v atau dari v ke u.
Terhubung kuat, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke
v dan dari v ke u.
Contoh :
A B
C
A B
C
A B
C
Terhubung Lemah Terhubung Unilateral Terhubung Kuat
Logika & Algoritma Halaman 39 dari 99 halaman RAT
Relasi dan Matriks
Pandang D(V,A) suatu graf berarah tanpa arc sejajar, maka A adalah himpunan bagian
dari V x V (produk Cartesis himpunan), jadi merupakan Relasi pada V. Sebaliknya bila
R adalah Relasi pada suatu himpunan V, maka D(V,R) merupakan graf berarah tanpa
arc sejajar. Jadi konsep Relasi dan konsep graf berarah tanpa arc sejajar adalah satu
dan sama.
Misalkan D(V,A) suatu graf berarah dengan simpul v1, v2, … , vm. Matriks M berukuran
(mxm) merupakan matriks (matriks adjacency) dari D, dengan mendefinisikan sebagai
berikut :
M = (Mij), dengan mij banyaknya arc yang mulai di vi dan berakhir di vj
Bila D tidak mengandung arc berganda, maka elemen M adalah 0 dan 1. Kalau Graf
berarah mengandung arc berganda, elemen M merupakan bilangan bulat non negatif.
Jadi suatu matriks berukuran (mxm) yang elemennya bilangan bulat non negatif
menyatakan secara tunggal suatu graf berarah dengan m simpul.
Contoh :
Teorema :
M adalah Matriks dari sutau graf berarah D, maka elemen baris ke i kolom ke j dari
Matriks Mn menyatakan banyaknya walk dengan panjang n dari simpul vi ke simpul vj.
V2
V4
V3
V1 1 0 0 0
1 0 0 0
0 2 0 1
0 0 1 0
D(V,A) :
Matriks M
Logika & Algoritma Halaman 40 dari 99 halaman RAT
Algoritma Jalur Terpendek
Pandang D suatu graf berarah yang hingga dengan tiap-taip arc mempunyai bobot. Jadi
D merupakan suatu network. Kita hendak menentukan Jalur Terpendek antara 2 simpul
u dan v.
Gambar berikut merupakan suatu network. Kita ingin menghitung jalur terpendek dari
simpul u ke simpul v.
Untuk dapat menentukan jalur terpendeknya, kita gunakan cara berikut :
Buat table jarak, dengan tiap kolom mewakili simpul yang ada, dan kita isikan
data jarak dari satu simpul ke simpul lainnya sesuai dengan kolom yang ada.
Usahakan diurut dari yang kecil ke besar.
Kita mulai dengan simpul u sebagai simpul awal. Beri harga = 0. Ambil simpul
dengan jarak terdekat dari u, dalam hal ini z (uz =2), kemudian tandai uz. Semua
arc lain, yang berakhir di z kita hapus. Beri harga = 2 pada kolom z. Kemudian
u x y z a b c v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u
x a
y b v
c z
4
2 2
3
6
1
5
2
2
3
3
3
4
Sumber Muara
Logika & Algoritma Halaman 41 dari 99 halaman RAT
pada judul kolom yang telah diberi harga, kita tandai *. Hasil langkah tersebut
dapat dilihat pada tabel berikut ini :
Dari simpul u dan z (yang telah ditandai *), dicari simpul lain yang jaraknya
terdekat dihitung dari u. Jadi harus diperhitungkan harga yang tertulis di judul
kolom. Disini ux =4 merupakan nilai terkecil, sehingga kita beri harga pada kolom
x = 4, kemudian kita hapus data yang berakhir dengan x dan kita beri tanda *
pada judul kolom x. Hasil langkah tersebut dapat dilihat pada tabel berikut ini :
Demikian proses dilanjutkan berturut-turut sebagai berikut :
u* (0) x y z* (2) a b c v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u* (0) x* (4) y z* (2) a b c v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u* (0) x* (4) y* (4) z* (2) a b c v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u* (0) x* (4) y* (4) z* (2) a b c* (5) v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
Logika & Algoritma Halaman 42 dari 99 halaman RAT
Dari tabel terakhir, data yang kita gunakan adalah data yang ditandai kotak. Terlihat
dari judul kolom masing-masing simpul, harga yang merupakan jarak terpendek dari
simpul awal (dalam hal ini simpul u) ke simpul tersebut. Sebagai contoh, jarak
terpendek dari u ke v adalah 8. Sedangkan dari u ke c adalah 5, dan seterusnya.
Jalur terpendek dari u ke v dapat ditentukan dengan cara mundur, yakni dari data yang
ada yang berakhir dengan v adalah cv, kemudian yang berakhir dengan c adalah yc,
yang berakhir dengan y adalah zy dan yang berakhir dengan z adalah u. Sehingga jalur
yang dimaksud adalah : u z y c v
Penggambaran dari solusi tersebut adalah sebagai berikut :
u* (0) x* (4) y* (4) z* (2) a b* (6) c* (5) v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u* (0) x* (4) y* (4) z* (2) a* (8) b* (6) c* (5) v
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
u* (0) x* (4) y* (4) z* (2) a* (8) b* (6) c* (5) v* (8)
uz = 2
ux = 4
uy = 6
xy = 3
xa = 4
yc = 1
yb = 2
zy = 2
zc = 5
ab = 2
av = 3
bv = 3 cv = 3
Logika & Algoritma Halaman 43 dari 99 halaman RAT
Problema Aliran Maksimal
Tujuan dari problema aliran maksimal adalah mengatur jadwal pengiriman barang agar
jumlah barang yang dikirimkan dari suatu simpul ke simpul lain (yang tertentu) adalah
maksimum. Simpul yang mengirimkan (simpul awal) disebut sumber (source) dan
simpul yang menerima kiriman disebut muara (sink). Antara sumber dan muara
terdapat pula simpul lain yang disebut simpul perantara. Dalam hal ini ditetapkan bahwa
simpul perantara tidak dapat menyimpan barang.
Contoh :
u
x a
y b v
c z
4
2 2
3
6
1
5
2
2
3
3
3
4
Sumber Muara
a b
c
d sumber muara
8 4 10
0 4
5
5
10 0
0
0 7
Logika & Algoritma Halaman 44 dari 99 halaman RAT
Untuk menyelesaikan problema aliran maksimal ini dapat digunakan beberapa cara,
antara lain dengan menelusuri satu persatu jalur yang dapat dilalui ataupun dengan
memanfaatkan max flow min cut. Adapun aliran maksimal dari contoh ini adalah 22.
Logika & Algoritma Halaman 45 dari 99 halaman RAT
Pertemuan ke-6
Graf Berarah (Lanjutan)
Mesin State Hingga
Mesin State Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas :
(1) Himpunan hingga A, berisi simbol input
(2) Himpunan hingga S, berisi internal state
(3) Himpunan hingga Z, berisi simbol output
(4) Sebuah fungsi f : S x A S, disebut fungsi next-state
(5) Seubuah fungsi g : S x A Z disebut fungsi output
M ( A, S, Z, f, g)
M (A, S, Z, q0, f, g)
Contoh : M ( A, S, Z, f, g) dengan :
(1) A = (a,b)
(2) S = (q0, q1, q2)
(3) Z = ( x, y, z)
(4) f : S x A S, yang didefinisikan sebagai :
f (qo, a) = q1 f (q0, b) = q2
f (q1, a) = q2 f (q1, b) = q1
f (q2, a) = qo f (q2, b) = q1
(5) g : S x A Z, yang didefinisikan sebagai :
g (q0, a) = x g (q0, b) = y
g (q1, a) = x g (q1, b) = z
g (q2, a) = z g (q2, b) = y
INPUT : Untai
OUTPUT : Untai
Logika & Algoritma Halaman 46 dari 99 halaman RAT
Automata Hingga
Automata Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas : (1) Himpunan hingga A, berisi simbul input
(2) Himpunan hingga S, berisi internal state
(3) Himpunan T (dimana T S), elemennya disebut state penerima
(4) State awal (biasanya q0), anggota S
(5) Fungsi next-state f : S x A S
M (A, S, T, qo, f)
Contoh : M (A, S, T, qo, f) dengan :
(1) A = a, b
(2) S = q0, q1, q2
(3) T = qo, q1
(4) State awal = q0
(5) Fungsi next-state f : S x A S, yang didefinisikan sebagai tabel berikut :
f a b
q0
q1
q2
q0
q0
q2
q1
q2
q2
INPUT : Untai
OUTPUT : Diterima
atau ditolak
Logika & Algoritma Halaman 47 dari 99 halaman RAT
Pertemuan ke-7
Algoritma
Algoritma
Istilah algoritma pertama kali diperkenalkan oleh seorang ahli matematika yaitu Abu
Ja’far Muhammad Ibnu Musa Al Khawarizmi.
Yang dimaksud dengan algoritma adalah :
Urutan dari barisan instruksi untuk menyelesaikan suatu masalah
Adapun algoritma dapat dinyatakan dalam bentuk : flow chart, diagram alur,
bahasa semu
Sedangkan secara bahasa, algoritma berarti suatu metode khusus untuk
menyelesaikan suatu masalah yang nyata (dari Webster Dictionary).
Dari suatu permasalahan yang akan diselesaikan, bisa terjadi terdapat lebih dari satu
algoritma. Dalam memilih algoritma yang terbaik yang dapat digunakan, harus
diperhatikan beberapa kriteria. Kriteria tersebut antara lain :
Efektif dan efisien
Jumlah langkahnya berhingga
Berakhir
Ada output
Terstruktur
Adapun langkah-langkah yang dilakukan dalam proses penyelesaian masalah dengan
bantuan komputer adalah sebagai berikut :
Logika & Algoritma Halaman 48 dari 99 halaman RAT
MASALAH ?
MODEL
PROGRAM
ALGORITMA
HASIL / SOLUSI
EKSEKUSI
DATA
Studi Tentang Algoritma
Hal-hal yang akan dipelajari mengenai studi algoritma yaitu :
1. Bagaimana Merencanakannya
2. Bagaimana Menyatakannya
3. Bagaimana Validitasnya
4. Bagaimana Menganalisisnya
5. Bagaimana Menguji suatu program
Merencanakan algoritma : Merupakan suatu studi tentang teknik variasi design (model)
Menyatakan algoritma : Menyatakannya dengan singkat, dibuat dalam bahasa
pemrograman yang terstruktur, misalnya Pascal, C
Logika & Algoritma Halaman 49 dari 99 halaman RAT
Validitas algoritma : Memenuhi kebutuhan yang diinginkan, dan
perhitungannya/solusinya selalu benar untuk semua kemungkinan input yang
legal
Menganalisis algoritma : Perbandingan dari waktu perhitungan dan banyaknya
storage/memori yang digunakan (efisiensi)
Menguji suatu program : Pengujian suatu program yang dilakukan dalam dua fase,
yakni :
Fase Debugging :
proses dari eksekusi program yang mengkoreksi kesalahan dalam bahasa
pemrograman (logic & syntax)
Fase Profiling :
program sudah benar
melihat/mengukur waktu tempuh & storage
Analisis Algoritma
Sebagaimana studi tentang algoritma, maka faktor yang sangat diperhitungkan adalah
faktor efisiensi, yang meliputi :
a. Waktu tempuh (running time)
banyaknya langkah
besar dan jenis input data
jenis operasi
jenis komputer dan kompilator
b. Jumlah memori yang dipakai
Dalam hal menganalisis algoritma, dikenal istilah kompleksitas.
Kompleksitas adalah :
Sebuah fungsi F(N) yang diberikan untuk waktu tempuh dan / atau kebutuhan
storage dengan ukuran N input data
Kompleksitas ini dapat berupa kompleksitas waktu & memori
Logika & Algoritma Halaman 50 dari 99 halaman RAT
Beberapa definisi kompleksitas:
1. f(n) = (g(n)) dua konstanta positif c dan n0
f(n) cg(n) n n0
2. f(n) = (g(n)) konstanta positif c dan n0
f(n) cg(n) n n0
3. f(n) = (g(n)) konstanta positif c1, c2 dan n0
c1g(n) f(n) c2g(n) n n0
4. f(n) (g(n)) sebuah konstanta positif n0
lim ( ) / ( )n
f n g n
1, n n0
Dari keempat definisi di atas, yang paling banyak digunakan untuk menganalisis
algoritma adalah definisi 1 (Big Oh).
Teorema :
Jika f(n) = am nm + am-1 nm-1 + . . .+ a1 n + a0 adalah polinomial tingkat m,
maka f(n) = (nm)
Sebagai contoh :
f(n) = 3n5 + 4n4 + 10n2 + 56 = (n5 )
f(n) = 9n7 + 5n6 + 36 = (n7 )
f(n) = 8n9 = (n9 )
f(n) = n6 + 19 = (n6 )
f(n) = 25 = (n0 ) = (1)
Berikut ini adalah urutan dari Big Oh - Big Oh :
(1) (log n) (n) (n log n) (n2) (n3) (2n)
Logika & Algoritma Halaman 51 dari 99 halaman RAT
Berikut ini beberapa contoh analisis terhadap algoritma
Contoh 1 :
(i) c a + b
(ii) for i 1 to n do
c a + b
repeat
(iii) for i 1 to n do
for j 1 to n do
c a + b
repeat
repeat
Analisisnya :
banyaknya
operasi +
f(n) Big Oh
(i) 1 kali f(n) = 1 (1)
(ii) n kali f(n) = n (n)
(iii) n2 kali f(n) = n2 (n2)
Contoh 2 :
Penjumlahan 2 buah matriks berorde (m X n) dan elemennya real
1. Set A[i,j], B[i,j], C[i,j] real
2. Untuk i 1 s/d m kerjakan
3. untuk j 1 s/d n kerjakan
4. C[i,j] A[i,j] + B[i,j]
5. akhir j
6. akhir i
Logika & Algoritma Halaman 52 dari 99 halaman RAT
Analisisnya :
jumlah operasi + = mn kali
jumlah memori = 3 mn x 4 = 12 mn
(asumsi : 1 elemen memerlukan 4 satuan memori/byte)
total = 13 mn
Keadaan Dari Kompleksitas Waktu Algoritma
Keadaan dari kompleksitas waktu algoritma meliputi :
a. WORST Case nilai maksimum dari f(n) input yang mungkin
b. BEST Case nilai minimum dari f(n) input yang mungkin
c. AVERAGE Case nilai ekspektasi dari f(n)
Contoh 3 :
Menentukan lokasi suatu elemen pada array data secara linier
1. Set k:= 1 ; loc := 0
2. Repeat langkah 3 dan 4 While loc := 0 dan k n
3. If Item := Data(k) then set loc := k
4. Set k := k + 1
5. If loc := 0 then
Write Elemen tidak ada pada array data
Else Write loc adalah lokasi dari elemen
6. Exit
Bila elemen (item) yang dicari merupakan elemen terakhir dari array tersebut atau tidak
terdapat dalam array :
WORST CASE
F(n) = (n)
Logika & Algoritma Halaman 53 dari 99 halaman RAT
Bila elemen (item) yang dicari merupakan elemen pertama dari array tersebut :
BEST CASE
F(n) = (1)
Bila elemen (item) yang dicari berada diantara elemen pertama dan elemen terakhir
dari array tersebut :
AVERAGE CASE
Banyaknya elemen dalam array tersebut adalah n, maka probabilitas masing-masing
elemen adalah 1/n
F(n) = 1 . 1/n + 2 . 1/n + 3 . 1/n + . . . + n . 1/n
= ( 1 + 2 + 3 + . . . + n ) . 1/n
= (n + 1) . n/2 . 1/n
= (n + 1)/2
= 1/2 n + 1/2
= (n)
Logika & Algoritma Halaman 54 dari 99 halaman RAT
Pertemuan ke-8
Teknik Iteratif & Rekursif
Teknik Iteratif
Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan
procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi
Contoh :
Teknik Iteratif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n,
adalah sebagai berikut :
Function FAK (n : integer) : integer
FAK=1
For i = 1 TO n
FAK = FAK * i
NEXT i
END FAK
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
FAK=1, kemudian
i FAK
1 1 * 1 = 1
2 1 * 2 = 2
3 2 * 3 = 6
4 6 * 4 = 24
5 24 * 5 = 120
Contoh :
BARISAN BILANGAN FIBBONACI
Logika & Algoritma Halaman 55 dari 99 halaman RAT
1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Iteratif pada algoritma untuk menentukan suku ke-n dari barisan bilangan
Fibbonaci, adalah sebagai berikut :
1. Set x, y, n, i, f : integer
2. x 1 ; y 1
3. If n 2 then
begin
4. for i 3 to n do
begin
5. F x + y
6. x y
7. y F
end
else
8. F x
9. Write(F)
End
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
x=1, y=1, kemudian
i F x y
3 1 + 1 = 2 1 2
4 1 + 2 = 3 2 3
5 2 + 3 = 5 3 5
Teknik Rekursif
Logika & Algoritma Halaman 56 dari 99 halaman RAT
Teknik Rekursif merupakan salah satu cara pembuatan algoritma dengan pemanggilan
procedure atau function yang sama
Contoh :
Teknik Rekursif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n,
adalah sebagai berikut :
Function FAK (n : integer) : integer
1. If n := 0 then FAK := 1
2. Else FAK := n * FAK(n-1)
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
FAK(5) = 5 * FAK(4)
FAK(4) = 4 * FAK(3)
FAK(3) = 3 * FAK(2)
FAK(2) = 2 * FAK(1)
FAK(1) = 1 * FAK(0)
1
Contoh :
BARISAN BILANGAN FIBBONACI
Logika & Algoritma Halaman 57 dari 99 halaman RAT
1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan
Fibbonaci, adalah sebagai berikut :
Procedure F(n : integer) : integer
1. If n 2 then F(n) = 1
else F(n) = F(n-1) + F(n-2)
Endif
End
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
F(2)
F(3)
F(4)
F(5)
F(1)
F(1)
F(2)
F(3)
F(2)
1
1
1
11
PERBEDAAN ANTARA TEKNIK ITERATIF DAN REKURSIF :
Logika & Algoritma Halaman 58 dari 99 halaman RAT
ITERATIF REKURSIF
Tidak ada variabel lokal baru Ada variabel lokal baru
Program tidak sederhana Program menjadi lebih sederhana
Permainan Menara Hanoi
Contoh paling umum dari penggunaan teknik rekursif adalah pada permainan menara
Hanoi. Berdasarkan legenda, pertama kali dimainkan secara manual oleh seorang
pendeta Budha di Hanoi, sehingga permainan ini disebut Menara Hanoi. Dalam
permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satu
tonggak ke tonggak lainnya, dengan diperbolehkan menggunakan (melewati) sebuah
tonggak bantuan. Aturan permainannya adalah semua piringan pada tonggak A akan
dipindahkan ke tonggak C (dapat dengan melewati tonggak bantuan B), dengan
ketentuan bahwa pemindahan piringan dilakukan satu per satu dan piringan yang lebih
besar tidak boleh diletakan di atas piringan yang lebih kecil. Untuk jelasnya lihat gambar
berikut :
Menurut legenda tersebut dikatakan bahwa jika anda selesai memindahkan seluruh 64
piringan, pada saat itu juga dunia kiamat. Ini menurut legenda, yang mungkin juga
benar. Secara umum, untuk menyelesaikan n buah piringan diperlukan pemindahan
Tonggak Asal (A) Tonggak Bantu (B) Tonggak Tujuan (C)
Logika & Algoritma Halaman 59 dari 99 halaman RAT
sebanyak 2n –1 kali. Bayangkan jika untuk setiap pemindahan memerlukan waktu 1
detik, maka berapa waktu yang diperlukan untuk menyelesaikan 64 buah piringan.
Logika & Algoritma Halaman 60 dari 99 halaman RAT
Pertemuan ke-9
Teknik Backtracking
Teknik Backtracking merupakan salah satu teknik dalam penyelesaian masalah secara
umum (General Problem Solving). Adapun dasar dari teknik ini adalah suatu teknik
pencarian (Teknik Searching). Teknik pencarian ini digunakan dalam rangka
mendapatkan himpunan penyelesaian yang mungkin. Dari himpunan penyelesaian
yang mungkin ini akan diperoleh solusi optimal atau memuaskan.
Teknik Backtracking ini diperkenalkan pertama kali oleh : D.H. Lehmer (1950),
Penulisan algoritmanya oleh : R.J. Walker (1960), dan
Variasi aplikasinya dikembangkan oleh : Golomb & Baumert (1960)
Berikut ini disajikan algoritma backtracking secara umum, yang menggunakan teknik
iteratif :
PROCEDURE BACKTRACK(n)
INTEGER k,n; LOCAL x(1:n)
k 1
WHILE k > 0 DO
IF ada x(k) yang belum dicoba sedemikian sehingga
x(k) T(x(1), … , x(k-1)) AND Bk(x(1), … , x(k)) = TRUE
THEN
IF (x(1), … , x(k)) adalah sebuah jalur (path) yang merupakan solusi
THEN PRINT (x(1), … , x(k)) ENDIF
k k + 1
ELSE k k – 1
ENDIF
REPEAT
Logika & Algoritma Halaman 61 dari 99 halaman RAT
END BACKTRACK
Sedangkan bentuk rekursifnya adalah sebagai berikut :
PROCEDURE RBACKTRACK(k)
GLOBAL n, x(1:n)
FOR setiap x(k) sedemikian sehingga
x(k) T(x(1), … , x(k-1)) AND Bk(x(1), … , x(k)) = TRUE
IF (x(1), … , x(k)) adalah sebuah jalur (path) yang merupakan solusi
THEN PRINT (x(1), … , x(k)) ENDIF
CALL RBACKTRACK(k + 1)
END RBACKTRACK
Contoh Pemakaian Teknik Backtracking :
The 8 - Queens Problem
The 4 - Queens Problem
Sum of Subsets
Graph Coloring
Hamilton Cycles
Knapsack Problem
Tic - Tac - Toe Game
The Travelling Salesman Problem
Sum of Subsets
Masalah utama dari Sum of Subsets adalah jika terdapat n bilangan real dan ingin
dihitung semua kombinasi yang mungkin dari himpunan bilangan tersebut. Kombinasi
yang diinginkan yaitu kombinasi yang jumlah seluruh elemennya sama dengan M
(tertentu).
Logika & Algoritma Halaman 62 dari 99 halaman RAT
Sebelum kita selesaikan masalah tersebut dengan menggunakan teknik backtracking,
perhatikan terlebih dahulu penyajian permasalahan dan penyelesaiannya dalam bentuk
pohon.
Misalkan banyaknya bilangan real tersebut adalah 4 (n=4). Terdapat 2 jenis pohon
pencarian, yakni Breadth First Search (BFS) yang menggunakan queue dan Depth First
Search (DFS) yang menggunakan stack. Berikut penggambaran kedua jenis pohon
tersebut.
1
2 3 4 5
6 7 8 11
12 13 14 15
16
9 10
Breadth First Search (BFS)
Logika & Algoritma Halaman 63 dari 99 halaman RAT
Kedua bentuk penyajian pohon dari persoalan sum of subsets, merupakan tahapan
pertama dalam proses mendapatkan solusi sesungguhnya (solusi optimal). Untuk
mendapatkan solusi yang optimal dari ruang penyelesaian digunakan suatu algoritma
lain. Algoritma tersebut menggunakan teknik backtracking, yang selanjutnya disebut
dengan algoritma SUMOFSUB.
PROCEDURE SUMOFSUB(s,k,r)
GLOBAL INTEGER M,n
GLOBAL REAL W(1:n)
GLOBAL BOOLEAN X(1:n)
REAL r,s; INTEGER k,j
X(k) = 1
IF s + W(k) = M THEN PRINT (X(j), j 1 TO k)
ELSE
IF s + W(k) + W(k+1) M THEN
2 3
18 19
6 7
8
21 12 13 20 26
30 9 10
Depth First Search (DFS)
1
31 24
4 5
28 16 17 11 29 22 25
27
23 14 15
Logika & Algoritma Halaman 64 dari 99 halaman RAT
CALL SUMOFSUB(s+W(k), k+1, r-W(k))
ENDIF
ENDIF
IF s + r - W(k) M AND s + W(k) M THEN
X(k) 0
CALL SUMOFSUB(s, k+1, r-W(k))
ENDIF
END SUMOFSUB
Contoh :
Suatu himpunan terdiri dari 6 bilangan, yakni {5, 10, 12, 13, 15, 18} yang disusun
secara tidak turun. Akan ditentukan himpunan-himpunan bagiannya, yang jumlah
seluruh elemennya adalah 30.
15,3,58 5,3,58 10,3,58 0,3,58
0,4,46 12,4,46 10,4,46 5,4,46 17,4,46 15,4,46 27,4,46
0,5,33 13,5,33 12,5,33 10,5,33 5,5,33 15,5,33
0,1,73
20,6,18
5,2,68 0,2,68
12,6,18 13,6,18 A
C
B
Bagian dari state space tree dengan SUMOFSUB
Logika & Algoritma Halaman 65 dari 99 halaman RAT
Perhatikan simpul A, B dan C yang merupakan outputnya dalam bentuk tuple
(1,1,0,0,1), (1,0,1,1) dan (0,0,1,0,0,1).
Logika & Algoritma Halaman 66 dari 99 halaman RAT
Pertemuan ke-10
Metode Devide And Conquer (DANDC) - Searching
Di dalam metode ini, kita mempunyai suatu fungsi untuk menghitung input. Kemudian n
input tersebut dipartisi menjadi k subset input yang berbeda (1< k n) k subproblem
k subproblem k subsolusi solusi
Bentuk Umum dari Proses Metode DANDC :
Jika subproblem masih relatif cukup besar, maka metode DANDC dapat digunakan lagi
untuk keadaan tersebut. Pemakaian ulang DANDC dinyatakan dengan teknik rekursif.
Pemecahan menjadi k subproblem ini menunjukkan bahwa ia mempunyai sifat yang
sama dengan problem aslinya (awalnya).
Algoritmanya secara umum :
n input
Subsolusi 1
Subproblem 1
Input 1
Solusi Optimal
Subsolusi 2
Subproblem 2
Input 2
Subsolusi 3
Subproblem 3
Input 3
Subsolusi k
Subproblem k
Input k . . .
. . .
. . .
Logika & Algoritma Halaman 67 dari 99 halaman RAT
PROCEDURE DANDC(p,q)
GLOBAL n,A(1:n); INTEGER m.p.q
IF SMALL(p,q) THEN G(p,q)
ELSE
M DIVIDE(p,q)
COMBINE(DANDC(p,m),DANDC(m+1,q))
ENDIF
END DANDC
SMALL(p,q) adlah fungsi yang bernilai boole yang menentukan apakah input q-p+1
berukuran cukup kecil solusi dapat dihitung tanpa pemecahan. Jika demikian halnya,
maka fungsi G(p,q) yang dipanggil.
Pada keadaan lain fungsi DIVIDE(p,q) yang dipanggil.
Fungsi DIVIDE(p,q) menghasilkan integer yang menguraikan input menjadi 2 bagian.
Misal m = DIVIDE(p,q), maka input dipecah A(p:m) dan A(m+1,q)
Metode DANDC biasa dipakai pada searching dan sorting.
Searching
Menentukan Bilangan Max dan Min
Sebelum kita lihat penggunaan metode DANDC-nya, maka kita lihat terlebih dahulu
algoritmanya secara iteratif sebagai berikut :
PROCEDURE STRAITMAXMIN
INTEGER i,n
max min A(1)
For i 2 TO n DO
IF A(i) > max THEN max A(i) ………bagian perbandingan
ELSE IF A(i) < min THEN min A(i) ………bagian perbandingan
Logika & Algoritma Halaman 68 dari 99 halaman RAT
ENDIF
ENDIF
REPEAT
END STRAITMAXMIN
Procedure STRAITMAXMIN tersebut akan menghasilkan 3 keadaan, yakni:
1. Best Case, bila datanya tersusun menaik, dengan banyak perbandingan adalah n-1
2. Worst Case, bila datanya tersusun menurun, dengan banyak perbandingan adalah
2(n-1)
3. Average Case, bila datanya tidak tersusun menaik ataupun menurun, dengan
banyak perbandingan adalah 3(n-1)/2
Bila pada procedure STRAITMAXMIN tersebut, bagian perbandingannya diubah
menjadi :
IF A(i) > max THEN max A(i) ENDIF
IF A(i) < min THEN min A(i) ENDIF
Maka Best Case = Worst Case = Average Case = 2(n-1)
Algoritmanya secara rekursif (dengan metode DANDC)
PROCEDURE MAXMIN(i,j,fmax,fmin)
INTEGER i,j; GLOBAL n,A(1:n)
CASE
: i=j ; fmax fmin A(i)
: i=j-1 ; IF A(i) < A(j) THEN fmax A(j); fmin A(i)
ELSE fmax A(i); fmin A(j)
ENDIF
: ELSE
mid (i+j)/2
CALL MAXMIN(i,mid,gmax,gmin)
CALL MAXMIN(mid+1,j,hmax,hmin)
Logika & Algoritma Halaman 69 dari 99 halaman RAT
fmax MAX(gmax,hmax)
fmin MIN(gmin,hmin)
ENDCASE
END MAXMIN
Contoh :
A = { 22, 13, -5, -8, 15, 60, 17, 31, 47 }
Maka simulasi dari procedure MAXMIN tersebut adalah :
Jadi outputnya adalah max = 60 dan min = -8
Jumlah perbandingan elemennya, yang direpresentasikan oleh T(n) adalah :
T( n/2 ) +T( n/2 ) + 2 ; n > 2
T(n) { 1 ; n = 2
7
1 9 60 -8
6 9 60 17 1 5 22 -8
8 9 47 31 6 7 60 17 4 5 15 -8 1 3 22 -5
3 3 -5 -5 1 2 22 13
2
9
5 8
3 6 4
1
Logika & Algoritma Halaman 70 dari 99 halaman RAT
0 ; n = 1
untuk n power value dari 2 = 2k dan k integer positif, maka :
T(n) = 2 T(n/2) + 2
= 2 (2 T(n/4) + 2) + 2
= 4 T(n/4) + 4 + 2 = 22 T(n/22) + 22 + 2
= 23 T(n/23) + 23 + 22 + 2
.
.
.
= 2k-1 T(2) + 2k-1 + 2k-2 + … + 23 + 22 + 2
= 2k-1 +2k - 2
= 3n/2 - 2
Jadi T(n) = (n)
Logika & Algoritma Halaman 71 dari 99 halaman RAT
Pertemuan ke-11
Metode Devide And Conquer (DANDC) - Sorting
Sorting
Untuk mengurutkan barisan n input elemen yang ditempatkan dalam suatu array.
Urutan yang diinginkan adalah urutan yang tidak turun (non decreasing).
Contoh barisan dengan urutan :
1. Menaik : 5, 8, 10, 12, 15, 16
2. Menurun : 20, 17, 15, 14, 12, 10
3. Tidak turun : 5, 9, 10, 12, 12, 15, 16
4. Tidak naik : 16, 15, 15, 12, 10, 8
Dari Metode Sorting yang ada, akan dibahas metode merge sort dan quick sort.
Merge Sort
Algoritma dari Merge Sort terdiri dari dua prosedur, yakni prosedur MERGESORT dan
prosedur MERGE. Kedua prosedur tersebut tidak dapat dipisahkan satu dengan yang
lainnya (terintegrasi).
PROCEDURE MERGESORT(low,high)
INTEGER low,high
IF low < high THEN
mid (low + high) / 2
CALL MERGESORT(low,mid)
CALL MERGESORT(mid+1,high)
CALL MERGE(low,mid,high)
ENDIF
END MERGESORT
Logika & Algoritma Halaman 72 dari 99 halaman RAT
PROCEDURE MERGE(low,mid,high)
INTEGER h,I,j,k,low,mid,high
GLOBAL A(low:high); LOCAL B(low:high)
h low; j mid + 1; i low
WHILE h mid AND j high DO
IF A(h) A(j) THEN B(i) A(h); h h+1
ELSE B(i) A(j); j j+1
ENDIF
i i+1
REPEAT
IF h > mid THEN FOR k j TO high DO
B(i) A(k); i i+1
REPEAT
ELSE FOR k h TO mid DO
B(i) A(k); i i+1
REPEAT
ENDIF
FOR k low TO high DO
B(k) A(k)
REPEAT
END MERGE
Contoh :
A(1:10) yakni :
A = { 310, 285, 179, 652, 351, 423, 861, 254, 450, 520 }
Logika & Algoritma Halaman 73 dari 99 halaman RAT
Representasi di dalam tree dari CALL MERGESORT sbb :
Representasi di dalam tree dari CALL MERGE sbb :
T(n) = (n 2log n)
1,10
10,10
1,3
9,9 8,8 6,7 5,5 4,4 3,3 1,2
2,2 1,1
6,8 4,5 9,10
7,7 6,6
1,5 6,10
1,1,2
1,2,3 4,4,5
1,3,5
6,7,8 9,9,10
6,6,7
6,8,10
1,5,10
Logika & Algoritma Halaman 74 dari 99 halaman RAT
Quick Sort
Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTITION dan prosedur
QUICKSORT.
PROCEDURE QUICKSORT(p,q)
IF p < q THEN
j q+1
CALL PARTITION(p,j)
CALL QUICKSORT(p,j-1)
CALL QUICKSORT(j+1,q)
ENDIF
END QUICKSORT
PROCEDURE PARTITION(m,p)
INTEGER m,p,i; GLOBAL A(m-1,p)
V A(m); i m
LOOP
LOOP i i+1 UNTIL A(i) V REPEAT
LOOP p p-1 UNTIL A(p) V REPEAT
IF i < p THEN CALL INTERCHANGE(A(i),A(p))
ELSE EXIT
REPEAT
A(m) A(p); A(p) V
END PARTITION
Contoh :
Suatu array A berisi elemen-elemen :
65 70 75 80 85 60 55 50 45
1 2 3 4 5 6 7 8 9
Logika & Algoritma Halaman 75 dari 99 halaman RAT
Hasil tracenya adalah sebagai berikut :
i p 1 2 3 4 5 6 7 8 9 10
65 70 75 80 85 60 55 50 45 +
2 9 65 45 75 80 85 60 55 50 70 +
3 8 65 45 50 80 85 60 55 75 70 +
4 7 65 45 50 55 85 60 80 75 70 +
5 6 65 45 50 55 60 85 80 75 70 +
6 5 60 45 50 55 65 85 80 75 70 +
5 4 55 45 50 60 65 85 80 75 70 +
4 3 50 45 55 60 65 85 80 75 70 +
3 2 45 50 55 60 65 85 80 75 70 +
10 9 55 45 50 60 65 70 80 75 85 +
9 8 50 45 55 60 65 70 75 80 85 +
8 7 45 50 55 60 65 70 75 80 85 +
Analisisnya :
Worst Case = (n2)
Average Case = (n log n)
Logika & Algoritma Halaman 76 dari 99 halaman RAT
Pertemuan ke-12
Metode Greedy
Masalah Knapsack
Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat
maksimum M dan sehimpunan benda A = {a0,a1,...,an-1} yang berbobot W =
{w0,w1,...,wn-1}. Setiap benda tersebut diberikan nilai profit yang dinotasikan dengan P
= {p0,p1,...,pn-1}. Jika kita diperbolehkan memasukkan zi bagian dari benda ai yang
ada ke dalam knapsack dimana 0 zi 1 , maka kita dapatkan profit sebesar zi pi
untuk benda ai tersebut.
Yang dimaksud dengan masalah knapsack adalah :
Bagaimana kita memilih atau menentukan zi untuk masing-masing benda ai dari
keadaan di atas dengan tujuan mendapatkan total profit yang maksimal, dan
dengan kendala bahwa total bobot dari benda-benda yang dimasukkan ke dalam
knapsack tidak melebihi M.
Secara matematis, masalah knapsack tersebut dapat ditulis sebagai berikut :
maksimumkan Q z pi i
i=0
n-1
dengan kendala zi
i
n
i w W
0
1
dan 0 zi 1 , pi 0 , wi 0 , 0 i n-1
Sebuah solusi yang optimal adalah himpunan Z = {z0,z1,...,zn-1} yang memaksimalkan
nilai Q dan memenuhi kendala-kendala yang ada.
Logika & Algoritma Halaman 77 dari 99 halaman RAT
Contoh :
Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat
maksimum 15 Kg dan sehimpunan benda A = {a0,a1,a2,a3} yang berbobot
(dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P =
{100,135,26,20}. Jika kita diperbolehkan memasukkan zi bagian dari benda ai
yang ada ke dalam knapsack dimana 0 zi 1 , maka tentukanlah Z =
{z0,z1,z2,z3} agar diperoleh total profit yang maksimal !
Algoritma Sekuensial Knapsack Metode Greedy
Salah satu cara untuk menyelesaikan masalah knapsack secara sekuensial
adalah dengan pemakaian metode Greedy. Procedure tersebut disebut procedure
GREEDY_KNAPSACK.
Sebelum procedure tersebut digunakan, benda-benda harus diurutkan rasio pi/wi -nya
tidak menaik. Dengan kata lain :
p0/ w0 p1 / w1 ... pn-1 / wn-1
Adapun procedure GREEDY_KNAPSACK adalah sebagai berikut :
procedure GREEDY_KNAPSACK(P,W,M,Z,n)
real P(0:n-1),W(0:n-1),Z(0:n-1),cu; {n = banyak benda}
integer i,n;
Z 0 { Z(0), Z(1), . . . , Z(n-1) = 0}
cu M
for i 0 to n-1 do
if W(i) cu then exit endif
Z(i) 1
cu cu - W(i)
repeat
if i n-1 then Z(i) cu/W(i) endif
end GREEDY_KNAPSACK
Logika & Algoritma Halaman 78 dari 99 halaman RAT
Jika algoritma ini digunakan untuk menyelesaikan masalah seperti pada contoh yang
lalu, dimana n = 4; M = 15; W = { 5,9,2,4 }; P = { 100,135,26,20 }, maka akan terlihat
hasil tracenya sebagai berikut :
Z 0
cu 15
i = 0
karena W(0) cu yaitu : 5 15 berarti : Z(0) 1
cu 15 - 5 = 10
i = 1
karena W(1) cu yaitu : 9 10 berarti : Z(1) 1
cu 10 - 9 = 1
i = 2
karena W(2) cu yaitu : 2 1 berarti : keluar dari loop (exit)
Karena 2 3 maka Z(2) cu/W(2) = 1/2 = 0,5
Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }
Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20
= 100 + 135 + 13 + 0
= 248
Analisis :
Kompleksitas waktu dari algoritma Greedy_Knapsack ini adalah O(n). Tetapi jika
data yang digunakan belum terurut rasio pi/wi -nya tidak menaik, maka
diperlukan kompleksitas waktu sebesar O(n log n) untuk mengurutkan
sebelumnya. Sehingga untuk masalah optimisasi knapsack, kompleksitas waktu
dari algoritma ini akan lebih besar pada waktu proses pengurutannya.
Logika & Algoritma Halaman 79 dari 99 halaman RAT
Latihan :
Diketahui 3 buah benda dan sebuah knapsack dengan kapasitas maksimum 20. Berat
dan profit dari masing-masing benda tersebut adalah (18, 15, 10) dan (25, 24, 15).
Tentukanlah Z agar diperoleh total profit yang maksimal !
Jawab :
Pertama, kita periksa apakah rasio pi/wi -nya tidak menaik.
p0/w0 = 25/18
p1/w1 = 24/15
p2/w2 = 15/10
Terlihat bahwa syarat rasio pi/wi -nya tidak menaik belum terpenuhi. Jadi
susunan (urutan) -nya untuk sementara kita ubah, agar syarat rasio pi/wi -nya
tidak menaik terpenuhi dan kita dapat menyelesaikan masalah tersebut
dengan procedure GREEDY_KNAPSACK.
Untuk itu, kita ubah sementara urutan benda-bendanya (setelah diperoleh
jawaban sementara, kita kembalikan urutan ke susunan semula). Perubahan
yang kita lakukan adalah sebagai berikut :
urutan ke-
(yang lama)
urutan ke-
(yang baru)
0 2
1 0
2 1
sehingga syaratnya terpenuhi ;
24/15 15/10 25/18 rasio pi/wi -nya tidak menaik
Logika & Algoritma Halaman 80 dari 99 halaman RAT
Sekarang kita sudah dapat menggunakan procedure GREEDY_KNAPSACK
untuk menyelesaikan masalah tersebut. Adapun hasil trace-nya adalah sebagai
berikut :
Z 0
cu 20
i = 0
karena W(0) cu yaitu : 15 20 berarti : Z(0) 1
cu 20 - 15 = 5
i = 1
karena W(2) cu yaitu : 10 5 berarti : keluar dari loop (exit)
Karena 1 2 maka Z(1) cu/W(1) = 5/10 = 0,5
Jadi diperoleh : Z(0) = 1 ; Z(1) = 0,5 ; Z(2) = 0
Sekarang urutannya kita kembalikan seperti semula, yakni :
urutan ke-
(yang saat ini)
urutan ke-
(yang
semula)
Z(i)
2 0 0
0 1 1
1 2 0,5
Jadi optimisasi masalah knapsack diperoleh bila Z = { 0; 1; 0,5 }
Sehingga Q = 0 x 25 + 1 x 24 + 0,5 x 15
= 0 + 24 + 7,5
= 31,5
Logika & Algoritma Halaman 81 dari 99 halaman RAT
Pertemuan ke-13
Metode Greedy (Lanjutan)
Masalah Pohon Rentangan Minimal
Permasalahan umum dari pohon rentangan minimal adalah mencari minimum biaya
(cost) pohon rentangan dari setiap ruas suatu graf yang membentuk pohon.
Setiap graf tidak dapat ditentukan pohon rentangan minimalnya. Adapun graf yang
dapat kita tentukan pohon rentangan minimalnya adalah graf yang memenuhi ketiga
syarat berikut :
1. graf tersebut harus terhubung
2. setiap ruas dari graf tersebut harus mempunyai nilai atau bobot (graf
berlabel)
3. graf teresbut tidak berarah
Algoritma yang dapat digunakan untuk menyelesaikan masalah pohon rentangan
minimal cukup banyak. Dalam pembahasan ini, algoritma yang akan dipakai adalah
algoritma PRIM’S.
Berikut ini akan disajikan langkah-langkah penyelesaian masalah pohon rentangan
minimal dengan menggunakan algoritma PRIM’S.
PROCEDURE PRIM(E,COST,n,T,mincost)
REAL COST(n,n),mincost
INTEGER NEAR(n),n,i,j,k,l,T(1:n-1,2)
(k,l) ruas dengan biaya atau bobot yang minimum
mincost COST(k,l)
(T(1,1),T(1,2)) (k,l)
FOR i 1 TO n DO
IF COST (i,l) < COST(i,k) THEN NEAR (i) l
Logika & Algoritma Halaman 82 dari 99 halaman RAT
ELSE NEAR(i) k ENDIF
REPEAT i
NEAR(k) NEAR(l) 0
FOR i 2 TO n-1 DO
Pilih j (sebuah index) sedemikian sehingga NEAR(j) 0 AND COST(j,NEAR(j)) adalah
minimum
(T(i,1),T(i,2)) (j,NEAR(j))
mincost mincost + COST(j,NEAR(j))
NEAR(j) 0
FOR k 1 TO n DO
IF NEAR(k) 0 AND COST(k,NEAR(k)) > COST(k,j)
THEN NEAR(k) j
ENDIF
REPEAT k
REPEAT i
IF mincost ~ THEN PRINT ‘bukan pohon rentangan’ ENDIF
END PRIM
Contoh :
Perhatikan graf berikut ini :
Tentukanlah nilai pohon rentangan minimalnya, serta pohon yang membentuk pohon
rentangan minimal tersebut.
1
6
3
4 5
2 10
25
45
20
40 35
55
30
15
50
Logika & Algoritma Halaman 83 dari 99 halaman RAT
Penyelesaian :
Dengan menggunakan algoritma PRIM’S, prosesnya adalah sebagai berikut :
(k,l) (1,2)
mincost COST(1,2) = 10
(T(1,1),T(1,2)) (1,2)
i=1
COST (1,2) < COST(1,1) … ?
10 < ~ … TRUE : NEAR (1) 2
i=2
COST (2,2) < COST(2,1) … ?
~ < 10 … FALSE : NEAR (2) 1
i=3
COST (3,2) < COST(3,1) … ?
50 < ~ … TRUE : NEAR (3) 2
i=4
COST (4,2) < COST(4,1) … ?
~ < 30 … FALSE : NEAR (4) 1
i=5
COST (5,2) < COST(5,1) … ?
40 < 45 … TRUE : NEAR (5) 2
i=6
COST (6,2) < COST(6,1) … ?
25 < ~ … TRUE : NEAR (6) 2
NEAR(1) NEAR(2) 0
i = 2
Pilih j = 6 karena NEAR(6) 0 dan COST(6,NEAR(6)) adalah minimum
(T(2,1),T(2,2)) (6,2)
mincost 10 + COST(6,2) = 10 + 25 = 35
Logika & Algoritma Halaman 84 dari 99 halaman RAT
NEAR(6) 0
k = 1
NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,6) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 2
NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,6) … ?
0 0 dan ~ > 25 … FALSE dan TRUE FALSE
k = 3
NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,6) … ?
2 0 dan 50 > 15 … TRUE dan TRUE TRUE : NEAR(3) = 6
k = 4
NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,6) … ?
1 0 dan 30 > 20 … TRUE dan TRUE TRUE : NEAR(4) = 6
k = 5
NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,6) … ?
2 0 dan 40 > 55 … TRUE dan FALSE FALSE
k = 6
NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,6) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
i = 3
Pilih j = 3 karena NEAR(3) 0 dan COST(3,NEAR(3)) adalah minimum
(T(3,1),T(3,2)) (3,6)
mincost 35 + COST(3,6) = 35 + 15 = 50
NEAR(3) 0
k = 1
NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,3) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 2
NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,3) … ?
Logika & Algoritma Halaman 85 dari 99 halaman RAT
0 0 dan ~ > 50 … FALSE dan TRUE FALSE
k = 3
NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,3) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 4
NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,3) … ?
6 0 dan 20 > ~ … TRUE dan FALSE FALSE
k = 5
NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,3) … ?
2 0 dan 40 > 35 … TRUE dan TRUE TRUE : NEAR(5) = 3
k = 6
NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,3) … ?
0 0 dan ~ > 15 … FALSE dan TRUE FALSE
i = 4
Pilih j = 4 karena NEAR(4) 0 dan COST(4,NEAR(4)) adalah minimum
(T(4,1),T(4,2)) (4,6)
mincost 50 + COST(4,6) = 50 + 20 = 70
NEAR(4) 0
k = 1
NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,4) … ?
0 0 dan ~ > 30 … FALSE dan TRUE FALSE
k = 2
NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,4) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 3
NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,4) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 4
NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,4) … ?
Logika & Algoritma Halaman 86 dari 99 halaman RAT
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 5
NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,4) … ?
3 0 dan 35 > ~ … TRUE dan FALSE FALSE
k = 6
NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,4) … ?
0 0 dan ~ > 20 … FALSE dan TRUE FALSE
i = 5
Pilih j = 5 karena NEAR(5) 0 dan COST(5,NEAR(5)) adalah minimum
(T(5,1),T(5,2)) (5,3)
mincost 70 + COST(5,3) = 70 + 35 = 105
NEAR(5) 0
k = 1
NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,5) … ?
0 0 dan ~ > 45 … FALSE dan TRUE FALSE
k = 2
NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,5) … ?
0 0 dan ~ > 40 … FALSE dan TRUE FALSE
k = 3
NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,5) … ?
0 0 dan ~ > 35 … FALSE dan TRUE FALSE
k = 4
NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,5) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 5
NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,5) … ?
0 0 dan ~ > ~ … FALSE dan FALSE FALSE
k = 6
NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,5) … ?
Logika & Algoritma Halaman 87 dari 99 halaman RAT
0 0 dan ~ > 55 … FALSE dan TRUE FALSE
mincost ~ … ?
105 ~ … FALSE
terdapat sebuah pohon rentangan, yang mempunyai nilai minimal = 105
Berikut adalah bentuk pohon rentangan minimalnya :
1
6
3
4 5
2 10
25
20
35
15
Logika & Algoritma Halaman 88 dari 99 halaman RAT
Pertemuan ke-14
Pemrograman Dinamis
Metode Umum
Pemrograman Dinamis adalah metode rancangan algoritma yang dapat dipakai bila
pemecahan masalah yang mungkin dipandang sebagai hasil dari rangkaian keputusan-
keputusan.
Untuk beberapa masalah dari masalah-masalah ynag dapat dipandang dengan cara ini,
rangkaian optimal dari keputusan-keputusan mungkin dapat ditemukan dengan
membuat satu dari keputusan-keputusan pada satu waktu dan jangan pernah membuat
keputusan yang keliru.
Satu cara untuk memecahkan masalah-masalah yang mana ini tidak mungkin untuk
membuat sebuah rangkaian dari langkah-langkah keputusan yang dapat dilakukan
mengacu (mengarah) kepada rangkaian keputusan optimal adalah untuk mencoba
semua kemungkinan rangkaian-rangkaian keputusan.
Pemrograman Dinamis seringkali secara drastic (spontan) mengurangi jumlah
pembilangan dengan menghindari pembilangan dari beberapa rangkaian keputusan
yang tidak memungkinkan menjadi optimal.
Dalam merumuskan hubungan-hubungan kembali pemrograman dinamis yang harus
dipecahkan, seseorang dapat menggunakan 1 dari 2 pendekatan yang berbeda yaitu
forward atau backward.
Multistage Graf
Sebuah multistage graf adalah sebuah graf berarah dimana bentuk tersebut dibagi
dalam k 2 disjoint set V1.
Berikut ini adalah contoh sebuah graf 5 stage.
Logika & Algoritma Halaman 89 dari 99 halaman RAT
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
27
11
111
8
6
3
54
5
6
2
4
5
ts
V1
V4
V2
V3
V5
Algoritma untuk menyelesaikan masalah multistage graf, dengan pendekatan forward
adalah sebagi berikut :
Procedure FGRAPH(E,k,n,P)
1. real COST(n), integer D(n-1), P(k), r, j, k, n
2. COST(n) 0
3. for j n-1 to 1 by -1 do
4. let r be a vertex such that j , r E and c( j,r ) +
COST(r) is minimum
5. COST(j) c( j,r ) + COST(r)
6. D(j) r
7. repeat
8. P(1) 1 ; P(k) n
9. for j 2 to k-1 do
10. P(j) D(P(j-1))
11. repeat
12. end FGRAPH
Logika & Algoritma Halaman 90 dari 99 halaman RAT
Contoh Soal
Graf & Analisis Algoritma
1. Orang yang dikenal sebagai bapak dari lahirnya (awal) teori graf adalah :
A. Solin dan Kruskal
B. Hamilton
C. Welch-Powell
D. Leonhard Euler
2. Bila size dari suatu graf adalah n, maka jumlah derajat grafnya adalah :
A. 2n-1
B. 2 (n-1)
C. 2n
D. 2n+1
3. Pada pohon, simpul yang bukan merupakan akar dan berderajat simpul 1 adalah :
A. Cabang
B. Daun
C. Brother
D. Level
4. Suatu bentuk graf yang terbentuk karena penambahan sejumlah vertex baru
terhadap graf asal disebut :
A. Isomorfis
B. Isograf
C. Homomorfis
D. Isographic
5. Suatu tree yang mempunyai cabang / anak selalu 2 disebut :
A. Unary tree
B. Binary tree
C. Union tree
D. Threenary Tree
6. Graf yang tidak memiliki self loop atau ruas sejajar disebut :
A. multigraf
B. graf sederhana
C. graf null
D. graf lengkap
Graf & Analisis Algoritma Halaman 91 dari 99 halaman RAT
7. Algoritma Welch-Powell digunakan untuk mencari :
A. Minimal Spanning Tree
B. Aliran Maksimal
C. Bilangan Kromatik
D. Jalur Terpendek
8. Perjalanan (walk) yang semua simpul dalam barisan berbeda adalah
A. jalur (path)
B. lintasan ( trail)
C. sirkuit (cycle)
D. diameter
9. Graf regular adalah graf yang memiliki :
A. gelung atau self-loop
B. ruas sejajar
C. derajat setiap simpulnya berbeda
D. derajat setiap simpulnya sama
Untuk soal no. 10 s/d 16, gunakan graf di bawah ini :
10. Order dan Size dari graf G1 adalah :
A. 4 dan 12
B. 12 dan 16
C. 12 dan 17
D. 16 dan 12
11. Derajat dari graf G1 adalah :
A. 12
B. 24
C. 32
D. 34
J
G
L
I
A B
C
D
E
K
H F
Graf G1
Logika & Algoritma Halaman 92 dari 99 halaman
RAT
12. Bilangan Kromatik dari graf G1 adalah :
A. 2
B. 3
C. 4
D. 5
13. Pada pewarnaan graf G1, simpul yang boleh menggunakan warna yang sama adalah
:
A. A dan L
B. A dan B
C. C dan H
D. B dan H
14. Jarak antara simpul A dan G pada graf G1 adalah :
A. 2
B. 3
C. 4
D. 5
15. Graf G1 mempunyai diameter :
A. 2
B. 3
C. 4
D. 5
16. Yang merupakan jalur (path) dalam graf G1 adalah :
A. A,B,C,H,A
B. E,D,K,J,C,D
C. A,L,K,F
D. A,H,C,J,F
17. Graf G2 berikut ini, mempunyai region sebanyak :
H
E
F I
A D
C
B
G J
K
Graf G2
Logika & Algoritma Halaman 93 dari 99 halaman
RAT
A. 2
B. 3
C. 4
D. 5
18. Pembuatan jadwal kuliah pada suatu Perguruan Tinggi dapat diselesaikan dengan
membawanya ke masalah graf, yakni masalah :
A. jalur terpendek
B. minimal spanning tree
C. pewarnaan graf
D. travelling salesman
19. Matriks adjasensi suatu graf bersifat :
A. simetris
B. refleksif
C. transitif
D. antisimetris
20. Pada graf berarah, simpul yang mempunyai derajat kedalam = 0 disebut :
A. muara
B. sumber
C. terpencil
D. artikulasi
21. Pada graf berarah, simpul yang mempunyai derajat keluar = 0 disebut :
A. muara
B. sumber
C. terpencil
D. artikulasi
22. Formula Euler untuk graf planar; dimana V adalah banyaknya simpul, E banyaknya
ruas dan R banyaknya region, adalah :
A. V - R + E = 2
B. V - E + R = 2
C. V - E + 2 = R
D. V + E - R = -2
23. Yang bukan merupakan graf planar adalah :
A. graf kubus
B. graf segitiga
C. graf berbentuk pohon
D. graf lengkap dengan 5 simpul
(K5)
24. Manakah dari pernyataan berikut yang paling benar ?
Logika & Algoritma Halaman 94 dari 99 halaman
RAT
A. Graf Regular juga merupakan
Graf Lengkap
B. Graf Lengkap juga merupakan
Graf Regular
C. Graf Bipartisi juga merupakan
Graf Regular
D. Graf Regular juga merupakan
Graf Bipartisi
25. Bilangan Kromatik dari graf bipartisi adalah :
A. 2
B. 3
C. 4
D. 5
26. Suatu urutan dari barisan langkah-langkah guna menyelesaikan masalah disebut :
A. algoritma
B. semi algoritma
C. instruksi
D. semi instruksi
27. Suatu prosedur yang hanya akan berhenti jika menghasilkan penyelesaian yang
diharapkan disebut :
A. algoritma
B. semi algoritma
C. instruksi
D. semi instruksi
28. Diagram alur dari proses penyelesaian masalah, yang paling benar adalah :
A. masalah semi algoritma model program eksekusi hasil
B. masalah model algoritma program eksekusi hasil
C. masalah algoritma model program eksekusi hasil
D. masalah program algoritma model eksekusi hasil
29. Penilaian dari suatu algoritma pertama kali dilihat dari :
A. efisiensi
B. efektivitas
C. terstruktur
D. ada output
30. Yang bukan termasuk kriteria dari suatu algoritma yang terbaik adalah :
A. efisiensi
B. terstruktur
C. berakhir
D. prosesnya cepat
Logika & Algoritma Halaman 95 dari 99 halaman
RAT
31. Jika diketahui F(x) = 20 x7 + 12 x4 + 38 merupakan fungsi waktu tempuh, maka
A. F(x) = O(20 x7)
B. F(x) = 20 O(x7)
C. F(x) = O(x7 + x4)
D. F(x) = O(x7)
32. Bila terdapat 4 algoritma sorting (kita sebut algoritma A, B, C dan D), dimana
algoritma A memiliki kompleksitas O(n2), algoritma B memiliki kompleksitas O(n3),
algoritma C memiliki kompleksitas O(log n), dan algoritma D memiliki kompleksitas
O(n), maka algoritma manakah dari keempat algoritma tersebut yang lebih baik ?
A. algoritma A
B. algoritma B
C. algoritma C
D. algoritma D
33. Diberikan sebuah algoritma sebagai berikut :
Set A[i,j], B[i,j], C[i,j] real
untuk i 1 s/d n kerjakan
untuk j 1 s/d n kerjakan
C[i,j] A[i,j] + B[i,j]
akhir j
akhir i
Algoritma diatas merupakan algoritma untuk :
A. melakukan penjumlahan matriks
B. melakukan perkalian matriks
C. melakukan penjumlahan
D. melakukan perkalian
34. Algoritma pada soal nomor 33 mempunyai kompleksitas waktu :
A. O(n)
B. O(n2)
C. O(log n)
D. O(n3)
Graf & Analisis Algoritma Halaman 96 dari 99 halaman RAT
35. Diberikan sebuah algoritma sebagai berikut :
Function RAT (n : integer) : integer
If n := 1 then RAT := 1
Else RAT := n * RAT(n-1)
End Function
Algoritma di atas menggunakan teknik :
A. Backtracking
B. Rekursif
C. Greedy
D. Iteratif
36. Bila Algoritma pada soal nomor 35 berinput n = 5, maka outputnya adalah :
A. 120
B. 720
C. 7
D. 5040
37. Bila Algoritma pada soal nomor 35 berinput n = 5, maka pemanggilan ulang
function RAT adalah :
A. 1 kali
B. 4 kali
C. 5 kali
D. n kali
38. Algoritma pada soal nomor 35 mempunyai kompleksitas waktu :
A. O(n)
B. O(log n)
C. O(n2)
D. O(n3)
39. Diberikan sebuah algoritma sebagai berikut :
Set x, y, n, i, f : integer
x 1 ; y 1
If n 2 then
begin
for i 3 to n do
begin
Graf & Analisis Algoritma Halaman 97 dari 99 halaman RAT
F x + y
x y
y F
end
end
else
F x
Write(F)
End
Algoritma di atas menggunakan teknik :
A. Iteratif
B. DANDC
C. Greedy
D. Rekursif
40. Bila Algoritma pada soal nomor 39 berinput n = 13, maka outputnya adalah :
A. 55
B. 233
C. 89
D. 144
41. Algoritma pada soal nomor 39 mempunyai keadaan kompleksitas waktu :
A. keadaan terbaik keadaan
terburuk
B. keadaan terbaik = keadaan
terburuk
C. keadaan terbaik > keadaan
terburuk
D. keadaan terbaik < keadaan
terburuk
42. Dasar dari teknik algoritma Backtracking adalah :
A. searching
B. merging
C. divide and conquer
D. sorting
43. Pencarian ruang solusi dengan menggunakan stack disebut juga dengan istilah :
A. Depth First Search
B. Breadth First Search
C. Binary Search
D. Mergesort
Logika & Algoritma Halaman 98 dari 99 halaman
RAT
44. Pencarian ruang solusi dengan menggunakan queue disebut juga dengan istilah :
A. Depth First Search
B. Breadth First Search
C. Binary Search
D. Mergesort
45. Solusi yang diperoleh dengan cara Depth First Search berupa tupel yang :
A. berbeda secara teratur
B. seragam atau sama
C. sembarang
D. berbeda dan tidak teratur
46. Teknik Divide AND Conquer adalah teknik yang digunakan untuk merancang
sebuah algoritma dengan cara :
A. memecah n input menjadi 2 subset input
B. memecah n input sebanyak k input, k < n
C. memecah n input sebanyak 2 input
D. memecah n input menjadi k subset input, 1 < k n
47. Perhatikan procedure berikut ini :
PROCEDURE STRAITMAXMIN(A,n,max,min)
INTEGER i,n
max min A(1)
FOR i 2 TO n DO
IF A(i) > max THEN max A(i)
ELSE IF A(i) < min THEN min A(i) ENDIF
REPEAT
END STRAITMAXMIN
Pada procedure STRAITMAXMIN di atas, akan tercapai keadaan terbaik bila :
A. elemen A(1: n) disusun secara menaik
B. elemen A(1: n) disusun secara menurun
C. elemen A(1: n) disusun secara acak
D. elemen A(1: n) disusun secara tidak naik
Graf & Analisis Algoritma Halaman 99 dari 99 halaman RAT
48. Bila diketahui sebuah prosedur sebagai berikut :
PROCEDURE XXX(A,n)
solusi 0 ......{solusi awal}
FOR i 1 TO n DO
x SELECT(A)
IF FEASIBLE (solusi,x)
THEN solusi UNION(solusi,x)
ENDIF
REPEAT
RETURN (solusi)
END XXX
Algoritma di atas adalah algoritma secara umum dari :
A. Metode DANDC
B. Teknik BackTracking
C. Pemrograman Dinamis
D. Metode Greedy
49. Pada permainan menara HANOI, algoritma yang paling baik adalah digunakannya
teknik/metode :
A. Backtracking
B. Iteratif
C. Greedy
D. Rekursif
50. Pada permainan menara HANOI, bila banyaknya piringan adalah 5 buah, maka
banyaknya pemindahan adalah sebanyak :
A. 15 kali
B. 16 kali
C. 31 kali
D. 32 kali