Aplikasi Algoritma DFS dan BFS di Dalam Search Engine Lokal

Aplikasi Algoritma DFS dan BFS di Dalam Search Engine Lokal - Mesin pencari atau search engine adalah kakas yang sangat berguna untuk mencari informasi yang dibutuhkan di dalam sekumpulan data yang tidak berstruktur seperti data di dalam internet atau data di dalam struktur direktori (folder). Contoh mesin pencari yang terkenal adalah Google, yang digunakan untuk mencari data di internet (Gambar 1).

Gambar 1 : Contoh antarmuka Google

Pada Tugas Besar II kali ini anda diminta membuat aplikasi search engine lokal mirip seperti Google, namun tidak sepenuhnya sama seperti Google. Mesin pencari yang anda akan buat hanya digunakan untuk mencari dokumen di dalam direktori Windows yang mengandung kata, frase kata, atau penggalan kalimat yang diinginkan dengan menggunakan fungsi string matching yang sudah tersedia di dalam bahasa pemrogaman (dalam hal ini Bahasa C#). Anda tidak perlu lagi membuat program string matching (belum diajarkan di dalam kuliah).

Dokumen-dokumen tersebut tersebar pada berbagai folder (directory) di dalam sebuah direktori. Pengguna ingin mencari dokumen yang mengandung string tertentu. String tersebut bisa berupa kata, frase kata, atau penggalan kalimat. Dengan mesin pencari yang anda buat, seluruh dokumen yang relevan (teks/doc) di dalam folder dibuka lalu string yang dicari dicocokkan dengan teks di dalam berkas. Selanjutnya, semua dokumen yang mengandung string yang dicari ditampilkan daftarnya di layar yang terdiri sejumlah kalimat yang mengandung string yang dicari. Setiap penggalan kalimat yang ditampilkan mengandung hyperlink sehingga dengan mengklik kalimat tersebut isi di dalam berkas ditampilkan di layar dalam sebuah window. Mirip dengan pencarian di dalam Google, jika pengguna mengetikkan query ‘himpunan’ di dalam antarmuka search engine, maka maka mesin pencari menampilkan semua dokumen yang mengandung string ‘himpunan’, kira-kira contoh hasilnya sebagai berikut:

Teori himpunan di dalam matematika
Himpunan Mahasiswa Kos Kuliah
...terbagi menjadi dua himpunan yang berukuran n/2
Perhimpunan Islam Tionghoa Indonesia (PITI)

Dengan meng-klik pranala yang terdapat pada judul, maka aplikasi membuka dokumen tersebut dan menampilkan isinya di layar.

Inti dari search engine adalah program explorer (atau crawler). Perhatikan bahwa direktori terdiri dari sekumpulan folder, dan setiap folder dapat memiliki sub-folder lagi atau dokumen (Gambar 2). Struktur direktori sama dengan struktur pohon.

Gambar 2. Contoh sebuah direktori

Bagaimana cara explorer melakukan penjelajahan?

Program explorer menjelajah seluruh folder dengan menggunakan algoritma DFS/BFS (Gambar 3), menemukan dokumen (yang merupakan daun dari pohon), lalu mencocokkan query dengan dengan isi dokumen.

Gambar 3 : Prinsip BFS dan DFS dalam penjelajahan direktori

Spesifikasi program :

1. Program search engine yang anda buat terdiri dari dua bagian: Program query dan explorer. Program query adalah berupa antarmuka pengguna-komputer, program query dibuat berbasis web (web-base). Tampilan antarmuka pengguna-komputer kira-kira seperti Gambar 4 di bawah ini:

Gambar 4 : Antarmuka program query

• Path : pengguna dapat menspesifikan path yang menyatakan folder tertentu (misalnya D:/Dataku/Laporan) atau disk drive (D:/, F:/, G:/)
• Algoritma traversal : pengguna dapat memilih algoritma DFS/BFS.
• Perihal : keterangan tentang program dan pembuatnya

Anda dapat menambahkan menu lainnya, gambar, logo, dan sebagainya

Program explorer adalah inti dari mesin pencari. Di dalam explorer terdapat implementasi algoritma DFS/BFS dan pencocokan string dengan menggunakan Bahasa C#.

2. Program explorer melakukan pencocokan string pada setiap dokumen yang terdapat di dalam folder. Seluruh dokumen yang mengandung query yang cocok ditampilkan daftarnya di halaman antarmuka. Misalnya jika query yang dimasukkan pengguna adalah “merapi”, maka luaran yang dihasilkan adalah seluruh dokumen yang mengandung kata “merapi” dan beberapa kalimat di dalam dokumen yang mengandung kata “merapi”, seperti pada contoh berikut:

Gunung Merapi meletus pada Jumat Dinihari
… penduduk di sekitar Merapi….letusan di puncak Merapi ….

Jalan-jalan ke Gunung Merapi
... liburan banyak yang jalan-jalan ke Kaliurang di kaki Merapi …

Mbah Maridjan, Juru Kunci Merapi
... diangkat oleh raja sebagai penunggu Merapi … dekat Sleman, gunung Merapi..

Antara Keraton, Merapi, dan Laut Kidul
… orang Jawa percaya antara Merapi dan Laut Kidul ….

3. Pohon ruang status (state space tree) dibangun selama pencarian.
4. Dokumen yang dicari minimal dokumen text dan word saja. Dokumen text adalah semua dokumen yang berekstensi .txt, .html, .htm, .c, .pas, .java, dan lain-lain. Dokumen word adalah dokumen berekstensi .doc dan .docx.
5. Pengguna dapat mengklik pranala pada judul tulisan yang terdapat di dalam hasil pencarian, kemudian aplikasi yang bersesuaian membuka dokumen tersebut.
6. Tampilkan progress bar selama proses pencarian untuk memperlihatkan kemajuan pencarian kepada pengguna.

7. Beri nama aplikasi search engine anda ini dengan nama yang menarik
8. Bonus (nilai 10): Membuat video aplikasi dan diunggah ke Youtube

Contoh video tubes tahun lalu: https://www.youtube.com/watch?v=j-GCBJA76YU dan https://www.youtube.com/watch?v=mrJxvm1LDKg

Data Uji

Data uji yang digunakan adalah sekumpulan dokumen teks dan word (dapat anda cari sendiri sendiri dari media daring (online)). Dokumen dapat berbahasa Indonesia atau Inggris. Untuk dokumen teks paling sedikit ada 50 dokumen yang dapat diambil dari media daring, kode program, dan lain-lain.

Lain – lain :

1. Anda dapat menambahkan feature-feature lain yang menunjang program yang anda buat (unsur kreatifitas diperbolehkan/dianjurkan). 
2. Anda dapat menambahkan pencarian berdasarkan nama file. 
3. Tipe dokumen minimal adakah teks dan doc, namun anda dapat menambahkan tipe lan seperti spreadsheet, pdf, dan lain-lain. 
4. Program explorer menggunakan Bahasa C#. 
5. Program query berbasis web dan dapat dikembangkan dengan salah satu kakas pemrograman web (PHP, JSP (Java Server Pages), JavaScript, dll). 
6. Tugas dikerjakan per kelompok dengan jumlah anggota maksimal 3 orang dan tidak sama dengan anggota kelompok sebelumnya. 
7. Program harus modular dan mengandung komentar yang jelas. 
8. Mahasiswa harus membuat program sendiri, tetapi belajar dari contoh-contoh program serupa yang sudah ada tidak dilarang (tidak boleh mengkopi source code dari program orang lain). 
9. Pengumpulan paling lambat adalah tanggal 30 Maret 2015 pukul 7.30. Asisten akan menunggu di lab IRK untuk pengumpulan. Keterlambatan akan mengurangi nilai. 
10. Program disimpan di dalam folder StrAlgo2-xxxxx. Lima digit terakhir adalah NIM anggota terkecil. Didalam folder tersebut terdapat tiga folder bin, src dan doc yang masing-masing berisi :
    a. Folder bin berisi executable file (exe)
    b. Folder src berisi source code dari program
    c. Folder test berisi data uji.
    d. Folder doc berisi dokumentasi program dan readme
    Folder ini disimpan dalam bentuk CD untuk dikumpulkan bersama berkas laporan dimasukan kedalam amplop coklat. 
11. Semua pertanyaan menyangkut tugas ini harus dikomunikasikan melalui milis agar dapat dicermati oleh semua peserta kuliah IF2211 (milis IF2211@students.if.itb.ac.id). 
12. Demo program akan dilaksanakan pada tanggal yang dimumkan oleh asisten. Peserta mengisi jadwal demo yang disediakan pada saat pengumpulan tugas. 
13. Tiap anggota harus memahami proses pembuatan program, karena akan ada pertanyaan-pertanyaan yang harus dijawab per individu. 
14. Pada saat demo, asisten akan memanggil per kelompok sesuai jadwal yang telah diisi sebelumnya. Kelompok yang tidak berkepentingan dilarang masuk. Demo dilakukan di Lab IRK. 

Isi laporan :

Cover : Cover laporan ada foto anggota kelompok (foto bertiga). Foto ini menggantikan logo “gajah” ganesha.

Bab 1: Deskripsi masalah (dapat meng-copy paste file tugas ini)

Bab 2: Dasar teori

Bab 3 : Analisis Pemecahan Masalah. Langkah-langkah pemecahan masalah ada di sini beserta contoh ilustrasi.

Bab 4 : Implementasi dan pengujian. Bab ini berisi:

1. Spesifikasi teknis program, termasuk di dalamnya struktur data atau kelas objek yang didefinisikan, fungsi dan prosedur (header fungsi dan prosedur saja, tidak perlu source code), antarmuka, dan lain-lain yang dianggap perlu. 
2. Eksperimen/pengujian dengan contoh-contoh query. 
3. Analisis hasil pengujian (DFS dan BFS), misalnya waktu pencarian, jumlah simpul yang dikunjungi, dsb

Bab 5 : Kesimpulan dan saran (hasil yang dicapai, saran pengembangan).

Tuliskan juga referensi (buku, web), yang dipakai/diacu di dalam Daftar Referensi.

Keterangan Laporan :

1. Laporan ditulis dalam bahasa Indonesia yang baik dan benar, tidak perlu panjang tetapi tepat sasaran dan jelas. 
2. Laporan tidak perlu memakai cover mika dan dijilid. Cukup dibuat agar laporan tidak akan tercecer bila dibaca. 
3. Laporan boleh menggunakan kertas rius, boleh bolak-balik, boleh dalam satu halaman kertas terdapat dua halaman tulisan asalkan masih terbaca. 
4. Identitas per halaman harus jelas (misalnya : halaman, kode kuliah). 

Penilaian :

1. Kebenaran program (40%) : program mampu berjalan sesuai dengan spesifikasi yang diberikan. 
2. Demo – pemahaman Anda dalam pembuatan program (30%) 
3. Laporan (20%) 
4. Interface, feature-feature program, dan unsur kreativitas (10%) 

Sekian Artikel Aplikasi Algoritma DFS dan BFS di Dalam Search Engine Lokal.

Aplikasi Algoritma Greedy Pada Smart Building Environment

Aplikasi Algoritma Greedy Pada Smart Building Environment - Saat, ini teknologi smart grid sudah semakin maju. Smart grid yang dimaksudkan di sini adalah teknologi yang merupakan integrasi dari berbagai proses dalam sistem tenaga listrik, mulai dari sumber penghasil listrik hingga sampai pada konsumen pengguna listrik, baik rumah tangga maupun perkantoran. Dengan memanfaatkan teknologi komunikasi dan pemrosesan komputer, smart grid bertujuan untuk dapat memanfaatkan tenaga listrik yang seefektif dan seefisien mungkin.

Lingkungan smart building, juga mulai banyak menggunakan teknologi ini, dengan memanfaatkan smart meter. Dengan smart meter, penggunaan listrik setiap waktu nya dapat langsung diketahui baik oleh konsumen maupun oleh pihak penyedia layanan listrik. Penyedia layanan listrik, dapat menerapkan tarif yang berbeda-beda untuk setiap slot waktu tertentu dalam satu hari. Pada saat-saat tertentu, biasanya saat penggunaan listrik cukup banyak, tarif yang diberlakukan adalah tarif mahal. Hal ini bertujuan agar konsumen dapat mengalihkan penggunaan listrik pada slot waktu lain, sehingga tidak menumpuk beban nya pada slot waktu tertentu.

Tarif listrik tersebut menerapkan system progresif, artinya semakin banyak penggunaan listrik, maka tarif per kWh juga akan meningkat. Gambar 1 menunjukkan contoh tarif listrik yang bersifat dinamik. Pada gambar tersebut, terlihat bahwa pada jam 07.00 – 16.00 adalah waktu puncak, di mana pemakaian listrik umumnya meningkat. Pada saat tersebut, tarif dasar listrik yang diberlakukan juga berbeda. Tarif juga bersifat progresif, dalam arti saat penggunaan listrik meningkat maka tariff per kWh juga meningkat.Sebagai contoh pada Gambar 1, penggunaan listrik pada jam 00.00 – 06.00 tarif dasarnya adalah sekitar 20/ kWh. Namun jika penggunaannya sudah mencapai 200 kWh, maka tarifnya menjadi 50/ kWh. Peningkatan tarif per kWh berlaku seiring meningkatnya jumlah pemakaian listrik.

Dengan adanya informasi dari smart meter dan informasi tarif dari penyedia listrik, maka pemilik smart building dapat mengatur penggunaan peralatan listrik di rumahnya agar mendapatkan biaya listrik seminimal mungkin, namun kebutuhannya terpenuhi.Pengaturan yang perlu dilakukan oleh pemilik smart building adalah penentuan kapan suatu peralatan listrik harus dinyalakan, dan kapan harus dimatikan. Sebagai contoh, jika terdapat 23 alat listrik, dan satu slot waktu untuk penentuan on atau off alat listrik adalah 30 menit, maka banyaknya kemungkinan jadwal untuk satu hari adalah:

Gambar 1 : Contoh tarif listrik yang dinamis

Setiap peralatan listrik, akan memiliki batasan kapan bisa dinyalakan, dan kapan harus dimatikan, sehingga alokasi waktu penyalaan harus dilakukan pada rentang waktu tersebut. Contoh pada Gambar

2 dapat dilihat, setiap aktivitas memiliki batasan waktu mulai dan waktu selesai. Oleh karena itu aktivitas tersebut harus dialokasikan di antara batasan waktu tersebut.

Gambar 2 : Contoh persoalan alokasi task

Di dalam tugas ini, Anda diminta mengaplikasikan algoritma greedy untuk mendapatkan tagihan biaya listrik seminimal mungkin, namun kebutuhan peralatan listrik yang diinginkan dapat terpenuhi semaksimal mungkin.Setiap peralatan listrik akan memiliki waktu minimum harus dinyalakan, bersifat wajib atau opsional untuk dinyalakan, serta waktu tertentu dapat beroperasi. Di akhir aplikasi yang anda buat, harus ada perhitungan kompleksitas dari pendekatan greedy yang Anda gunakan. Pada saat demo tugas, asisten akan memberikan file teks yang berisi daftar tarif dan daftar peralatan listrik. Setiap kelompok akan dibandingkan hasil akhir nya, dan kelompok dengan optimasi terbaik, serta kompleksitas yang optimal, adalah kelompok pemenang dan mendapatkan nilai bonus. Jadwal yang dihasilkan dapat ditampilkan dengan visualisasi yang menarik dan ‘mudah’ dibaca oleh yang menggunakan.

Spesifikasi Program :

Program mampu membaca input file berisi daftar tarif setiap slot waktu, daftar peralatan listrik konsumen, dan kebutuhan waktu penggunaan alat listrik dengan satuan slot waktu.

2. Program menampilkan hasil penjadwalan dalam visualisasi yang memudahkan pengguna melihat, dengan menampilkan tarif yang dikeluarkan berdasarkan jadwal yang dibuat, dan terlihat alat listrik mana yang mendapatkan alokasi, dan mana yang tidak mendapatkan alokasi.

3 .Setiap kelompok harus menyatakan secara eksplisit semuaspesifikasi detil tambahan yang dibutuhkan.

Lain-Lain :

1. Anda dapat menambahkan fitur fungsional lain yang menunjang program yang anda buat (unsur kreatifitas).Sebagai contoh, hasil penjadwalan bisa dilakukan “drag and drop”, dan saat dilakukan terlihat task mana yang dilanggar dan perubahan tarif yang dihasilkan.Jika diperlukan penyederhanaan, jelaskanlah alasannya pada laporan dan deskripsikanlah penyederhanaan yang dilakukan tersebut. 
2. Program ini harus Anda buat berbasis Graphical User Interface (GUI). 
3. Tugas dikerjakan per kelompok dengan jumlah anggota adalah 3 orang dan boleh lintas kelas. 
4. Program harus modular dan mengandung komentar yang jelas. 
5. Mahasiswa harus membuat program sendiri, tetapi belajar dari contoh-contoh program game serupa yang sudah ada tidak dilarang (tidak boleh mengkopi source code dari program orang lain). 
6. Pengumpulan paling lambat adalah tanggal 23Februari 2014pukul 7.30. Keterlambatan akan mengurangi nilai. 
7. Program disimpan di dalam folder StrAlgo1-xxxxx. Lima digit terakhir adalah NIM anggota terkecil. Didalam folder tersebut terdapat tiga folder bin, src dan doc yang masing-masing berisi :
   a. Folder bin berisi executable file (exe)
   b. Folder src berisi source code dari program
   c. Folder doc berisi dokumentasi program dan readme
   Folder ini disimpan dalam bentuk CD untuk dikumpulkan bersama berkas laporan dimasukan kedalam amplop coklat. 
8. Semua pertanyaan menyangkut tugas ini harus dikomunikasikan melalui milis agar dapat dicermati oleh semua peserta kuliah IF2211 (milis IF2211@students.if.itb.ac.id. 
9. Demo program akan dilaksanakan setelah pengumpulan. Jadwal demo akan diumumkan pada saat pengumpulan di Lab IRK. Pengaturan jadwal demo akan dikoordinasikan oleh asisten. 
10. Tiap anggota harus memahami proses pembuatan program, karena akan ada pertanyaan-pertanyaan yang harus dijawab per individu. 
11. Pada saat demo, asisten akan memanggil per kelompok sesuai jadwal yang diisi sebelumnya. Kelompok yang tidak berkepentingan dilarang masuk. Demo dilakukan di Lab IRK. 

Isi laporan :

Cover : Cover laporan ada foto anggota kelompok (foto bertiga).

Foto ini menggantikan logo “gajah” ganesha.

Bab 1: Deskripsi masalah

Dapat meng-copy paste file tugas ini

Bab 2 : Dasar teori 

Berisi deskripsi singkat algoritma greedy.

Bab 3 : Analisis Pemecahan Masalah

Di dalam bab ini diuraikan langkah-langkah pemecahan masalah dengan algoritma greedy. Anda harus menuliskan apa yang menjadi elemen-elemen algoritma greedy-nya pada masalah ini (himpunan kandidat, himpunan solusi, fungsi seleksi, dll). Nilai bonus bagi anda jika dapat membuktikan apakah algoritma Greedy anda itu memberikan solusi optimal dan contoh kontranya (contoh yang tidak selalu memberikan solusi optimal).

Bab 4 : Implementasi dan pengujian. 

Bab ini berisi:

• Spesifikasi teknis program, termasuk di dalamnya struktur data, fungsi dan prosedur (header fungsi dan prosedur saja, tidak perlu source code), antarmuka, dan lain-lain yang dianggap perlu. 
• Capture layar yang memperlihatkan hasil penjadwalan. 
• Analisis hasil pengujian.

Bab 5: Kesimpulan dan saran (hasil yang dicapai, saran pengembangan).

Tuliskan juga referensi (buku, web), yang dipakai/diacu di dalam Daftar Referensi.

Keterangan Laporan :

1. Laporan ditulis dalam bahasa Indonesia yang baik dan benar, tidak perlu panjang tetapi tepat sasaran dan jelas. 
2. Laporan tidak perlu memakai cover mika dan dijilid. Cukup dibuat agar laporan tidak akan tercecer bila dibaca. 
3. Laporan boleh menggunakan kertas rius, boleh bolak-balik, boleh dalam satu halaman kertas terdapat dua halaman tulisan asalkan masih terbaca. 
4. Identitas per halaman harus jelas (misalnya : halaman, kode kuliah). 

Penilaian :

1. Kebenaran program (40%) : program mampu berjalan sesuai dengan spesifikasi yang diberikan. 
2. Demo – pemahaman Anda dalam pembuatan program (30%) 
3. Laporan (20%) 
4. Interface, features program, dan unsur kreativitas (10%)

Sekian artikel Aplikasi Algoritma Greedy Pada Smart Building Environment.