MAKALAH TUGAS PENDAHULUAN
PRAKTIKUM TEKNOLOGI INFORMATIKA
IMPLEMENTASI ALGORITMA DALAM
PEMROGRAMAN
Disusun
oleh:
1. Anggita
Maya Dewi (21070114120009)
2. Alif
Abdurrahman Hafiz (21070114130133)
3. Febby
Veronica (21070114120055)
PROGRAM
STUDI TEKNIK INDUSTRI
FAKULTAS
TEKNIK UNIVERSITAS DIPONEGORO
SEMARANG
2014
Pertama, marilah kita panjatkan puji
syukur ke hadirat Tuhan Yang Maha Esa. Karena atas limpahan karunia-Nya,
kelompok 33 diberikan kelancaran sehingga mampu menyelesaikan makalah sesuai
dengan waktu yang telah dijadwalkan.
Makalah ini berisi tentang Implementasi
Algoritma dalam Pemrograman. Seperti yang kita ketahui bahwa algoritma menjadi
landasan dalam penyusunan program-program komputer. Maka penting untuk mengetahui
penerapan-penerapan algoritma tersebut dalam penyusunan suatu program.
Kami sadar bahwa dalam penyusunan makalah ini
masih jauh dari kata sempurna. Oleh karena itu, sebagai manusia yang ingin
terus bertambah baik kami mengharapkan saran dan kritik dari pembaca. Sekiranya
saran dan kritik tersebut dapat membangun kami agar dapat menyusun makalah
lebih baik lagi. Tak lupa kami juga berharap makalah ini akan bermanfaat
sebagaimana mestinya.
Semarang,
8 November 2014
Penyusun
DAFTAR ISI
BAB I
Berdasarkan
tugas pendahuluan praktikum teknologi informatika, kami mencari tahu tentang implementasi
algoritma dalam pemrograman. Namun sebelum kita tahu apa penerapan algoritma
dalam pemrograman, kita harus tahu bahasa pemrograman terlebih dahulu. Banyak diantara kita yang belum mengetahui
bahasa pemrograman dari suatu aplikasi karena kita hanya menggunakan bantuan aplikasi
tersebut.
Bahasa
pemrograman merupakan alat yang sangat penting untuk mengaplikasikan algoritma.
Ada banyak bahasa pemrograman dan setiap bahasa pemrograman memiliki kelebihan
dan kekurangan masing-masing. Pada bahasan kali ini, kita akan membahas tentang
implementasi algoritma bahasa pemrograman java.
1.2 Rumusan Masalah
Makalah ini merumuskan beberapa permasalahan
sebagai berikut :
1. Apa
definisi algoritma?
2. Apa
jenis-jenis algoritma?
3. Apa
definisi pemrograman dan bahasa
pemrograman?
4. Apa
implementasi algoritma dalam pemrograman?
2.1 Definisi Algoritma
Menurut Abu Ja’Far Mohammad Ibn Musa Al
Khoarismi, algoritma adalah suatu metode khusus untuk menyelesaikan suatu
persoalan. Algoritma harus tersusun secara sistematis, logis, dan memberikan
keluaran yang dikehendaki. Karena, sebagus apapun algoritma bila hasil yang
dikeluarkan tidak sesuai yang kita kehendaki maka algoritma tersebut bukanlah
algoritma yang baik.
2.2 Jenis-Jenis Algoritma
a. Algoritma Brute Force
Algoritma brute force adalah algoritma dengan
pendekatan secara langsung (straight forward) untuk memecahkan atau
menyelesaikan suatu masalah. Algoritma
brute force memecahkan sesuatu masalah dengan cara yang sederhana dan
jelas (obvious way)
b. Algoritma Greedy
Algoritma greedy adalah algoritma yang
menyelesaikan masalah dengan
mengeluarkan solusi yang optimum melalui
proses penyelesaian langkah demi langkah (step by step) dengan menerapkan
prinsip memilih solusi atau penyelesaian terbaik yang ada pada saat itu tanpa
memikirkan konsekuensi di depannya. Itu karena prinsip dari algoritma greedy
yaitu “take what you can get now”.
c. Algoritma Branch and Bound
Algoritma branch and bound merupakan algoritma
yang paling umum untuk mencari dan menentukan solusi optimal untuk suatu
masalah optimasi kombinatorial seperti masalah penjadwalan. Algoritma branch
and bound dikembangkan untuk menentukan penyerahan pekerjaan sepenuhnya kepada
mesin.
d. Algoritma Pseudo Code
Algoritma pseudo-code adalah algoritma yang paling mudah digunakah
dalam bahasa pemrograman. Algoritma pseudo-code adalah penulisan
langkah-langkah atau cara-cara dalam penyelesaian suatu masalah.
e. Algoritma divide and conquer
Algoritma
divide and conquer adalah alogaritma yang penyelesaiannya dengan membagi satu
permasalahan besar atau permasalahan utama ke dalam bentuk masalah yang lebih
kecil. Pembagian masalah ini akan terus dilakukan sampai ditemukannya solusi
atau terpecahkannya masalah yang sudah terbagi menjadi bagian terkecil.
f. Algoritma Dynamic Programming
Algoritma Dynamic Programming adalah algoritma
yang memecahkan masalah dengan metode menguraikan atau membagi solusi menjadi
sekumpulan tahapan (langkah) sehingga solusi dari persoalan tersebut dapat
dipandang dari serangkaian keputusan yang saling berkaitan
g. Algoritma Backtracking
Algoritma backtracking adalah algoritma yang digunakan
untuk menyelesaikan suatu masalah dengan memiliki banyak kemungkinan yang perlu
diuji secara bertahap.
h. Flowchart
Flowchart adalah algoritma yang berbentuk
seperti bagan-bagan yang memiliki arus (aliran) yang mendeskripsikan
(menggambarkan) penyelesaian suatu masalah.
2.3 Pemrograman
Pemrograman
adalah susunan logis dari kumpulan perintah untuk menyelesaikan masalah.
Pemrograman adalah pemberian instruksi kepada komputer agar dapat bekerja
sesuai dengan perintah kita (sesuai yang kita kehendaki) . Komputer memahami
pemograman sebagai data dan instruksi (perintah) dalam bentuk biner (rangkaian
bit-bit bernilai ‘0’ dan ‘1’).Sedangkan manusia mengerti dan memahami sebagai
logika, aritmatika, alogaritma, konsep, model dan sebagainya. Dan sebagai
solusi untuk menjembatani hal tersebut, dibuatlah bahasa pemrograman untuk
menerjemahkan bahasa manusia ke dalam bahasa mesin/komputer. Dalam dunia
komputer dikenal banyak bahasa pemrograman sehingga bahasa pemrograman itu
dikelompokkan ke dalam beberapa kriteria tertentu.
2.4 Implementasi Pemrograman
A. Teori Algoritma Backtracking
Pertama kali teori ini di kemukakan
oleh D.H. Lehmer pada tahun 1950. Jenis algoritma ini banyak dikembangkan
uraian umum dan penerapannya oleh beberapa ahli seperti Rwalker, Golomb, dan
Baumert.
“Algoritma
backtracking merupakan salah satu metode pemecahan masalah yang termasuk dalam
strategi yang berbasis pencarian pada ruang status”.(Purwadi, Joko dan Erick
K.,2010). Cara kerja algoritma backtracking mencari solusi dari suatu masalah
dengan cara mencoba segala kemungkinan solusi yang ada. Hal ini
dikarenakanalgoritma ini masuk ke algoritma berbasis Depth-First Search
(DFS). Prinsip dasarnya semua solusi
dibuat pohon solusinya kemudian pohon solusi tersebut ditelusuri secara DFS
sehingga ditemukan solusi terbaik dari suatu masalah.
B. Depth First Search (DFS)
24 tahun yang lalu Tarjan dan Hopcroft
memperkenalkan algoritma DFS. Mereka menunjukkan bagaimana metode ini dapat
digunakan untuk membangun sejumlah grafik algoritma yang lebih efisien. Cara
kerja metode ini adalah dengan menelusuri satu kemungkinan yang ada hingga
akar-akar maksimal, kemudian menelusuri kemungkinan yang lain hingga akar
maksimal begitu seterusnya. Meskipun begitu hanya sebagian ruang yang ditempuh oleh algoritma DFS. Hal ini dikarenakan oleh
sifat algoritma DFS yaitu jika semakin dalam kedalaman pohon maka semakin lama
pula waktu yang dibutuhkan proses pencarian. Terlebih jika kedalaman pohon
tidak terbatas atau ruang pencarian mengandung siklus keadaan tertentu maka dapat
dimungkinkan bahwa algoritma tidak akan berhenti. Inilah mengapa algoritma
tidak menunjukkan sipat komplit.
While
belum sampai tujuan do
if
terdapat arah yang benar dan kita belum pernah
berpindah pada sel arah tersebut
Then
Pindah satu langkah ke arah tujuan
Else
Backtrack langkah sampai terdapat
arah tujuan
Endif
Endwhile
Berikut langkah langkah pencarian solusi
dengan Backtracking :
1. Solusi dicari dengan cara membentuk pohon
solusi. Lintasan yang ada pada pohon tersebut menghasilkan simpul hidup dan
simpul hidup yang di perluas adalah simpul-E (Expand-node)
2. Jika lintasan yang mengalami perluasan
simpul-E tidak mengarah pada solusi, maka simpu tersebut akan menjadi simpul
mati dan tidak akan di perluas lagi.
3. Jika posisi terakhir berada di simpul mati,
maka pencarian akan dilakukan ke simpul anak lainnya dan jika tidak memiliki
simpul anak maka pencarian akan backtracking ke simpul sebelumnya yaitu simpul
induk.
4.
Pencarian
dihentikan jika telah menemukan solusi atau tidak ada simpul hidup yang mengarah
ke solusi.
Berikut contoh gambaran langkah-langkah pohon
pencarian solusi dengan Backtracking :
Penerapan algoritma Backtrack terdapat pada
proses pencarian jalan keluar pada permainan labirin seperti gambar diatas.
Salah satu contohnya adalah permainan Math Maze. Permainan Math Maze maerupakan
game sederhana yang bertujuan menentukan jalur yang tepat untuk sampai ke
tujuan dengan cara menjawab soal
matematika, jika jawaban benar maka akan muncul petunjuk arah menuju jalan
keluar. Selain itu penerapan jenis algoritma ini juga ada pada game lainnya
seperti tic-tac-toe, catur, Dota, Pro Evolution Soccer, Fifa dan pada berbagai
masalah yang berkaitan dengan kepintaran buatan yang biasa di sebut dengan AI
(Artificial Intellegence).
C. Penerapan Algoritma Backtrack pada Permainan Math Maze
Math maze adalah sebuah permainan sederhana
dimana kita di tuntut untuk mencari sebuah jalan keluar untuk memenangkan
permainan tersebut. Pada dasarnya Math Maze termasuk permainan yang menggunakan
labirin sebagai rintangannya. Labirin disini berupa grid yang terdiri dari
sel-sel. Pemain biasanya akan mulai pada sel yang terletak di pojok kiri atas.
Nah dari situ kita berjalan dengan cara meng-klik sel-sel yang berada di dekat
sel kita berada. Pemain hanya boleh memilih sel yang ada pada kiri, kanan,
atas, bawah sel yang kita tempati.Jalan menuju titik finish tersembunyi di
balik soal matematika. Pemain harus menjawab semua soal matematika dengan
benar. Jika membuat kesalahan pemain akan dituntun ke arah jalan yang salah.
Dan jika terus salah pemain bisa saja menemui jalan buntu.
Algoritma adalah suatu metode khusus untuk menyelesaikan suatu persoalan . Salah satu contoh algoritma backtracking merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status”.(Purwadi, Joko dan Erick K.,2010). Cara kerja algoritma backtracking mencari solusi dari suatu masalah dengan cara mencoba segala kemungkinan solusi yang ada. Penerapan algoritma Backtrack terdapat pada proses pencarian jalan keluar pada permainan labirin seperti gambar diatas. Salah satu contohnya adalah permainan Math Maze. Permainan Math Maze maerupakan game sederhana yang bertujuan menentukan jalur yang tepat untuk sampai ke tujuan
DAFTAR PUSTAKA
1. ana.staff.gunadarma.ac.id/Downloads/files/.../Algoritma+Brute+Force.ppt
2. portalgaruda.org/download_article.php?article=123405&val=5541
3. informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/.../MakalahStmik04.pdf
4. eprints.undip.ac.id/18630/1/pertemuan2.pdf
5. informatika.stei.itb.ac.id/~rinaldi.../Makalah-IF3051-2012-084.pdf
6. informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/.../MakalahStmik35.pd
7. digilib.uin-suka.ac.id/.../BAB%20I,%20V,%20DAFTAR%20PUSTAKA..
8. lecturer.eepis-its.edu/~zenhadi/.../Algoritma%20dan%20Flowchart.pdf
Tidak ada komentar:
Posting Komentar