Kategori: Algoritma

Permasalahan Pada Google Colab

Salah satu tools untuk pemrograman dengan Python yang terkenal saat ini adalah Google Colab. Tools ini sangat praktis karena cukup dengan sebuah browser dengan disertai akun Google sudah bisa menjalankan kode dalam bahasa Python yang berat. Bahkan Google colab juga menyediakan hardwarenya yang berupa Graphic Processing Unit (GPU) dan Tensor Processing Unit (TPU).

Dalam praktiknya ternyata banyak kendala-kendala yang kerap dialami peneliti dalam memanfaatkan fasilitas canggih milik Google tersebut. Beberapa masalah akan dibahas dalam postingan ini, tentu saja berdasarkan pengalaman yang terjadi. Mungkin banyak hal lain yang tidak dibahas dalam postingan ini yang butuh share juga dari pembaca lewat kolom komentar. Selain membahas masalah-masalah yang muncul, dibahas pula cara-cara penyelesaiannya.

Kompatibilitas

Banyak kode-kode yang dishare di internet dalam bentuk Google Colab ketika dijalankan tidak bisa/error. Hal ini kerap terjadi karena Google Colab sudah mengupdate ke versi terbaru dan tidak bisa lagi menjalankan versi-versi yang lama. Langkah terbaik untuk penyelesaiannya adalah mengembalikan Google Colab ke versi sebelumnya.

Ternsor Flow

Beberapa aplikasi terkadang masih menggunakan tensorflow versi 1.x yang lama, sedangkan Google Colab saat ini sudah menggunakan yang versi 2. Oleh karena itu perlu sebuah instruksi untuk mengembalikan ke versi tersorflow yang lam.

Simbol “%” biasanya digunakan untuk setting library pada Google Colab. Memang ada baiknya mengkonversi program Python kita dengan versi yang terbaru, namun ada kalanya karena keterbatasan waktu, cara tersebut layak untuk dipertimbangkan.

TIdak Semua Library Tersedia

Beberapa library seperti NumPy, Pandas, dan sejenisnya sudah disiapkan oleh Google Colab. Namun library tertentu yang jarang dipakai perlu dipasang pada Google Colab. Caranya tentu saja tidak bisa dengan cara konvensional pada command prompt dengan “PIP”, melainkan dengan running pada Cell Google Colab lewat tanda “!” di awal.

Sebagai contoh di atas adalah library “rasterio” yang sering digunakan untuk menampilkan network Deep Learning berupa gambar yang jelas. Namun yang menjengkelkan adalah ketika Google Colab dishutdown dan dihidupkan kembali, kita harus menginstal ulang, berbeda jika menggunakan Jupyter Notebook yang cukup sekali menginstall Library.

Perlu Mencabut Instalasi Library

Ternyata bukan masalah belum terinstal saja yang muncul, sudah diinstal pun terkadang perlu dicabut karena tidak sesuai dengan kondisi sebelumnya. Misalnya ketika dahulu kita men-training dengan library tertentu pada Deeplearning, ketika hasil training tersebut akan digunakan ternyata tidak kompatibel dengan library terkini, alhasil perlu dilakukan proses training ulang yang terkadang memakan waktu.

Cara paling gampang adalah mencabut library Google Colab terkini dilanjutkan dengan instal versi sebelumnya yang tepat ketika proses training berlangsung.

Sebelumnya akan ada proses konfirmasi apakah akan dicabut library terkininya? Ketik saja y dan proses uninstall akan berjalan. Lanjutkan dengan menginstall versi yang kompatibel dengan yang lampau agar hasil pelatihan dapat berjalan.

Kode di atas terjadi ketika Deeplearning dilatih, versi h5py menggunakan versi yang lama. Alhasil dengan versiyang baru tidak dapat dipanggil dan dikompilasi dengan networknya. Setelah uninstall dan diinstal dengan versi yang cocok, barulah dapat dimanfaatkan hasil pelatihan/training Deeplearning yang telah dilakukan dahulu.

File Terhapus Ketika Shutdown

Problem yang sering terjadi adalah ketika suatu file diupload di Google Colab maka file tersebut sejatinya adalah sementara. Artinya ketika Google Colab ditutup maka file tersebut otomatis hilang. Untungnya Google Colab menyediakan fasilitas terkoneksi ke Google Drive, sehingga fila akan tersimpan permanen di Google Drive. Hanya saja perlu setting tambahan seperti berikut ini.

Google Colab akan meminta kode tertentu (cukup dengan copas) dari Google Drive. Pastikan folder di Google Drive dapat diakses pada Google Colab. Kalau hanya berukuran beberapa kilobyte sih tidak masalah, repotnya jika filenya berukuran besar mendekati 1 Gb, tentu saja menjengkelkan. Jadi melakukan akses ke Google Drive wajib dilakukan.

Waktu Akses Terbatas

Jika proses memerlukan waktu yang lama, maka Google akan memutus proses itu, dalam waktu 1×24 jam (mirip pesan pak RT untuk para tamu). Selain itu terkadang jika Google melihat tidak ada aktivitas pada sesi Google Colab terkadang akan direset prosesnya.

Butuh Koneksi Internet

Tentu saja karena Google Colab menggunakan browser. Ada baiknya Anda menggunakan Jupyter Notebook karena lebih fleksibel. Ketika kode bisa dirunning, akan terus bisa dirunning, kecuali Versi Library Anda rubah.

Hal-hal di atas merupakan permasalahan yang harus dipahami oleh pengguna Google Colab. Mungkin banyak hal-hal lain yang belum disebutkan di atas. Oiya, untuk pemrograman hal-hal rahasia, sensitif, dan sejenisnya ada baiknya tidak menggunakan fasilitas cloud seperti Google Colab.

Normalisasi Tabel

Dalam mata kuliah basis data, ada satu materi yang cukup berat, yaitu normalisasi tabel. Prinsip dasarnya adalah database relasional dimana ada aturan-aturan tertentu yang mengharuskan database designer mengikuti standar yang baku. Postingan berikut sedikit berdiskusi apa saja yang perlu diperhatikan dalam menormalisasi sebuah tabel.

Multivalue

Ini merupakan prinsip dasar database relasional dimana satu field/kolom dalam satu record tidak boleh berisi lebih dari satu item. Misalnya tabel transaksi pembelian barang, tidak boleh ada satu field, misalnya barang, yang berisi item-item barang yang dibeli. Di sini lah letak perbedaan basis data relasional dengan objek. Dalam basis data objek, isi field (diistilahkan dengan atribut) bisa multivalue dalam bentuk array.

Functional Dependency & Transitive Dependency

Dalam tabel transaksi terdapat dua ketergantungan yakni ketergantungan fungsi dan transitif. Jika Unnormalize Form (UNF) berisi field-field dalam transaksi (termasuk yg multivalue), dan 1NF yang berisi para kandidate key, 2NF berisi tabel-tabel yang mendukung ketergantungan fungsi, misalnya dalam pembelian barang, tabel yang terkait adalah tabel penjualan, detil penjualan dan barang.

Sementara itu ketergantungan yang sifatnya transitif, misalnya pelanggan, suplier, kasir/teler, dan lain-lain dipecah dalam 3NF. Ada level yang lebih rumit dan khusus, diberi nama Boyce-Code Normal Form (BCNF), biasanya terjadi ketika suatu field misalnya harga barang yang mengikuti wilayah cabang tertentu, padahal wilayah bukan merupakan primary key.

Surrogate Key

Dalam detil transaksi, misalnya detil pembelian, terkadang dibuat suatu surrogate key yang agar praktis dibuatkan/di-generate secara otomatis oleh sistem (increment). Mengapa harus dibuatkan surrogate key, silahkan simak video yang merupakan materi kuliah berikut. Semoga sedikit membantu.

Menghitung Kompleksitas Algoritma

Saat ini dimana komputer sudah canggih terkadang pengguna tidak terlalu memperhatikan seberapa kompleks sebuah algoritma. Tinggal jalankan, jika proses terasa lama dan berat, maka algoritma yang diterapkan dalam sebuah bahasa pemrograman berarti “boros” perhitungan. Sedikit memanipulasi dan kemudian dijalankan ulang maka diketahui apakah modifikasi menghasilkan eksekusi yang lebih baik atau tidak. Hal ini tidak dapat dijumpai ketika jaman dahulu dimana komputer belum secanggih saat ini yang bahkan sebuah kalkulator pun belum diciptakan. Dalam mata kuliah algoritma selalu dibahas bagaimana menghitung biaya sebuah algoritma yang diistilahkan dengan time complexity, atau terkadang disebuh kompleksitas saja.

Kalang (Loop) dan Rekursif (Recursive)

Ada dua jenis proses terkenal yang ditemukan oleh pakar-pakar algoritma. Yang pertama adalah kalang dalam sebuah iterasi. Jenis proses ini merupakan jenis yang paling banyak diketahui atau dinalar oleh mahasiswa yang belajar algoritma karena alurnya yang mudah dicerna. Tinggal mensimulasikan tiap iterasi, diketahui hasilnya. Biasanya untuk kasus yang rumit dalam skripsi/tugas akhir, mahasiswa hanya diminta menjalankan satu atau dua iterasi saja sekedar membuktikan bahwa yang bersangkutan memahami proses kerja algoritmanya dan selanjutnya tinggal eksekusi pada komputer yang meneruskan.

Sebagai ilustrasi, misalnya kita memiliki sekumpulan data sebanyak tiga buah, a={1,3,5}. Di sini n menyatakan jumlah data, yaitu tiga buah. Algoritma sederhana penjumlahan seluruh data dengan kalang ditunjukan oleh gambar berikut:

Kolom paling kiri menunjukan algoritma penjumlahan (Sum) data “a” sebanyak “n”. Jadi jika dijalankan akan terjadi perhitungan 0+(1+3+5)=8. Angka 1 di kolom berikutnya merepresentasikan “sekali eksekusi”. Di sini tidak dalam bentuk berapa detik atau milidetik karena tergantung prosesor yang dimiliki sehingga hanya dinyatakan dengan satuan eksekusi/step. Dimulai dari inisialisasi “s” yang dihitung satu step, kalang “for” sebanyak n+1 dengan “+1” perlu ditambahkan mengingat n=0 pun tetap dihitung satu step. Operasi di dalam kalang (akumulasi s) dihitung sebanyak “n” data. Akhir sebuah fungsi, yaitu “return” dihitung sekali. Jadi total 2n+3 langkah. Untuk contoh kasus kita adalah 2(3)+3 atau sebesar 9 langkah. Nah, untuk yang rekursif agak ribet sedikit.

Rekursif adalah fungsi yang memanggil diri sendiri. Untuk contoh penjumlahan data, rekursif di kolom kiri menyatakan fungsi RSum yang menambahkan sebuah data ke-n dengan data sebelumnya (n-1) dan berhenti ketika n nol atau negatif. Untuk data a={1,3,5} di atas operasi yang dilakukan algoritma rekursif adalah (((0)+1)+3 )+5)=8. Di sini perlu variabel x yang berisi kompleksitas (n-1). Tanpak jika n=0 (tidak ada data) jika dieksekusi tetap dibutuhkan 2 step (if dan return). Untuk contoh kita maka kompleksitasnya berarti 2+(2+(2+(2))) atau sebesar 8 langkah dimana kurung menyatakan proses rekursifnya. Atau secara sederhana berarti (n+1)*2. Pastikan dengan n lain yang lebih besar, misalnya 100 untuk memastikan mana yang lebih sedikit langkahnya. Untuk kalang: 2(100)+3=203 dan rekursif: (100+1)*2=202. Contoh lain yang lebih rumit misalnya untuk penjumlahan matriks berikut ini:

Untuk matriks a dan b berukuran misal m=2 baris dan n=3 kolom memiliki kompleksitas 2(2)(3)+2(2)+1 atau sebesar 17 langkah.

Ringkasan

Singkatnya, untuk kondisi if, total step adalah 1 baik ada atau tidak ada data. Return stepnya 1 jika tidak kosong. Kalang for (atau while) membutuhkan n+1 step dengan +1 perlu ditambahkan karena data kosong pun tetap dihitung 1 step. Contoh di atas diambil dari buku karya Ellis Horowitz (Computer Algorithms). Sekian, semoga bermanfaat.

Memanggil Fungsi Eksternal Pada Python

[Hari|Matkul|Jur|Dosen: Rabu.13.05.2020|Logika-prt.9|AK|Rahmadya,PhD]

Sebelumnya telah dibahas bagaimana menggunakan fungsi pada bahasa pemrograman Python (lihat pos yang lalu). Terkadang fungsi-fungsi tertentu digunakan oleh program-program Python lain sehingga perlu dibuat satu file terpisah agar tidak perlu menulis kode fungsi di tiap-tiap program. Misalnya kode pembelian barang berikut berisi kode yang ada di dalamnya fungsi yang dibutuhkan, didefinisikan dengan keyword “def”.

print(" ———Toko Amanah Jaya———")
def total(harga,jumlah):
	"""fungsi untuk menghitung Total bayar"""
	return harga*jumlah
def diskon(harga):
	""" fungsi menghitung diskon """
	if (harga >= 500000):
		potongan=harga*0.1
	else:
		potongan=harga*0.05
	return potongan
def bayar(harga,potongan):
	""" fungsi menghitung total bayar """
	return harga-potongan

#input data
harga= int(input("masukan harga barang: "))
jumlah= int(input("masukan jumlah baju yang dibeli: "))
Total=total(harga,jumlah)
potongan=diskon(Total)
tagihan=bayar(Total,potongan)
print("Total Harga = ", "Rp.",Total)
print("Diskon", "Rp.", potongan)
Bayar=int(input("Jumlah Nominal Uang =" ))
Kembalian= (Bayar-tagihan)
print("Uang Kembalian = ", "Rp.",Kembalian)

Bagaimana cara memindahkan fungsi tersebut ke file lain? Caranya mudah saja. Pertama cek dulu apakah program sudah berjalan sesuai dengan spesifikasinya. Jika sudah tidak ada masalah, tinggal “cut” saja dan buat file baru, di sini saya beri nama “diskon.py” dan letakan di folder yang sama. Jika dengan Google Colab, upload saja file tersebut di menu “upload file”. Untuk memanggil file tersebut gunakan instruksi “from” dan “import” di program utama berikut ini.

from diskon import total,diskon,bayar
print(" ———Toko Amanah Jaya———")
#input data
harga= int(input("masukan harga barang: "))
jumlah= int(input("masukan jumlah baju yang dibeli: "))
Total=total(harga,jumlah)
potongan=diskon(Total)
tagihan=bayar(Total,potongan)
print("Total Harga = ", "Rp.",Total)
print("Diskon", "Rp.", potongan)
Bayar=int(input("Jumlah Nominal Uang =" ))
Kembalian= (Bayar-tagihan)
print("Uang Kembalian = ", "Rp.",Kembalian)

Jalankan program dan pastikan berjalan seperti sebelumnya (tanpa file eksternal). Perhatikan juga penggunaan “if-else” pada python di file “diskon.py” tersebut.

Untuk jelasnya silahkan buka link youtube saya berikut ini.

Program Sederhana Python dengan Fungsi

[Hari|Matkul|Jur|Dosen: Rabu.29.04.2020|Logika-prt.7|AK|Rahmadya,PhD]

Jika pada pertemuan yang lalu program menggunakan input, proses dan output seperti biasa, pada pertemuan kali ini menggunakan sebuah fungsi. Setelah data diterima, fungsi dipanggil untuk memproses data tersebut. Hasilnya ditampilkan lewat perintah print.

print(" ———Toko Amanah Jaya———")
def total(harga,jumlah):
"""fungsi untuk menghitung Total bayar"""
return harga*jumlah
#input data
harga= int(input("masukan harga barang: "))
jumlah= int(input("masukan jumlah baju yang dibeli: "))
Total=total(harga,jumlah)
#diskon 5% tiap pembelian di atas Rp.100rb
if Total>100000:
Total=Total-0.05*Total
print("Total Harga = ", "Rp.",Total)
Bayar=int(input("Jumlah Nominal Uang =" ))
Kembalian= (Bayar-Total)
print("Uang Kembalian = ", "Rp.",Kembalian)

Baris kedua sampai keempat menunjukan fungsi perhitungan total yang harus dibayarkan. Kata kunci yang menyatakan sebuah fungsi adalah def dilanjutkan dengan tab segai indikator bahwa statemen tersebut adalah fungsi. Pada baris ke-10 dan ke-11 diperkenalkan cara menggunakan if untuk pengecekan kondisi tertentu, misalnya apa perlu diberi diskon atau tidak.

Untuk jelasnya dapat dilihat pada link berikut ini. Lihat postingan berikutnya tentang memanggil fungsi eksternal (file lain). Sekian, semoga bermanfaat.

Metaheuristic Optimization – Advanced

Metaheuristic pengertiannya telah sedikit diulas pada postingan yang lalu. Di sini sedikit diulas metode-metode yang dapat dikatakan advanced. Namun di sini advanced tidak serta-merta untuk tingkat lanjut melainkan sekedar memberitahukan metode-metode terbaru berdasarkan artikel-artikel jurnal yang sudah diterbitkan.

Metode heuristik terkini dapat diklasifikasikan berdasarkan aliran algoritma pencariannya, antara lain:

  • Mengambil inspirasi dari sifat-sifat alami (nature)
  • Mengambil inspirasi dari sifat-sifat fisika

Sifat-sifat yang diambil dari hukum alam telah banyak diteliti di metaheuristik, tetapi yang terkini dapat dirinci sebagai berikut:

  • PSO, bersasarkan sekolompok binatang dalam mencari makan
  • Dolphin     Echolocation (DE), berdasarkan teknik sonar yang dimiliki oleh lumba-lumba
  • Big Bang-Big Crunch (BB-BC), berdasarkan teori evolusi alam
  • Cuckoo Search (CS), berdasarkan sifat burung
  • Imperialist Competitive Algorithm (ICA)

Sementara itu ada algoritma-algoritma yang diambil dari sifat fisika, antara lain:

  • Charged System Search (CSS) dan Magnetic Charged System Search (MCSS), berdasarkan hukum Coulomb dan Newton
  • Colliding Bodies Optimization (CBO), berdasarkan tumbukan satu dimensi partikel
  • Ray Optimization (RO), berdasarkan hukum refraksi cahaya (snell)

Demikian kira-kira metode advanced metaheuristic yang bisa dibaca dari literatur-literatur baik jurnal maupun buku. Sekian informasinya, mudah-mudahan bisa dijelaskan lebih detil pada postingan berikutnya.

Praktek Longest Common Subsequence (LCS) dengan C++ Online

[algoritma|t.informatika|r.408|pert.11]

Longest Common Subsequence (LCS) merupakan rentetan string dari dua string yang dibandingkan. Misalnya string1: a-b-d-a-c-e dan string2: b-a-b-c-e.

Di sini b-a-c-e merupakan LCS. String a tidak boleh dengan a pada string 1 karena berbenturan dengan koneksi b-b antara string 1 dan string 2. Salah satu metode yang efisien adalah dengan pemrograman dinamis dengan cara:

  • Membuat tabel
  • Mengekstrak LCS

Tabel berisi arah panah (kiri, atas, atau diagonal) disertai nilai tertentu yang gunanya untuk mengekstrak LCS.

Dari tabel diketahui LCS yang berwarna pink yaitu b-a-c-e.

Implementasi Dalam Bentuk Program

Banyak situs-situs ok yang menyediakan kode sumber untuk algoritma mencari LCS lewat pemrograman dinamis. Untungnya juga banyak situs-situs yang menyediakan compiler beberapa bahasa pemrograman, misalnya bahasa C++. Jadi tidak perlu khawatir jika di komputer tidak terinstal kompiler C++. Bahkan bisa dijalankan lewat handphone. Situs yang jalan untuk kode program sampel berikut adalah onlinegdb. Hapus semua lembar kerjanya (berisi contoh program mengeprint: “hello word”) copy dan paste kode berikut:

Program tersebut mencontohkan mencari LCS dari dua string AGGTAB dan GXTXAYB yang menghasilkan string LCS: GTAB. Tekan tombol RUN dan lihat hasilnya di bagian bawah jendela onlinegdb. Atau ganti dengan contoh di atas Char X[]=”ABDACE” dan Char Y[]=”BABCE” yang hasilnya berikut:

Untuk mengetahui prinsip kerja dasarnya dapat dilihat di video sederhana berikut. Sekian semoga bermanfaat.

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.

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: