BAB 2 LANDASAN TEORI
2.1
Algoritma Optimal Mismatch Algoritma Optimal Mismatch ini mencari data secara berurut pada tiap
karakter dalam teks sehingga pencarian seperti ini disebut pencarian sekuensial atau sequential search. Algoritma Optimal Mismatch mencari pola karakter mulai dari frekuensi yang paling sedikit hingga frekuensi yang paling banyak pada teks. Sebelum menggunakan algoritma Optimal Mismatch, terdapat tiga tahap yang harus dilewati. Tahap pertama adalah prosedur pengurutan karakter pada pola. Tahap kedua adalah prosedur Quick search bad–character dan tahap ketiga adalah pencarian nilai pergeseran karakter dalam teks menggunakan good suffix adapted. Contoh :
Teks : binanusantara Pola : sant
Prosedur pertama adalah pengurutan karakter pada teks atau disebut order pattern yang berguna untuk mencari frekuensi tiap-tiap karakter pada teks, kemudian mengurutkan pola karakter mulai dari frekuensi terendah hingga frekuensi tertinggi. Jika terdapat dua atau lebih karakter yang berbeda tetapi memiliki frekuensi yang sama maka pengurutan didasarkan pada posisi pencarian dari kanan ke kiri, yang berarti karakter yang ditemukan terlebih dahulu diurutkan lebih awal, seperti yang ditunjukkan pada Tabel 2.1 hingga Tabel 2.3 berikut:
8
Tabel 2.1 Frekuensi karakter pada teks Char
a
b
i
n
r
s
t
u
Freq [char]
4
1
1
3
1
1
1
1
Tabel 2.2 Pola awal Pos
0
1
2
3
Pola[Pos]
s
a
n
t
Freq[Pola[Pos]]
1
4
3
1
Tabel 2.3 Pola setelah diurutkan Pos
0
1
2
3
Pola[Pos]
t
s
n
a
Freq[Pola[Pos]]
1
1
4
3
Proses kedua adalah pre search bad–character atau preQsBc yang menghitung nilai qsBc pada tiap-tiap karakter yang selanjutnya nilai tersebut kemungkinan akan digunakan untuk pergeseran pada pola dengan cara menentukan posisi karakter dalam pola dari kanan ke kiri dan jika ada karakter sama dalam pola maka posisi karakter yang pertama ditemukan yang dicatat. Posisi dihitung mulai dari satu dan dimulai dari kanan ke kiri, seperti yang ditunjukkan pada Tabel 2.4 berikut:
9
Tabel 2.4 PreQsbc Pada Algoritma Optimal Mismatch Char
a
b
i
n
r
s
t
u
Qsbc [char]
3
5
5
2
5
4
1
5
Proses ketiga adalah preAdaptedGs yang menghitung nilai pada tiap posisi dan kemudian nilai inilah yang kemungkinan akan digunakan untuk pergeseran pada pola, seperti pada Tabel 2.5 berikut: Tabel 2.5 PreAdaptedGs Pada Algoritma Optimal Mismatch i
0
1
2
3
AdaptedGs[i]
1
4
4
4
Selanjutnya akan dimulai langkah-langkah pencarian dengan menggunakan algoritma Optimal Mismatch. Setelah langkah-langkah diatas selesai, maka dimulai pencarian string dengan cara mencocokkan pola sesuai dengan tabel yang telah diurutkan. Pertama-tama dihitung selisih panjang pola dan panjang teks. Karakter dengan urutan pertama dalam orderPattern dicocokkan dengan teks pada posisi yang sama pada pola. Jika terjadi kecocokan, maka pencarian akan diteruskan dengan cara mencocokkan pola sesuai dengan urutan posisi yang telah diurutkan pada orderPattern dan setelah itu dicocokkan dengan karakter pada teks. Jika semua karakter pada pola telah berhasil dicari maka dianggap telah menemukan output string yang dicari. Sedangkan jika tidak cocok maka dilakukan perhitungan qsBc dan perhitungan adaptedGs. Kemudian diambil nilai terbesar dari perhitungan qsBc atau
10
adaptedGs, yang selanjutnya digunakan untuk pergeseran. Pergeseran akan terjadi sampai ketika jumlah seluruh pergeseran lebih besar daripada selisih panjang teks dengan panjang pola, hal ini dapat dijelaskan seperti pada proses berikut: Langkah 1 :
i
:0
Selisih : 9 Geser : 0 Urutan pencarian dimulai dari huruf “t” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [0]=1 dan qsBc untuk karakter berikutnya atau qsBc[n] = 2. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 2. Maka: Langkah 2 :
i
:0
Selisih : 9 Geser : 2
11
Urutan pencarian dimulai dari huruf “t” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [0]=1 dan qsBc untuk karakter berikutnya atau qsBc[s] = 4. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 4. Maka: Langkah 3 :
i
:3
Selisih : 9 Geser : 6 Urutan pencarian dimulai dari huruf “t” yang ternyata cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “s” yang ternyata juga cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “n” dan huruf “a” sehingga pencarian dianggap menemukan output string yang sama. Selanjutnya dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [3]=4 dan qsBc untuk karakter berikutnya atau qsBc[a] = 3. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 4, sehingga nilai geser menjadi 10. Karena nilai geser telah melebihi nilai selisih, maka pencarian dianggap selesai.
12
2.2
Algoritma Maximal Shift Salah satu algoritma lain untuk mencari pola di dalam teks adalah algoritma
Maximal Shift. Algoritma Maximal Shift adalah algoritma yang mencari pola dalam teks dengan cara pola dicari dari karakter yang memiliki nilai minShift yang terbesar hingga nilai minShift yang terkecil. Seperti halnya algoritma Optimal Mismatch yang memiliki langkah-langkah yang harus dilakukan sebelum proses pencarian pola dalam teks dilakukan, algoritma Maximal Shift juga memiliki langkah-langkah yang harus dilakukan sebelum proses pencarian dilakukan. Contoh :
Teks : binanusantara Pola
: sant
Proses pertama adalah prosedur perhitungan nilai minShift karakter pada pola yang akan digunakan untuk proses pengurutan, seperti pada Tabel 2.6 berikut: Tabel 2.6 Nilai minShift Pada Algoritma Maximal Shift i
0
1
2
3
char
s
a
n
t
MinShift [i]
1
2
3
4
Proses kedua adalah orderPattern yang digunakan untuk mengurutkan karakter pada pola dari nilai minShift tertinggi hingga terkecil pada pola. Jika ditemukan karakter yang memiliki nilai minShift yang sama maka pengurutan
13
didasarkan pada posisi pencarian dari kanan ke kiri, yaitu posisi karakter yang ditemukan dahulu diurutkan lebih awal, seperti pada Tabel 2.7 berikut: Tabel 2.7 OrderPattern Pada Algoritma Maximal Shift i
0
1
2
3
char
t
n
a
s
MinShift [i]
4
3
2
1
Proses ketiga adalah preQsBc yang menghitung nilai qsBc pada tiap-tiap karakter yang selanjutnya nilai tersebut kemungkinan akan digunakan untuk pergeseran pola dengan cara menentukan posisi karakter dalam pola dari kanan ke kiri dan jika ada karakter sama dalam pola maka posisi karakter yang pertama ditemukan yang dicatat. Posisi dihitung mulai dari satu dan dari kanan ke kiri, seperti pada Tabel 2.8 berikut: Tabel 2.8 PreQsbc Pada Algoritma Maximal Shift Char
a
b
i
n
r
s
t
u
Qsbc [char]
3
5
5
2
5
4
1
5
Proses keempat adalah preAdaptedGs yang menghitung nilai pada tiap posisi dan kemudian nilai inilah yang kemungkinan akan digunakan untuk pergeseran pada pola, seperti pada Tabel 2.9 berikut:
14
Tabel 2.9 PreAdaptesGs Pada Algoritma Maximal Shift i
0
1
2
3
AdaptedGs[i]
1
4
4
4
Selanjutnya akan dimulai langkah-langkah pencarian dengan menggunakan algoritma Maximal Shift dengan menentukan terlebih dahulu pola yang dicari. Setelah langkah-langkah diatas selesai dilakukan, maka proses pencarian dimulai dengan mencocokkan pola yang telah diurutkan terhadap teks. Pertama-tama dihitung selisih panjang pola dan panjang teks. Karakter dengan urutan pertama dalam orderPattern dicocokkan dengan teks pada posisi yang sama pada pola. Jika terjadi kecocokan maka pencarian diteruskan dengan mencocokkan pola sesuai dengan posisi yang telah diurutkan dengan karakter pada teks. Jika semua pola telah ditemukan maka dianggap telah menemukan output string yang dicari. Jika ada ketidakcocokan maka terjadi perhitungan qsBc dan adaptedGs. Kemudian diambil nilai terbesar dari hasil perhitungan qsBc atau adaptedGs, yang digunakan untuk pergeseran. Pergeseran terus terjadi hingga jumlah pergeseran lebih besar daripada selisih panjang teks dengan panjang pola, hal ini dapat dijelaskan seperti pada proses berikut: Langkah 1 :
i
:0
15
Selisih : 9 Geser : 0 Urutan pencarian dimulai dari huruf “t” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [0]=1 dan qsBc untuk karakter berikutnya atau qsBc[n] = 2. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 2. Maka: Langkah 2 :
i
:0
Selisih : 9 Geser : 2 Urutan pencarian dimulai dari huruf “t” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [0]=1 dan qsBc untuk karakter berikutnya atau qsBc[s] = 4. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 4. Maka:
16
Langkah 3 :
i
:3
Selisih : 9 Geser : 6 Urutan pencarian dimulai dari huruf “t” yang ternyata cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “n” yang ternyata juga cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “a” dan huruf “s” sehingga pencarian dianggap menemukan output string yang sama. Selanjutnya dilakukan pergeseran yang akan ditentukan oleh nilai adaptedGs yang ke-i atau adaptedGs [3]=4 dan qsBc untuk karakter berikutnya atau qsBc[a] = 3. Nilai yang akan dipakai untuk pergeseran adalah nilai yang lebih besar atau dalam hal ini adalah 4, sehingga nilai geser menjadi 10. Karena nilai geser telah melebihi nilai selisih, maka pencarian dianggap selesai.
2.3
Algoritma Quick Search Algoritma Quick Search ini mencari data secara berurut pada tiap karakter
dalam teks sehingga pencarian seperti ini disebut pencarian sekuensial atau sequential search. Algoritma Quick Search search bad–character
mencari pola karakter berdasarkan nilai Quick
atau qsBc pada tiap-tiap karakter yang selanjutnya nilai
17
tersebut akan digunakan untuk pergeseran, seperti yang ditunjukkan pada Tabel 2.10 berikut: Contoh :
Teks : binanusantara Pola
: sant
Tabel 2.10 PreQsbc Pada Algoritma Quick Search Char
a
b
i
n
r
s
t
u
Qsbc [char]
3
5
5
2
5
4
1
5
Selanjutnya akan dimulai langkah-langkah pencarian dengan menggunakan algoritma Quick Search. Pertama-tama dihitung selisih panjang pola dan panjang teks. Proses pencarian dimulai dengan mencocokkan karakter pola pertama dengan karakter teks pertama, jika terjadi kecocokan maka pencarian diteruskan dengan mencocokkan karakter pola selanjutnya dengan karakter pada teks. Jika semua pola telah ditemukan maka dianggap telah menemukan output string yang dicari. Jika ada ketidakcocokan maka terjadi perhitungan qsBc. Hasil perhitungan qsBc akan digunakan untuk pergeseran. Pergeseran terus terjadi hingga jumlah pergeseran lebih besar daripada selisih panjang teks dengan panjang pola, hal ini dapat dijelaskan seperti pada proses berikut:
18
Langkah 1 :
i
:0
Selisih : 9 Geser : 0 Urutan pencarian dimulai dari huruf “s” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai qsBc untuk karakter berikutnya atau qsBc[n] = 2. Maka: Langkah 2 :
i
:0
Selisih : 9 Geser : 2 Urutan pencarian dimulai dari huruf “s” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai qsBc untuk karakter berikutnya atau qsBc[s] = 4. Maka:
19
Langkah 3 :
i
:3
Selisih : 9 Geser : 6 Urutan pencarian dimulai dari huruf “s” yang ternyata cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “a” yang ternyata juga cocok dengan teks, maka pencarian dilanjutkan dengan mencari huruf “n” dan huruf “t” sehingga pencarian dianggap menemukan output string yang sama. Selanjutnya dilakukan pergeseran yang akan ditentukan oleh qsBc untuk karakter berikutnya atau qsBc[a] = 3. Maka: Langkah 3 :
i
:3
Selisih : 9 Geser : 9
20
Urutan pencarian dimulai dari huruf “s” yang ternyata tidak cocok dengan teks, maka dilakukan pergeseran yang akan ditentukan oleh nilai qsBc untuk karakter berikutnya yang ternyata tidak tersedia, maka pencarian dianggap selesai.
2.4
Hipotesis Statistik Hipotesis statistik adalah pernyataan atau dugaan kesamaan atau perbedaan
mengenai satu atau lebih populasi. Kebenaran dari suatu hipotesis statistik tidak akan pernah diketahui dengan pasti kecuali bila seluruh populasi diamati. Dalam kebanyakan situasi hal itu tidak mungkin untuk dilakukan, karena itu diperlukan sampel dari populasi yang akan digunakan sebagai informasi dari sampel untuk memutuskan seberapa besar kemungkinan hipotesis tersebut benar atau salah.
2.4.1
Pengujian Hipotesis Pengujian hipotesis statistik mempunyai beberapa elemen yaitu hipotesis nol
(Ho), hipotesis alternatif, uji statistik dan daerah kritik. Hipotesis nol merupakan pernyataan yang dirumuskan dengan harapan akan ditolak. Uji statistik merupakan uji yang digunakan untuk membuktikan penerimaan atau penolakan Ho. Daerah kritik adalah daerah penolakan hipotesis nol. Penolakan terhadap hipotesis nol bukan berarti bahwa hipotesis nol tersebut salah, tetapi lebih kepada tidak cukupnya bukti untuk menerima hipotesis tersebut.
21
2.4.2
Uji Perbedaan Nilai Tengah Uji perbedaan nilai tengah dilakukan untuk mengetahui ada tidaknya
perbedaan nilai tengah dari dua populasi atau lebih yang dibandingkan. Uji ini memiliki hipotesis Ho yang menyatakan tidak ada perbedaan nilai tengah antara populasi dan hipotesis alternatif yang menyatakan adanya perbedaan nilai tengah antar populasi. Kebenaran suatu hipotesis statistik diketahui melalui pengujian. Banyaknya cara pengujian yang dapat digunakan tergantung pada kasus yang dihadapi dan banyaknya sampel yang diambil. Salah satu jenis pengujian parametrik yang ada adalah analisis ragam. Analisis ragam mengacu pada sebaran normal, yaitu sebaran peluang kontinu yang dipengaruhi oleh suatu besaran yang berubah-ubah yaitu ratarata. Uji normalitas dapat dilakukan dengan melihat besaran Kolmogorov-Smirnov. Angka signifikansi (Sig.) > 0.05 menyatakan data berdistribusi normal. Sedangkan Angka signifikansi (Sig.) < 0.05 menyatakan data tidak berdistribusi normal. Uji Kruskal-Wallis,
disebut juga uji H Kruskal-Wallis, merupakan
generalisasi uji dua-contoh Wilcoxon untuk sampel lebih dari dua. Uji ini digunakan untuk menguji hipotesis nol H0 bahwa sampel bebas berasal dari populasi yang identik. Diperkenalkan pada tahun 1952 oleh W. H. Kruskal dan W. A. Wallis, uji non-parametrik ini merupakan alternatif bagi uji F untuk pengujian kesamaan beberapa nilai tengah dalam ANOVA bila kita ingin menghindar dari asumsi bahwa sampel diambil dari distribusi normal.
22
2.5
Analisis Algoritma Menurut Horowitz et.al (1998) algoritma adalah suatu kumpulan instruksi
tertentu yang bila diikuti akan menyelesaikan tugas tertentu. Algoritma dapat dituliskan dengan berbagai cara namun perlu diperhatikan bahwa setiap instruksi dalam algoritma harus jelas dan tidak membingungkan. Flow chart sering digunakan untuk menggambarkan algoritma namun kendala akan muncul apabila algoritma terlalu panjang. Dapat disimpulkan bahwa algoritma dapat dinyatakan dengan berbagai cara namun perlu diperhatikan kejelasan tiap instruksinya. Analisis algoritma merupakan suatu cara untuk menilai kinerja dari algoritma, analisis ini lebih ditekankan kepada waktu pencarian string dan jumlah memory yang dibutuhkan. Suatu algoritma dapat diketahui tingkat kompleksitasnya dengan menghitung kompleksitas ruang dan kompleksitas waktu. Pada kompleksitas ruang Sn diukur dr besarnya ruang memory yang dibutuhkan oleh struktur data pada suatu algoritma sebagai fungsi ukuran dari sebuah input n. Sedangkan pada kompleksitas waktu T(n) diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi ukuran dari sebuah input n. Untuk menganalisis kompleksitas tersebut maka dilakukan dua fase, yaitu: 1. A priori analysis, yaitu suatu analisis untuk mendapatkan waktu proses atau memory dari suatu algoritma dalam bentuk fungsi matematik, yang disebut fungsi batas suatu proses. Analisis ini membahas kompleksitas algoritma dilihat dari segi matematis. Dalam hal ini dikenal tiga macam notasi yaitu Θ, Ω dan O yang akan dijelaskan kemudian.
23
2. A posteriori testing, yaitu suatu analisis untuk mendapatkan waktu proses aktual atau memory proses aktual dari suatu algoritma dalam bentuk data statistik ketika dijalankan. Biasanya data dijalankan dari komputer yang menjalankan algoritma tersebut. Kompleksitas waktu suatu program bergantung pada waktu instruksi-instruksi program dijalankan. Instruksi-instruksi ini dapat berupa instruksi dasar aritmatika seperti perhitungan floating point, perbandingan, menjalankan fungsi atau prosedur. Untuk instruksi-instruksi tersebut hanya membutuhkan satu langkah pengerjaan dan dapat dinyatakan dengan nilai konstan. Dalam analisis algoritma dikenal adanya order of magnitude, yaitu suatu bilangan yang menunjukkan frekuensi suatu instruksi atau perintah dijalankan. Misalkan ada tiga buah program seperti berikut:
Gambar 2.1 Contoh Tiga Bagian Program Pada program (a) hanya terdiri dari x = x+ y, yang artinya instruksi hanya dijalankan satu kali dan nilai kompleksitasnya adalah 1, sedangkan pada program (b) instruksi dijalankan sebanya n kali dan nilai kompleksitasnya adalah n, dan pada program (c)
24
instruksi dijalankan sebanyak n2 kali sehingga nilai kompleksitasnya adalah n2. Nilainilai 1, n, dan n2 adalah yang disebut dengan order of magnitude. Nilai kompleksitas waktu pada a priori analysis dinyatakan dalam bentuk notasi matematik Θ, Ω dan O. Notasi ini dikenal dengan nama Notasi Asimtotik (Asymtotic Notation). Notasi Θ merupakan fungsi yang menyatakan kompleksitas waktu dari suatu instruksi. Jika terdapat dua fungsi kompleksitas waktu yaitu f(n) dan g(n), dapat dinyatakan bahwa f(n) adalah Θ(g(n)) jika terdapat suatu nilai riil positif C1 dan C2 dan sebuah nilai positif integer no, sedemikian sehingga C1 g(n) ≤ f(n) ≤ C2 g(n) untuk semua n > no. Jadi dapat disimpulkan jika f(n) adalah Θ(g(n)) maka g(n) merupakan fungsi batas atas dan batas bawah dari f(n) ; yang artinya kondisi terbaik (batas bawah) dan kondisi terburuk (batas atas) memiliki suatu nilai waktu yang sama yaitu pada suatu faktor konstan. Notasi Ω menyatakan batas atas dari kompleksitas waktu dari suatu instruksi. Jika terdapat dua fungsi kompleksitas waktu yaitu f(n) dan g(n), dapat dinyatakan bahwa f(n) adalah Ω(g(n)) jika terdapat suatu nilai riil konstan C > 0 dan sebuah nilai positif integer no, sedemikian sehingga f(n) ≥ C g(n) untuk semua n > no. Artinya jika f(n) adalah O(g(n)) maka fungsi g(n) memiliki nilai pertambahan waktu yang lebih besar dari f(n). Notasi O menyatakan batas bawah dari kompleksitas waktu dari suatu instruksi. Jika terdapat dua fungsi kompleksitas waktu yaitu f(n) dan g(n), dapat dinyatakan bahwa f(n) adalah O(g(n)) jika terdapat suatu nilai riil konstan C > 0 dan sebuah nilai
25
positif integer no, sedemikian sehingga f(n) ≤ C g(n) untuk semua n > no. Artinya jika f(n) adalah Ω(g(n)) maka fungsi g(n) memiliki nilai pertambahan waktu yang lebih kecil dari f(n). Teorema 2.1 Jika f(n) dan g(n) adalah suatu fungsi kompleksitas waktu maka berlaku: 1. f(n) adalah Θ(f(n)) 2. f(n) adalah Θ(g(n)) jika dan hanya jika g(n) adalah Θ(f(n)) 3. Jika f(n) adalah Θ(g(n)) dan g(n) adalah Θ(f(n)) maka f(n) adalah Θ(h(n)) Teorema 2.2 Jika f(n) dan g(n) adalah suatu fungsi kompleksitas waktu maka berlaku: 1. Untuk semua C>0, fungsi C.f(n) adalah Θ(f(n)) 2. Jika f1(n) adalah Θ(g(n)) dan f2(n) adalah Θ(g(n)) maka (f1+f2)(n) adalah Θ(g(n)) 3. Jika f1(n) adalah Θ(g1(n)) dan f2(n) adalah Θ(g2(n)) maka (f1*f2)(n) adalah Θ((g1*g2)(n)) Teorema 2.3 Hubungan antara notasi Θ, Ω dan O 1. f(n) adalah O(g(n)) jika dan hanya jika g(n) adalah Ω(f(n)) 2. f(n) adalah Θ(g(n)) jika dan hanya jika f(n) adalah O(g(n)) dan f(n) adalah Ω(f(n))
26
Teorema 2.4 Jika A(n) = amnm + am-1nm-1 + …+ a1n + ao adalah sebuah polinomial yang memiliki derajat m maka A(n) = O(nm). Hal ini menunjukkan bahwa suku yang berderajat lebih tinggi mendominasi suku yang lebih rendah artinya laju pertambahan waktunya akan lebih besar jika derajatnya lebih tinggi, f(n) akan mendominasi T(n) jika T(n) sama dengan O(f(n)). Teorema 2.5 Misalkan T1(n) = O(f(n)) dan T2(n) = O(g(n)) maka: 1. T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n))) 2. T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n)) 3. (C*f(n)) = O(f(n)), C merupakan suatu konstanta 4.
f(n) = O( f(n))
Teorema-teorema menurut Sahni (2003) diatas dapat digunakan dalam a priori analysis untuk mempermudah dalam penyederhanaan algoritma kedalam bentuk notasi-notasi yang lebih mudah untuk dimengerti.
2.6
Siklus Hidup Pengembangan Sistem Algoritma siklus hidup pengembangan sistem atau sering disebut dengan
System Development Life Cycle (SDLC) merupakan suatu tahapan – tahapan algoritma untuk merancang sebuah program aplikasi perangkat lunak. Nama lain dari algoritma SDLC yaitu algoritma waterfall. Algoritma ini disebut waterfall karena model dari langkah – langkah yang dilakukan mirip dengan air terjun (bertingkat).
27
Jadi proses yang harus dilakukan secara bertingkat untuk menghasilkan suatu program aplikasi yang baik. Perancangan aplikasi perangkat lunak dengan algoritma SDLC dilakukan dalam 6 tahap. Tahapan – tahapan yang harus dilakukan terdiri dari perencanaan (system engineering), analisis desain, pengkodean (coding), pengujian (testing), dan pemeliharaan (maintenance). Berikut ini akan dijelaskan setiap tahapan dalam SDLC tersebut yaitu : 1. Perencanaan Perencanaan adalah suatu kegiatan untuk menentukan program aplikasi yang akan dirancang, tempat program aplikasi akan dirancang dan dijalankan, dan siapa yang akan merancang program aplikasi tersebut. 2. Analisis Analisis adalah suatu kegiatan untuk menentukan tentang topic dari permasalahan yang sedang dihadapi dan bagaimana cara pemecahan atau solusi masalah tersebut. 3. Desain Desain adalah suatu kegiatan untuk menentukan konsep dasar rancangan dari suatu program yang akan dibuat sehingga diharapkan dengan desain yang baik, maka para pengguna akan merasa nyaman dalam menggunakan program aplikasi yang dirancang tersebut.
28
4. Pengkodean Pengkodean
adalah
suatu
kegiatan
yang
berguna
untuk
mengimplementasikan konsep dasar dari tahapan sebelumnya (desain) ke dalam bahasa pemrograman, 5. Pengujian Pengujian adalah suatu kegiatan untuk mencari kelemahan dan kesalahan yang terjadi pada program aplikasi dan kemudian memperbaiki kesalahan atau kelemahan tersebut. Ada beberapa algoritma pengujian untuk menguji fungsi – fungsi dari suatu program aplikasi. Algoritma tersebut adalah : •
Algoritma Pengujian White-Box Algoritma ini menerapkan pengujian terhadap struktur logika program dan detail procedural. Pengujian dilakukan terhadap setiap baris kode program untuk meyakinkan bahwa semua operasi internal bekerja sesuai dengan spesifikasi dan semua komponen internal telah dicoba.
•
Algoritma Pengujian Black-Box Algoritma ini merupakan pengujian interface dari perangkat lunak oleh pemakai untuk mengetahui spesifikasi dari suatu fungsi dalam program aplikasi. Pengujian dilakukan dengan memberi input pada program aplikasi, kemudian diproses, dan hasil keluarannya
29
dibandingkan apakah telah sesuai dengan kebutuhan fungsional yang diinginkan pemakai. •
Algoritma pengujian Gray-Box Algoritma ini merupakan gabungan dari algoritma pengujian WhiteBox dan algoritma pengujian Black-Box yaitu memvalidasi interface perangkat lunak dan pemilihan beberapa logika internal.
6. Pemeliharaan Pemeliharaan adalah suatu kegiatan yang berguna untuk memastikan bahwa program aplikasi akan berjalan dengan baik sehingga diperlukan pemeliharaan secara berkala.
