qilaworld: MAKALAH LOGIKA DAN ALGORITMA “METODE GREEDY”

MAKALAH

LOGIKA DAN ALGORITMA

“METODE GREEDY”

Dosen Pengampu:

Rabiatul Adwiya

DISUSUN OLEH :

KELOMPOK 6

1. Fitrianisa Indah 12182388

2. Rizqi Yuliarta 12184867

3. Hafizah 12182290

4. Gita Andini 12182121

5. FahrurRazi 12182488

6. Asrul Arpan Lubis 12182432

7. Ryan Fardhiansyah 12182489

12.1B.30

SISTEM INFORMASI

UBSI PSDKU PONTIANAK

2018

KATA PENGANTAR

Dengan menyebut nama Allah SWT yang Maha Pengasih dan Maha Penyanyang. Kami panjatkan puji syukur kehadirat-Nya yang telah melimpahkan rahmat, hidayah, serta inayah-NyA kepada kami sehingga kami bisa menyelesaikan makalah ini.

Makalah ini sudah kami susun dengan maksimal dan mendapat bantuan dari berbagai pihak sehingga bisa memperlancar pembuatan makalah ini. Untuk itu kami menyampaikan terimakasih kepada semua pihak yang telah berkontribusi dalam pembuatan makalah ini.

Terlepas dari segala hal tersebut, Kami sadar sepenuhnya bahwa masih ada kekurangan baik dari segi materi maupun susunan kalimat dan tata bahasanya. Oleh karena itu kami dengan lapang dada menerima segala saran dan kritik dari pembaca agar kami dapat memperbaiki makalah ini.

Akhir kata kami berharap semoga makalah tentang “Metode Greedy” ini bisa memberikan manfaat bagi kita semua.

Pontianak, 19 Desember 2018

Penyusun

DAFTAR ISI

KATA PENGANTAR…………………………………………………….. .ii

DAFTAR ISI……………………………………………………………….iii

BAB I

PENDAHULUAN

A. Latar Belakang…………………………………………………..1

B. Rumusan Masalah……………………………………………….1

C. Tujuan…………………………………………………………...1

BAB II

PEMBAHASAN

A. Pengertian Metode Greedy……………………………………...2

B. Prinsip Utama Metode Greedy………………………………….2

C. Skema Umun……………………………………………………3

D. Masalah yang Dapat Diselesaikan dengan Metode Greedy…….4

BAB III

PENUTUP

A. Kesimpulan……………………………………………………..7

DAFTAR PUSTAKA……………………………………………………..8

BAB I

PENDAHULUAN

A. Latar Belakang

Di zaman yang serba canggih seperti saat ini, computer merupakan kebutuhan dasar di bidang kehidupan manusia. Komputer erat kaitannya dengan pemrograman. Di dalam pemrograman itulah kita akan mengenal algoritma. Algoritma diartikan sebagai langkah –langkah yang logis untuk memecahkan suatu permasalahan yang ingin diselesaikan oleh program. Untuk itu, algoritma dan pemrograman merupakan satu kesatuan yang saling mempengaruhi sehingga membentuk suatu sistemyang terintegrasi. Salah satu metode yang populer digunakan untuk memecahkan persoalan optimasi dalam algoritma adalah metode greedy.

B. Rumusan Masalah

1. Apa yang dimaksud dengan metode greedy?

2. Bagaimana implementasi dari metode greedy?

C. Tujuan

1. Mengidentifikasi pengertisn metode greedy.

2. Mengidentifikasi implementasi dari metode greedy.

BAB II

PEMBAHASAN

A. Pengertian Metode Greedy

Metode Greedy merupakan algoritma yang membentuk solusi langkah per langkah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Pada kebanyakan kasus, metode ini tidak akan menghasilkan solusi paling optimal, tetapi biasanya metode ini memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Greedy sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah.

B. Prinsip Utama Metode Greedy

Prinsip utama dari metode ini adalah “take what you can get now!”. Maksud dari prinsip tersebut ialah pada setiap langkah dalam metode greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya.

C. Skema Umum Metode Greedy

Metode greedy disusun oleh elemen-elemen berikut:

1. Himpunan kandidat

Berisi elemen-elemen pembentuk solusi.

2. Himpunan solusi

Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan

3. Fungsi seleksi(selection function)

Memilih kandidat yang paling memungkinkan mencapai solusi optimal.Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

4. Fungsi kelayakan(Feasible)

Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak,yakni kandidat tersebut Bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar solusi,sedangkan kandidat yang tidak layak dibuang dan tidak pernah di pertimbangkan lagi.

5. Fungsi obyektif

Fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya Panjang lintasan,keuntungan,dan lain-lain).

D. Masalah yang Dapat Diselesaikan dengan Metode Greedy

Metode greedy dapat digunakan dalam penyelesaian masalah-masalah berikut:

1. Optimal Storage on Tapes Problem

Bagaimana mengoptimalkan penyimpanan, agar data yang disimpan dapat termuat dengan optimal.

Contoh masalah:

Diketahui 3 program yang akan disimpan dalam media penyimpanan dengan Panjang masing-masing 5, 10, dan 3. Bagaimana proses penyimpanan yang optimal denganmetode greedy.

Penyelesaian:

1. Tentukan nilai panjang, waktu, dan waktu rata-rata

Ada 3 program, dimisalkan panjangnya L1, L2, dan L3 dengan nilai L1=5, L2=10, dan L3=3

Waktu, disini tidak diketahui, berarti dianggap waktu tidak mempengaruhi proses penyimpanan, berarti tidak ada waktu rata-rata.

Berarti dalam kasus ini yang berpengaruh hanya panjang dari setiap datanya.

2. Urutkan penyimpanan dengan menggunakan teknik faktorial sesuai dengan jumlah data.

Dari kasus diketahui jumlah data (n) adalah 3, berarti kombinasi yang dibutuhkan adalah n!, yaitu 3!=3*2*1 = 6. Jadi dibutuhkan 6 langkah dalam proses penyusunannya.

No	Order	D(L)	Total
1	1,2,3	5+(5+10)+(5+10+3)	38
2	1,3,2	5+(5+3)+(5+3+10)	31
3	2,1,3	10+(10+5)+(10+5+3)	43
4	2,3,1	10+(10+3)+(10+3+5)	41
5	3,1,2	3+(3+5)+(3+5+10)	29
6	3,2,1	3+(3+10)+(3+10+5)	34

Ket. No:1 : Order 1 = 5

Order 1, 2 =5+10

Order 1,2,3 = 5+10+3

Jadi Total Order 1,2,3 = 5+(5+10)+(5+10+3)

3.Dari nilai di atas didapat nilai minimal adalah

a. Nilai terkecil pertama adalah 29, yaitu untuk posisi penyimpanan urutan ke-3 pada posisi pertama

b. Nilai terkecil kedua adalah 31, yaitu untuk posisi penyimpanan urutan ke-1 pada posisi pertama

c. Nilai terkecil ketiga bukan 34 dan 38, sebab urutan penyimpanan pada posisi ke-3 dan ke-1 sudah diwakili oleh 29 dan 31, sehingga untuk urutan ketiga adalah 41.

2. Knapsack Problem

Bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Contoh masalah:

Diketahui 3 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 20 kg. berat masing-masing barang adalah 18 kg, 15 kg, dan 20 kg dimana setiap barang memiliki profit sebesar masing-masing 25, 24, dan 15.

Penyelesaian: M-W

n = 3 -> objek (1,2,3) O 1 2 3 20-15=5

M = 20 kg P 25 24 15 5- 5=0

W = 18, 15, 10 W 18 15 10

P = 25, 24, 15 P/W 1,39 1,6 1,5

Probabilitas 0 ≤ Xi ≤ 1 X 0 1 1/2

(X₁ X₂X₃)

Fungsi pembatas:

∑Xi.Wi = 1.15 + 1/2.10 = 15 + 5 = 20

Fungsi tujuan:

∑Pi.Xi = 24.1 + 15.1/2 = 24 + 7,5 = 31,5

3. Minimum Spanning Tree Problem

Permasalahan umum dari minimum spanning tree adalah mencari minimum biaya (cost) spanning tree dari setiap ruas (edge) suatu graph yang membentuk pohon (tree).

4. Shortest Path Problem

Adalah pencarian jarak terpendek dari suatu lokasi ke lokasi lainnya.

BAB III

PENUTUP

A. Kesimpulan

Berdasarkan dengan apa yang telah diuraian di atas, dapat di simpulkan bahwa metode greedy dapat digunakan untuk menyelesaikan 4 jenis masalah yang berkaitan dengan permasalahan optimasi.