Ujicobatamplate.blog

          Seperti yang kita ketahui mengenai Nama menara yang di sebut sebagai "Tower of Hanoi" adalah Menara Hanoi. Menara Hanoi ini adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut.
Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut:

• Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
• Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
• Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

          Dan untuk yang menemukan teka - teki  ini adalah Édouard Lucas, ahli matematika Perancis di tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal di masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya.
          Tapi tahukah kalian ??? ..... Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 2⁶⁴−1 detik atau kurang lebih 584,582 milyar tahun.

               Nah sekarang kalian sudah tahu mengenai "Tower of Hanoi" kan.....Tapi... :) :( (-_-)a" yang jadi masalahnya saya bukan mau ngejelasin mengenai sejarah atau mengenai pa itu Menara hanoi ? Disini saya mau ngejelasin sebuah tugas yang saya emban dari mata kuliah Analisis Algoritma . Tugasnya yakni membuat sebuh algoritma dari teori "The tower of Hanoi". dan alhamdulillah akhirnya  jadi, hasilnya adalah sebagai berikut :

Soal :
Diketahui Piringan, dimana sejumlah piringan dipindahkan dari tonggak satu ke tonggak lainnya dan dapat menggunakan tonggak bantuan . Sesuai gambar berikut :

Pindahkan piringan ketiang lainnya

                 Untuk malakukan semua itu, caranya semua piringan di tonggak A akan dipindahkan ke tonggak C secara satu persatu dan piringan yang besar tidak boleh diletakkan di atas piringan yang kecil.
                Untuk lebih jelasnya soal prosesnya bisa lihat gambar di bawah ini:

Proses perpindahan Piringan dengan menggunakan Tiang pembantu.

                  Lalu lihat yang ini pula :

Perpindahan Piringan

                Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.
Jadi algoritmanya adalah …

Kalau N = 1 maka

N dipindahkan dari A ke C secara langsung

Tapi kalau N > 1 maka

pindahkan N-1 dari A ke B

pindahkan N dari A ke C

pindahkan N-1 dari B ke C

catatan :

N = banyaknya piringan

 Lihat skema perpindahan piringan dari "Tower of Hanoi" :


Nahhh.....untuk melakukan analisisnya sudah dilakukan diatas, untuk algoritmanya adalah sebagai berikut :
Algoritma Menara Hanoi dengan Program C++

#include<iostream>

using namespace std;

void MenaraHanoi(int N, char asal, char bantu, char tujuan);

int main()

{

    int piringan;

    cout<< "\nPROGRAM MENARA HANOI\n";

    cout<< "--------------------\n\n";

    cout<< "Banyaknya piringan: ";

    cin >> piringan;

    cout<< endl;

    MenaraHanoi(piringan,'A','B','C');

    return 0;

}

void MenaraHanoi(int N, char asal, char bantu, char tujuan)

{

    if(N == 1)

        cout<<"Piringan 1 dari "<<asal<< " ke " << tujuan <<endl;

    else

        {

            MenaraHanoi(N-1,asal,tujuan, bantu);

            cout<<"Piringan " << N <<" dari " << asal << " ke " << tujuan<<endl;

            MenaraHanoi(N-1, bantu, asal, tujuan);

        }

}

 Setelah kamu berhasil jalankan maka hasil outputnya sebagai berikut :) :

Output

               Sekian bahasan Herdi Blog kali ini. Semoga bahasan ini bermanfaat bagi kalian semua.
Thank untuk kedatangannya diblog saya ini.

                  Buat para sobat blogger kali ini saya membahas lagi sedikit mengenai D and C ini. Padahal sudah pernah saya bahas juga sih di Algoritma Devide and Conquer, Namun saya rasa blom lengkap dengan bahasan dibawah ini. Saya harap bahasan saya yang kali ini bermanfaat bagi para blogger. :)
                  Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.

Pada algoritma Divide and Conquer ini memiliki tiga proses utama yaitu :
1. Divide: membagi masalah menjadi beberapa upa masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2. Conquer: memecahkan (menyelesaikan) masing-masing upa masalah (secara rekursif), dan
3. Combine: mengabungkan solusi masing-masing upa masalah sehingga membentuk solusi masalah semula.

Ada 4 hal penting yang harus dipahami dalam strategi ini :
Yakni branching factor, balance, data dependence of divide function dan sequentiality.

1. Branching Factor
              Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2.

2. Balance
               Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance).
 
3. Data Dependence of Divide Function
               Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah Pseudocode untuk model algoritma n-way divide and conquer subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide.

4. Control Parallelism or Sequentiality
                 Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program.

                  Algoritma Divide and Conquer memiliki kelebihan yang membuatnya banyak diterapkan dan digunakan dalam aplikasi-aplikasi dunia nyata, diantaranya :

- Mampu menyelesaikan masalah yang sulit, algoritma ini mampu menyelesaikan masalah rumit yang hingga kini masih cukup sulit dipecahkan oleh komputer biasa, seperti Tower of Hanoi Problem.
- Algoritma lebih efisien untuk beberapa kasus tertentu, misalnya kasus Fast Fourier Transform maupun Sorting dapat dilakukan dengan kompleksitas algoritma O(n log n) dari algoritma lainnya yang hanya mampu mencapai kompleksitas O (n2).
- Algoritma ini dapat bekerja secara paralel dan dapat memaksimalkan penggunaan dari cache memory.

Skema Umum Algoritma Divide and Conquer 

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n <= n0 then {ukuran masalah sudah cukup kecil }
        SOLVE upa-masalah yang berukuran n ini
else
        Bagi menjadi r upa-masalah, masing-masing berukuran n/k
        for masing-masing dari r upa-masalah do
           DIVIDE_and_CONQUER(n/k)
        endfor
     COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }
endif

Sekian bahasannya. Thank untuk kunjungannya ke blog saya ini. Wasalam !

#USB Safely Remove 4.3.2.950

               Ohhhh...   (-_-)a", kebetulan sobat blogger. hari ini saya baru saja selesai kumpul sama teman saya buat ngerjain tugas, dan waktu saya disana saya liat ada temen saya yang nyodorin laptopnya. Secontak saya otak atik dan saya liat disana ada yang menarik ketika saya masukin Flashdisk. Tahu itu apa.......

               Ketika saya liat ternyata ada software yang mempermudah kita untuk meng-eject yang namanya flasdisk.software itu namanya USB Safely Remove. And ...sekejap saat saya internetan di kostan saya, saya cari dan akhirnya daet..dan hasilnya dibawah ini : " Baca saja, semoga bermanfaat "

               Tepat tanggal 7 Mei kemarin USB Safely Remove kembali melakukan revisi untuk softwarenya. Sehingga untuk versi kali ini menjadi USB Safely Remove 4.3.2.950, dimana pada versi ini, telah dilakukan beberapa perbaikan dan bug-bug yang terdapat pada versi sebelumnya. USB Safely Remove 4.3.2.950 ini merupakan salah satu tool yang memudahkan kita untuk melepas media-media yang bersifat USB secara aman dan cepat hanya dengan sekali klik saja. Sehingga dengan software ini flashdisk, memory atau sebagainya menjadi tahan lama dan awet. Karena jika kita langsung mencabut tiba-tiba media USB yang sedang tertanam di komputer kita, tentu saja media USB tersebut akan cepat rusak dan tidak awet. Salah satu keunggulan dari software ini adalah ketika kita tidak bisa menghentikan proses dari suatu media yang sedang berjalan, kita dapat fitur forced stop, yaitu menghentikan proses dari media tersebut dengan aman.

Gambar : Menghentikan proses dengan cepat

Berfungsi untuk menghentikan proses dengan aman ketika mesia tidak bisa dihentikan.

• Jalankan file setupnya
• Setelah selesai, tutup terlebih dahulu programnya
• Kopikan file yang ada pada Aktivasi ke
• C: – Program Files – USB Safely Remove
• Jalankan programnya

Pass****  Rar : pakalawiren45
Untuk download Klik disini ! 

Kebetulan sobat blogger, saya baru ada tugas dan dapet materi yang baru dari Mata kuliah saya di UNIK**, Yakni Analisis Algoritma. Buat engak ngelamaain bagi yang mau nyari data nya silahkan baca aja sedikit penjelasan nya :

1.  Pengertian 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.

             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 :

Gambar 1.0 Pricedure Divide & Conquer

2. Penerapan Algoritma
2.1. Pemecahan 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 :

Gambar 1.2 A table eit value of elemens

 Ide dasar algoritma secara Divide and Conquer :

Gamabar 1.3 Ide Dasar algoritma

           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

Gambar 1.4 Skema Procedure

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer :

Gambar 1.5 Procedure Konveksi

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) :

Gambar 1.6 Closest Pair

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.


Sekian yang bisa saya share buat para Blogger dunia. "Semoga bermanfaat. "