Download - Resume Algoritma & Struktur Data
-
PENGANTAR ALGORITMA
A. PENGERTIAN ALGORITMA Algoritma adalah cara kerja komputasi yang baik, dimana memiliki nilai
input dan output. Algoritma digunakan untuk menyelesaikan masalah
komputasional yang mana hasil penyelesainnya ini dimengerti dan
sesuai dengan masalah yang disediakan. Gambaran algoritma dapat
dilihat dari ilustrasi dibawah ini :
B. Desain dan Analisis Algoritma
- Pseucodocode Kode yang digunakan dalam menerapkan suatu algoritma yang bisa
dijalankan oleh berbagai bahasa pemograman.
- Kompleksitas algoritma
Untuk mengetahui hal-hal yang dibutuhkan suatu algoritma, seperti
waktu komputasi dan kapasitas memory.
- Strategi algoritma
- Struktur data
Menyimpan data dan mengatur data untuk dimodifikasi.
- Masalah NP-lenkap
Hal ini akan muncul jika masalah yang ada tidak memiliki solusi
yang efisien
input output
masalah
Algoritma
-
C. Contoh Masalah Komputasional
Masalah pencarian data (searching problem) Kita akan menginput barisan n yang bilangan asli di dalam larik A,
dan sebuah bilangan yang dicari (key). Dan hasilnya key berada
dalam larik A, tetapi jika key tidak ditemukan dalam larik A makan
akan ditambahkan pada barisan terakhir sebagai unsur terakhir.
Algoritmanya :
1. Mengecek satu persatu dari setiap unsur yang terdapat dalam
larik A, apakah ada yang mirip dengan key.
2. Jika terdapat unsur yang mirip dengan key, maka pencarian
berhenti. Tetapi jika tidak ditemukan, maka key ditambahkan
sebagai unsur terakhir dalam larik A.
3. Algoritma berhenti dan kembalikan nilai indeksnya.
Pada algoritma ini, dibutuhkan perulangan (looping) dan
penyeleksian kondisi (selection condition).
Pseudocode algoritma
Linear-Search (A, key)
1. indeks 1 ;
2. ada False;
3. Mengecek key dalam A[1..length[A]]
4. While indeks length [A] and ada = False
5. If A[indeks] = key;
6. Then ada = True;
7. Indeks indeks + 1;
8. If ada = False
9. Then indeks length[A]+1;
10. Return indeks
-
Contohnya :
27 36 15 2 31
Key = 7
Solusinya :
1. Indeks = 1;
2. Ada False;
3. Mengecek key dalam A[1..length[A]]
4. While indeks length [5] and ada = false
5. If A [1] = 7
27 = 7
Indeks+1 = 1+1=2
If A [2] = 7
36 = 7
Indeks+1 = 2+1=3
If A [3] = 7
15 = 7
Indeks+1 = 3+1=4
If A [4] = 7
2 = 7
Indeks+1 = 4+1=5
If A [5] = 7
31 = 7
Then indeks length[[5]+1]
If A [6] = 7
7= 7
Return indeks
Proses diatas akan mengeluarkan output seperti ini :
27 36 15 2 31 7
Jika key yang ditentukan sama dengan salah satu unsur dalam larik A, maka proses hanya akan sampai pada langkah 5 dan kembali padproses awal.
A =
Salah, maka akan
dilanjutkan ke langkah berikutnya
Masih salah, lanjut!
Masih salah, lanjut!
Masih salah, lanjut!
Masih salah, lanjut!
Karena unsur yang disediakan sudah
habis sedangkan key belelum
ditemukan makan length (kotaknya)
ditambahkan. Seperti langkah 9. Key dijadikan unsur
terakhir..
-
Masalah Pengurutan Data (Sorting Problem)
Kita akan menginput barisan n bilangan (a1, a2,..,an), dan outputnya
adalah barisan bilangan yang sudah diurutkan (a1, a2,..,an), dimana
a1a2.an.
Algoritmanya:
1. Menscanning semua kartu.
2. Memilih satu kartu sebagai patokan untuk dijadikan perbandingan
dengan kartu lain.
3. Menukar kartu yang ter-scanning jika ternyata lebih kecil daripada
kartu yang dijadikan patokan tadi.
Pseudo codenya:
Insertion-Sort(A)
0 perulangan untuk patokan
1 for j 2 to length[A]
2 key A[j]
3 Sisip A[j] kedalam barisan terurut A[1.. j 1]
4 i j 1
5 while (i > 0 A[i] > key)
6 A[i + 1] A[i]
7 i i 1
8 A[i + 1] key
Contohnya : Urutkan data tersebut dari terkecil ke terbesar:
27 36 15 2
Solusinya : o For j = 2 , key = A[2] = 36 , i = j-1 = 1
While (1 > 0 27 > 36 ) Karena, salah satu persyaratan salah maka lanjut j = 3. Urutan sekarang : (masih seperti awal)
27 36 15 2
I > 0 , berfungsi untuk menghetikan
proses jika unsur telah habis
diseleksi.
A[i] > key, berfungsi untuk
membandingkan key dengan angka
sebelumnya.
(i > 0 A[i] > key) T F
-
o For j = 3, key = A[3] = 15 , i = j-1 = 2
While (1 > 0 36 > 15 ) A [i+1] = 36 urutan sekarang :
27 36 36 2
i = i-1= 2-1 = 1
While (1 > 0 27 > 15) A [i+1] = 27 urutan sekarang :
27 27 36 2
i = i-1= 1-1 = 0
While (0 > 0 . > 15) A[i] = key = 15 Karena, salah satu persyaratan salah maka lanjut j = 4. Urutan sekarang : (masih seperti awal)
15 27 36 2
o For j = 4, key = A[4] = 2 , i = 4-1 = 3
While (3 > 0 36 > 2 ) A [i+1] = 36 urutan sekarang :
15 27 36 36
i = i-1= 3-1 = 2
While (2 > 0 27 > 2) A [i+1] = 27
T
(i > 0 A[i] > key) T
36 bertukar posisi 15 pada A[3]
T T
27 bertukar posisi 15 pada A[2]
15 sebetulnya sudah berada
A[2], tapi nilainya < 36.
15 sebetulnya sudah berada
A[1], tapi nilainya < 27.
F
T
(i > 0 A[i] > key) T
36 bertukar posisi 2 pada A[4]
T T
27 bertukar posisi 2 pada A[3]
2 sebetulnya sudah berada
A[3], tapi nilainya < 36.
-
n
j jt
2
urutan sekarang :
15 27 27 36
i = i-1= 2-1 = 1
While (1 > 0 15 > 2) A [i+1] = 15 urutan sekarang :
15 15 27 36
i = i-1= 1-1 = 0
While (0 > 0 . > 2) A[i] = key = 2 Urutan akhir : ( karena j hanya sampai 5)
2 15 27 36
Analisis Algorima : Insertion-Sort(A)
1 for j 2 to length[A]
2 key A[j]
3 Sisip A[j] kedalam barisan terurut A[1.. j 1]
4 i j 1
5 while (i > 0 A[i] > key)
6 A[i + 1] A[i]
7 i i 1
8 A[i + 1] key
Total waktu dari algoritma ini (running time) :
2 sebetulnya sudah berada
A[2], tapi nilainya < 27.
F
T T
15 bertukar posisi 2 pada A[3]
2 sebetulnya sudah berada
A[1], tapi nilainya < 15.
cost times
c1 n
c2 n 1
0 n 1 c
4 n 1
c5
c
6
c
7
c
8 n 1
n
j jt
2)1(
n
j jt
2)1(
-
Urutan data yang diinput juga mempengaruhi waktu komputasi. Pada urutan yang diinpu terdapat dua kasus yaitu :
- Kasus terbaik (best case) yakni dimana data yang diiput sudah berurut, tj=1. Laju komputasi dalam fungsi linear.
- Kasus terburuk (worst case) akni dimana data yang diiput terurut terbalik, tj=j. laju komputasi dalam fungsi kuadratik.
)1()1()1()1()1()( 82
7
2
6
2
5421
nctctctcncncncnTn
j
j
n
j
j
n
j
j
)()(1)( 1321322
1 kknkkknkknTn
j
)()(2
)( 13212121
32
2
1 kknkknk
knkjknTn
j
-
PERANCANGAN ALGORITMA DAN STRUKTUR DATA
Masalah pencarian data (searching problem)
Kita menginput barisan n bilangan asli (a1, a2,..,an) dalam larik A dan akan terdapat sebuah key yang akan dicari. Maka outputnya adalah lokasi key dalam larik A atau jika tidak ditemukan maka akan ditambahkan sebagai unsur terakhir dalam larik A.
Pencarian Linier Linear-Search(A, key)
1 ada False
2 for i 1 to length[A]
3 if A[i] = key then
4 posisi i
5 ada True
6 if not(ada) then
7 posisi length[A] + 1
8 A[posisi] data
Jika unsur dalam larik A semuanya sama dengan key, maka hal ini akan menjadi kasus terburuknya.
Times
1
n + 1
n
1
s
s
n
i it
1
n
i it
1
)32(22)(1
stnnTn
i
i
34)32(22)(1
nstnnTn
i
i
-
Sebaliknya, akan terjadi kasus terbaik jika tidak ada sama seklai unsur dalam larik A sama dengan key.
Pencarian Biseksi Pencarian ini merupakan ide ilmiah dalam menyelesaikan masalah ini,
yaitu dengan cara membagi dua data. Sehingga pencarian dua kali lebih cepat. Kasus terburuk dan kasus terbaik dari cara ini akan mengalami pengurangan n, sehinggan waktu komputasionalis kasus terburuknya akan menjadi 7/2n+3 dan waktu komputasionalis kasus terbaiknya menjadi 3/2n+5.
Binary Search Tree (BST) Sebuah pohon yang digunakan dalam prosedur penyimpana dalam
berbagai bentuk sehingga operasi algoritma menjadi lebih optimal. Susunan data dalam BST itu adalah bagian kiri pohon lebih kecil daripada rootnya sedangkan bagian kanan pohon lebih besar dari rootnya.
simpul kiri < root < simpul kanan
Contohnya:
52)32(22)(1
nstnnTn
i
i
-
N = jumlah data , k = jumlah langkah
N = 2k-1 = 24-1 = 16-1 = 15
k = log2 (N+1) = 0,3(15+1) = 0,3(16) = 4
Bentuk penyimpanannya :
31
26 41
11 28 36
50
52
49
48
34
32
27
13
5
1 data
3 data
7 data
15 data
1 langkah
2 langkah
3 langkah
4 langkah
1
2 3
4 5 6
7
15
14
13
12
11
10
9
8
-
Merge Sort Merge sort adalah metode mengurutkan data dengan menggunkan
divide and conquer, yaitu dengan cara memecahkan masalah kemudian
menyelesaikannya dan menggabungkannya kembali.
Divide and conquer memiliki tiga langkah yaitu :
- Divide
Membagi-bagi data menjadi beberapa bagian.
- Conquer
Menyelesaikan masalah data yang telah dibagi-bagi.
- Combine
Menggabungkan kembali data yag telah diselesaikan.
Contoh :
Urutkan data tersebut dari terkecil ke terbesar
21 5 10 8 25 16
Solusi :
Data ke-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Data kiri
2 4 6 8 10 12 14 Tidak memiliki data kiri (data paling bawah)
Data kanan
3 5 7 9 11 13 15 Tidak memiliki data kanan (data paling bawah)
Nilai 31 26 41 11 28 36 50 5 13 27 32 34 48 29 50
-
Kotak dan panah warna kuning menunjukkan terjadinya prose divide,
sedangkan kotak dan panah warna biru menunjukka terjadinya proses
conquer dan combine.
21 5 10
8 25 16
5 10
25 16
21 8 5 10 16
6
25
21 5 10
16 25
8
5 10 21
8 16 25
21 5 10 8 25 16
5 8 10 16 21 25
-
KOMPLEKSITAS ALGORITMA Kompleksitas algoritma adalah perubahan data yang diiput terhadap hasilnya(output) yakni menghitung waktu/ruang yang dibutuhkan suatu
algoritma dalam menyelesaikan satu masalah (running time). Kompleksitas
algoritma bisa dipengaruhi oleh kondisi data yang diinput, seperti urutan data
yang tidak terurut atau terurut terbalik.
Batas Atas (Upper Bound)
O(g(n)) = {f(n) : terdapat konstanta c dan n0
sedemikian sehingga 0 f(n) cg(n), n n0}
O(g(n)) (dibaca : big oh g(n)) menyatakan batas atas kompleksitas algoritma.
Cocok digunakan untuk kondisi terburuk.
Batas Bawah (Lower Bound)
n0
f(n) = O(g(n))
cg(n)
n0
f(n) = (g(n))
cg(n)
n
-
(g(n)) = {f(n) : terdapat konstanta c dan n0
sedemikian sehingga 0 cg(n) f(n), n n0}
(g(n)) (dibaca : big omega g(n)) menyatakan batas bawah kompleksitas
suatu algoritma. Cocok digunakan untuk kondisi terbaik.
Batas Ketat (Tight Bound)
(g(n)) = {f(n) : terdapat konstanta c1, c2, dan n0 sedemikian sehingga 0
c1g(n) f(n) c2g(n) , n n0}
(g(n)) (dibaca : big theta g(n)) menyatakan batas ketat suatu kompleksitas
algoritma. Cocok digunakan untuk kasus rata-rata.
Diantara ketiga batas diatas, yang paling efisien digunakan adalah batas atas
(upper bound), karena dengan menentukan batas atas suatu algoritma maka kita
tidak perlu khawatir akan adanya suatu kemungkinan terjadi kebutuhan
ruang/waktu yang besar.
n0
f(n) = (g(n))
c1g(n)
n
c2g(n)