Algoritma

Master Theorem

rahmadya Algoritma

[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:

Iklan

Bahasa Pemrograman Online

rahmadya Algoritma

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

rahmadya Algoritma, Univ. Bayangkara

[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: