Proses Testing
• System Testing
– Pengujian terhadap integrasi sub-system, yaitu
keterhubungan antar sub-system
• Acceptance Testing
– Pengujian terakhirs sebelum sistem dipakai oleh user.
– Melibatkan pengujian dengan data dari pengguna
sistem.
– Biasa dikenal sebagai “alpha test” (“beta test” untuk
software komersial, dimana pengujian dilakukan oleh
potensial customer)

The testing process
Component testing
􀂄 Pengujian komponen-komponen program
􀂄 Biasanya dilakukan oleh component developer
(kecuali untuk system kritis)
Integration testing
􀂄 Pengujian kelompok komponen-komponen yang
terintegrasi untuk membentuk sub-system
ataupun system
􀂄 Dialakukan oleh tim penguji yang independent
􀂄 Pengujian berdasarkan spesifikasi sistem

Rencana Pengujian
Proses testing
􀂄 Deskripsi fase-fase utama dalam pengujian
Pelacakan Kebutuhan
􀂄 Semua kebutuhan user diuji secara individu
Item yg diuji
􀂄 Menspesifikasi komponen sistem yang diuji
Jadual Testing
Prosedur Pencatatan Hasil dan Prosedur
Kebutuhan akan Hardware dan Software
Kendala-kendala
􀂄 Mis: kekuranga staff, alat, waktu dll.

Failures, Faults
Failure: output yang tidak benar/tidak sesuai
ketika sistem dijalankan
Fault: kesalahan dalam source code yang
mungkin menimbulkan failure ketika code yg
fault tsb dijalankan
Corrupting Failure yang merusak sistem data
Non-corrupting Failure tidak merusak data
Unrecoverable Sistem tidak dapat memperbaiki secara otomatis
Recoverable Sistem dapat memperbaiki secara otomatis
Permanent Muncul untuk semua input
Transient Muncul untuk input tertentu
Failure Class Deskripsi

Failures, Faults
Failure: output yang tidak benar/tidak sesuai
ketika sistem dijalankan
Fault: kesalahan dalam source code yang
mungkin menimbulkan failure ketika code yg
fault tsb dijalankan
Corrupting Failure yang merusak sistem data
Non-corrupting Failure tidak merusak data
Unrecoverable Sistem tidak dapat memperbaiki secara otomatis
Recoverable Sistem dapat memperbaiki secara otomatis
Permanent Muncul untuk semua input
Transient Muncul untuk input tertentu
Failure Class Deskripsi

Test data: Input yang yang
direncankan digunakan oleh sistem.
Test cases: Input yang digunakan
untuk menguji sistem dan memprediksi
output dari input jika sistem beroperasi
sesuai dengan spesifikasi.
Test data dan kasus test

Disebut juga white-box testing
Penentuan test case disesuaikan
dengan struktur sistem. Knowledge
program digunakan untuk
mengidentifikasi test case tambahan.
Tujuannya untuk menguji semua
statement program (debug).
Structural testing

Path testing
Tujuannya meyakinkan bahwa himpunan test
case akan menguji setiap path pada suatu
program paling sedikit satu kali.
Titik awal untuk path testing adalah suatu
program flow graph yang menunjukkan nodenode
yang menyatakan program decisions
(mis.: if-then-else condition) dan busur
menyatakan alur kontrol
Statements dengan conditions adalah nodenode
dalam flow graf.

Menggambarkan alur kontrol. Setiap cabang
ditunjukkan oleh path yg terpisah dan loop
ditunjukkan oleh arrows looping kembali ke
loop kondisi node.
Digunakan sebagai basis untuk menghitung
cyclomatic complexity
Cyclomatic complexity = Jumlah edges –
Jumlah Node +2
Cyclomatic complexity menyatakan jumlah
test untuk menguji control statements
Program flow graphs

1, 2, 3, 8, 9
1, 2, 3, 4, 6, 7, 2
1, 2, 3, 4, 5, 7, 2
1, 2, 3, 4, 6, 7, 2, 8, 9
Test cases harus ditentukan sehingga
semua path tsb tereksekusi.
Independent paths


Black-box testing
Pendekatan pengujian dimana program
dianggap sebagai suatu ‘black-box’
(‘kotak hitam’)
Program test case berbasiskan
spesifikasi
Test planning dapat dimulai sejak awal
proses pengembangan sistem

Black-box testing
• Pengujian black box berusaha
menemukan kesalahan dalam kategori :
– Fungsi-fungsi yang tidak benar atau hilang
– Kesalahan interface
– Kesalahan dalam struktur data atau akses
database eksternal
– Kesalahan kinerja
– Inisialisasi dan kesalahan terminasi

Partisi Ekivalensi (equivalensi
partition)
Input data dan output hasil terdapat di klas
yang berbeda yang sesuai dengan klas
inputnya
Masing-masing klas equivalensi partition
diprosres dimana program akan memproses
anggota klas-klas tersebut secara equivale.
Test cases dipilih dari masing-masing partisi


Contoh Analisa Kebutuhan, Pengujian Black Box, dan Pengujian White Box pada Web Aplikasi Penjualan Online “Fast & Cheap”
Posted: 28/08/2010 by celulux in Rekayasa Perangkat Lunak
11
Pengantar
Fastncheap merupakan sebuah toko yang khusus menjual Khusus barang elektronik, mulai komputer, LCD, GPS, Laptop, dan asesoris lainnya. Fastncheap juga menyediakan toko atau website secara online. Di dalam website ini terdapat beberapa kategori dimana di setiap topik diberikan penjelasan secara rinci baik spesifikasi, kelebihan dan kelemahan terhadap produk yang dikehendaki sehingga menjadi bahan pertimbangan sebelum membeli produk tersebut.
Toko Fast & Cheap telah menggunakan Sistem Web Aplikasi Penjualan Online dimana produk disana sudah bisa dibeli secara online. Sistem disini harus bisa menampilkan Informasi Penjualan Komputer pada Toko Toko Fast & Cheap (FNC) secara online yang mempunyai beberapa cabang di Indonesia
Analisa Kebutuhan Sistem
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi tentang penjualan komputer secara online
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi pelanggan yang melakukan pembelian
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi jumlah dan spesifikasi barang (Komputer) yang dijual.
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi tentang jumlah rupiah dari transaksi penjualan
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi penambahan kas dari transaksi penjualan.
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi atau laporan penjualan baik perminggu/perbulan dan pertahun.
• Dengan Menggunakan Aplikasi Penjualan Komputer secara komputerisasi Admin dapat menampilkan informasi peningkatan penjualan dari periode sebelumnya dengan periode sekarang.
Pengujian Black Box
Pada pengujian Black Box, yang pertama kami menguji form dari registrasi untuk menjadi anggota supaya bisa memberikan komentar terhadap produk yang ditampilkan pada sistem penjualan online fast & cheap.


Pada form tersebut kami menemukan beberapa kesalahan validasi yaitu sebagai berikut :
• Tab index tidak berjalan semestinya
• Kolom nama bisa dimasukkan angka & karakter
• Kolom telepon bisa dimasukkan huruf & karakter
• Tidak terdapat captcha untuk memastikan bahwa user adalah manusia
Yang kedua yaitu pengujian terhadap form New Produk


Pada form tersebut kami menemukan beberapa ketidak nyamanan pengguna yaitu :
• Ada beberapa rincian produk tidak lengkap
• Pengurutan produk tidak jelas menurut sub mana.
Yang ketiga yaitu pengujian terhadap form pencarian

 
Pada form tersebut kami menemukan kesalahan validasi dan pesan kesalahan yang belum sempurna yaitu :
• Kolom harga bisa dimasukkan huruf dan karakter
• Pesan kesalahan pada pencarian tidak sesuai dengan kenyataan (pesan kesalahan selalu “without thousand and decimal separator”)
Yang keempat yaitu pengujian terhadap form komentar


Pada form tersebut kami menemukan tidak ada validasi batas karakter yaitu :
• Isi jumlah karakter komentar tidak dibatasi, sehingga bisa memasukkan ribuan jumlah karakter.
Pengujian White Box
Seperti yang diatas, pertama-tama kami menguji form registrasi anggota


Yang kedua kami menguji form tambah komentar

screenshot:
Fungsi tombol “Close Window” setelah memberikan komentar tidak berjalan sesuai fungsinya.
Diperkirakan link yang terdapat pada Tulisan “Close Window” sama dengan link pada posting komentar sehingga halaman tidak berpindah
Yang ketiga kami menguji form shoping cart

screenshot :
Tidak terdapat validasi jumlah stok produk terhadap database sehingga bisa memasukkan angka jumlah produk yang sangat besar
Maintenance yang bisa dilakukan
• Pembersihan, pengawasan, dan pengecekan komentar yang masuk selama proses update produk
• Pengecekan kebenaran dan kecocokan database sistem terhadap produk yang ditampilakan
• Perbaikan tampilan sistem web agar lebih mudah diakses
• Pengecekan terhadap domain yang digunakan
• Pengecekan keamanan program (pembelian secara curang atau order dari Negara tertentu yang ilegal) yang digunakan sistem seiring perkembangan jaman
• Pengecekan terhadap pihak penerima pembayaran online
• Peningkatan kualitas layanan searching (pencarian)
Terlalu sering maintenance juga tidak baik karena berdampak buruk terhadap kenyamanan pelanggan
Fitur-fitur yang bisa ditambahkan
• Forum per topik, sehingga terdapat pertimbangan-pertimbangan dalam hal menentukan pilihan dalam membeli produk yangs sedang di bahas dalam forum tersebut
• Terdapat fasilitas diskon untuk member dengan ketentuan sedemikian rupa sehingga bisa memperbanyak pelanggan.
• Fitur pengganti bahasa. Sehingga pelanggan dari dalam negeri dan luar negeri bisa juga menggunakan web tersebut.
• Fitur Cetak dokumen bagi pelanggan yang ingin mencetak informasi tentang produk ataupun di forum (jika sudah ada)
• Sistem agar bisa diakses lewat mobile
• Penambahan fitur facebook, twitter, blog dsb. Untuk dapat lebih memudahkan dalam hal promosi.
NOTE :
Semua tulisan diatas dibuat dengan alasan proses pembelajaran. Data tersebut ditemukan sesuai tanggal postingan. Saya mohon maaf jika ada kata-kata yg atau tulisan yg tidak berkenan bagi semua pihak. Jika ada saran ataupun kritik silahkan komentar. Semoga tulisan ini bermanfaat bagi kawan-kawan semua ^_^



1
PENGUJIAN BLACK-BOX
Pengujian black-box berfokus pada persyaratan fungsional perangkat lunak.
Pengujian ini memungkinkan analis sistem memperoleh kumpulan kondisi
input yang akan mengerjakan seluruh keperluan fungsional program.
Tujuan metode ini mencari kesalahan pada:
 Fungsi yang salah atau hilang
 Kesalahan pada interface
 Kesalahan pada struktur data atau akses database
 Kesalahan performansi
 Kesalahan inisialisasi dan tujuan akhir
Metode ini tidak terfokus pada struktur kontrol seperti pengujian white-box
tetapi pada domain informasi.
Pengujian dirancang untuk menjawab pertanyaan sebagai berikut:
 Bagaimana validitas fungsional diuji?
 Apa kelas input yang terbaik untuk uji coba yang baik?
 Apakah sistem sangat peka terhadap nilai input tertentu?
 Bagaimana jika kelas data yang terbatas dipisahkan?
 Bagaimana volume data yang dapat ditoleransi oleh sistem?
 Bagaimana pengaruh kombinasi data terhadap pengoperasian sistem?
EQUIVALENCE PARTITIONING
Equivalence partitioning adalah metode pengujian black-box yang memecah
atau membagi domain input dari program ke dalam kelas-kelas data
sehingga test case dapat diperoleh.
Perancangan test case equivalence partitioning berdasarkan evaluasi kelas
equivalence untuk kondisi input yang menggambarkan kumpulan keadaan
yang valid atau tidak. Kondisi input dapat berupa nilai numeric, range nilai,
kumpulan nilai yang berhubungan atau kondisi Boolean.
Contoh :
Pemeliharaan data untuk aplikasi bank yang sudah diotomatisasikan.
Pemakai dapat memutar nomor telepon bank dengan menggunakan mikro
komputer yang terhubung dengan password yang telah ditentukan dan diikuti
dengan perintah-perintah. Data yang diterima adalah :
Kode area : kosong atau 3 digit
Prefix : 3 digit atau tidak diawali 0 atau 1
Suffix : 4 digit
Password : 6 digit alfanumerik
Perintah : check, deposit, dll
2
Selanjutnya kondisi input digabungkan dengan masing-masing data elemen
dapat ditentukan sebagai berikut :
Kode area : kondisi input, Boolean – kode area mungkin ada atau tidak
kondisi input, range – nilai ditentukan antara 200 dan 999
Prefix : kondisi input range > 200 atau tidak diawali 0 atau 1
Suffix : kondisi input nilai 4 digit
Password : kondisi input boolean – password mungkin diperlukan atau
tidak kondisi input nilai dengan 6 karakter string
Perintah : kondisi input set berisi perintah-perintah yang telah
didefinisikan
BOUNDARY VALUE ANALYSIS
Untuk permasalahan yang tidak diketahui dengan jelas cenderung
menimbulkan kesalahan pada domain outputnya. BVA merupakan pilihan test
case yang mengerjakan nilai yang telah ditentukan, dengan teknik
perancangan test case melengkapi test case equivalence partitioning yang
fokusnya pada domain input. BVA fokusnya pada domain output.
Petunjuk pengujian BVA :
1. Jika kondisi input berupa range yang dibatasi nilai a dan b, test case harus
dirancang dengan nilai a dan b.
2. Jika kondisi input ditentukan dengan sejumlah nilai, test case harus
dikembangkan dengan mengerjakan sampai batas maksimal nilai
tersebut.
3. Sesuai petunjuk 1 dan 2 untuk kondisi output dirancang test case sampai
jumlah maksimal.
4. Untuk struktur data pada program harus dirancang sampai batas
kemampuan.




PENGUJIAN BLACK BOX
Pengujian black box berfokus pada persyaratan fungsional perangkat lunak. Disebut juga pengujian behavioral atau pengujian partisi. Pengujian black box memungkinkan perekayasa perangkat lunak mendapatkan serangkaian input yang sepenuhnya menggunakan semua persyaratan fungsional untuk
suatu program. Pengujian black box berusaha menemukan :
• Fungsi-fungsi yang tidak benar atau hilang
• Kesalahan interface
• Kesalahan dalam struktur data atau akses database eksternal.
• Kesalahan kinerja
• Inisialisasi dan kesalahan terminasi.
Dengan mengaplikasikan teknik black box, maka kita menarik serangkaian test case yang
memenuhi kriteria berikut :
• Test case yang mengurangi, dengan harga lebih dari satu, jumlah test case
tambahan yang harus di desain untuk mencapai pengujian yang dapat
dipertanggungjawabkan.
• Test case yang member tahu kita sesuatu mengenai kehadiran atau ketidakhadiran
kelas kesalahan, daripada member tahu kesalahan yang berhubungan hanya
dengan pengujian spesifik.
Diposkan oleh Blogqu di 05:26

20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 2
Pengujian Perangkat Lunak
􀂄 Pengujian perangkat lunak mencakup:
􀂅 Strategi
= mengintegrasikan metode perancangan kasus uji dlm sekumpulan langkah yg direncanakan
􀂅 Teknik/Metode
= perancangan kasus uji
􀂄 White-box
􀂄 Black-box
􀂄 Pengujian perangkat lunak seharusnya menghabiskan 30% - 40% dari total biaya
pembangunan perangkat lunak.
􀂄 Testing (pengujian) tidak sama dengan debugging
􀂄 Pengujian perangkat lunak merupakan salah satu tugas yang dilakukan dalam
software verification and validation
􀂄 Verifikasi dan validasi perangkat lunak adalah bagian dari software quality
assurance.


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 3
Tujuan Pengujian
􀂄 Pengujian adalah proses menjalankan program dengan maksud
untuk mencari kesalahan (error)
􀂄 Kasus uji yang baik adalah kasus yang memiliki peluang untuk
mendapatkan kesalahan yang belum ketahuan
􀂄 Pengujian dikatakan berhasil bila dapat memunculkan
kesalahan yang belum ketahuan
􀂄 Jadi, pengujian yang baik bukan untuk memastikan tidak ada
kesalahan tetapi untuk mencari sebanyak mungkin kesalahan
yang ada di program
􀂄 Pengujian tidak dapat menunjukkan ke-tidak-hadir-an defect,
pengujian hanya menunjukkan bahwa kesalahan perangkat
lunak ada.



20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 3
Tujuan Pengujian
􀂄 Pengujian adalah proses menjalankan program dengan maksud
untuk mencari kesalahan (error)
􀂄 Kasus uji yang baik adalah kasus yang memiliki peluang untuk
mendapatkan kesalahan yang belum ketahuan
􀂄 Pengujian dikatakan berhasil bila dapat memunculkan
kesalahan yang belum ketahuan
􀂄 Jadi, pengujian yang baik bukan untuk memastikan tidak ada
kesalahan tetapi untuk mencari sebanyak mungkin kesalahan
yang ada di program
􀂄 Pengujian tidak dapat menunjukkan ke-tidak-hadir-an defect,
pengujian hanya menunjukkan bahwa kesalahan perangkat
lunak ada.


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 5
Testability
􀂄 Perancangan perangkat lunak harus mempunyai kualitas:
􀂅 Operability
􀂅 Observability
􀂅 Controllability
􀂅 Decomposability
􀂅 Simplicity
􀂅 Stability
􀂅 Understandibility
􀂄 Kualitas pengujian yang baik:
􀂅 Memiliki peluang yang besar dalam menemukan kesalahan
􀂅 Tidak berganda (redundant)
􀂅 Cukup mewakili semua kemungkinan
􀂅 Tidak terlalu sederhana dan tidak terlalu rumit


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 6
Strategi Pengujian
􀂄 Pengujian Modul/Unit
􀂅 umumnya dilakukan oleh pengembang sendiri atau antar pengembang
􀂅 menguji modul/unit
􀂅 metode: white-box
􀂄 Pengujian Integrasi
􀂅 lebih baik menggunakan penguji independen (ITG = Independent Test Group)
􀂅 menguji perancangan perangkat lunak
􀂅 metode: white-box dan black-box
􀂄 Pengujian Validasi
􀂅 menguji kesesuaian dengan requirement
􀂅 metode: black-box
􀂄 Pengujian Sistem
􀂅 menguji perangkat lunak dan elemen sistem lain sebagai suatu kesatuan



20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 7
Strategi Pengujian
􀂄 Spesifikasikan kebutuhan (requirement) produk dalam bentuk yang dapat
diukur (quantifiable) jauh sebelum pengujian dimulai
􀂄 Nyatakan tujuan pengujian secara eksplisit
􀂄 Pahami pengguna perangkat lunak dan buatlah profil dari tiap kategori
pengguna
􀂄 Buat rencana pengujian yang menekankan pada rapid cycle testing
􀂄 Buat perangkat lunak robust yang dapat menguji dirinya sendiri
􀂄 Gunakan formal technical review sebagai penyaring sebelum pengujian
dilakukan
􀂄 Gunakan formal technical review untuk menilai strategi pengujian dan
kasus uji
􀂄 Kembangkan ancangan peningkatan berlanjut untuk proses pengujian


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 8
Strategi Pengujian - Pengujian
Modul/Unit
􀂄 Hal-hal yang diujikan:
􀂅 Antarmuka modul
􀂄 memastikan bahwa informasi yang berasal dari dan keluar dari modul yang diuji
mengalir dengan benar
􀂅 Struktur data lokal
􀂄 memastikan bahwa data yang disimpan sementara menjaga integritasnya selama
eksekusi perintah dalam modul
􀂄 mencari kesalahan-kesalahan dalam bentuk:
􀂅 Penggunaan tipe yang tidak tepat atau nirtaatasas
􀂅 Inisialisasi yang salah atau nilai pasti (default) yang salah
􀂅 Nama peubah yang salah
􀂅 Tipe data yang nirtaatasas
􀂅 Underflow, overflow, dan addressing exceptions
􀂅 Kondisi batas
􀂄 memastikan bahwa modul beroperasi dengan benar pada batas-batas pemrosesan
yang ditentukan


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 9
Strategi Pengujian - PengujianModul/Unit
􀂅 Jalur-jalur bebas
􀂄 memastikan bahwa semua kemungkinan jalur kontrol yang mungkin dieksekusi
dengan benar paling tidak sekali
􀂄 mencari kesalahan-kesalahan dalam bentuk:
􀂅 penghitungan/pemrosesan yang salah
􀂅 pembandingan yang salah
􀂅 alur kontrol yang tidak tepat
􀂅 Jalur-jalur penanganan kesalahan
􀂄 perancangan perangkat lunak yang baik menuntut agar kondisi salah dapat diantisipasi
dan memiliki penanganan kesalahan agar pemrosesan dapat berhenti dengan bersih
(antibugging) - Yourdon
􀂄 mencari kesalahan-kesalahan dalam bentuk:
􀂅 Perian kesalahan tidak dapat dipahami
􀂅 Pemberitahuan kesalahan tidak sesuai dengan kesalahan yang dialami
􀂅 Kondisi kesalahan menyebabkan intervensi sistem sebelum penanganan kesalahan
dilakukan
􀂅 Penanganan kesalahan tidak benar
􀂅 Perian kesalhan tidak memberikan informasi yang cukup untuk mencari sumber kesalahan

20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 11
Strategi Pengujian - Pengujian Integrasi
􀂄 Ada dua ancangan dalam pengujian integrasi secara incremental:
􀂅 Top-Down
􀂄 modul diintegrasikan dengan menurun dilihat dari hirarki kontrol, dimulai dari
modul pengendali utama (main program)
􀂄 pengintegrasian modul-modul di bawah digabungkan dengan cara:
􀂅 breadth-first
􀂅 depth-first
􀂄 proses integrasi:
Driver =
Main
Program
Modul
Subordinat Stub
Test Cases
Test Results
Stub
Regression
Test

20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 16
Strategi Pengujian - Pengujian
Sistem
􀂄 Persiapkan masalah: Saling Tuding
􀂅 Rancang penanganan kesalahan untuk semua kemungkinan masuknya
informasi dari elemen sistem di luar perangkat lunak
􀂅 Lakukan pengujian yang mensimulasikan masuknya data jelek dan salah
􀂅 Catat semua hasil pengujian untuk bukti
􀂅 Ikut andil dalam perencanaan dan perancangan pengujian sistem untuk
memastikan bahwa pengujian perangkat lunak sudah cukup
􀂄 Jenis sistem test:
􀂅 Pengujian pemulihan (recovery testing)
􀂅 Pengujian keamanan (security testing)
􀂅 Pengujian kekuatan (stress testing)
􀂅 Pengujian kinerja (performance testing)




20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 17
Teknik Pengujian -White Box
􀂄 Jenis teknik white-box:
􀂅 Basis Path Testing
􀂄 Buat Flow Graph Notation
􀂄 Hitung Cyclomatic Complexity = salah satu dari:
􀂅 Jumlah region
􀂅 V(G) = E - N + 2
􀂃 E = jumlah busur pada flow graph
􀂃 N = jumlah simpul pada flow graph
􀂅 V(G) = P + 1
􀂃 P = simpul predikat (simpul yang memiliki kondisi = 2 atau lebih busur yang
keluar)
􀂄 Tentukan jalur bebas (independent path) = jalur program yang merupakan satu
kumpulan perintah pengolahan atau satu kondisi pengolahan
􀂄 Siapkan kasus uji untuk setiap jalur bebas
􀂄 Graph Matrices = Connection Matrices = representasi lain dari FGN


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 18
Teknik Pengujian -White Box
􀂅 Control Structure Testing
􀂄 Condition Testing
􀂅 cara merancang kasus uji untuk kondisi logika yang ada pada suatu modul
program:
􀂃 kondisi sederhana = peubah boolean | ekspresi relasional
􀂃 kondisi bentukan (compound) = gabungan dari beberapa kondisi
sederhana
􀂄 Data Flow Testing
􀂅 cara menguji berdasarkan lokasi dari pendefinisian dan penggunaan suatu
peubah dalam modul program
􀂄 Loop Testing
􀂅 cara menguji berdasarkan validitas dari konstruksi pengulangan yang
digunakan dalam modul program:
􀂃 sederhana
􀂃 bercabang
􀂃 bersambung (concatenated)
􀂃 takterstruktur


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 19
Teknik Pengujian - Black Box
􀂄 Jenis pengujian black-box:
􀂅 Graph-based Testing
􀂄 geraf yang mewakili hubungan antar objek pada modul sehingga tiap objek
dan hubungannya tersebut dapat diuji
􀂅 Equivalence Partitioning
􀂄 pembagian domain masukan dari program menjadi kelas data yang dapat
dibuatkan kasus ujinya
􀂅 Boundary Value Analysis
􀂄 pemilihan kasus uji dengan mencari batas-batas ekstrim dari kelas data
􀂅 Comparison Testing
􀂄 digunakan untuk sistem yang menganut redundancy
􀂄 kasus uji yang dirancang untuk satu versi perangkat lunak dijadikan
masukan pada pengujian versi perangkat lunak lainnya
􀂄 hasil kedua versi perangkat lunak harus sama


20092006 SE6161 Perancangan dan Analisis Perangkat Lunak 20
Debugging
􀂄 Ancangan:
􀂅 Brute-force
􀂄 memory dump, run-time trace, WRITE statements
􀂅 Backtracking
􀂄 perunutan balik mulai kesalahan ketahuan hingga sampai lokasi sumber
􀂅 Cause elimination
􀂄 dengan induksi atau deduksi: isolasi kemungkinan penyebab kesalahan
􀂄 Proses:
Eksekusi Debugging
Penyebab
Diketahui
Penyebab
Dicurigai
Pengujian
Tambahan
Pengujian
Regresi
Kasus Uji
Hasil


Pendekatan Strategis ke
pengujian perangkat lunak
Pengujian Unit
Pengujian Integrasi
Pengujian Validasi
Pengujian Sistem

Pengujian Unit
Berfokus pada inti terkecil dari desain
perangkat lunak yaitu modul
Biasanya berorientasi pada white box
MMOODDUULL Interface
Struktur data lokal
Kondisi Batas
Jalur independen
Jalur penanganan kesalahan
Test Case


Pengujian Unit
Checklist untuk pengujian interface
􀂄 Apakah jumlah parameter input sama dengan
jumlah argumen?
􀂄 Apakah antara atribut dan parameter argumen
sudah cocok?
􀂄 Apakah antara sistem satuan parameter dan
argumen sudah cocok?
􀂄 Apakah jumlah argumen yang ditransmisikan ke
modul yang dipanggil sama dengan atribut
parameter?

Pengujian Unit
􀂄 Apakah atribut dari argumen yang ditransmisikan
ke modul yang dipanggil sama dengan atribut
parameter?
􀂄 Apakah sistem unit dari argumen yang
ditransmisikan ke modul yang dipanggil sama
dengan sistem satuan parameter?
􀂄 Apakah jumlah atribut dan urutan argumen ke
fungsi-fungsi built-in sudah benar?
􀂄 Adakah referensi ke parameter yang tidak sesuai
dengan poin entri yang ada?
􀂄 Apakah argumen input only diubah?

Pengujian Unit
􀂄 Apakah definisi variabel global konsisten dengan
modul ?
􀂄 Apakah batasan yang dilalui merupakan argumen?
Test case harus didesain untuk mengungkap kesalahan
dalam kategori
pengetikan yang tidak teratur dan tidak konsisten
inisialisasi yang salah atau nilai-nilai default
Nama variabel yang tidak benar
Tipe data yang tidak konsisten
Underflow, overflow dan pengecualian pengalamatan

● Dua Aspek yang dipertimbangkan:
• Apakah implementasi sudah sesuai dengan spesifikasi ?
• Apakah spesifikasi sesuai dengan kebutuhan user ?
● Validasi
• “Apakah sistem yang dikembangkan sudah benar?”
• Pengujian dimana sistem ketika diimplementasikan sesuai dengan
yang iharapkan
● Verifikasi
• “Apakah sistem dikembangkan dengan cara yang benar ?”
• Pengujian apakah sistem sudah sesuai dengan spesifikasi
Seberapa baik sistem yang
sudah dibangun ?


Integration testing
Pengujian keseluruhan system atau subsystem
yang terdiri dr komponen yg
terintegrasi.
Test integrasi menggunakan black-box
dengan test case ditentukan dari spesifikasi.
Kesulitannya adalah menemukan/melokasikan
Penggunaan Incremental integration testing
dapat mengurangi masalah tersebut.


Pendekatan integration testing
Top-down testing
􀂄 Berawal dari level-atas system dan terintegrasi
dengan mengganti masing-masing komponen
secara top-down dengan suatu stub (program
pendek yg mengenerate input ke sub-system yg
diuji).
Bottom-up testing
􀂄 Integrasi components di level hingga sistem
lengkap sudah teruji.
Pada prakteknya, kebanyakan test integrasi
menggunakan kombinasi kedua strategi
pengujian tsb.


Pendekatan Testing
Architectural validation
􀂄 Top-down integration testing lebih baik digunakan
dalam menemukan error dalam sistem arsitektur.
System demonstration
􀂄 Top-down integration testing hanya membatasi
pengujian pada awal tahap pengembangan system.
Test implementation
􀂄 Seringkali lebih mudah dengan menggunakan
bottom-up integration testing


Dilakukan kalau module-module dan subsystem
terintegrasi dan membentuk sistem
yang lebih besar
Tujuannya untuk medeteksi fault terhadap
kesalahan interface atau asumsi yg tidak valid
terntang interface tsb.
Sangat penting untuk pengujian terhadap
pengembangan sistem dgn menggunakan
pendekatan object-oriented yg didefinisikan
oleh object-objectnya
Interface testing

Pengujian perangkat lunak adalah elemen kritis dari jaminan kualitas perangkat lunak dan merepresentasikan spesifikasi, desain dan pengkodean.

Meningkatnya visibilitas (kemampuan) perangkat lunak sebagai suatu elemen sistem dan “biaya” yang muncul akibat kegagalan perangkat lunak, memotivasi dilakukannya perencanaan yang baik melalui pengujian yang teliti. Pada dasarnya, pengujian merupakan satu langkah dalam proses rekayasa perangkat lunak yang dapat dianggap sebagai hal yang merusak daripada membangun.

Dalam melakukan uji coba ada 2 masalah penting yang akan dibahas, yaitu :
A. Teknik uji coba perangkat lunak
B. Strategi uji coba perangkat lunak

TEKNIK UJI COBA PERANGKAT LUNAK

Pada dasarnya, pengujian merupakan suatu proses rekayasa perangkat lunak yg dapat dianggap (secara psikologis) sebagai hal yg destruktif daripada konstruktif.

SASARAN PENGUJIAN (Glen Myers) :

1. Pengujian adalah proses eksekusi suatu program dengan maksud menemukan kesalahan.
2. Test case yg baik adalah test case yg memiliki probabilitas tinggi untuk menemukan kesalahan yg belum pernah ditemukan sebelumnya.
3. Pengujian yg sukses adalah pengujian yg mengungkap semua kesalahan yg belum pernah ditemukan sebelumnya.


PRINSIP PENGUJIAN (diusulkan Davis) :
1. Semua pengujian harus dapat ditelusuri sampai ke persyaratan pelanggan.
2. Pengujian harus direncanakan lama sebelum pengujian itu dimulai.
3. Prinsip Pareto berlaku untuk pengujian perangkat lunak. Prinsip Pareto mengimplikasikan 80% dari semua kesalahan yg ditemukan selama pengujian sepertinya akan dapat ditelusuri sampai 20% dari semua modul program.
4. Pengujian harus mulai "dari yg kecil" dan berkembang ke pengujian "yang besar".
5. Pengujian yg mendalam tidak mungkin.
6. Paling efektif, pengujian dilakukan oleh pihak ketiga yg independen.

TESTABILITAS
Testabilitas perangkat lunak adalah seberapa mudah sebuah program komputer dapat diuji. Karena pengujian sangat sulit, perlu diketahui apa yg dapat dilakukan untuk membuatnya menjadi mudah.

Karakteristik perangkat lunak yg diuji :

* OPERABILITAS, semakin baik dia bekerja semakin efisien dia dapat diuji.
* OBSERVABILITAS, apa yg anda lihat adalah apa yg anda uji.
* KONTROLABILITAS, semakin baik kita dapat mengontrol perangkat lunak semakin banyak pengujian yg adapat diotomatisasi dan dioptimalkan.
* DEKOMPOSABILITAS, dengan mengontrol ruang lingkup pengujian kita dapat lebih cepat mengisolasi masalah dan melakukan pengujian kembali.
* KESEDERHANAAN, semakin sedikit yg diuji semakin cepat pengujian.
* STABILITAS, semakin sedikit perubahan semakin sedikit gangguan pengujian.
* KEMAMPUAN DIPAHAMI, semakin banyak informasi yg dimiliki semakin detail pengujiannya.

ATRIBUT PENGUJIAN YG BAIK :
* Memiliki probabilitas yg tinggi menemukan kesalahan.
* Tidak redundan.
* Harusnya ‘jenis terbaik’.
* Tidak boleh terlalu sederhana atau terlalu kompleks.



DESAIN TEST CASE

Terdapat bermacam-macam rancangan metode test case yg dapat digunakan, semua menyediakan pendekatan sistematis untuk uji coba, yg terpenting metode menyediakan kemungkinan yg cukup tinggi menemukan kesalahan.

Terdapat 2 macam test case:

1. Pengetahuan fungsi yg spesifik dari produk yg telah dirancang untuk diperlihatkan, test dapat dilakukan untuk menilai masing-masing fungsi apakah telah berjalan sebagaimana yg diharapkan.
2. Pengetahuan tentang cara kerja dari produk, test dapat dilakukan untuk memperlihatkan cara kerja dari produk secara rinci sesuai dengan spesifikasinya.

Dua macam pendekatan test yaitu :

1. Black Box Testing

Test case ini bertujuan untuk menunjukkan fungsi perangkat lunak tentang cara beroperasinya, apakah pemasukan data keluaran telah berjalan sebagaimana yang diharapkan dan apakah informasi yang disimpan secara eksternal selalu dijaga kemutakhirannya.

Tehnik pengujian black-box berfokus pada domain informasi dari perangkat lunak, dengan melakukan test case dengan menpartisi domain input dari suatu program dengan cara yang memberikan cakupan pengujian yang mendalam.

Metode pengujian graph-based mengeksplorasi hubungan antara dan tingkah laku objek-objek program. Partisi ekivalensi membagi domain input ke dalam kelas data yang mungkin untuk melakukan fungsi perangkat lunak tertentu. Analisis nilai batas memeriksaa kemampuan program untuk menangani data pada batas yang dapat diterima.

Metode pengujian yang terspesialisasi meliputi sejumlah luas kemampuan perangkat lunak dan area aplikasi. GUI, arsitektur client/ server, dokumentasi dan fasilitas help dan sistem real time masing-masing membutuhkan pedoman dan tehnik khusus untuk pengujian perangkat lunak.

2. White Box Testing

Adalah meramalkan cara kerja perangkat lunak secara rinci, karenanya logikal path (jalur logika) perangkat lunak akan ditest dengan menyediakan test case yang akan mengerjakan kumpulan kondisi dan atau pengulangan secara spesifik. Secara sekilas dapat diambil kesimpulan white box testing merupakan petunjuk untuk mendapatkan program yang benar secara 100%.

Pengujian white-box berfokus pada struktur control program. Test case dilakukan untuk memastikan bahwa semua statemen pada program telah dieksekusi paling tidak satu kali selama pengujian dan bahwa semua kondisi logis telah diuji. Pengujian basic path, tehnik pengujian white-box, menggunakan grafik (matriks grafiks) untuk melakukan serangkaian pengujian yang independent secara linear yang akan memastikan cakupan.

Pengujian aliran data dan kondisi lebih lanjut menggunakan logika program dan pengujian loop menyempurnakan tehnik white-box yang lain dengan memberikan sebuah prosedur untuk menguji loop dari tingkat kompleksitas yang bervariasi. Pengujian black-box didesain untuk mengungkap kesalahan pada persyaratan fungsional tanpa mengabaikan kerja internal dari suatu program.

STRATEGI UJI COBA PERANGKAT LUNAK

Strategi uji coba perangkat lunak memudahkan para perancang untuk menentukan keberhasilan system yg telah dikerjakan. Hal yang harus diperhatikan adalah langkah-langkah perencanaan dan pelaksanaan harus direncanakan dengan baik dan berapa lama waktu, upaya dan sumber daya yg diperlukan.

Strategi uji coba mempunyai karakteristik sbb :

* Pengujian mulai pada tingkat modul yg paling bawah, dilanjutkan dgn modul di atasnya kemudian hasilnya dipadukan.
* Teknik pengujian yang berbeda mungkin menghasilakn sedikit perbedaan (dalam hal waktu)
* Pengujian dilakukan oleh pengembang perangkat lunak dan (untuk proyek yang besar) suatu kelompok pengujian yang independen.
* Pengujian dan debugging merupakan aktivitas yang berbeda, tetapi debugging termasuk dalam strategi pengujian.

Pengujian perangkat lunak adalah satu elemen dari topik yang lebih luas yang sering diacu sebagai verifikasi dan validasi (V& V).

Verifikasi : Kumpulan aktifitas yg menjamin penerapan perangkat lunak benar-benar sesuai dgn fungsinya.

Validasi : Kumpulan aktivitas yang berbeda yang memastikan bahwa perangkat lunak yang dibangun dapat memenuhi keperluan pelanggan.

1. PENGUJIAN UNIT
Unit testing (uji coba unit) fokusnya pada usaha verifikasi pada unit terkecil dari desain perangkat lunak, yakni modul. Uji coba unit selalu berorientasi pada white box testing dan dapat dikerjakan paralel atau beruntun dengan modul lainnya.

2. PENGUJIAN INTEGRASI
Pengujian terintegrasi adl teknik yg sistematis untuk penyusunan struktur program, pada saat bersamaan dikerjakan uji coba untuk memeriksa kesalahan yg nantinya digabungkan dengan interface.

Metode pengujian

a) Top- down integration

Top down integration adalah pendekatan incremental dengan menggerakkan ke bawah melalui hirarki control, dimulai dengan control utama. Strategi intergrasi top-down memeriksa control mayor atau keputusan pada saat awal di dalam proses pengujian. Pada struktur program yang difaktorkan dengan baik, penarikan keputusan terjadi pada tingkat hirarki yang lebih tinggi sehingga terjadi lebih dulu.

Strategi top-down kelihatannya tidak sangat rumit, tetapi di dalam praktenya banyak menimbulkan masalah logistic. Biasanya masalah ini terjadi jika dibutuhkan pemrosesan di dalam hirarki pada tingkat rendah untuk menguji secara memadai tingkat yang lebih tinggi.

b) Pengujian Integrasi Bottom-up

Bottom up integration memulai konstruksi dan pengujian dengan modul atomic (modul pada tingkat paling rendah pada struktur program). Karena modul diintegrasikan dari bawah ke atas, maka pemrosesan yang diperlukan untuk modul subordinate ke suatu tuingkat yang diberikan akan selalu tersedia dan kebutuhan akan stub dapat dieliminasi. Strategi integrasi bottom-up dapat diimplementasi dengan langkah-langkah:

1. modul tingkat rendah digabung ke dalam cluster (build) yang melakukan subfungsi perangkat lunak spesifik.
2. Driver (program control untuk pengujian) ditulis untuk mengkoordinasi input dan output test case
3. cluster diuji
4. driver diganti dan cluster digabungkan dengan menggerakkannya ke atas di dalam struktur program.


PENGUJIAN DAN IMPLEMENTASI PERANGKAT LUNAK

Testing (Pengujian Perangkat Lunak)
Adalah elemen kritis dari jaminan kualitas perangkat lunak dan merepresentasikan kajian pokok dari spesifikasi, desain, dan pengkodean.
Pentingnya pengujian perangkat lunak dan implikasinya yang mengacu pada kualitas perangkat lunak tidak dapat terlalu ditekan karena melibatkan sederetan aktivitas produksi di mana peluang terjadinya kesalahan manusia sangat besar dan arena ketidakmampuan manusia untuk melakukan dan berkomunikasi dengan sempurna maka pengembangan perangkat lunak diiringi dengan aktivitas jaminan kualitas.
Meningkatnya visibilitas (kemampuan) perangkat lunak sebagai suatu elemen sistem dan “biaya” yang muncul akibat kegagalan perangkat lunak, memotivasi dilakukannya perencanaan yang baik melalui pengujian yang teliti. Pada dasarnya, pengujian merupakan satu langkah dalam proses rekayasa perangkat lunak yang dapat dianggap sebagai hal yang merusak daripada membangun.
Sejumlah aturan yang berfungsi sebagai sasaran pengujian pada perangkat lunak adalah:
1. Pengujian adalah proses eksekusi suatu program dengan maksud menemukan kesalahan
2. Test case yang baik adalah test case yang memiliki probabilitas tinggi untuk menemukan kesalahan yang belum pernah ditemukan sebelumnya
3. Pengujian yang sukses adalah pengujian yang mengungkap semua kesalahan yang belum pernah ditemukan sebelumnya
Sasaran itu berlawanan dengan pandangan yang biasanya dipegang yang menyatakan bahwa pengujian yang berhasil adalah pengujian yang tidak ada kesalahan yang ditemukan. Data yang dikumpulkan pada saat pengujian dilakukan memberikan indikasi yang baik mengenai reliabilitas perangkat lunak dan beberapa menunjukkan kualitas perangkat lunak secara keseluruhan, tetapi ada satu hal yang tidak dapat dilakukan oleh pengujian, yaitu pengujian tidak dapat memperlihatkan tidak adanya cacat, pengujian hanya dapat memperlihatkan bahwa ada kesalahan perangkat lunak.
Sebelum mengaplikasikan metode untuk mendesain test case yang efektif, perekayasa perangkat lunak harus memahami prinsip dasar yang menuntun pengujian perangkat lunak, yaitu:
 semua pengujian harus dapat ditelusuri sampai ke persyaratan pelanggan, maksudnya mengungkap kesalahan dari cacat yang menyebabkan program gagal.
 Pengujian harus direncanakan lama sebelum pengujian itu mulai, maksudnya semua pengujian dapat direncanakan dan dirancang sebelum semua kode dijalankan.
 Prinsip Pareto berlaku untuk pengujian perangkat lunak, maksudnya dari 80% kesalahan yang ditemukan selama pengujian dapat ditelusuri sampai 20% dari semua modul program.
 Pengujian harus mulai “dari yang kecil” dan berkembang ke pengujian “yang besar”, Selagi pengujian berlangsung maju, pengujian mengubah focus dalam usaha menemukan kesalahan pada cluster modul yang terintegrasi dan akhirnya pada sistem.
 Pengujian yang mendalam tidak mungkin karena tidak mungkin mengeksekusi setiap kombinasi jalur skema pengujian dikarenakan jumlah jalur permutasi untuk program menengah pun sangat besar.
 Untuk menjadi paling efektif, pengujian harus dilakukan oleh pihak ketiga yang independent
Dalam lingkungan yang ideal, perekayasa perangkat lunak mendesain suatu program computer, sebuah sistem atau produk dengan testabilitas dalam pikirannya. Hal ini memungkinkan individu yang berurusan dengan pengujian mendesain test case yang efektif secara lebih mudah. Testabilitas adalah seberapa mudah sebuah program computer dapat diuji. Karena sangat sulit, perlu diketahui apa yang dapat dilakukan untuk membuatnya menjadi lebih mudah. Procedural dan menggunakannya sebagai pedoman untuk menetapkan basis set dari jalur eksekusi.
Sasaran utama desain test case adalah untuk mendapatkan serangkaian pengujian yang memiliki kemungkinan tertinggi di dalam pengungkapan kesalahan pada perangkat lunak. Untuk mencapai sasaran tersebut, digunakan 4 kategori yang berbeda dari tehnik desain test case: Pengujian white-box, pengujian black-box, Integrasi Bottom-Up dan Integrasi Top-Down.

Pengujian white-box berfokus pada struktur control program. Test case dilakukan untuk memastikan bahwa semua statemen pada program telah dieksekusi paling tidak satu kali selama pengujian dan bahwa semua kondisi logis telah diuji. Pengujian basic path, tehnik pengujian white-box, menggunakan grafik (matriks grafiks) untuk melakukan serangkaian pengujian yang independent secara linear yang akan memastikan cakupan.
Pengujian aliran data dan kondisi lebih lanjut menggunakan logika program dan pengujian loop menyempurnakan tehnik white-box yang lain dengan memberikan sebuah prosedur untuk menguji loop dari tingkat kompleksitas yang bervariasi. Pengujian black-box didesain untuk mengungkap kesalahan pada persyaratan fungsional tanpa mengabaikan kerja internal dari suatu program.
Tehnik pengujian black-box berfokus pada domain informasi dari perangkat lunak, dengan melakukan test case dengan menpartisi domain input dari suatu program dengan cara yang memberikan cakupan pengujian yang mendalam.
Metode pengujian graph-based mengeksplorasi hubungan antara dan tingkah laku objek-objek program. Partisi ekivalensi membagi domain input ke dalam kelas data yang mungkin untuk melakukan fungsi perangkat lunak tertentu. Analisis nilai batas memeriksaa kemampuan program untuk menangani data pada batas yang dapat diterima.
Metode pengujian yang terspesialisasi meliputi sejumlah luas kemampuan perangkat lunak dan area aplikasi. GUI, arsitektur client/ server, dokumentasi dan fasilitas help dan sistem real time masing-masing membutuhkan pedoman dan tehnik khusus untuk pengujian perangkat lunak.

Integrasi Top-Down adalah pendekatan incremental dengan menggerakkan ke bawah melalui hirarki control, dimulai dengan control utama. Strategi intergrasi top-down memeriksa control mayor atau keputusan pada saat awal di dalam proses pengujian. Pada struktur program yang difaktorkan dengan baik, penarikan keputusan terjadi pada tingkat hirarki yang lebih tinggi sehingga terjadi lebih dulu.
Strategi top-down kelihatannya tidak sangat rumit, tetapi di dalam praktenya banyak menimbulkan masalah logistic. Biasanya masalah ini terjadi jika dibutuhkan pemrosesan di dalam hirarki pada tingkat rendah untuk menguji secara memadai tingkat yang lebih tinggi.

Pengujian Integrasi Bottom-up memulai konstruksi dan pengujian dengan modul atomic (modul pada tingkat paling rendah pada struktur program). Karena modul diintegrasikan dari bawah ke atas, maka pemrosesan yang diperlukan untuk modul subordinate ke suatu tuingkat yang diberikan akan selalu tersedia dan kebutuhan akan stub dapat dieliminasi. Strategi integrasi bottom-up dapat diimplementasi dengan langkah-langkah:
1. modul tingkat rendah digabung ke dalam cluster (build) yang melakukan subfungsi perangkat lunak spesifik.
2. Driver (program control untuk pengujian) ditulis untuk mengkoordinasi input dan output test case
3. cluster diuji
4. driver diganti dan cluster digabungkan dengan menggerakkannya ke atas di dalam struktur program.

IMPLEMENTASI ENTEPRISE SISTEM

Enterprise system adalah sistem berbasis software untuk membantu pengelolaan sistem informasi pada suatu organisasi dengan skala besar. Skala besar berarti volume transaksi yang besar, concern terhadap kualitas informasi yang tinggi, mengintegrasikan berbagai proses bisnis, lintas bidang (horisontal) maupun lintas strata (vertikal). Contoh dari ES adalah ERP (Enterprise Resource Planning) atau e-Business secara umum, e-Government, dan ingrated software lainnya.
Mengimplementasikan ES tidak mudah, atau setidaknya memilki strategi yang berbeda dengan sistem lain yang terbatas ruang lingkupnya, penggunanya dan tidak terpadu. Implementasi di sini bermakna bahwa software telah dapat digunakan dan bisa memberikan value bagi penggunanya sesuai tujuan pemanfaatan software tsb. Implementasi ini bisa dilakukan secara internal organisasi (oleh divisi IT/MIS) atau dengan pihak eksternal dalam kerangka proyek dan terikat legalitas berbentuk kontrak.
implementator sebagai pihak eksternal yang melakukan implementasi dan klien sebagai organisasi yang diimplementasikan softwarenya.
Implementasi ES berbeda dengan implementasi software berskala kecil atau yang penggunanya tunggal seperti MS Word, Database Rental VCD atau website, meskipun produknya sama-sama software yang berjalan di atas server dan membutuhkan konektivitas. Tentu nanti ada strategi yang berbeda, metode pemilihan bahan yang berbeda, tahapan yang berbeda, standar-standar tertentu, dst. Demikian pula dalam konteks software, bisa dipilah berdasar cakupan penggunaannya, bisa dilihat juga dari jenisnya (generik dan customized), yang masing-masing punya strategi implementasi yang berbeda. SE berkaitan dengan pengelolaan sistem informasi, yang tidak hanya bicara teknologi saja, tapi berkaitan dengan proses bisnis, struktur organisasi dan manusianya.
Pola pikir ”developer” adalah menganggap suatu problem bisa selesai dengan solusi berbasis software yang baik dan tepat. Tapi apakah cukup seperti itu? Dalam membangun solusi, ya itu cukup, tapi belum tentu menjamin kesuksesan implementasi. Pola pikir developer cenderung berfokus pada analisis dan development tidak pada implementasinya. Padahal sukses tidaknya proyek software, baik buruknya reputasi implementator, seringkali orang luar melihat pada keberhasilan implementasinya dan value yang didapatkan klien. ES untuk organisasi dengan puluhan divisi, ribuan orang, puluhan kepentingan, dan mungkin ratusan konflik. Apalagi jika software yang kita implementasikan bukan sekedar supporting tools tapi adalah core dari bisnis itu sendiri (konsep e-business). Cara implementasi dengan pola pikir seperti ini hanya akan menghasilkan solusi dan software yang bagus, tapi tidak optimal dan memberikan value untuk organisasi tsb, atau bahkan malah tidak pernah akan digunakan.
Implementator tidak bisa memposisikan diri sebagai project manager pada sebuah proyek yang berkaitan langsung dengan proses bisnis internal klien. Seorang project manager harus mampu mengelola semua resource berkaitan dengan proyek. Kadang kita tidak menyadari bahwa sebagaian besar resource dari proyek software justru berada di sisi organisasi klien. Sementara, project manager seharusnya memiliki akses ke seluruh resource tersebut, karena jika tidak, itu bukan project manager namanya.
Dalam kasus ini, maka project manager seharusnya justru berada di sisi klien, bukan implementator. Akan sia-sia jika aktivitas project planning, project controlling dsb sepenuhnya dilakukan oleh implementator, sementara klien hanya ”tahu beres” saja. Pada akhirnya aktivitas-aktivitas project management tsb hanya akan menghasilkan berkas-berkas dan dokumen administratif saja, yang pada kenyataannya tidak pernah dilaksanakan.
Peran yang paling pas untuk implementator adalah sebagai konsultan. Tugas utama dari konsultan adalah memberikan informasi, mendampingi, memfasilitasi dan menjadi motor ”behind the screen”. Tentu saja jika kontraknya melibatkan pengadaan software, konsultan juga akan melakukan development atau implementasi secara teknis, namun implementasi keseluruhannya harus dipimpin oleh klien sendiri melalui project manager. Jika klien tidak memiliki pengetahuan yang cukup untuk mengelola proyek software, itulah tugas konsultan untuk mendampinginya, sehingga proses project planning, control, evaluation, dst sepenuhnya akan berasal dari ide-ide, komitmen dan effort dari klien sendiri.
Tugas konsultan adalah memfasilitasi dan mengarahkannya. Model seperti ini yang kemudian memunculkan teknik JAD (Joint Application Design), yang intinya adalah melibatkan dan kolaborasi seluruh stakeholder proyek. salah satu fase dalam implementasi sistem adalah fase transisi, yang pasti akan menuntut perubahan baik kecil maupun besar. Adanya sistem baru, mau tidak mau akan merubah proses bisnis. Perubahan proses bisnis berarti perubahan cara kerja, alur kerja dan bahkan budaya kerja. Perubahan ini menyangkut aspek people dan proses bisnis, sehingga dikenal konsep change management.
Dalam eksekusinya, change ini harus dipimpin dan dimanage oleh leader di internal organisasi. Yang jelas seorang konsultan tidak hanya dituntut memiliki pengetahuan tentang software engineering dan hal-hal teknis, dan juga tidak cukup ditambah dengan pengalaman dan keterampilan project management, namun konsep dan bestpractice tentang change management, communication skill yang excellent sangat diperlukan.

JAD (Joint Application Development/Design) sebagai salah satu teknik manajemen dalam mengimplementasikan sebuah sistem informasi (SI) dalam konteks proyek. porsi terbesar dan terumit dari proses implementasi SI adalah justru pada proses transisinya, karena terkait banyak aspek tidak hanya di sisi teknologi tapi harus memahami sisi sosial, manajerial dan SDM.

Implementasi SI
Masalah terbesar dari implementasi SI adalah untuk mengetahui kebutuhan dari user, apalagi dengan karakter proyek :
• Sistem yang melibatkan multi-organisasi/divisi (penggunanya dari beberapa role dan divisi)
• Bisnis proses yang kompleks
• Kebutuhan yang sangat spesifik dan customized.
Dengan karakter proyek yang semacam ini, tidak cukup bagi seorang system analyst (SA) menentukan kebutuhan hanya dengan teknik wawancara, observasi ataupun kuesioner. Banyak kasus ditemui, bahwa pada akhirnya apa yang kita dapatkan dari proses analisa kebutuhan di awal proyek, tidak match dengan kebutuhan sesungguhnya dari pengguna sistem, sehingga sistem akhirnya tidak dapat digunakan dengan baik. Masalah lain adalah di sisi waktu. Teknik-teknik seperti itu seringkali sangat time consuming, sangat membutuhkan waktu yang lama. Sering juga tim developer dihadapkan situasi bahwa tidak semua stakeholder proyek memiliki kepedulian yang sama dengan yang lain. Seorang manajer tidak mengetahui kebutuhan detail dari staf-staf operasional, sementara itu staf operasional mungkin juga tidak memahami sepenuhnya spirit, goal dari SI. JAD merupakan sebuah teknik yang berfokus pada keterlibatan dan komitmen pengguna dalam menentukan kebutuhan dan merancang (desain) aplikasi. JAD biasanya dilakukan dalam bentuk tim yang merupakan gabungan dari seluruh stakeholder proyek, yang bekerja dalam bentuk workshop-workshop atau forum diskusi.
Kenapa workshop ? karena teknik JAD ini bukanlah sekedar rapat-rapat, yang biasa dilakukan dalam sebuah proyek dan melibatkan seluruh stakeholder proyek. JAD adalah tim yang nantinya akan membuat rancangan dan mengawasi, memonitor bersama jalannya proyek.

Siapa yang perlu terlibat ?
Secara garis besar yang perlu terlibat adalah :
1. Sponsor. Sponsor ini berarti project owner, memiliki kedudukan yang cukup tinggi dalam organisasi dan sebagai pengambil keputusan tertinggi dalam pengelolaan sistem informasi. Satu hal yang penting dilakukan oleh seorang project owner adalah komitmen yang kuat akan implementasi SI yang dilakukan. Without the executive sponsor's commitment, people do not show up for workshops on time or sometimes at all. Schedules change and projects are delayed. In short, without an executive sponsor, there is no project!
2. Business Users. Business User ini terdiri dari 2 jenis, yaitu real end user dan representative end user. Real end user adalah person yang melakukan pekerjaan real di lapangan. Dalam kasus, ini adalah operator-operator. Sedangkan representative end user adalah person yang mengetahui seharusnya bisnis proses itu dilakukan, memahami spirit dan goal dari sistem yang dikelolanya. Biasanya ini adalah kepala bagian, manajer, atau operator senior.
3. System Analyst (Tim Developer). Person/tim ini yang akan in-charge dari sisi teknologi dan proses engineeringnya.
4. System Experts. Tidak semua referensi mencantumkan peran ini. Perannya lebih seperti konsultan yang memahami seluk beluk bisnis proses dari sisi konseptual dan berbasis pengalaman.
5. Facilitator. Seorang fasilitator berfungsi sebagai moderator dan mengarahkan setiap aktivitas JAD yang melibatkan banyak pihak, untuk menjadi efektif. Seorang fasilitator harus memiliki kecakapan yang baik dalam berkomunikasi, memberikan stimulus-stimulus dan trik-trik agar diskusi bisa berjalan dengan baik.
Tentu saja, setelah penyusunan tim JAD, diperlukan strategi yang tepat dalam melakukan workshop-workshop, sehingga proses dilakukan lebih efektif. Yang jelas, teknik ini sudah terbuktif efektif dalam menyelesaikan masalah-masalah implementasi SI.


Kesimpulan studi kasus oleh Standish grouph report
Success Criteria Points DMV CONFIRM HYATT ITAMARATI
1. keterlibatan pemakai 19 NO ( 0) NO ( 0) YES (19) YES (19)
2. dukungan manajemen eksekutif 16 NO ( 0) YES (16) YES (16) YES (16)
3. kebutuhan yg jelas 15 NO ( 0) NO ( 0) YES (15) NO ( 0)
4. perencanaan yg sesuai 11 NO ( 0) NO ( 0) YES (11) YES (11)
5. harapan yg realistis 10 YES(10) YES (10) YES(10) YES (10)
6. proyek terkecil 9 NO ( 0) NO ( 0) YES ( 9) YES ( 9)
7. staff yg kompeten 8 NO ( 0) NO ( 0) YES ( 8) YES ( 8)
8. pemilik 6 NO ( 0) NO ( 0) YES ( 6) YES ( 6)
9. visi & sasaan ygjelas 3 NO ( 0) NO ( 0) YES ( 3) YES ( 3)
10. kerja keras, staff dipusatkan 3 NO ( 0) YES ( 3) YES ( 3) YES ( 3)
TOTAL 100 10 29 100 85


Sukses / gagalnya proyek
Project Success Factors % of Responses
1. keterlibatan pemakai 15.9%
2. dukungan manajemen eksekutif 13.9%
3. kebutuhan yg jelas 13.0%
4. perencanaaan yg sesuai 9.6%
5. harapan yg realistis 8.2%
6. proyek terkecil 7.7%
7. staff yg kompeten 7.2%
8. pemilik 5.3%
9. visi dan sasaran yg jelas 2.9%
10.kerja keras, staff dipusatkan 2.4%
Lainnya 13.9%






Project Challenged Factors % of Responses
1. tidak ada masukkan dari pemakai 12.8%
2. kebutuhan & spesifikasi tg tdk sempurna 12.3%
3. mengubah kebutuhan dan spesifikasi 11.8%
4. tidak ada dukungan dr manajemen eksekutif 7.5%
5. ketidakmampuan teknologi 7.0%
6. tidak ada sumber daya 6.4%
7. harapan yg tdk realistis 5.9%
8.sasaran tdk jelas 5.3%
9. batasan waktu tdk realistis 4.3%
10. teknologi baru 3.7%
Lainnya 23.0%

Project Impaired Factors % of Responses
1. kebutuhan tdk lengkap 13.1%
2. tidak ada masukan/keterlibatan dr pemakai 12.4%
3. tidak ada sumber daya 10.6%
4. harapan yg tdk realistis 9.9%
5. tidak ada dukungan dr manajemen eksekutif 9.3%
6. perubahan kebutuhan dan spesifikasi 8.7%
7. tidak ada perencanaan 8.1%
8. tidak diperlukan sama sekali 7.5%
9. tidak ada manajemen IT 6.2%
10. buta teknologi 4.3%
Lainnya 9.9%

Istilah
DMV : the California department of motor vehicles
Banco itamarti : bank brazil
Confirm : American airlines utk penyewaan mobil di hotel marriott
& hilton

;/==============================\;
; PROGRAM : BRA1.ASM ;
; AUTHOR : S’to ;
; FUNGSI : MENCETAK KALIMAT ;
; DENGAN BASE ;
; RELATIVE ADDRESSING;
; ;
;\==============================/;

.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
Kalimat DB 'NYAMUK GORENG' ; 13 karakter
Proses:
XOR BX,BX ; BX=0 Untuk penunjuk Offset
MOV CX,13 ; Counter LOOP
Ulang :
MOV DL,Kalimat[BX] ; Ambil karakter yang ke BX
MOV AH,02 ; Servis untuk cetak karakter
INT 21h ; Cetak Karakter
INC BX ; BX:=BX+1
LOOP Ulang ; Lompat ke Ulang sampai CX=0
INT 20h ; Selesai, kembali ke DOS !!
END TData


;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;
; Program: kal0.asm ;
; Oleh : S’to ;
; Fungsi : Mencetak String ;
; dengan Int 21 servis 9 ;
;=====================================;
.MODEL SMALL
.CODE
ORG 100h
Tdata : JMP Proses
Kal0 DB 'PROSES PENCETAKAN STRING ',13,10,'$'
Kal1 DB 'DIBELAKANG TANDA $ TIDAK BISA DICETAK '
Proses:
MOV AH,09h ; Servis ke 9
MOV DX,OFFSET Kal0 ; Ambil Alamat Offset Kal0
INT 21h ; Cetak perkarakter sampai tanda $
LEA DX,Kal0 ; Ambil Alamat Offset Kal0
INT 21h ; Cetak perkarakter sampai tanda $
LEA DX,Kal0+7 ; Ambil Alamat Offset KAl0+7
INT 21h ; Cetak perkarakter sampai tanda $
LEA DX,KAL1 ; Ambil Offset kal1
INT 21h ; Cetak perkarakter sampai ketemu $
INT 20h ; Selesai, kembali ke DOS
END Tdata

;/=============================================\;
; Program : ATTR-KLM.ASM ;
; Author : S’to ;
; Fungsi : Mencetak kalimat disertai ;
; atributnya ;
;-----------------------------------------------;
; INT 10h ;
;-----------------------------------------------;
; Input : ;
; AX = 1300h ;
; BL = Atribut ;
; BH = Halaman tampilan ;
; DL = Posisi X ;
; DH = Posisi Y ;
; CX = Panjang kalimat;
; ES:BP = Alamat awal string ;
; ;
;\=============================================/;
.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
Kal0 DB ' Menulis kalimat dengan Atributnya '
Proses:
MOV AX,1300h ; Servis 13h subfungsi 00
MOV BL,10010101b ; Atribut tulisan
MOV BH,00 ; Halaman tampilan 0
MOV DL,20 ; Posisi X
MOV DH,12 ; Posisi Y
MOV CX,35 ; Banyaknya karakter dalam string
LEA BP,Kal0 ; ES:BP alamat string
INT 10h ; Cetak kalimat !
INT 20h ; Selesai, kembali ke DOS
END TData


;/========================================\;
; Program : READKEY.ASM ;
; Author : S’to ;
; Fungsi : Input satu karakter ;
; dari keyboard. ;
;==========================================;
; INTERUPSI 16h ;
;==========================================;
; Input: OutPut: ;
; AH = 0 Jika tombol biasa, maka: ;
; AL = ASCII ;
; AH = SCAN ;
; ;
; Jika Tombol khusus, maka ;
; AL = 00 ;
; AH = Extended ;
; ;
;\========================================/;
.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
T_ASCII DB 13,10,'Ini adalah tombol ASCII : $'
T_Extended DB 13,10,'Ini adalah tombol Extended $'
Proses :
MOV AH,0 ; Servis Input satu karakter
INT 16h ; Laksanakan
PUSH AX ; Simpan hasil pembacaan pada stack
CMP AL,00 ; Apakah ini karakter extended ?
JE Extended ; Ya !, Lompat ke Extended
ASCII:
LEA DX,T_ASCII ; Ambil alamat efektif T_ASCII
MOV AH,09 ; Servis cetak kalimat
INT 21h ; Cetak kalimat !
POP AX ; Ambil kembali nilai AX pada stack
MOV DL,AL ; Ambil kode ASCII yang ditekan
MOV AH,2 ; Servis cetak karakter
INT 21h ; Cetak karakter !
CMP AL,'Q' ; Apakah yang ditekan huruf 'Q' ?
JE exit ; Ya !, lompat ke Exit
CMP AL,'q' ; Apakah yang ditekan huruf 'q' ?
JE exit ; Ya !, lompat ke Exit
JMP Proses ; Lompat ke Proses
Extended:
LEA DX,T_Extended ; Ambil alamat efektif T_Extended
MOV AH,09 ; Servis cetak kalimat
INT 21h ; Cetak kalimat !
JMP Proses ; Lompat ke Proses
exit: INT 20h ; Kembali ke DOS !
END TData


;/=========================================================\;
; Program : IN-KAL.ASM ;
; Author : S’to ;
; Fungsi : Input Kalimat dari ;
; keyboard. ;
;===========================================================;
; INTERUPSI 21h ;
;===========================================================;
; Input: ;
; AH = 0Ah ;
; DS:DX = Penampung dengan spesifikasi: ;
; Byte 1 = Maksimum karakter yang dapat dimasukkan ;
; Byte 2 = Akan dijadikan Indikator banyaknya ;
; karakter yang dimasukkan ;
; Byte 3 keatas = Tempat hasil masukan ditampung ;
; ;
; ;
;\=========================================================/;
.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
T_Enter EQU 0Dh
Kal0 DB 'Ketikkan satu Kalimat : $'
Kal1 DB 13,10,'Kalimat pada buffer : $'
Buffer DB 23,?,23 DUP(?)
Proses : MOV AH,09
LEA DX,Kal0
INT 21h ; Cetak kalimat Kal0
MOV AH,0Ah ; Servis Input kalimat
LEA DX,Buffer ; DX menunjuk pada offset Buffer
INT 21h ; Input kalimat !
MOV AH,09
LEA DX,Kal1
INT 21h ; Cetak kalimat Kal1
LEA BX,Buffer+2 ; BX menunjuk byte ke 3 Buffer
Ulang:
CMP BYTE PTR [BX],T_Enter ; Apakah karakter Enter?
JE EXIT ; Ya! Lompat ke Exit
MOV DL,[BX] ; Masukkan karakter pada DL
MOV AH,02 ; Servis cetak karakter
INT 21h ; Cetak karakter
INC BX ; BX := BX+1
JMP Ulang ; Lompat ke Ulang
EXIT: INT 20h ; Kembali ke DOS !
END TData


;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;
; PROGRAM : PROC_KAR.ASM ;
; FUNGSI : MENCETAK KARATER ;
; DENGAN PROCEDURE ;
; ;
;==========================S’to=;
.MODEL SMALL
.CODE
ORG 100h
Proses : CALL Cetak_Kar ; Panggil Cetak_Kar
INT 20h
Cetak_Kar PROC NEAR
MOV AH,02h
MOV DL,'S'
INT 21h ; Cetak karakter
RET ; Kembali kepada si pemanggil
Cetak_Kar ENDP ; END Procedures
END Proses


.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
Kar DB ?
Klm DB 'BATMAN SI MANUSIA KELELAWAR ' ; 28 Karakter
Proses : MOV CX,28 ; Banyaknya pengulangan
XOR BX,BX ; Addressing Mode
Ulang :
MOV DL,Klm[BX]
MOV Kar,DL
CALL Cetak_Kar ; Panggil Cetak_Kar
INC BX
LOOP Ulang
INT 20h
Cetak_Kar PROC NEAR
PUSH AX ; Simpan semua register
PUSH DX ; Yang digunakan
MOV AH,02h
MOV DL,Kar
INT 21h ; Cetak karakter
POP DX ; Kembalikan semua register
POP AX ; Yang disimpan
RET ; Kembali kepada si pemanggil
Cetak_Kar ENDP ; END Procedures
END TData
Program 16.2. Menggunakan Procedure





;/====================================\;
; Program : TPTK.ASM ;
; Fungsi : Contoh menggunakan ;
; pustaka macro ;
;\====================================/;
INCLUDE PUSTAKA.MCR ; Gunakan file PUSTAKA.MCR
.MODEL SMALL
.CODE
ORG 100h
TData : JMP Proses
Kal0 DB 'PENGGUNAAN PUSTAKA MACRO $'
Proses:
Cetak_Klm Kal0 ; Cetak Kalimat Kal0
Cetak_Kar 'Y' ; Cetak Huruf 'Y'
INT 20h
END TData


;/========================\;
; Program : PUSTAKA.MCR ;
;\========================/;
Cetak_Kar MACRO Kar ; Macro untuk mencetak
MOV AH,02 ; Karakter
MOV DL,Kar
INT 21h
ENDM
Cetak_Klm MACRO Klm ; Macro untuk mencetak
LEA DX,Klm ; kalimat
MOV AH,09
INT 21h
ENDM
Program 17.3. Pustaka.MCR




Tulis_Kar MACRO X,Y,Kar,Attr
MOV AX,0B800h
MOV ES,AX ; ES Menunjuk pada segment layar
MOV AH,Y
MOV AL,160
MUL AH ; Hitung offset baris
MOV BX,AX ; Simpan hasilnya pada BX
MOV AH,X
MOV AL,2
MUL AH ; Hitung offset kolom
ADD BX,AX ; Tambahkan hasilnya pada BX
MOV AL,Kar ; AL=karakter yang akan ditampilkan
MOV AH,Attr ; AH=Atribut yang akan ditampilkan
MOV ES:[BX],AL ; Tampilkan Karakter dan atributnya
MOV ES:[BX+1],AH ; pada posisi kolom X dan baris Y
ENDM

;/===============================================\;
; Program : LAYAR1.ASM ;
; Author : S’to ;
; ;
; Fungsi : Menampilkan karakter dan atributnya ;
; dengan menuliskannya langsung pada ;
; memory layar ;
;\===============================================/;
.MODEL SMALL
.CODE
ORG 100h
Proses :
Tulis_Kar 40 12 'S' 95 ; Tulis karakter 'S' dengan
; no atribut 95 pada posisi
INT 20h ; kolom 40 dan baris 12
END Proses



Cls MACRO ; Macro untuk menghapus layar
MOV AX,0600h
XOR CX,CX
MOV DX,184Fh
MOV BH,10 ; Atribut Hijau diatas hitam
INT 10h
ENDM
GotoXY MACRO X,Y ; Macro untuk memindahkan kursor
MOV AH,02
XOR BX,BX
MOV DH,Y
MOV DL,X
INT 10h
ENDM
SimpanL MACRO ; Macro untuk menyimpan seluruh
LOCAL Ulang ; isi layar monitor
MOV AX,0B800h
MOV ES,AX
MOV CX,4000
XOR BX,BX
Ulang:
MOV AL,ES:[BX]
MOV Layar[BX],AL
INC BX
LOOP Ulang
ENDM
BalikL MACRO ; Macro untuk mengembalikan semua
LOCAL Ulang ; isi layar yang telah disimpan
MOV CX,4000
XOR BX,BX
Ulang:
MOV AL,Layar[BX]
MOV ES:[BX],AL
INC BX
LOOP Ulang
ENDM
Sorot MACRO X,Y ; Macro untuk membuat sorotan
LOCAL Ulang ; pada menu
MOV BL,Y
MOV AL,160
MUL BL
MOV BX,AX
MOV AL,X
MOV AH,2
MUL AH
ADD BX,AX
INC BX ; Alamat warna pada posisi X,Y
MOV CX,25 ; Panjangnya sorotan
Ulang:
MOV BYTE PTR ES:[BX],4Fh ; Atribut sorotan
; putih diatas merah
ADD BX,2
LOOP Ulang
ENDM
Readkey MACRO ; Macro untuk membaca masukan dari
MOV AH,00 ; keyboard.
INT 16h ; hasilnya AH=Extended, AL=ASCII
ENDM
MenuL MACRO String ; Macro untuk mencetak menu
MOV AH,09
LEA DX,String
INT 21h
ENDM
;/==============================================\;
; Program : SOROT.ASM ;
; Author : S’to ;
; Fungsi : Membuat menu sorot untuk ;
; digunakan program ;
;\==============================================/;
.MODEL SMALL
.CODE
ORG 100h
TData: JMP Proses
Layar DB 4000 DUP (?)
Menu DB 9,9,'+=============================+',13,10
DB 9,9,'| »»» MENU SOROT ««« |',13,10
DB 9,9,'+=============================+',13,10
DB 9,9,'| |',13,10
DB 9,9,'| 1. Pilihan pertama |',13,10
DB 9,9,'| 2. Pilihan Kedua |',13,10
DB 9,9,'| 3. Pilihan Ketiga |',13,10
DB 9,9,'| 4. Pilihan Keempat |',13,10
DB 9,9,'| |',13,10
DB 9,9,'+=============================+$'
PosX DB 22 ; Posisi kolom mula-mula
PosY DB 12 ; Posisi baris mula-mula
Panah_Atas EQU 72 ; Kode tombol panah atas
Panah_Bawah EQU 80 ; Kode tombolpanah bawah
TEnter EQU 0Dh ; Kode tombol Enter
Proses :
Cls ; Hapus layar
GotoXY 0 8 ; kursor = 0,8
MenuL Menu ; Gambar menu
SimpanL ; Simpan isi layar
Ulang :
BalikL ; Tampilkan isi layar yang
; disimpan
Sorot PosX,PosY ; Sorot posisi X,Y
Masukan:
Readkey ; Baca masukan dari keyboard
CMP AH,Panah_Bawah ; Panah bawah yang ditekan ?
JE Bawah ; Ya! lompat bawah
CMP AH,Panah_Atas ; Panah atas yang ditekan ?
JE CekY ; Ya, lompat CekY
CMP AL,TEnter ; Tombol enter yang ditekan ?
JNE Masukan ; Bukan, lompat ke ulangi
JMP Selesai ; Ya, lompat ke selesai
CekY :
CMP PosY,12 ; Apakah sorotan paling atas ?
JE MaxY ; Ya! lompat ke MaxY
DEC PosY ; Sorotkan ke atas
JMP Ulang ; Lompat ke ulang
MaxY :
MOV PosY,15 ; PosY=Sorotan paling bawah
JMP Ulang ; lompat ke ulang
Bawah :
CMP PosY,15 ; apakah sorotan paling bawah ?
JE NolY ; Ya! lompat ke NolY
INC PosY ; Sorotkan ke bawah
JMP Ulang ; Lompat ke ulang
NolY :
MOV PosY,12 ; Sorotan paling atas
JMP Ulang ; Lompat ke ulang
Selesai:
INT 20h
END TData



.model small
.code
org 100h
start : jmp mulai
kt1 db “Masukkan Angka [1..3] : $”,13,10
kt2 db “Saya Laki-laki $”,13,10
kt3 db “Saya Perempuan $”,13,10
kt4 db “Saya Bukan Keduanya $”,13,10
mulai : mov ax,03h
int 10h
mov ah,09h
lea dx,kt1
int 21h
mov ah,01h
cmp al,’1’
je laki
cmp al,’2’
je wanita
cmp al,’3’
je bukan
laki : mov ah,09h
lea dx,kt2
int 21h
jmp selesai
wanita : mov ah,09h
lea dx,kt3
int 21h
jmp selesai


bukan : mov ah,09h
lea dx,kt4
int 21h
jmp selesai
selesai : int 20h
end start



.model small
.code
org 100h
start : jmp mulai
menu db “** MENU UTAMA **”13,10
db “<>”,13,10
db “********************”,13,10
db “1. Sarapan Pagi “,13,10
db “2. Makan Siang”,13,10
db “3. Makan Malam”,13,10
db “4. Exit”,13,10
db “------------------------------“,13,10
db “Tentukan Pilihan Anda [1..4] : $”
jwb1 db “1. Nasi Goreng”,13,10
db “2. Udang Goreng”,13,10
db “3. The Manis $”
jwb2 db “1. Nasi Putih”,13,10
db “2. Cumi Rebus”,13,10
db “3. Ikan Bakar”,13,10
db “4. Air Putih $”

jwb 3 db “1. Nasi Putih”,13,10
db “2. Kerang Rebus”,13,10
db “3. Kepiting Panggang:,13,10
db “4. Air Putih $”
mulai : mov ax,03h
int 10h
mov ah,02h
lea dx,menu
int 21h
mov ah,01h
cmp al,’1’
je pil1
cmp al,’2’
je pil2
cmp al,’3’
je pil3
jmp selesai
pil1 : mov ah,09h
lea dx,jwb1
int 21h
jmp selesai
pil2 : mov ah,09h
lea dx,jwb2
int 21h
jmp selesai
pil3 : mov ah,09h
lea dx,jwb3
jmp selesai
selesai : int 20h
end start

ORGANISASI KOMPUTER DASAR
A. KOMPONEN SISTEM
Sebuah komputer moderen/digital dengan program yang
tersimpan di dalamnya merupakan sebuah system yang
memanipulasi dan memproses informasi menurut kumpulan
instruksi yang diberikan. Sistem tersebut dirancang dari
modul-modul hardware seperti :
1. Register
2. Elemen aritmatika dan logika
3. Unit pengendali
4. Unit memori
5. Unit masukan/keluaran (I/O)
Komputer dapat dibagi menjadi 3 bagian utama, yaitu :
1. Unit pengolahan pusat (CPU)
2. Unit masukan/keluaran (I/O)
3. Unit memori

CPU mengendalikan urutan dari semua pertukaran informasi
dalam komputer dan dengan dunia luar melalui unit I/O.
Sedangkan unit memori terdiri dari sejumlah besar lokasi
yang menyimpan program dan data yang sedang aktif
digunakan CPU. Ketiga unit tersebut dihubungkan dengan
berbagai macam bus.

Bus adalah sekelompok kawat atau sebuah jalur fisik yang
berfungsi menghubungkan register-register dengan unitunit
fungsional yang berhubungan dengan tiap-tiap modul.
Informasi saling dipertukarkan di antara modul dengan
melalui bus.

B. OPERASI MIKRO
Adalah operasi tingkat rendah yang dapat dilakukan oleh
komputer atau CPU sehingga fungsi-fungsi operasi akan
dihasilkan untuk memindahkan data antar register.
Salah satu cara dalam melakukan operasi mikro tersebut
dengan menggunakan bahasa transfer register / Register
Transfer Language (RTL).
RTL adalah sebuah bahasa yang digunakan untuk
menjabarkan atau melaksanakan operasi mikro.
SIC (SIMPLIFIED INSTRUCTIONAL COMPUTER)
Komputer yang didasarkan pada SIC ini merupakan komputer yang
termasuk dalam perancangan arsitektur yang sangat sederhana dan
komputer ini dipersembahkan oleh BECK (1985).
Struktur Mesin SIC terdiri dari :
1. CPU
2. Unit memori
3. Minimal satu unit prinati I/O
Untuk CPU yang digunakan terdiri dari 13 register khusus, seperti
yang ada pada table di bawah ini.

NO REGISTER UKURAN (bit) NAMA
1 A 24 Accumulator
2 X 15 Register Index
3 L 15 Register Linkage
4 PC 15 Program Counter
5 IR 24 Instruction Register
6 MBR 24 Memori Buffer Register
7 MAR 15 Memori Address Register
8 SW 11 Status Word
9 C 2 Counter
10 INT 1 Interrupt Flag
11 F 1 Fetch Cycle Flag
12 E 1 Execute Cycle Flag
13 S 1 Start / Stop Flag

Penggunaan register-register pada SIC
1. Register A = register yang digunakan untuk proses
perhitungan
2. Register X = register yang digunakan untuk mode
pengalamatan berindex
3. Register PC = register yang menyimpan alamat instruksi
berikutnya
4. Register L = register yang menyimpan alamat asal sebelum
melakukan subroutines
5. Register IR = register yang menyimpan instruksi yang
sedang dikerjakan
6. Register MBR = register yang digunakan untuk proses
masukan atau keluaran data dari memori
7. Register MAR = register yang menyimpan alamat memori
untuk proses pembacaan atau penulisan
8. SW = register yang berisi informasi status relatif terhadap
instruksi sebelumnya
9. C = register yang membangkitkan signal waktu t0, t1, t2, t3
10. INT = register yang menentukan apakah signal interrupt
telah diterima
11. F = register yang digunakan dalam proses”siklus fetch’
12. E = register khusus yang digunakan dalam proses “siklus
eksekusi’
13. S = register yang akan mengaktifkan register C
Kumpulan Instruksi SIC
Ada 21 instruksi SIC yang digunakan, dimana pada instruksi ini
m menunjukkan address memori dari operand dan (m)
menunjukkan nilai yang disimpan pada address memori tersebut.
Opcode instruksinya ditulis dalam notasi heksadesimal.
• JSUB dan RSUB merupakan dua instruksi yang berhubungan
dengan subrutin. JSUB menyimpan PC saat ini ke L dan
kemudian melompat ke subrutin dengan menyimpan operand
ke PC. RSUB kembali dari subrutin dengan melompat ke lokasi
yang dinyatakan oleh L.
• Instruksi TD digunakan untuk menguji piranti I/O sebelum
berusaha untuk membaca dari atau menulis ke piranti
tersebut.Hasil pengujian tersebut disimpan di dalam kode
kondisi (condition code), field CC, pada SW. Panjang field ini 2
bit dan digunakan untuk mewakili salah satu dari tiga nilai <, =, >
Jika instruksi TD dijalankan, nilai field CC aka di-set menurut
kode berikut :
< menunjukkan bahwa piranti telah siap = menunjukan bahwa piranti sedang sibuk dan tidak dapat digunakan pada saat itu > menunjukkan bahwa piranti tidak beroperasi
• Instruksi COMP digunakan juga untuk men-set field CC. Nilai
yang disimpan field CC setelah sebuah instruksi COMP setelah
sebuah instruksi COMP menggambarkan hubungan antara A
dan operand instruksi
• Instruksi IRT digunakan oleh interrupt handler agar
menyebabkan lompatan kembali ke tempat dimana CPU
berada sebelum intrupsi terjadi.
Jika interupsi terjadi, CPU akan menyimpan PC saat ini ke
dalam memori pada address 0.
Untuk kembali dari sebuah interupsi , isi dari alamat memori
ini harus di-load kembali ke dalam PC.
• Instruksi-instruksi lainnya adalah operasi aritmatika dan
logika, transfer dari pengendalian(jump), loading register,
storing register atau membaca dan menulis ke piranti I/O.

SOAL 2
#include (iostream.h>
#include (string.h>
#include (dos.h>
#include (stdlib.h>
#include (conio.h>

class elemen
{
struct list
{
int bil;
struct list *next;
};

public:
typedef struct list NODE;
typedef NODE *PNODE;

void tampil_stack (PNODE atas);
void PUSH (PNODE *atas, PNODE baru);
void POP (PNODE *atas);
PNODE masuk_stack (void);

void tampil_queue (PNODE head);
void insert (PNODE *tail,PNODE *head, PNODE baru);
void INSERT_QUEUE (PNODE *tail,PNODE *head, PNODE baru);
void DELETE_QUEUE (PNODE *head, PNODE *tail);
PNODE masuk_queue (void);
};

void elemen :: tampil_stack (PNODE atas)
{
PNODE pos;
pos = atas;
cout<<"\n\nbilangan : "; while(pos != NULL) { cout< bil<<", "; pos = pos -> next;
}
cout<<"\n\n\n [TEKAN ENTER UNTUK MELANJUTKAN]"; getch(); } void elemen :: PUSH (PNODE *atas, PNODE baru) { if (*atas == NULL) { *atas = baru; } else{ baru -> next = *atas;
*atas = baru;
}
}

void elemen :: POP (PNODE *atas)
{
PNODE PH;
PH = *atas;

if(*atas == NULL)
{
cout<<"\n\nSTACK KOSONG !!!\n\n"; } else { if (PH -> next == NULL)
{
*atas = NULL;
free(PH);
}
else
{
*atas = (*atas) -> next;
free(PH);
}
}
getch();
}

PNODE elemen :: masuk_stack (void)
{
PNODE baru;
baru = (NODE *) malloc (sizeof(NODE));
cout<<"\nbil : ";cin>>baru->bil;
baru -> next = NULL;
return (baru);
getch();
}

void elemen :: tampil_queue (PNODE head)
{
PNODE pos;
pos = head;
cout<<"\n\nbilangan : "; while(pos != NULL) { cout< bil<<", "; pos = pos -> next;

}
cout<<"\n\n\n [TEKAN ENTER UNTUK MELANJUTKAN]"; getch(); } void elemen :: INSERT_QUEUE (PNODE *tail,PNODE *head, PNODE baru) { if(*tail == NULL) { *head = baru; *tail = baru; } else { (*tail) -> next = baru;
*tail = baru;
}
}

void elemen :: DELETE_QUEUE (PNODE *head, PNODE *tail)
{
PNODE PH;
PH = *head;
if(*head == NULL)
{
cout<<"\n\nQUEUE KOSONG !!!\n\n"; } else { if (PH -> next == NULL)
{
*head = NULL;
*tail = NULL;
free(PH);
}
else
{
*head = (*head) -> next;
free(PH);
}
}
getch();
}

PNODE elemen :: masuk_queue (void)
{
PNODE baru;
baru = (NODE *)malloc(sizeof(NODE));
cout<<"\nbil : ";cin>>baru -> bil;
baru -> next = NULL;
return(baru);
getch();
}


void main()
{
PNODE atas = NULL;
PNODE baru;
PNODE head = NULL,tail = NULL;
int pil=1, x, m;
char *a = "Created bY Tendi Setiadi (6306211) ";
char *b = "Í";
elemen data;
textbackground (RED);
clrscr();

m=strlen(a);
gotoxy (20,20);
for (x=0; x<<*(a+x); delay(200); } gotoxy (3,24); for (x=0; x<75; x++) { cout<<*b; delay(40); } while (pil != 3) { clrscr(); cout<<"\n-> Menu Utama <-"<<<"\n1> Stack";
cout<<"\n2> Queue";
cout<<"\n3> Exit";
cout<<"\nPilihan : ";cin>>pil;

if (pil == 1)
{
while(pil != 4)
{
clrscr();
cout<<"\n>> Menu STACK <<"<<<"\n1. PUSH STACK"; cout<<"\n2. LIHAT DATA STACK"; cout<<"\n3. POP STACK"; cout<<"\n4. Menu Utama"; cout<<"\nPilihan : ";cin>>pil;

if (pil == 1)
{
baru = data.masuk_stack();
data.PUSH(&atas, baru);
}

if (pil == 2)
data.tampil_stack(atas);

if (pil == 3)
{
data.POP(&atas);
}
}
}

if (pil == 2)
{
while(pil != 4)
{
clrscr();
cout<<"\n>> Menu QUEUE <<"<<<"\n1. INSERT_QUEUE LIST"; cout<<"\n2. LIHAT DATA LIST"; cout<<"\n3. DELETE_QUEUE LIST"; cout<<"\n4. Menu Utama"; cout<<"\nPilihan : ";cin>>pil;

if (pil == 1)
{
baru=data.masuk_queue();
data.INSERT_QUEUE(&tail,&head,baru);
}

if (pil == 2)
data.tampil_queue(head);

if (pil == 3)
{
data.DELETE_QUEUE(&head,&tail);
}
}
}
}
}






SOAL 3
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"

struct list
{
char nama[35];
char kode[10];
struct list * next;
};
typedef struct list node;
typedef node * pnode;
typedef struct list NODE;
typedef NODE * PNODE;

void TAMPIL(PNODE ATAS)
{
int x;
PNODE POS;
POS = ATAS;
cout<<"\nKode : "; while(POS!=NULL) { cout<kode<<" - "; POS=POS->next;
}
}

void PUSH(PNODE *ATAS,PNODE BARU)
{
if(*ATAS==NULL)
{
*ATAS = BARU;
}
else
{
BARU->next = *ATAS;
*ATAS = BARU;
}
}

void POP(PNODE *ATAS)
{
PNODE PH;
PH = *ATAS;
if(*ATAS==NULL)
{
cout<<"\n\nSTACK KOSONG !!!\n\n"; } else { if (PH->next==NULL)
{
*ATAS = NULL;
free(PH);
}
Else
{
*ATAS = (*ATAS)->next;
free(PH);
}
}
}

PNODE MASUK(void)
{
PNODE BARU;
BARU=new(NODE);
cout<<"KODE : "; gets(BARU->kode);
BARU->next=NULL;
return(BARU);
}

void tampil(pnode atas)
{
int x;
pnode pos;
pos = atas;
cout<<"NEGARA : "; while(pos!=NULL) { cout<nama<<" - "; pos=pos->next;
}
}

void push(pnode *atas, pnode baru)
{
if(*atas==NULL)
{
*atas = baru;
}
else
{
baru->next = *atas;
*atas = baru;
}
}

void pop(pnode *atas)
{
pnode ph;
ph = *atas;

if(*atas==NULL)
{
cout<<"\n\nSTACK KOSONG !!!\n\n"; } else { if (ph->next==NULL)
{
*atas = NULL;
free(ph);
}
else
{
*atas = (*atas)->next;
free(ph);
}
}
}

pnode masuk(void)
{
pnode baru;
baru=new(node);
cout<<"\nNEGARA : "; gets(baru->nama);
baru->next=NULL;
return(baru);
}

void main()
{
pnode atas=NULL;
pnode baru;
PNODE BARU;
PNODE ATAS=NULL;
int pil=1;
clrscr();

while(pil!=4)
{
cout<<"\n\n=======STACK======="; cout<<"\n1. PUSH STACK"; cout<<"\n2. VIEW DATA STACK"; cout<<"\n3. POP STACK"; cout<<"\n4. EXIT"; cout<<"\nPilihan [1/2/3/4] : "; cin>>pil;

if (pil==1)
{
clrscr();
baru=masuk();
BARU=MASUK();
push(&atas,baru);
PUSH(&ATAS,BARU);
}
if (pil==2)
{
clrscr();
tampil(atas);
TAMPIL(ATAS);
}
if (pil==3)
{
clrscr();
pop(&atas);
POP(&ATAS);
}
}
}

contoh program STACK

#include (iostream.h)
#include (stdlib.h)
#include (conio.h)
class elemen{
struct list{
int bil;
struct list * next;
};
public:
typedef struct list NODE;
typedef NODE * PNODE;

void tampil(PNODE atas);
void PUSH(PNODE *atas, PNODE baru);
void POP(PNODE *atas);
PNODE masuk(void);
};

void elemen::tampil(PNODE atas){
PNODE pos;
pos = atas;
cout<<"\n\nbilangan : "; while(pos!=NULL){ cout<bil<<", "; pos=pos->next;
}
}

void elemen::PUSH(PNODE *atas, PNODE baru){
if(*atas==NULL){
*atas = baru;
}else{
baru->next = *atas;
*atas = baru;
}
}

void elemen::POP(PNODE *atas){
PNODE PH;
PH = *atas;
if(*atas==NULL){
cout<<"\n\nSTACK KOSONG !!!\n\n"; }else{ if (PH->next==NULL){
*atas = NULL;
free(PH);
}else{
*atas = (*atas)->next;
free(PH);
}
}
}

PNODE elemen::masuk(void){
PNODE baru;
baru=(NODE *)malloc(sizeof(NODE));
cout<<"\nbil : ";cin>>baru->bil;
baru->next=NULL;
return(baru);
}

void main(){
PNODE atas=NULL;
PNODE baru;
int pil=1;
elemen data;
clrscr();
while(pil!=4){
cout<<"\n\n1. PUSH STACK"; cout<<"\n2. LIHAT DATA STACK"; cout<<"\n3. POP STACK"; cout<<"\n4. EXIT"; cout<<"\nPilihan : ";cin>>pil;
if (pil==1){
baru=data.masuk();
data.PUSH(&atas, baru);
}
if (pil==2)
data.tampil(atas);
if (pil==3){
data.POP(&atas);
}
}
}

STRUKTUR DATA HIRARKIS : TREE
Tree merupakan salah satu struktur data yang paling penting, karena
banyak aplikasi menggunakan informasi dan data yang secara alami
memiliki struktur hirarkis berguna dalam membantu memecahkan
banyak masalah algoritmis.
Aplikasi pohon biner :
a. sebagai representasi ekspressi matematika
b. aplikasi pohon biner dalam Huffman Coding.
Cara Penggambaran Tree :
• Notasi Kurung
• Diagram Venn
• Notasi Tingkat
• Notasi Garis

1
Heap Tree dan Kegunaannya dalam Heap Sort
Efendy Chalikdjen1, Hermanto Ong2, Satria Putra Sajuthi3
Laboratorium Ilmu dan Rekayasa Komputasi
Departemen Teknik Informatika, Institut Teknologi Bandung
Jl. Ganesha 10, Bandung
E-mail : if13068@students.if.itb.ac.id1, if13069@students.if.itb.ac.id2,
if13099@students.if.itb.ac.id3
Abstrak
Mahasiswa Teknik Informatika dan orang-orang lain yang berkecimpung dalam bidang pemrograman
(programming) sering sekali menghadapi masalah pengurutan dalam membangun sebuah program aplikasi.
Misalnya saja dalam membangun sebuah aplikasi pengolah data mahasiswa, programmer akan dihadapkan pada
masalah pengurutan data mahasiswa berdasarkan atribut tertentu, seperti nama, NIM, nilai, dan sebagainya. Di
dalam bidang Teknik Informatika sendiri terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat
digunakan untuk memecahkan masalah pengurutan tersebut, di antaranya adalah bubble sort, merge sort, insertion
sort, quick sort, dan selection sort, serta masih banyak lagi jenis algoritma pengurutan lainnya. Oleh karena itu,
teknik dan kejelian untuk memilih algoritma pengurutan yang tepat dan sesuai dengan permasalahan pengurutan
yang dihadapi sangat diperlukan karena masing-masing algoritma pengurutan tersebut memiliki karakteristik yang
berbeda-beda. Penulis memilih untuk mengangkat tema Heap Sort dalam makalah ini sebab heap sort merupakan
salah satu algoritma pengurutan yang memiliki kompleksitas waktu asimptotik terbaik. Selain itu juga, heap sort
menerapkan teknik yang unik di dalam memecahkan masalah pengurutan, yaitu dengan menggunakan heap tree.
Pada makalah ini akan dibahas dan dianalisis heap tree dan kegunaanya dalam heap sort, serta contoh sederhana
mengenai cara penerapan algoritma pengurutan heap sort dalam memecahkan suatu masalah pengurutan.
Kata kunci: algoritma pengurutan, mangkus, kompleksitas waktu asimptotik, heap sort, heap tree.
1. Pendahuluan
Untuk memecahkan masalah pengurutan dalam
membangun suatu program aplikasi, dibutuhkan
algoritma pengurutan. Di dalam bidang Teknik
Informatika terdapat banyak sekali jenis-jenis
algoritma pengurutan yang dapat digunakan untuk
memecahkan masalah pengurutan. Oleh karena itu,
teknik untuk memilih algoritma pengurutan yang
tepat, sesuai dengan kebutuhan, dan mangkus sangat
diperlukan karena masing-masing algoritma
pengurutan memiliki karakteristik yang berbedabeda.
Heap sort merupakan salah satu contoh
algoritma pengurutan yang memiliki kompleksitas
waktu asimptotik terbaik serta menerapkan teknik
yang unik/khas di dalam memecahkan masalah
pengurutan, yaitu dengan menggunakan heap tree.
2. Heap Tree dan Priority Queue
2.1 Pengertian Heap Tree
Secara umum, pengertian dari heap adalah bagian
dari memori yang terorganisasi untuk dapat
melayani alokasi memori secara dinamis [2].
Suatu heap tree adalah Complete Binary Tree (CBT)
di mana harga-harga key pada node-nodenya
sedemikian rupa sehingga haga-harga key pada
node-node anaknya tidak ada yang lebih besar dari
harga key pada node orang tuanya [2].
Pengertian "lebih besar" di atas tidak mutlak, untuk
beberapa kasus maka dapat diganti sesuai dengan
permasalahan yang dihadapi.
2.2 Implementasi Priority Queue
Berdasarkan pengertian di atas maka heap tree
bermanfaat untuk mengimplementasikan priority
queue. Priority queue merupakan struktur data yang
sifatnya sangat mirip dengan antrian, yaitu
penghapusan/pengurangan anggota selalu dilakukan
pada anggota antrian yang terdepan dan penambahan
anggota selalu dilakukan dari belakang antrian
berdasarkan prioritas anggota tersebut (anggota yang
memiliki prioritas lebih besar selalu berada di depan
anggota yang memiliki prioritas lebih rendah).
2
Sebagai suatu priority queue, heap tree memerlukan
beberapa metoda sebagai berikut: [2]
a. Metoda untuk menginisialisasi suatu CBT
(Complete Binary Tree) a secara umum
menjadi heap tree.
b. Metoda untuk mengambil data paling besar,
yaitu root dari heap tree.
c. Metoda untuk menambahkan satu key baru ke
dalam heap tree.
d. Metoda untuk menyusun ulang menjadi heap
tree kembali setelah dilakukan metoda b atau c
Kriteria yang penting untuk dipenuhi adalah bahwa
setiap metoda di atas beroperasi pada tree yang
selalu berbentuk CBT (Complete Binary Tree)
karena struktur level lebih rendahnya tetap
merupakan suatu array[2].
3. Algoritma Pengurutan(Sorting Algorithm)
Heap Sort
Contoh penggunaan heap tree dalam priority queue
dapat kita lihat pada algoritma pengurutan heap sort.
Algoritma pengurutan ini mengurutkan isi suatu
array masukan dengan memandang array yang
dimasukkan sebagai suatu Complete Binary Tree
(CBT). Dengan metoda a maka Complete Binary
Tree (CBT) ini dapat dikonversi menjadi suatu heap
tree. Setelah Complete Binary Tree (CBT) berubah
menjadi suatu priority queue, maka dengan
mengambil data root satu demi satu dan disertai
dengan metoda d, key-key dari data root yang kita
ambil secara berturutan itu akan terurut dengan
output hasil pengurutan akan dituliskan dalam array
hasil dari arah kanan ke kiri.
Untuk optimasi memori, kita dapat menggunakan
hanya satu array saja. Yaitu dengan cara
memodifikasi metoda b untuk menukar isi root
dengan elemen terakhir dalam heap tree. Jika
memori tidak menjadi masalah maka dapat tetap
menggunakan 2 array yaitu array masukan dan array
hasil.
Algoritma utama heap sort:[2]
heapify()
for i ← 0 to n-1 do
remove()
reheapify()
endfor
3.1 Algoritma Metoda Heapify
Ide pertama yang harus kita pikirkan untuk
melakukan operasi heapify adalah dari bagian mana
kita harus memulai. Bila kita mencoba dari heapify
dari root maka akan terjadi operasi runut-naik seperti
algoritma bubble sort yang akan menyebabkan
kompleksitas waktu yang ada akan berlipat ganda.
Setelah diuji, dengan berbagai hasil maka ide yang
efisien adalah membentuk heap tree - heap tree
mulai dari subtree-subtree yang paling bawah. Jika
subtree-subtree suatu node sudah membentuk heap
maka tree dari node tersebut mudah dijadikan heap
tree dengan mengalirkannya ke bawah.
Jadi, algoritma utama heapify adalah melakukan
iterasi mulai dari internal node paling kanan-bawah
(atau berindeks array paling besar) hingga root,
kemudian ke arah kiri dan naik ke level di atasnya,
dan seterusnya hingga mencapai root (sebagai array
[0..N-1] ). Oleh karena itu, iterasi dilakukan mulai
dari j = N/2 dan berkurang satu-satu hingga
mencapai j = 0.
Pada internal node tersebut, pemeriksaan hanya
dilakukan pada node anaknya langsung (tidak pada
level-level lain di bawahnya). Di samping itu, pada
saat iterasi berada di level yang lebih tinggi, subtreesubtreenya
selalu sudah membentuk heap. Jadi,
kemungkinan yang paling buruk adalah
restrukturisasi hanya akan mengalirkan node
tersebut ke arah bawah. Dengan demikian, algoritma
metoda heapify ini melakukan sebanyak N/2 kali
iterasi, dan pada setiap interasi paling buruk akan
melakukan pertukaran sebanyak log2 (N) kali.
3.2 Algoritma Metoda Remove
Algoritma metoda remove hanya menukarkan
elemen array pertama dengan elemen array terakhir
yang terdapat di dalam heap tree. Secara logika,
node yang berada paling kanan-bawah dipindahkan
ke root untuk menggantikan node root yang akan
diambil.
3.3 Algoritma Metoda Reheapify
Algoritma metoda reheapify melakukan
restrukturisasi dari atas ke bawah seperti halnya
iterasi terakhir dari algoritma metoda heapify.
Perbedaan antara metoda heapify dengan metoda
reheapify terletak pada iterasi yang dilakukan oleh
kedua algoritma tersebut. Algoritma metoda
reheapify hanya melakukan iterasi terakhir dari
algoritma metoda heapify. Hal ini disebabkan baik
subtree kiri maupun subtree kanannya sudah
merupakan heap, sehingga tidak perlu dilakukan
iterasi yang lengkap seperti algoritma metoda
heapify. Dan setelah reheapify maka node yang
akan diiterasikan berikutnya akan berkurang satu.
4. Penerapan Algoritma Pengurutan Heap
Sort
Salah satu contoh penerapan algoritma pengurutan
(sorting algorithm) heap sort adalah sebagai berikut:
Misalkan terdapat suatu array bilangan bulat yang
terdiri dari sepuluh buah anggota dengan nilai data
3
11, 9, 8, 27, 16, 25, 12, 13, 34, dan 43. Kita akan
mengurutkan data diatas dengan menggunakan
heapsort.
Pertama-tama, array di atas dapat dipandang sebagai
suatu Complete Binary Tree (CBT) sebagai berikut:
Selanjutnya algoritma metoda heapify dilakukan
dengan iterasi dari subtree node ke-4, ke-3, dan
seterusnya berturut-turut hingga mencapai root
(akar). Iterasi dilakukan mulai dari node ke-4 karena
N/2 dalam contoh di atas adalah 5. Dan elemen
kelima dari array memiliki nilai indeks 4 sebab
indeks array biasanya diawali dari 0.
Penerapan algoritma metoda heapify terhadap
Complete Binary Tree (CBT) pada contoh di atas
menghasilkan operasi-operasi pertukaran sebagai
berikut:
1. Subtree node ke-4: pertukaran 16 dengan 43
2. Subtree node ke-3: pertukaran 27 dengan 34
3. Subtree node ke-2: pertukaran 8 dengan 25
4. Subtree node ke-1: pertukaran 9 dengan 43, lalu
pertukaran 9 dengan 16
5. Subtree node ke-0: pertukaran 11 dengan 43, lalu
pertukaran 11 dengan 34, serta akhirnya
pertukaran 11 dengan 27
Perubahan-perubahan (pertukaran) tersebut dapat
digambarkan sebagai berikut:
Semua perubahan di atas terjadi dalam array yang
bersangkutan, sehingga pada akhirnya diperoleh tree
terakhir yang merupakan heap tree.
Sementara itu, dalam iterasi yang
melakukan/menerapkan algoritma metoda remove( )
dan algoritma metoda reheapify() akan terjadi
pemrosesan berikut:
1. Setelah 43 di-remove dan 9 menggantikan posisi
yang ditinggalkan oleh 43, maka terjadi
reheapify: penukaran 9 dengan 34, 9 dengan 27,
dan 9 dengan 13.
menjadi
dan data yang telah terurut adalah 43.
2. Setelah 34 di-remove dan 11 menggantikan
posisi yang ditinggalkan oleh 34, maka terjadi
reheapify: penukaran 11 dengan 27, dan 11
dengan 16.
4
menjadi
dan data yang telah terurut adalah 34, 43.
3. Setelah 27 di-remove dan 9 menggantikan posisi
yang ditinggalkan oleh 27, maka terjadi
reheapify: penukaran 9 dengan 25, dan 9 dengan
12.
menjadi
dan data yang telah terurut adalah 27, 34, 43.
4. Demikian seterusnya dilakukan algoritma
metoda remove dan algoritma metoda reheapify
hingga tidak ada lagi node yang tersisa. Dan
pada akhirnya akan didapatkan hasil data yang
telah terurut adalah 8, 9, 11, 12, 13, 16, 25, 27,
34, 43.
5. Representasi Alokasi Dinamis Algoritma
Pengurutan Heap Sort
Karakteristik dari algoritma pengurutan heap sort
adalah bahwa dalam implementasinya heap sort
menggunakan heap tree agar dapat diselesaikan
secara heapsort. Oleh karena itu, untuk
mengimplementasikan algoritma pengurutan heap
sort dalam suatu program aplikasi, dibutuhkan
adanya alokasi dinamis dengan menggunakan
struktur data tree (pohon).
Prinsip-prinsip dasar mengenai struktur data tree
yang digunakan untuk merealisasikan heap tree
adalah sebagai berikut:
a. Node-node saling berhubungan dengan
menggunakan pointer. Pada struktur data tree ini
digunakan minimal dua buah pointer pada setiap
node, masing-masing untuk menunjuk ke cabang
kiri dan cabang kanan dari tree tersebut.
Misalnya dalam bahasa C, struktur data tree
dideklarasikan sebagai berikut:
class BinaryTreeNode {
KeyType Key;
InfoType Info;
BinaryTreeNode Left, Right;
}
b. Left dan Right berharga NULL apabila tidak ada
lagi cabang pada arah yang bersangkutan.
c. Struktur dari binary tree, termasuk hubunganhubungan
antar-node, secara eksplisit
direpresentasikan oleh Left dan Right. Apabila
diperlukan penelusuran naik (backtrack), maka
hal tersebut dapat dilakukan dengan penelusuran
ulang dari root, penggunaan algoritma-algoritma
yang bersifat rekursif, atau penggunaan stack.
d. Alternatif lain adalah dengan menambahkan
adanya pointer ke parent. Namun hal ini akan
mengakibatkan bertambahnya jumlah tahapan
pada proses-proses penambahan/penghapusan
node.
6. Kesimpulan
Algoritma pengurutan heap sort dapat digunakan
untuk menyelesaikan masalah-masalah pengurutan
dalam membangun suatu program aplikasi dengan
mangkus.
Algoritma pengurutan heap sort dapat dikategorikan
ke dalam algoritma divide and conquer dengan
pendekatan pengurutan sulit membagi, mudah
menggabung (hard split/easy join) seperti halnya
algoritma pengurutan quick sort dan selection sort.
Hal ini disebabkan pembagian dilakukan dengan
terlebih dahulu menerapkan algoritma metoda
heapify sebagai inisialisasi awal untuk
mentransformasi suatu Complete Binary Tree (CBT)
menjadi heap tree dan pada setiap tahapan
diterapkan algoritma metoda reheapify untuk
menyusun ulang heap tree. Pembagiannya sendiri
dilakukan dengan menerapkan metoda remove yang
akan membagi data yang akan diurutkan menjadi
dua bagian, masing-masing berukuran sebanyak satu
dan sebanyak jumlah node di dalam heap tree
dikurangi dengan satu. Sementara itu, proses
penggabungannya sangat mudah sebab pada setiap
tahapan, data terbesar dari tahap tersebut
digabungkan dengan cara disisipkan di depan data
terbesar yang diperoleh dari tahap sebelumnya.
Keunggulan algoritma pengurutan heap sort terletak
pada kompleksitas waktu asimptotiknya yang sangat
baik. Untuk melakukan algoritma metoda heapify
dilakukan iterasi mulai dari elemen ke-N/2 sampai
dengan elemen ke-1, dan pada setiap iterasi paling
banyak akan dilakukan operasi pertukaran sebanyak
log2 (N) kali. Oleh karena itu, kompleksitas waktu
asimptotik algoritma metoda heapify adalah T(N) =
N/2 * log2 (N) = O (N log2 (N)). Sementara itu,
5
algoritma metoda remove hanya melakukan
pertukaran elemen pertama dengan elemen terakhir
dalam heap tree sehingga kompleksitas waktu
asimptotiknya adalah T(N) = O (a), a adalah
konstanta. Sedangkan algoritma metoda reheapify
hanya melakukan restrukturisasi ulang elemen root
untuk membentuk heap tree setelah dilakukan
algoritma metoda remove. Dengan demikian,
kompleksitas waktu asimptotik algoritma metoda
reheapify setara dengan T(N) = O (log2 (N)). Pada
algoritma pengurutan (sorting algorithm) heap sort,
algoritma metoda heapify dilakukan hanya satu kali
sebagai inisialisasi sebelum iterasi, dan algoritma
metoda remove dan reheapify dilakukan sebanyak
jumlah iterasi, yaitu N. Jadi, kompleksitas waktu
asimptotik algoritma pengurutan (sorting algorithm)
heap sort adalah T(N) = (N/2 * log2 (N)) + (N * (a +
log2 (N))) = N/2 log2 (N) + Na + N log2 (N) = 3N/2
log2 (N) + Na = bN log2 (N) + Na = O (N log2 (N)).
Karakteristik (ciri khas) dari algoritma pengurutan
(sorting algorithm) heap sort terletak pada
penggunaan heap tree sebagai sarana untuk
menyelesaikan / memecahkan permasalahan
pengurutan. Hal ini menjadi salah satu faktor yang
membuat algoritma pengurutan (sorting algorithm)
heap sort menjadi unik (khas), menarik, dan
berbeda apabila dibandingkan dengan algoritmaalgoritma
pengurutan (sorting algorithm) lainnya.
Daftar Pustaka
1. http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets
/sortingII/heapSort/heap.html. Diakses tanggal 17
Mei 2005 pukul 16.30 WIB.
2. http://www.cs.ui.ac.id/kuliah/IKI10100/1998/
handout/handout15.html. Diakses tanggal
17Mei 2005 pukul 17.00 WIB.