Kamis, 17 Februari 2011

Alogaritma

ALOGARITMA


Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.

algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
 
Jenis - Jenis Alogaritma:

  • Alogaritma Divide and Conquer
    Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes.
    Alogaritma Divide and Conquer Adalah mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
    Contoh Alogaritma 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


     Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:


    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 2 upa-masalah, masing-masing berukuran n/2
         DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2) 
         DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2)   
         COMBINE solusi dari 2 upa-masalah 
      endif


    Kompleksitas Waktu algoritma:

                                       
    Persoalan Minimum dan Maksimum (MinMaks)
    ·         Persoalan: Misalkan diketahui tabel A yang berukuran n elemen sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam tabel tersebut.


    Penyelesaian dengan Algoritma Brute Force



    procedure MinMaks1(input A : TabelInt, n : integer,
                       output min, maks : integer)
    { Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force.
    Masukan: tabel A yang sudah terdefinisi elemen-elemennya
    Keluaran: nilai maksimum dan nilai minimum tabel
    }
    Deklarasi
        i : integer

    Algoritma:
        min¬ A1   { inisialisasi nilai minimum}
        maks¬A1   { inisialisasi nilai maksimum }
        for i¬2 to n do

          if Ai < min then
           min¬Ai
          endif

          if Ai > maks then
           maks¬Ai
          endif
         
       endfor

               

    Jika T(n) dihitung dari  jumlah perbandingan elemen-elemen tabel:

                            T(n) = (n – 1) + (n – 1)
            = 2n – 2
            = O(n)


    Penyelesaian dengan Algoritma Divide and Conquer

    Contoh 4.1. Misalkan tabel A berisi elemen-elemen sebagai berikut:

    4          12        23        9          21        1          35        2          24       

    Ide dasar algoritma secara Divide and Conquer: 


    4          12        23        9          21        1          35        2          24       







     

                                                       DIVIDE

    4          12        23        9          21        1          35        2          24       








     

                                   SOLVE: tentukan min &
           maks pada  tiap bagian

    4          12        23        9          21        1          35        2          24       
                min = 4                                    min = 1
                maks = 23                                maks = 24







     



     COMBINE

    4          12        23        9          21        1          35        2          24       
                min = 1                                               
                maks = 24                               
      
    Ukuran tabel 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,
    (a)      DIVIDE: Bagi dua tabel A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

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

    (c)      COMBINE:
     Bandingkan min1 dengan min2 untuk menentukan min tabel A
    Bandingkan maks1 dengan maks2 untuk menentukan maks tabel A.



    • Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.





     

Tidak ada komentar:

Poskan Komentar