Pemrograman Dinamis – Konsep Memoization

[algoritma|tek.inf|r408|pert.8]

Salah satu materi algoritma standar adalah pemrograman dinamis (Dynamic Programming). Walaupun ada kata “programming”-nya ternyata tidak ada hubungannya dengan kode/script. Ternyata istilah pemrogramannya karena teknik yang biasanya digunakan untuk optimalisasi ini memanggil suatu fungsi diri sendiri (rekursif) sebelum menentukan hasil-hasil yang optimal. Optimal di sini bisa maksimal atau minimal.

Pemotongan Batang (Rod Cutting)

Kasus ini contoh proses pemotongan bilah batang panjang agar dihasilkan margin keuntungan yang optimal. Misalnya batang baja sepanjang 10 inchi yang akan dipotong dengan potongan kelipatan 1 inchi.

Kombinasi dari ukuran potongan ternyata sangat menentukan keuntungan berdasarkan harga per potongnya. Misal, untuk baja sepanjang 4 inchi memiliki keuntungan dengan komposisi dua buah batang berukuran 2 inchi.

Selain dua buah potongan berukuran 2 inchi, panjang potongan menghasilkan harga 4, 7, dan 9. Sementara dua buah potongan 2 inchi menghasilkan harga 10 (tentu saja ini kasus bagi penjual, kalau pembeli tentu lebih menguntungkan beli potongan-potongan kecil satu inchi).

Memoization

Istilah ini saya fikir salah tulis, harusnya memorization, ternyata tidak. Istilah ini berasal dari kata “memo”, yaitu secarik surat/infor singkat. Misal untuk tiap-tiap panjang bilah akan dihasilkan nilai optimal sebagai berikut:

Perhatingan untuk baja sepanjang 1 sampai 3 inchi, optimalnya adalah tanpa dipotong, masing-masing berharga $1, $5, dan $8. Baja 2 in ada dua kemungkinan yaitu 1+1 atau 2 in tanpa dipotong. Karena 1in+1in menghasilkan hanya $2 maka yang dipilih 2 in tanpa dipotong, yaitu $5. Untuk baja berukuran 4 in ada beberapa kemungkinan seperti gambar batangan di atas dan dihitung semua kemungkinannya hingga diperoleh maksimal adalah dua potongan @2in. Pseucode-nya sebagai berikut:

Keterangan: baris ke-4 sampai 6 menghitung komposisi potongan baja. Misal untuk i=1, maka akan dicari maksimal dari 1 dan (n-1)-nya. Jika batang 4 in, maka 1 dan 3, berikutnya 2 dan 2 (dari n-2) dan seterusnya. Untuk kasus contoh di atas diperoleh nilai maks 10 (ketika i=2 dan satu potongan lainnya 2 in juga).

Karena potongan 2in sudah dihitung dari sebelumnya (batang ukuran 2in) maka ketika menghitung 4in tidak perlu menghitung kembali yang 2in hanya menggunakan riwayat yang lalu, alias dari “memo” sebelumnya. Di sinilah muncul istilah memoization, atau dalam bahasa Indonesianya mungkin memoisasi.

Top Down Memoization

Dengan rekursif, beberapa perhitungan dihitung berulang kali sehingga tidak efisien (naif). Oleh karena itulah pemrograman dinamis diterapkan untuk menggantikan proses rekursif berulang tersebut. Jadi sekali telah dihitung, maka jika akan menghitung proses yang sama hanya me-ngintip (lookup) hasil perhitungan yang lampau.

Untuk dengan memoization, ditambahkan arrah yang berisi nilai yang sudah dihitung dengan suatu routine yang disebut helper “Memouzed-Cut-Rod-Aux” (simbol minus tak hingga artinya unknown dan perlu dihitung):

Baris 1-3 mengecek apakah nilai sudah ada di array hasil perhitungan atau tidak. Jika tidak ada (else) masuk ke q yang unkhown (minus tak hingga) dengan baris 7 yang berisi maksimal komposisi-komposisi yang maksimal. Hanya saja di sini rekursif yang bekerja dengan mengecek hasil hitungan sebelumnya jika sudah ada di array hasil, langsung mengkopi saja tidak perlu menghitung lagi nilai r-nya (lihat r1 sampai r10 di contoh paling atas postingan ini untuk batang sepanjang 10 in).

Buttom Up Memoization

Teknik buttom up lebih sederhana karena tidak membutuhkan mekanisme rekursif, hanya dengan menghitung maksimal potongan-potongan dari terkecil hingga terbesarnya.

Keterangan: Seperti biasa array hasil dipersiapkan. Variabel j merupakan hasil optimal komposisi potongan yang bergerak dari kombinasi i dengan pasangannya. Misal ketika j=4 maka i bergerak dari i=1 dan r(3) mana yang lebih maksimal dibanding komposisi lainnya misal i=2 dan r(2), dan seterusnya. Baik buttom up ataupun top down memiliki running time yang kuadratik. Sekian, semoga bermanfaat.

Referensi:

Cormen, dkk. “intro to algorithms”, MIT Press: 2009.

Iklan

Master Theorem

[algoritma&pemrograman/pert4/TIF-1101/r-408]

Ketika menangani kalkulasi menghitung waktu proses sorting dengan rekursif, salah satu metode yang praktis digunakan adalah master theorem. Oiya, rekursif adalah sebuah prosedur/fungsi yang didalamnya memanggil fungsi itu lagi. Misalnya pada algoritma heapshort.

  • Untuk seluruh angka
  • Ambil nilai max di akar
  • Isi akar dengan nilai index terakhir
  • Lakukan fungsi heapify()
  • Turunkan jumlah index sebanyak satu angka

Tampak ada pemanggilan fungsi heapify() di setiap rutin. Contoh lain adalah merge sort dengan devide and conquer. Dimana fungsi merge-sort() dipanggil lagi:

Master Theorem digunakan untuk mencari theta oh ataupun big oh suatu waktu proses T(n). Berikut ini rumus yang digunakan.

Langkah-langkah yang dilakukan untuk menggunakan teori ini antara lain:

  • Tentukan a, b, k dan p.
  • Cari tiga kemungkinan (lebih besar, sama dengan, atau lebih kecil) antara a dengan b^k.
  • Untuk a=b^k cek lagi apakah p>-1, p=-1, atau p<-1
  • Untuk a<b^k cek lagi apakah p>=0, atau p<0.
  • Masing-masing kemungkinan memiliki time complexity T(n) yang berbeda.

Tentu saja teori ini ada batasannya, misalnya jika di sebelah kiri T(n/b) ada n maka a tidak bisa ditentukan. Namun beberapa metode bisa mengkonversi menjadi bentuk standarnya dimana di sisi kiri berupa konstanta.

Ref:

Bahasa Pemrograman Online

Terkadang ada mata kuliah tertentu yang memerlukan praktek pemrograman. Bahasa yang dipilih pun beragam seperti Java, C++, Python, Ruby, Matlab, dan lain-lain. Jika ingin dituruti maka lab atau laptop pengajar harus menginstall aplikasi-aplikasi yang berisi bahasa pemrograman tersebut. Hal ini tentu saja sangat mengganggu karena tiap instalasi memerlukan space harddisk. Belum lagi jika fasilitas lab tidak memadai dan tidak terinstal compiler dari bahasa pemrograman yang digunakan.

Bahasa Pemrograman Online

Salah satu jawaban untuk mengatasi hal tersebut adalah menggunakan bahasa pemrograman online. Dengan mengakses situs-situs penyedia bahasa pemrograman online kita dapat belajar memrogram tanpa terlebih dahulu instal compilernya. Sangat praktis, tapi tentu saja tidak untuk production. Hanya saja untuk latihan siswa cukup memadai.

a. Bahasa C++

Bahasa ini banyak digunakan dalam perkuliahan karena sangat powerful, sudah tua, dan pembuat bahasa-bahasa lainnya. Salah satu situs yang lumayan bagus adalah OnlineGdb. Untuk mengujinya kita coba dengan algoritma insertion yang diambil dari mata kuliah algoritma. Silahkan buka kodenya di situs berikut ini. Copas dan letakan di bagian kode. NOTE: perhatikan lagi struktur kode-nya soalnya ada angka yang ikut ter-copas.

Lumayan OK dalam mensortir angka di atas. Hanya saja ketika menginput angka yang akan disortir sepertinya terlalu lama “lag”-nya, mungkin karena berbasis web.

b. Java

Sebenarnya situs OnlineGdb di atas bisa untuk java juga. Tinggal klik language di bagian kanan atas dilanjutkan dengan memilih java. Tetapi situs lain mungkin bisa dipertimbangkan seperti
Jdoodle
. Atau jika ingin bisa mengunduh hasil kompilasinya bisa dengan situs CompileJava. Di bawah ini tampilan Jdoodle ketika copas insertion short in java dari Situs ini.

Perhatikan, setelah Execute ditekan maka Result … memunculkan hasil di atas. Lumayan praktis tanpa menggunakan compiler java beneran. Minimal bisa menerapkan algoritma dengan bahasa Java secara instan.

c. Python

Bahasa ini merupakan bahasa yang cukup terkenal, khususnya yang bermain dengan machine learning, data mining dan sejenisnya. Bisa diakses via situs
Tutorialspoint

ini. Situs ini hanya khusus untuk python, tidak ada pilihan bahasa lainnya. Kode diambil dari Github insertion. Hasilnya lumayan ok, letaknya di kanan, hanya saja ada iklan mengganggu di bagian result

hh

Untuk bahasa-bahasa lainnya seperti ruby, c#, bahkan assembler tersedia di OnlineGdb. Selamat mencoba.

Algoritma

[algoritma&pemrograman/TIF-1101/r-408]

Asal Usul

Algoritma merupakan ilmu yang spesifik untuk jurusan ilmu komputer dan turunannya (teknik informatika, sistem informasi, sistem komputer, dan lain-lain). Ilmu ini diambil dari nama seorang ilmuwan persia bernama “al-Khowarizmi” yang oleh lidah orang Eropa diucapkan menjadi “Algorithm”. Artinya adalah prosedur komputasi yang menghasilkan nilai tertentu dari suatu masukan. Prosedur tersebut berupa tahapan-tahapan komputasi.

Untuk yang SMA di tahun 90-an, biasanya sudah diperkenalkan Algoritma di mata pelajaran matematika, dengan satu bahasa pemrograman yang terkenal waktu itu: Basic. Algoritma sendiri telah dikembangkan jauh sebelum komputer ditemukan.

Algoritma merupakan Teknologi

Tidak hanya perangkat keras yang termasuk teknologi, algoritma juga bagian dari teknologi karena mengandung unsur efisiensi dan pemilihan metode yang cocok. Jujur saja, algoritma merupakan salah satu mata kuliah yang saya benci. Tapi ternyata merupakan salah satu bagian dari judul disertasi saya (hybrid multi-criteria evolutionary algorithms), unik juga.

Salah satu aspek teknologi adalah efisiensi. Berikut ini contoh perbandingan dua komputer yang menggunakan dua prosesor yang berbeda dengan algoritma pencarian (searching) yang berbeda pula. Rinciannya adalah sebagai berikut:

  • Komputer A: Memiliki kecepatan 10 miliar instruksi per detik. Menggunakan algoritma insertion sort dengan T(n)=C1*n^2.
  • Komputer B: Memiliki kecepatan 10 juta instruksi per detik. Menggunakan algorithma merge sort dengan T(n)=C2*n*log(n).

Jika C1=2 dan C2=50 (waktu proses tiap prosesor dimana komputer B lebih lama dari komputer A). Jika kedua komputer diminta untuk mensortir 10 juta angka berapakah waktu yang dibutuhkan oleh komputer A dan B?

Jawab: Soal tersebut diambil dari buku “introduction to algorithms” karya Cormen. Dengan membagi jumlah instruksi dengan kecepatan prosesor maka diperoleh waktu yang diperlukan.

  • Komputer A membutuhkan waktu proses = 2*(10^7)^2 : 10^10 = 20 ribu detik (kira-kira 5.5 jam) sementara komputer B memiliki waktu proses 50*10^7*log(10)^7 : 10^7 = 350 detik (kira-kira 6 menit).

Bayangkan prosesor yang 1000 kali lebih cepat (komputer A) dikalahkan oleh komputer B karena menggunakan algoritma yang lebih efisien. Selain itu algoritma bisa bekerja sama dengan teknologi-teknologi lainnya:

  • Arsitektur komputer dan teknologi perakitan/pembuatan komponen
  • GUI yang intuitif, mudah dan praktis.
  • Sistem berorientasi objek
  • Teknologi web terintegrasi, dan
  • Jaringan cepat baik kabel dan nirkabel.

Demikian uraian singkat tentang pembuka mata kuliah algoritma. Siapa tahu ada yang berminat/tertarik dengan materi kuliah utama ilmu komputer ini.

Referensi: