Archive for February, 2012

Desain dan Analisis Algoritma


2012
02.24

Algoritma adalah suatu prosedur yang digunakan untuk memecaskan suatu masalah yang biasanya menggunakan bantuan komputer serta menggunakan suatu bahasa pemrogaman tertentu seperti bahasa Pascal, Visual Basic, Java, dan lain-lain. Sedangkan desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut.

Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari system komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama. Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

Syarat Algotitma menurut Donald E Knuth yaitu:

  • Finiteness
  • Definiteness
  • Input
  • Output
  • Effectiveness

Jenis-jenis Algoritma terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma antara lain:

  1. Divide and Conquer

Paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk

 

  1. Dynamic programming

Paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal dan mengandung beberapa bagian permasalahan yang tumpang tindih. Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

 

  1. Metode serakah

Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan “serakah” apa yang dilihat terbaik pada saat itu.

 

Jenis-jenis algoritma yang lain yaitu:

  1. Bahasa Semu (pseudo code)

Menggunakan bahasa sehari-hari, tetapi harus jelas dan struktur.

 

  1. Diagram Alir/Alur (Flowchart)

Dengan membuat suatu penulisan atau penyajian algoritma berupa diagram yang menggambarkan susunan alur logika dari suatu permasalahan.

 

Macam Algoritma antara lain:

  • Metode Seleksi
  • Metode Sisipan
  • Metode Shell
  • Metode Bubble
  • Metode Cepat
  • Metode Radix
  • Metode Merge
  • Metode Pohon Biner
  • Metode Tournament
  • Metode Heap

 

Proses pemecahan masalah dengan algoritma tertentu hingga menjadi program dapat dibagi dalam sembilan tahap, tahap-tahap tersebut yakni:

  1. Mendefinisikan masalah

Masalah yang ingin dipecahkan harus jelas lingkupnya.

  1. Membuat model

Yang dimaksud model ini adalah model (bentuk) matematis yang dapat digunakan untuk memecahkan masalah, misalnya apakah harus dilakukan pengurutan terhadap data, apakah menggunakan perhitungan kombinatorik dan sebagainya.

  1. Merancang algoritma (flowchart/pseudocode)

Apa maksudnya, bagaimana rincian prosesnya, apa keluarannya.

  1. Menulis program

Ubah algoritma menjadi program (source code) dalam bahasa pemrograman tertentu.

  1. Mengubah source code menjadi executable code melalui proses compiling.
  2. Memeriksa hasil compiling, jika salah maka kembali ke tahap empat.
  3. Menjalankan program (run) untuk diuji kebenarannya dengan menggunakan berbagai data
  4.  Memperbaiki kesalahan (debugging dan testing)

Apabila hasilnya salah, kesalahan mungkin terjadi saat konversi rancangan algoritma manjadi program, atau salah rancang algoritma, atau salah menentukan model, atau salah mendefinisikan masalah. Ulangi langkah yang sesuai.

  1. Mendokumentasi program bila sudah benar.

 

Fungsi algoritma adalah untuk mempermudah kerja atau memudahkan kita dalam membuat program atau biasa di sebut sebagai Problem Solving. Selain itu, algoritma dapat mengatasi masalah logika dan masalah matematika. Dengan algoritma, kita dapat mengatasi masalah dari yang sederhana sampai yang kompleks sekalipun. Namun, seorang user harus mampu membuat suatu program dengan menggunakan bahasa yang difahami oleh komputer. Sebelum disajikan dalam bentuk bahasa pemrogaman, sebaiknya kita membuat diagram alir (Flow Chart) dan Pseudocode. Hal ini dimaksudkan agar dapat mempermudah kerja atau mempermudah dalam membuat program. Selain itu, algoritma dapat mengatasi masalah logika dan masalah matematika dengan cara berurutan, tetapi kadang-kadang algoritma tidak selalu berurutan, hal ini dikenal dengan proses percabangan.

Kriteria program algoritma harus komplit, nyata, dan jelas. Meskipun tugas algoritma tidak menghasilkan solusi, tetapi proses harus berakhir hal ini disebut dengan semi algorithm (prosedur akan berjalan terus atau biasa disebut dengan perulangan). Intinya kita tidak boleh menambah masalah, akan tetapi kita harus mampu menyelesaikan masalah untuk mendapat hasil yang tepat.

Masalah Analisis Algoritma antara lain tantangan yang dihadapi dalam membandingkan kinerja berbagai algoritma, yang perlu diperhatikan yaitu:

  • Kasus rata-rata; running time untuk tipikal data tertentu.
  • Kasus terjelek; running time yang mungkin paling jelek pada konfigurasi masukan data tertentu
  • Program → bahasa yang dipakai
  • Program sensitif terhadap input
  • Program sulit dimengerti, dan secara matematis hasil tah tersedia/diketahui
  • Sering kali program tidak bisa membandingkan, misal untuk data tertentu sangat efisien, tetapi yang lain pada kondisi yang sangat berbeda.