METODE DEVIDE AND CONQUER DAN PENYELESAIANNYA

1. Metode Greedy

Algoritma Greedy adalah salah satu jenis algoritma, algoritma greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiaplangkahnya atau local maxium.Algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktuyang cukup cepat. 

Persoalan:

Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum 15 Kg dan sehimpunan benda A = {a₀, a₁, a₂, a₃} yang berbobot (dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P = {100, 135, 26, 20}. Jika kita diperbolehkan memasukkan zi  bagian dari benda ai yang ada ke dalam knapsack dimana 0 ≤ zi ≤ 1 , maka tentukanlah Z = {z0,z1,z2,z3} agar diperoleh total profit yang maksimal !

Jawab :

Dik : 

n = 4; M = 15;       

W = { 5,9,2,4 };        

P = { 100,135,26,20 }, 

Dit : total profit yang maksimal ?

Barang ke -	Berat(Wi)	Keuntungan(Pi)	Pi/Wi
Z0	5	100	20
Z1	9	135	15
Z2	2	26	13
Z3	4	20	5

Z ← 0

cu ← 15

i = 0

karena W(0) 〈 cu yaitu : 5 〈 15 berarti : Z(0) ← 1

cu ← 15 - 5 = 10

i = 1

karena W(1) 〈 cu yaitu : 9 〈 10 berarti : Z(1) ← 1

cu ← 10 - 9 = 1i = 2

karena W(2) 〉 cu yaitu : 2 〉 1 berarti : keluar dari loop (exit)

Karena 2 ≤ 3 maka Z(2) ← cu/W(2) = 1/2 = 0,5

Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }

Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20

= 100 + 135 + 13 + 0

= 248

2. Metode Divide and Conquer

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.

Rumus Algoritma Divide and Conquer:

Persoalan : 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.

Optimasi Konversi Bilangan Desimal Ke Biner

Skema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer

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 masing - masing 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.

Keindahan Secara Luas

1.      Keindahan adalah sifat-sifat yang merujuk kepada sesuatu yang indah di mana manusia mengekspresikan perasaan indah tersebut melalui berbagai hal yang mengandung unsur estetis yang dinilai secara umum oleh masyarakat.

Keindahan sebagai suatu kualitas abstrak (Beauty as an abstract quality)menggambarkan sesuatu yang kontemporer dan bersifat nonrealistic di mana sang pencipta karya menggambarkan sesuatu yang tidak bisa dimengerti secara umum dan tidak sesuai dengan realita.

Keindahan sebagai kualitas abstrak menggambarkan suatu bentuk dalam yang keindahan di mana keindahan tersebut bersifat eksklusif dan hanya dapat dimengerti oleh orang yang menciptakan keindahan tersebut berdasarkan apa yang dipahaminya.

Keindahan sebagai benda tertentu yang menunjukkan keindahan keindahan memiliki konsep pemahaman dan nilai yang berbeda dengan kualitas abstrak di mana benda yang dimaksud dalam hal ini adalah sesuatu yang mewakili keindahan secara umum dan dapat dengan mudah diterima maupun dipahami oleh masyarakat.

Menurut The Liang Gie dalam bukunya “G,a-ris Besar Estetik” (Filsafat Keindahan) dalam bahasa Inggris keindahan itu diterjemahkan dengan kata “beautiful”, Perancis “beau”, Italia dan Spanyol “bello”, kata-kata itu ber­asal dari bahasa Latin “bellum”. Asal katanya adalah ”bonum” yang berarti kebaikan kemudian mempunyai bentuk pengecilan menjadi’ ”bonellum” dan terakhir dipendekkan sehingga ditulis “bellum”.

Pengertian Keindahan Seluas-luasnya Meliputi :
1.Keindahan Seni
2.Keindahan Alam
3.Keindahan Moral
4.Keindahan Intelektual

2.        Estetik berasal dari kata Estetika yang berarti salah satu cabang dari filsafat, dan Estetika merupakan ilmu yang mempelajari tentang keindahan dari suatu objek yang indah, jadi Nilai Estetik sendiri mempunyai arti nilai dari suatu keindahan yang kita rasakan setelah kita rasakan maka kita pun akan menilai seberapa indah objek tersebut.

Nilai Estetika biasa nya ada pada bidang/dunia seni,karna seni merupakan salah satu dunia yang selalu menghadirkan keindahan dalam setiap kali kita merasakan nya,pada seni Nilai Estetik sangat di butuhkan agar para seniman dapat menyajikan keindahan ketika mereka menampilkan dan menyajikan kepada para penonton.dan juga bisa di gunakan untuk layak atau tidak nya suatu seni untuk di pertontonkan ke masyarakat.

Bidang seni erat kaitan nya dengan nilai Estetik,sebagai contoh bidang pada seni yang membutuhkan nilai Estetik yaitu bidang musik,di bidang musik sangat di butuhkan keindahan agar keindahan dari musik yang di mainkan dan dengar oleh para pendengar musik,ketika musik dimainkan barulah musik itu di nilai dan memiliki nilai Estetik.

3.        Unsur ekstrinsik adalah nilai yang di pengaruhi dari luar maksudnya adalah sebagai alat atau sarana untuk sesuatu hal lainnya (“instrumental! Contributory value”), yakni nilai yang bersifat sebagai alat atau membantu.. Misalnya dalam surat, pembuka, isi, dan penutup merupakan nilai ekstrinsik.

Nilai intrinsik adalah unsur nilai yang dipengaruhi dari dalam maksudnya adalah sifat dari benda yang bersangkutan, atau sebagai suatu tujuan, ataupun demi kepentingan benda itu sendiri. Misalnya pesan puisi yang ingin disampaikan kepada pembaca melalui (alat benda) puisi itu disebut nilai intrinsik.

4.        Kontemplasi adalah dasar dalam diri manusia untuk menciptakan sesuatu yang indah. Kontemplasi itu berarti memberi perhatian penuh pada sesuatu obyek. Sangat penting bagi manusia untuk memberikan kesempatan kepada dirinya untuk berhenti, dan mengkonsentrasikan diri kepada setiap obyek, dengtan mengamati, tanpa memikirkannya, dan kemudian menemukan keindahan di dalamnya yang akan membawa manusia pada rasa syukur yang besar kepada realitas tertinggi.

Ekstansi adalah dasar dalam diri manusia untuk menyatakan, merasakan dan menikmati sesuatu yang indah.

Apabila kontemplasi dan ekstansi itu dihubungkan dengan kreativitas, maka kontemplasi itu faktor pendorong untuk menciptakan keindahan, sedangkan ekstansi merupakan faktor pendorong untuk merasakan, menikmati keindahan.

5.      TEORI-TEORI RENUNGAN
 

Teori Pengungkapan

Dalil dari teori ini Adalah “Arts are in expression of human feeling” (seni adalah merupakan ungkapan dari perasaan manusia).

Teori Metafisik

Teori yang bersifat metafisik merupakan salah satu teori yang tertua, yakni berasal dari Plato yang karya-karya tulisnya sebagian membahas estetik filsafat, konsepsi keindahan dan teori seni. Seniman besar adalah seseorang yang mampu dengan perenungannya itu menembus segi-segi praktis dari benda-benda di sekelilingnya dan sampai pada makna yang dalam, yakni memahami ide-ide dibaliknya.

Teori Psikologis

Teori salah satunya ialah teori permainan yang dikembangkan oleh Freedrick Schiller (1757-1805) dan Herbert Spencer (1820-1903). Menurut Schiller, asal mula seni adalah dorongan batin untuk bermain-main (play impulse) yang ada dalam diri seorang. Seni ini merupakan permainan yang menyeimbangkan segenap kemampuan mental manusia berhubungan dengan adanya kelebihan energy yang harus dikeluarkan. Bagi Spencer, permainan itu berperan untuk mencegah kemampuan-kemampuan mental manusia menganggur dan kemudian menciut karena disia-siakan.

Teori Penandaan

Teori yang dapat dimasukkan ke dalam teori psikologis yaitu teori yang memandang seni sebagai suatu lambing atau tanda dari perasaan manusia.

6.        TEORI KESERASIAN

a.     Teori objektif dan subjektif 

Teori objektif berpendapat bahwa keindahan atau ciri-ciri yang menciptakan nilai estetika adalah sifat yang memang melekat dalam bentuk indah yang bersangkutan, terlepas dari orang yang mengamatinya.

Teori subjektif menyatakan bahwa ciri-ciri yang menciptakan keindahan suatu benda itu tidak ada, yang ada hanya perasaan dalam diri seseorang yang mengamati suatu benda.

b.    Teori Perimbangan

Teori perimbangan tentang keindahan dari bangsa Yunani Kuno dulu dipahami dalam arti terbatas, yakni secara kualitatif yang diungkapkan dengan angka-angka. Keindahan dianggap sebagai kualitas dari benda-benda yang disusun (mempunyai bagian-bagian). Hubungan dari bagian-bagian yang menciptakan keindahan dapat dinyatakan sebagai perimbangan atau perbandingan angka-angka.

REFERENSI:

·         http://gegehare.blogspot.com/2011/03/ilmu-budaya-dasar-bab-4-manusia-dan.html

·         http://kevin-denianri.blogspot.com/2011/06/pengertian-nilai-estetik.html

·         https://annisafeb.wordpress.com/2013/10/29/keindahan-yang-mengandung-nilai-ekstrinsik-dan-instrisik/

·         http://nhseptiawan.blogspot.com/2013/04/pengertian-keindahanteori-teori.html