TUGAS AP-2C

NAMA  : BARNABAS SEBASTIAN

KELAS : 1IA24

NPM     : 52414038

Berikan contoh soal dan penyelesaian dengan menggunakan metode greedy dan jelaskan!

Metode Greedy 

Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya 

• Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.

• Elemen Algoritma Greedy

Elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain :

1. Himpunan Kandidat

Himpunan yang berisi elemen pembentuk solusi.

2. Himpunan Solusi

Himpunan yang terpilih sebagai solusi persoalan.

3. Fungsi Seleksi

Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.

4. Fungsi Kelayakan

Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.

5. Fungsi Solusi

Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.

6. Fungsi Objektif

Fungsi yang mengoptimalkan solusi.

• Contoh Soal Metode greedy

Diketahui:

Himpunan Kandidat = C,

Himpunan Solusi = S,

Fungsi Seleksi = select(),

Fungsi Kelayakan = feasible(),

Fungsi Solusi = solution(), dan

Fungsi Obyektif = objective().

Pertanyaan:

Tuliskan Skema umum dari algoritma greedy pada soal diatas

Jawab:

Inisialisasi S dengan kosong.

1. Pilih sebuah kandidat dari C (dengan select()).
2. Kurangi C dengan kandidat yang telah terpilih di atas.
3. Periksa apakah kandidat yang dipilih tersebut bersama sama dengan S membentuk solusi yang layak (dengan feasible()). 
4. Jika ya, masukkan kandidat ke S; jika tidak buang kandidat tersebut dan tidak perlu ditelaah lagi.
5. Periksa apakah S yang sudah terbentuk telah memberikan solusi yang lengkap (dengan solution()).
6. Jika ya, berhenti; jika tidak, ulangi dari langkah 2.

 

Berikan contoh soal dan penyelesaian dengan menggunakan divide dan conquer dan jelaskan!

 

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

• Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).

• Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).

• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Skema Umum Algoritma Divide and Conquer 

•  Contoh Soal Metode greedy

 Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

Ide dasar algoritma secara Divide and Conquer : 

Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.

COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

Penyelesaian dengan Algoritma Divide and Conquer secara umum :

=======================================================

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

- SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.

- DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama

- CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

- Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

Pasangan titik terdekat terdapat di bagian PLeft.

Pasangan titik terdekat terdapat di bagian PRight.

Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

Seberapa dewasa diri ini dalam menghadapi suatu masalah dan Bagaimana cara mengatasinya

Sebelum membahas dan meceritakan masalah yang terjadi pada saya, Perkenalkan nama saya Barnabas Sebastian, saya anak ke 3 dari 5 bersaudara, umur saya 19 tahun dan untuk saat ini saya duduk di bangku kuliah semester 2. 

Lalu masalah yang akan saya ceritakan(share) merupakan sebuah permasalah dari keluarga saya. Saya yang merupakan anak ke- 3 dalam keluarga saya, menurut saya  terkadang saya mendapat perlakuan yang berbeda dibanding kakak dan adik adik saya yang umurnya masih jauh dibawah saya.

Masalah ini terkadang terjadi ketika orang tua saya mengharapkan sesuatu yang di inginkanya pada anak anaknya meskipun anak anaknya pun mempunyai keinginan dan harapan yang berbeda dan Hal yang paling membuat saya risih ketika orang tua mulai membandingkan saya dengan saudara saudara saya yang lebih tua dari saya. 

Pernah saya mencoba untuk melakukan dan mengikuti jalan pikiran orang tua saya dengan keinginan dan harapannya terhadap saya, namun hal tersebut menjadi tabu bagi saya karena saya berpikir bukan hal tersebut yang menjadi keinginan saya. 

Sebagai anak saya sangat mengerti apa yang dilakukan dan di pikirkan oleh orang tua saya untuk membuat anak anaknya hidup bahagia namun yang ingin saya sampaikan kepada mereka adalah saya pun mempunyai cara tersendiri untuk mendapatkan hal tersebut. 

 Lalu saya pun berpikir bagaimana caranya untuk mengatasi masalah tersebut untuk dapat melakukan hal yang saya ingin dan cita citakan tanpa membuat orang tua saya sakit hati. suatu saat sayapun memberanikan diri untuk berbicara terhadap orang tua saya, dan saya bilang kepada mereka "ma maaf sebelum ini aku rasa apa yang mama inginkan untuk membuat aku jadi seperti yang mama inginkan di luar batas kemampuanku dan mulai terlihat terlalu memaksakan. namun bukan berarti aku menolak apa yang mama inginkan hanya saja aku mempunyai cara tersendiri untuk bagaimana menentukan masa depan aku. tenang aja ma aku janji kalau jalan yang aku pilih ini memang gagal dan tidak berarti untuk kehidupan aku, aku tidak akan pernah membantah apa yang mama katakan dan melakukan apapun yang mama inginkan. Mamaku pun hanya terdiam dan diakhir mamaku pun berkata untuk tidak perlu khawatir lagi lakukan apa yang saya inginkan. dan mama ku pun berkata juga mama hanya melakukan apa yang diperlukan sebagai orang tua jadi mama akan mendukung.