Metode Greedy

Definisi

            Metode yang digunakan untuk memecahkan persoalan optimasi dengan pencarian solusi optimum.

Ada 2 macam persoalan optimasi:

1. Maksimasi (maximization)
2. Minimasi (minimization)

• Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
• Prinsip greedy: “take what you can get now!”.

Contoh Kasus algoritma Greedy

Misalkan tersedia koin : 1, 3, 5.

Uang senilai X=8 dapat di tukar dengan cara :

• 1+1+1+1+1+1+1+1 = 8 (8 koin)
• 1+1+1+1+1+3=8 (6 koin)
• 1+1+1+5=8 (4 koin)
• 1+1+3+3=8 (4 koin)
• 3+5=8 (2 koin)                                    solusi optimal.

Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

Metode Divide & 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.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

Skema Umum Algoritma Divide and Conquer :

Penerapan Algoritma

2Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

• Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

• Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).

• Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.

• Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

• Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

2.2. Persoalan Minimum dan Maksimum (MinMaks)

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.

2.3. Optimasi Konversi Bilangan Desimal Ke Biner

Salah satu cara optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan menjadi hasil jawaban.

Karena angka pembagi yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah satu proses yang cukup rumit.

Tentu saja optimasi ini harus kita bayar dengan menangani konversi bilangan octal ke biner. Akan tetapi jika kita gunakan teknik perbandingan ( tanpa harus melakukan konversi secara manual ), maka proses ini akan menjadi sangat cepat dan mudah. Penerapan algoritma ini adalah dengan menggunakan sintaks case of. Begitu juga dengan permasalahan pemakaian memori ( kompleksitas ruang ) yang lebih besar yang muncul akibat penggunaan algoritma rekursif. Karena pada proses rekursif-nya kita tidak banyak menggunakan variable yang memerlukan tempat yang begitu besar, maka hal ini bias kita abaikan. Dengan penggunaan optimasi ini, maka seharusnya proses konversi akan lebih cepat karena pemangkasan jumlah pembagian yang dilakukan.

Skema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer

Kompleksitas waktu algoritma :

T(n) = O(n/3)

dengan n menyatakan eksponen terkecil dari 2 yang mempunyai nilai 2n lebuh besar dari angka decimal

Algoritma konversi system bilangan dengan menggunakan algoritma dengan optimasi yang menerapkan algoritma Divide and Conquer lebih mangkus daripada algoritma konversi dengan metode pembagian sisa biasa jika dilihat dari segi kompleksitas waktunya. Hanya saja optimasi ini diimbangi dengan kenaikan pada kompleksitas ruangnya, meskipun pengaruhnya tidak sebesar optimasi yang kita lakukan.

2.4. Mencari Pasangan Titik yang Jaraknya Terdekat ( Closest Pair )

Persoalan : Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :

Penyelesaian dengan Algoritma Divide and Conquer :

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.

Nama     : Silvina Reskia
Kelas      : 1IA25
NPM      : 5A414284

Manusia dan Keindahan

Keindahan

Keindahan berasal dari kata Indah, Keindahan adalah sifat dari sesuatu yang memberi kita rasa senang bila melihatnya. Dalam Kamus Besar Bahasa Indonesia, keindahan diartikan sebagai keadaan yang enak dipandang, cantik, bagus benar atau elok. Keindahan dipelajari sebagai bagian dari estetika, sosiologi, psikologi sosial, dan budaya. Sebuah “kecantikan yang ideal” adalah sebuah entitas yang dikagumi, atau memiliki fitur yang dikaitkan dengan keindahan dalam suatu budaya tertentu, untuk kesempurnaannya.

Keindahan yang seluas-luasnya

Keindahan dalam arti luas, menurutThe Liang Gie, mengandung gagasan tentang kebaikan. dari pemikiran Plato, yang menyangkut adanya watak yang indah dan hukum yang indah: Aristoteles yang melihat keindahan sebagai sesuatu yang baik dan juga menyenangkan. Tetapi bangsa Yunani juga mengenal pengertian keindahan dalam arti estetik disebutnya “ Syimmetria”, untuk keindahan berdasarkan pengelihatan. jadi pengertian yang seluas-luasnya meliputi: Keindahan Seni, Keindahan Alam, Keindahan Moral, Keindahan Intelektual.

Nilai Estetika

Kata estetika berasal dari kata Aesthesiss yang artinya perasaan atau sensitivitas, karena memang pada awalnya pengertian ini berhubungan dengan lidah dan perasaan. Dalam pengertian teknis, Estetika adalah ilmu keindahan atau ilmu yang mempelajari keindahan, kecantikan secara umum. Estetika adalah salah satu cabang filsafat. Secara sederhana, estetika adalah ilmu yang membahas keindahan. Pembahasan lebih lanjut mengenai estetika adalah sebuah filosofi yang mempelajari nilai-nilai sensoris, yang kadang dianggap sebagai penilaian terhadap sentimen dan rasa. Estetika merupakan cabang yang sangat dekat dengan filosofi seni. Nilai yang berhubungan dengan segala sesuatu yang tercakup dalam pengertian keindahan disebut Nilai Estetik.

Nilai Ekstrinsik dan Nilai Intrinsik

Nilai instrinsik adalah nilai yang terkandung dari benda atau sesuatu itu sendiri, yang bersifat baik dari benda yang bersangkutan, atau sebagai suatu tujuan, ataupun demi kepentingan benda itu sendiri. Sedangkan nilai ekstrinsik adalah nilai yang berasal dari luar benda atau sesuatu itu sendiri yang bersifat baik dari suatu benda sebagai alat atau sarana untuk sesuatu hal lainnya (Instrumental/ Contributory value), yakni nilai yang ber sifat sebagai alat atau membantu.

Pengertian tentang kontemplasi dan ekstansi

Kontemplasi adalah memandang jauh ke depan demi mendapatkan arah dan kemungkinan tindakan lain (antisipasi) yang lebih bermakna. Kontemplasi adalah suatu tindakan untuk memahami penuh suatu hal. Kontemplasi adalah memandang sesuatu dengan cara ambil bagian dalam hidup, dalam adegan, terlibat langsung. Kontemplasi adalah dasar dalam diri manusia untuk menciptakan sesuatu yang indah. Sedangkan Ekstansi adalah dasar dalam diri manusia untuk menyatakan, merasa, dan menikmati sesuatu yang indah. Setiap manusia memiliki nilai ekstansi yang berbeda-beda. Apabila kontemplasi dan ekstansi itu dihubungkan dengan kreativitas, maka kotemplasi itu adalah faktor pendorong untuk menciptakan keindahan. Sedangkan ekstansi itu merupakan faktor pendorong untuk merasakan menikmati keindahan karena derajat kontemplasi dan ekstansi itu berbeda-beda antara setiap manusia.

Teori-teori Dalam Renungan

Merenung adalah aktifitas berfikir mendalam (deep thinkings) yang sungguh berbeda dengan termenung. Merenung adalah secara diam-diam memikirkan sesuatu hal kejadian yang mendalam. Sedangkan termenung adalah gambaran tentang kondisi hanyutan sebuah pikiran, tentu saja ia kehilangan ofektivitasnya karena memang sedang out of control. Termenung bias dikatakan meratapi hidup, orang termenung pasti melakukan dialog dengan diri sendiri. Berarti hal ini banyak menguraikan masalah dari termenung, orang berbicara dengan nurani dan akalnya menyamakan persepsi antara hati dan otak. Renungan berasal dari kata renung artinya memikirkan sesuatu jadi Renungan adalah pembicaraan diri kita sendiri atau pembicaraan dalam hati kita tentang suatu hal

1. Teori Pengungkapan Dalil dari teori ini ialah bahwa “Art is an expression of human feeling” (Seni adalah suatu pengungkapan dari perasaan manusia). Tokoh teori ekspresi yang paling terkenal ialah filsuf Italia Benedeto Croce (1886-1952) dengan karyanya yang telah diterjemahkan kedalam bahasa Inggris.
2. Teori Metafisik Merupakan salah satu teori yang tertua, yakni berasal dari Plato yang karya-karya tulisannya untuk sebagian membahas estetik filsafati, 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.
3. Teori Psikologis Salah satunya ialah teori permainan yang dikembangkan oleh Freedrick Schiller (1757-1805) dan Herbert Spencer (1820-1903). Seni merupakan semacam permainan y menyeimbangkan segenap kemampuan mental manusia berhubungan dengan adanya kelebihan energi yang harus dikeluarkan.

TEORI KESERASIAN

          Keserasian berasal dari kata serasi dan kata dasar rasi, artinya cocok, kena benar, dan sesuai benar.

Keindahan adalah suatu kumpulan hubungan yang serasi pada suatu benda dan diantara benda itu dengan si pengamat.

Filsuf Inggris Herbert Read merumuskan definisi bahwa keindahan adalah kesatuan dan hubungan-hubungan bentuk yang terdapat diantara pencerapan-pencerapan indrawi kita (beauty is unity of formal relations among our sense-perception).

Keserasian adalah perpaduan, pertentangan, ukuran, seimbang. Terdapat 2 teori keserasian

• Teori objectif dan subjectif

• Teori Objectif berpendapat bahwa keindahan atau ciri-ciri yang menciptak nilai estetika adalah sifat (kulitas) yang memang melekat dalam bentuk indah yang bersangkutan, terlepas dari orang yang mengamatinya.Pendukung teori objectif adalah Plato, Hegel 
• Teori Subjectif menyatakan bahwa ciri-ciri yang menciptakan keindahan suatu benda itu tidak ada, yang ada hanya perasaan dalam diri sesorang yang mengamati suatu benda. Pendukung nya adalah Henry Home, Earlof Shaffesburry

• Teori Perimbangan

    Dalam arti yang terbatas yakni secara kualitatif yang di ungkapkan dengan angka-angka, keindahan hanyalah kesan yang subjectif sifatnya dan berpendapat bahwa keindahan sesungguhnya tercipta dan tidak ada keteraturan yakni tersusun dari daya hidup, penggembaraan, dan pelimpahan.

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

   Teori ini hanya berlaku dari abad ke-5 sebelum Masehi sampai abad ke-17 Masehi selama 22 abad. Teori tersebut runtuh karena desakan dari filsafat empirisme dan aliran-aliran termasuk dalam seni.

Sumber

https://adeadangsuryana.wordpress.com/tag/keindahan-dalam-arti-luas/

http://rizkywulancils.blogspot.com/2011/05/teori-keserasian.html