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.

Mengambil File Microsoft Word dan Indexing Pada Matlab

[inf.retrievalt.komputer|lab.software|pert.9]

Salah satu langkah perolehan informasi yang penting adalah pembuatan indeks. Indeks merupakan salah satu kunci untuk pencarian informasi. Untuk menghasilkan pengindeks yang baik perlu menggunakan teknik-teknik yang ada pada pemrosesan teks. Postingan kali ini bermaksud mengetahui cara pembuatan indeks dengan file yang diambil dari microsoft word.

Mengambil File Ms Word

Banyak informasi yang memberikan cara bagaimana mengambil file word agar bisa diproses lebih lanjut pada Matlab. Biasanya file yang langsung bisa digunakan adalah file berekstensi txt, namun karena banyaknya file berformat DOC atau DOCX maka perlu mengetahui cara pengambilan file bertipe itu agar bisa diolah lebih lanjut pada Matlab. Agar lebih nyaman, ada baiknya membuat Graphic User Interface (GUI) agar lebih mudah digunakan atau disimpan agar mudah digunakan nantinya.

Masuk ke callback Ambil File dan isikan kode berikut menggunakan uigetfile yang mengeluarkan form ambil file. Akhiri dengan membuat variabel agar bisa digunakan nantinya lewat mekanisme handles.

  • [a,b]=uigetfile(‘*.docx’)
  • handles.a=a;
  • handles.b=b;
  • guidata(hObject,handles)

Sementara pada callback Pra-Proses diisi dengan kode-kode berikut dimulai dari mengambil data dari word:

  • word = actxserver(‘Word.Application’);
  • file=strcat(handles.b,handles.a)
  • wdoc = word.Documents.Open(file);
  • sometext = wdoc.Content.Text;

Variabel “file” merupakan string yang diambil dari instruksi “uigetfile” pada pushbutton sebelumnya yang kemudian disimpan dalam variabel sometext. (Lihat penjelasannya di buku Text Mining dengan Matlab karya Bachs).

  • temp = sometext
  • temp = lower(temp)
  • temp = regexprep(temp,'</verse>’,’ S ‘)
  • temp = regexprep(temp,'<.*?”‘,”)
  • temp= regexprep(temp,’ ‘,”’,”’)
  • temp = regexprep(temp,’\W’,’ ‘)
  • temp = strtrim(regexprep(temp,’\s*’,’ ‘))
  • temp=regexprep(temp,’ ‘,”’,”’)
  • eval([‘wordsofverses={”’,temp,”’};’]);
  • limits = [0,find(strcmp(wordsofverses,’S’))]
  • for k=1:length(limits)-1
  • verses(k).vocab = unique(wordsofverses(limits(k)+1:limits(k+1)-1));
  • end;

Variabel “temp” berisi hasil pemrosesan yang dimulai dari lower untuk mengecilkan seluruh huruf hingga mengkonversi string word tersebut menjadi cell dalam variabel wordsofverses. Hasilnya kira-kira sebagai berikut. Semoga bermanfaat.

Lex and Yacc via Konsol (DOS Prompt)

[t.kompilasi|t.informatika|s.103|pert.11]

Jika yang lalu telah dibahas membuat kompiler lewat GUI Lex and Yacc, terkadang perlu mencoba lewat mode console karena jika bisa dengan mode ini, akan mudah jika menggunakan versi linux-nya. Coba masuk ke folder Lex and yacc di folder Flex Windows. Untuk memastikan file lex and yacc lengkap coba ketik “yacc –help”. Jika muncul seperti gambar berikut berarti tersedia.

Siapkan dulu file lex dan yacc contoh misalnya calc.l yang tersedia sebagai latihan. Ketik:

yacc –d –y calc2.y

Instruksi di atas akan menghasilkan dua file yaitu y.tab.h dan y.tab.c yang masing-masing adalah berturut-turut file header dan file bahasa c (bukan c++). Untuk yang LINUX (dengan nama aplikasi bison) sepertinya tidak perlu menggunakan –y (langsung yacc –d calc2.y saja). Tekan “dir y.tab*.*” untuk melihat kedua file tersebut.

Jalankan instruksi berikutnya:

lex calc2.l

Pastikan muncul file baru lex.yy.c yang akan digunakan untuk compile dan linking sehingga dihasilkan output calc.exe. Di sini linking antara lex.yy.c dengan y.tab.c hasil yacc sebelumnya.

cc lex.yy.c y.tab.c –ocalc2.exe

Hasilnya adalah file calc2.exe yang jika dijalankan dengan mengetik “calc2.exe” pada command prompt akan dihasilkan kalkulator berikut. Ketik 1+2 dan ketika ditekan enter muncul angka 3.

Oiya, postingan ini sekedar menginformasikan teknik pembuatan kompiler lewat aplikasi lex and yacc mode konsol yang biasanya jika menggunakan linux. Untuk yang dengan GUI lebih mudah lagi. Selamat mencoba.

Membuat Sebuah Interpreter dengan Lex and Yacc

[t.kompilasi|t.informatika|s.103|pert.10]

Jika pada pertemuan yang lalu dibahas bagaimana cara membuat kompiler yang berisi persamaan matematis dengan satu variabel keluaran, misal variabel x maka pada pertemuan kali ini akan diilustrasikan bagaimana membuat interpreter (yang berisi eksekusi baris-perbaris). Saat ini interpreter paling banyak digunakan mengingat aplikasi berbasis web yang paling banyak digunakan, misalnya php yang menerapkan prinsip interpreter.

Tutorial Lex and Yacc

Software Lex and Yacc memanfaatkan fasilitas yang dimiliki bahasa pemrograman c++. Hasilnya adalah sebuah kompiler baru yang sesuai dengan keinginan programmer. Untuk tutorial dapat dilihat di situs resminya yang disertai juga dengan contoh kode program yang akan digunakan pada postingan kali ini.

File-File yang Dibutuhkan

Seperti biasa file berekstensi *.l dan *.y diperlukan. Masing-masing berfungsi sebagai lexical generator (lex) dan semantic (yacc). Untuk sampel (silahkan unduh di sini), dua file utama adalah calc3.l dan calc3.y diperlukan selain satu buah file header, calc3.h. Ada satu buah file tambahan untuk interpreter (calc3a.c) yang menjalankan satu listing kalang/loop “while” sementara dua lainnya (calc3b.c dan calc3g.c). Lakukan proses kompilasi dan build pada calc3.l dan calc3.y.

Bagaimana cara menggunakan calc3a.c yang berfungsi sebagai interpreter? Tidak ada penjelasan detil pada situs resminya, sementara saya mengkopi isi dari calc3a.c di bawah instruksi “Include …” dan diletakan di bagian bawah calc3.y sebelum mengkompilasi file tersebut (akan menghasilkan y.tab.c dan y.tab.h). Jalankan file exe hasil build lex+yacc hingga menghasilkan interpreter di bawah. Untuk yang compiler dan graph sepertinya butuh penjelasan yang lebih rinci lagi di postingan yang akan datang.

 

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.

Membuat Compiler Sendiri – Persamaan Matematis

[tek.kompilasi|t.inf|s.104|pert.9]

Pertemuan yang lalu telah disinggung membuat kompiler yang melakukan operasi perhitungan layaknya menggunakan kalkulator. Di sini dengan Lex and Yacc akan dicoba membuat kompiler yang bisa melakukan perhitungan seperti ini:

Yang belum mempunyai software lex and yacc silahkan klik di sini untuk mengunduhnya dengan ukuran sekitar 20-an Mb. Kebetulan software yang dishare berbasis Windows. Jika ingin yang linux, vendor juga menyediakan aplikasi lex and yacc berbasis linux seperti Ubuntu.

Prinsip Kerja

Generasi saya (kuliah 90-an) hanya mengenal disket dan belum mengenal punch card yang berisi kartu berlubang yang fungsinya sebagai instruksi ke komputer. Bayangkan jika kita diminta menghitung iterasi ratusan kali dengan kalkulator, tentu akan bentol jempol kita. Tapi dengan menginstruksikan agar komputer menghitung iterasi ratusan kali tersebut, sekali jalan langsung selesai. Jika dulu dengan kartu berlubang, saat ini instruksi berbasis teks yang diketik. Jadi komputer harus mampu melakukan scanning agar mengetahui instruksi tersebut sesuai dengan aturan sebelumnya atau tidak, baik dari sisi kata perkata atau logika yang berupa grammar. Jadi Lex and Yacc memiliki dua mesin:

  • Scanning kata per kata dengan mesin Lex (singkatan dari lexical generator), dan
  • Grammar check dengan mesin Yacc (singkatan dari yet another compilers compiler)

Makanya software tersebut dinamakan Lex and Yacc. Jika software sudah diinstal, silahkan pelajari dari situs resminya, yang juga dilengkapi dengan kode sumber untuk praktek kali ini.

Mengkompilasi File Lex

Ada dua file yang diperlukan untuk menghasilkan satu kompiler yaitu file lex (berekstensi *.l) dan yacc (berekstensi *.y). Silahkan masuk ke bab “Practice 2”. Kopi-kan saja ke Flex Windows (software Lex and Yacc versi windows) yang baru kita instal. Masuk ke menu Tools – Lex Compile. Lanjutkan dengan masuk ke menu yang sama: Tools – Lex Build. Maka akan dihasilkan satu file baru lex.yy.c yang merupakan hasil generate ke bahasa c.

Mengkompilasi File Yacc

Jika Lex bertanggung jawab mengecek kata/word yang terdaftar di bahasa pemrograman yang dirancang, Yacc bertanggung jawab terhadap grammatical-nya. Buat kode dengan nama yang sama dengan file Lex, hanya saja untuk Yacc harus berekstensi *.y. Lakukan proses yang sama dengan Lex di menu Tools – Yacc Compile dan dilanjutkan dengan membuild beserta Lex-nya lewat menu yang sama Tools – Lex+Yacc Build. Hasil dari proses kompilasi adalah dua buah file y.tab.c dan y.tab.h yang satu untuk header (di bahasa c dengan kode #include) yaitu y.tab.h dan satu lagi y.tab.c digunakan untuk build Lex+Yacc. Di bagian indikator bawah pastikan tidak ada masalah dan cek di file lokasi penyimpanan (di folder yang sama dengan lex dan yacc) apakah file berekstensi exe dengan nama yang sama dengan lex and yacc ada, misalnya yang saya gunakan calc2.exe.

Menjalankan Bahasa Pemrograman

Ada dua cara menjalankan bahasa pemrograman yang baru dibentuk yaitu dengan mengklik file calc2.exe atau nama lain yang Anda buat, atau dengan menekan Tools – Execute Exe Directly. Hasilnya akan memunculkan jendela di bawah ini, coba dengan melakukan operasi matematis tertentu dengan variabel. Selamat mencoba, semoga bermanfaat.

NOTE: Ada kesalahan di bagian yacc, tambahkan di bagian atas:

  • %{
  • #include <stdio.h>
  • void yyerror(char *);
  • int yylex(void);
  • int sym[26];
  • %}

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.

Shift and Reduce Parsing

[tek.kompilasi|t.informatika|s-103|pert.8]

Untuk orang yang non ilmu komputer atau teknik informatika, istilah parsing merupakan istilah asing yang membuat dahi keriput. Bagaimana tidak, hanya menggunakan bahasa pemrograman saja sudah pusing, ini malah diminta membuat suatu bahasa pemrograman. Tapi perlu diingat, salah satu kewajiban pembelajaran adalah “apakah yang kita ajarkan sudah seharusnya yang kita ajarkan?”. Pertanyaan itu merupakan pertanyaan yang harus dijawab. Pertanyaan yang dikeluarkan oleh Mahatma Gandhi ketika India baru merdeka dan ingin segera bersaing dengan negara maju.

Grammar

Kembali ke proses pembuatan bahasa pemrograman. Sebelum bisa membuat suatu bahasa, perlu mengetahui cara kerja suatu bahasa. Bahasa bekerja mengikut grammar yang ada. Chomsky mengusulkan suatu context free grammar yang bebas dari linguistik lokal yang tidak beraturan. Sebagai contoh kita memiliki aturan grammar sebagai berikut:

Apa maksudnya? Di sini ada tiga aturan yang membolehkan pengguna mengoperasikan: 1) variabel ditambah variabel. Variabel di sini diistilahkan dengan non-terminal (bukan titik destinasi akhir), sementara terminal berupa konstanta atau operasi seperti tambah, kurang, kali dan bagi. 2) variabel dikalikan dengan variabel, serta 3) variabel diisi oleh konstanta. Secara singkat, notasi grammar di atas dapat ditulis dalam satu baris: E->E+E|E*E|id. Ekspresi di atas mengikut kaidah Backus Naur Form (BNF) yang terkenal untuk context free language.

Tugas bagian parsing adalah mengecek validitas operasi yang diberikan oleh pengguna apakah sudah sesuai dengan grammar yang ada atau tidak. Sebagai contoh user mengetikan persamaan matematis: E->x+y*z. Parsing akan mengecek apakah sudah sesuai atau tidak dengan grammar.

Shift and Reduce Parsing

Sesuai dengan namanya metode ini mengkombinasikan antara penggeseran dan pengurangan parsing. Contoh sebelumnya jika kita kerjakan maka otak kita lebih mudah mengerjakan lewat mekanisme ‘top down’ sambil melihat grammarnya. Dalam contoh di atas, ada penjumlahan (x+y) dan perkalian (dengan z). Dengan menggunakan left hand first diperoleh urutan berikut ini:

Perhatikan aturan grammar yang diterapkan di dalam kurung di samping kanan proses top-down. Pertama-tama digunakan aturan perkalian yang menghasilkan dua non-terminal E. E yang kanan dengan menerapkan rule no.3 diperoleh konversi dari E ke id (dalam hal ini z). Langkah berikutnya dengan menggunakan aturan no.1 dimana E menurunkan E+E (simbol -> diistilahkan turunan (derrive). Teruskan dengan menggunakan rule no. 3 akan merubah non-terminal menjadi terminal berturut-turut x dan y. Karena hasil akhir sama dengan soal, maka dapat dikatakan instruksi x+y*z dapat diterima parser.

Kita mungkin mudah mengerjakan dengan top-down method ini. Bagaimana dengan komputer? Tentu saja berbeda dengan otak kita. Untuk itulah metode shift and reduce layak diperhitungkan. Cara kerja shift and reduce adalah sebagai berikut:

  • Tulis operasi yang akan dicek grammar-nya
  • Lakukan operasi shift untuk memisahkan non-terminal/variabel yang akan diisikan id.
  • Lakukan operasi reduce untuk mengganti variabel menjadi terminal.

Perhatikan 11 langkah di atas, yang merupakan tipikal operasi shift and reduce. Pada langkah pertama, instuksi akan siap-siap melakukan proses “shift” dimana x bergeser ke kiri. Selanjutnya, x yang telah berada di kiri dikonversi menjadi terminal/variabel E. Berikutnya langkah ke3 dan 4 dua buah proses shift yaitu untuk plus dan y dilanjutkan dengan reduce y menjadi terminal E. Langkah 8, 9, dan 10 bermaksud mereduksi instruksi mengikut grammar sehingga dihasilkan E yang artinya instruksi x+y*z dapat diterima (accepted). Berikutnya akan dicoba lewat perangkat lunak Lex and Yacc, khususnya bagian Yacc yang bertanggung jawab mengurusi Grammar.

Perhatikan saat kompilasi Yacc di bagian komentar. Tampak Yacc menunjukan 4 shift/reduce [1] yang konflik. Ini tipikal dari bagian pengecekan instruksi (dengan shift and reduce). Perhatikan di sini saya iseng mengganti “+” dengan “p” dan “-” dengan “m”. Kira-kira hasil bahasa pemrograman primitif sebagai berikut di bawah ini. Perhatikan, “p” bermakna plus dan “m” bermakna minus. Sekian, semoga bermanfaat.

 

Membuat Bahasa Pemrograman Sendiri

[tek.kompilasi|tek.inf|s-103|pert.7]

Sebelumnya kita kerap melihat program yang dibuat oleh pengembang. Program yang dibuat tersebut diramu dengan bahasa pemrograman tertentu seperti visual basic, c++, pascal, php, phyton, dan lain-lain. Pernahkah berfikir siapa yang membuat bahasa pemrograman tersebut? Apakah sama dengan membuat program? Postingan kali ini sedikit banyak menjelaskan masalah itu.

Compiler atau Interpreter?

Di tahun 80-an atau 90-an waktu SMA saya belajar bahasa basic sebagai bahasa pemrograman. Materi tersebut disisipkan dalam mata pelajaran matematika. Jadi tidak heran di beberapa universitas ilmu komputer merupakan sempalan dari jurusan matematika. Bahasa basic sendiri ketika diprogram hasilnya berupa program executable (*.exe). Proses membentuk source code (format text berekstensi *.bas) menjadi *.exe dikenal dengan istilah kompilasi atau beberapa aplikasi diberi nama deployment. Bagaimana dengan bahasa pemrograman lainnya seperti php?

Berkembangnya website membuat tuntutan terhadap aplikasi yang bisa berjalan di atas platform tersebut. Salah satunya adalah php dengan basis datanya yang terkenal MySQL. Bahasa ini berbeda dengan bahasa berbasis desktop seperti VB, C++, dan sejenisnya karena instruksi tidak dikompilasi menjadi executable, melainkan dijalankan baris per baris di engine PHP. Jadi kode sumber tersimpan dalam server (biasanya apache). Proses penerjemahan kode sumber menjadi eksekusi dikenal dengan istilah interpreter. Perbedaan nyatanya adalah jika program yang di-compile dapat dijalankan hanya dengan mengandalkan sistem operasi, pada program yang dijalankan dengan interpreter membutuhkan engine pembaca, salah satunya browser seperti mozilla, internet explorer, safari dan lain-lain. Salah satu keunggulannya adalah karena berbasis browser maka dapat dijalankan di berbagai platform (windows, linux, dll) atau pun beragam alat seperti PC, laptop, handphone, tablet dan lain-lain yang memiliki browser. Java sendiri sebelumnya memang telah getol mengembangkan kompilernya dengan teknik byte code yang dapat dijalankan diberagam platform dan mesin, asalkan menginstal terlebih dahulu Java Runtime-nya (JRE).

Peran Pembuat Bahasa Pemrograman

Dahulu, pembuat bahasa pemrograman dapat diibaratkan sebagai fardhu kifayah (maksudnya cukup segelintir orang saja yang mengerjakan), yaitu para vendor bahasa pemrograman. Namun saat ini dikala merajalelanya aplikasi berbasis android maka kebutuhan akan bahasa pemrograman yang mudah dan memanjakan programmer mutlak diperlukan. Apalagi saat ini programmer tidak harus dari jurusan informatika dan komputer, jadi peran pembuat bahasa pemrograman banyak diperlukan. Bahkan seoarang anak SD pun saat ini mampu membuat aplikasi android yang canggih berkat bantuan compiler yang spesifik untuk aplikasi tertentu, khususnya di android atau ios.

Aplikasi Pembuat Bahasa

Memang untuk bisa menggunakan aplikasi-aplikasi pembuat bahasa pemrograman diperlukan teori khusus yaitu teori otomata dan bahasa (grammar). Tanpa hal itu dijamin kebingungan menggunakannya. Biasanya aplikasi yang digunakan untuk membuat bahasa adalah aplikasi yang berbasis C++ atau Java. Salah satu yang terkenal dan banyak dijadikan bahan praktek mata kuliah teknik kompilasi adalah Lex and Yacc (lihat pertemuan 6). Bagan dibawah adalah proses pembuatan bahasa pemrograman dengan mengkonversi Lex-file dan Yacc-file menjadi executable.

Di sini dicontohkan dua buah kode sumber (bas.y dan bas.l) yang masing-masing berfungsi sebagai grammar (yacc) dan scanner (lex). Setelah di-build/compile dengan cc, diperoleh file bas.exe yang siap digunakan. Apa maksudnya? Sepertinya masih bingung ya.

Kita ambil contoh sebuah bahasa pemrograman Matlab. Jalankan Matlab.exe (bahasa pemrograman) dan masuk ke Command Window. Ketik 1+1 dan tekan Enter. Apa yang dihasilkan? Matlab akan meng-scan 1+1 dan mengeksekusi menjadi “makna” penjumlahan satu dengan satu dan dihasilkan 2.

Walaupun sederhana banget, toh itu contoh bahasa pemrograman. Perlu diketahui Matlab biasanya berfungsi sebagai interpreter (Matlab harus dibuka untuk menjalankan program m-file) namun bisa juga sebagai compiler (terlebih dahulu mengkompilasi m-file menjadi exe). Di pertemuan berikutnya akan kita coba menggunakan lex and yacc untuk membuat bahasa pemrograman seperti Matlab di atas (walau sederhana) seperti di bawah ini. Terus mengikuti ya.

 

 

Instal Lex and Yacc untuk Praktikum Teknik Kompilasi

[tek.kompilasi|tek.informatika|s.103|pert.6]

Compilers and language atau yang di Indonesia dikenal dengan mata kuliah teknik kompilasi merupakan materi dasar ilmu komputer, teknik informatika atau sistem komputer. Isinya adalah seluk beluk bagaimana compiler bekerja dari saat scanning, parsing, hingga menghasilkan output dalam bahasa mesin (komputer).

Peran Kompiler

Dahulu, teori-teori kompilasi yang berasal dari teori automata dan grammar dapat diibaratkan “fardhu kifayah”. Hanya segelintir yang tertarik, karena fokusnya adalah menciptakan compiler yang handal dan interaktif, dimana tiap kesalahan dapat diketahui letak kesalahannya. Level mahasiswa doktoral yang biasanya mengutak-atik bidang ini.

Namun saat ini dengan makin memasyarakatnya bidang pemrograman, para pemerhati kompiler berusaha membuat compiler yang bahkan mensuport para anak-anak yang tertarik dengan bahasa pemrograman. Munculnya bahasa-bahasa baru seperti Groovy, Rust, Elixir, Go, Swift, Arduino, Kotlin, dan bahasa pemrograman untuk Android. Android sendiri sangat mensuport Kotlin yang merupakan bahasa pemrograman yang dirancang dalam rangka mengisi kelemahan-kelemahan Java.

Lex and Yacc

Lex yang merupakan Lexical Analyzer Generator bermaksud men-scan kode yang ditulis. Sementara pasangannya Yacc (yet another compilers compiler) berfungsi melakukan parsing berdasarkan grammar. Dengan lex and yacc ini kita dapat membuat kompiler sendiri yang akan memerintahkan komputer menjalankan instruksi sesuai keinginan kita. Misalnya jika dalam bahasa pemrograman rata-rata menggunakan kata “if-else”, maka kita bisa saja menggantinya menjadi “jika-maka” setelah mengaturnya dengan Lex and Yacc ini. Silahkan unduh sourcecode nya lewat Google, lalu instal.

Instalasi

Lex and Yacc dapat berjalan di banyak platform. Untuk mudahnya di sini akan kita coba pada Windows 10. Setelah memperoleh kode sumbernya, klik ganda hingga muncul informasi bahwa akan diinstal Lex and Yacc.

Tekan saja Next> untuk lanjut ke menu persetujuan. Tekan saja Agree.

Berikutnya, Lex and Yacc akan meminta folder tempat program diinstal. Arahkan sesuai dengan keinginan, atau biarkan secara default dengan menekan Next>.

Berikutnya instalasi menanyakan lokasi menu folder Lex and Yacc nantinya. Biarkan secara default saja.

Akhirnya setelah menekan tombol Install maka proses instalasi akan berjalan hingga selesai. Hanya butuh satu hingga beberapa menit.

Pastikan instalasi lengkap dan tombol Finish muncul. Centang jika ingin langsung menjalankan aplikasi ini.

Akan muncul konsol dos (CMD) ketika aplikasi ini berjalan. Tunggu sesaat.

Jika sudah muncul tampilan seperti gambar di bawah berarti Lex and Yacc sudah siap untuk digunakan. Silahkan cari tatacara penggunaannya, bahkan ada juga yang menyediakan sampel programnya. Selamat mencoba.

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: