PAPER RANCANGAN ANALISA ALGORITMA

PAPER

RANCANGAN ANALISA ALGORITMA

By:

Moh. Zein Saedi           (100411100034)

M. Aminur Rosyid        (100411100021)

M. Zamroni Hamzah   (100411100085)

Yusuf Machsar             (100411100026)

TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS TRUNOJOYO MADURA

2012

ALGORITMA PRIM

Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung.

A.   Algoritma Prim ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Transformer. Karena, dalam metode penyelesaiannya memerlukan proses untuk menukar-kan posisi edge yang menjadi pertimbangan untuk perbandingan.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

A ← V[G]                                                                          1

 for each vertex u in Q                                                         N+1
     do key [u] ← ∞                                                               1
 key [r] ← 0                                                                      1
 π[r] ← NIL                                                                       1
 while array A is empty                                                         N+1
     /* do scan over A find the node u with smallest key, and remove it from

array A*/
     for each vertex v in Adj[u]                                                N+1
         if v is in A and w[u, v] < key[v]                                      N+1
           then  π[v] ← u                                                         1
                   key[v] ← w[u, v]                                               1

Tn = Cn * Cop

     = (1+N+1+1+1+1+N+1+N+1+N+1+1+1) * 10

     = (3N + 10) * 10

     = 30N + 100

C.   Berikut Inisialisasi Oh-nya

ALGORITMA HUFFMAN

Konsep dasar dari metode Huffman adalah dengan membangun sebuah skema atau tabel yang berisikan frekuensi kemunculan masing-masing simbol. Dari tabel tersebut kemudian dibangun suatu kode-kode unik untuk mengidentifikasikan masing-masing simbol. Proses kompresi dengan metode huffman adalah sebagai berikut:

·  Menyusun tabel frekuensi kemunculan masing-masing karakter, dan melakukan source reduction.

·  Langkah kedua dari algoritma ini adalah mengkodekan masing-masing source yang telah direduksi, dimulai dari reduksi terakhir kembali ke sumber awalnya.

·  Langkah berikutnya adalah mengkodekan data sumber berdasarkan table look-up yang ter-bentuk.

A.   Algoritma Huffman ini, merupakan algoritma yang dapat dikategorikan sebagai ConquerDecrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

algorithm:

   1- sort the message ensemble by decreasing probability.                  N+1                      

   2- N is the cardinal of the message ensemble (number of different              1

      messages).

   3- compute the integer n_0 such as 2<=n_0<=D and (N-n_0)/(D-1) is              1

      integer.

   4- select the n_0 least probable messages, and assign them each adigit   1

      code.

   5- substitute the selected messages by a composite message summing            N+1

      their probability, and re-order it.

   6- while there remains more than one message, do steps thru 8.                N+1

   7- select D least probable messages, and assign them each adigit code.   1

   8- substitute the selected messages by a composite message summing their N+1 

probability, and re-order it.

   9- the code of each message is given by the concatenation of the code          1

      digits of the aggregate they've been put in.

Tn = Cn * Cop

     = (N+1+1+1+1+N+1+N+1+1+N+1+1) * 9

     = (4N + 9) * 9

     = 36N + 81

C.   Berikut Inisialisasi Oh-nya

 

ALGORITMA KRUSKAL

Algoritma Kruskal adalah sebuah algoritma dalam teori graph yang menemukan pohon rentang minimum untuk terhubunggraf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total semua tepi di pohon diminimalkan. Jika grafik tidak terhubung, maka ia menemukan hutan rentang minimum (minimal spanning pohon untuk setiap komponen terhubung ). Algoritma Kruskal adalah contoh dari algoritma rakus .

Algoritma Kruskal adalah algoritma dalam teori graph untuk mencari minimum spaning tree di dalam graph. Algoritma Kruskal adalah contoh dari salah satu strategi algoritma yaitu Greedy Algorithm.

A.   Algoritma Kruskal ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Transformer. Karena, dalam metode penyelesaiannya memerlukan proses untuk menukar-kan posisi edge yang menjadi pertimbangan untuk perbandingan.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

int kruskal(int n, int m, set_of_edges E,set_of_edges& F)

{

set_pointer p, q;                                                             1

edge e;                                                                       1

sort the m edges in E by weight;//mengurutkan berdasarkan bobot              N+1

initial(n);                                                                   1

while (# of edges in F < n1)                                                 N+1

{

e = next lowest weight edge;                                           1

i,j = e.indices();                                                     1

p = find(i);                                                           1

q = find(j);                                                           1

if (! equal(p,q)) {                                                    1

merge(p,q);                                                     1

add e to F;                                                     1

}

}

}

Tn = Cn * Cop

     = (1+1+N+1+1+N+1+1+1+1+1+1+1+1) * 12

     = (2N + 12) * 12

     = 24N + 144

C.   Berikut Inisialisasi Oh-nya

ALGORITMA GREEDY

Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now.

Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :

• Memilih beberapa jenis investasi

• Mencari jalur tersingkat

           

Ada juga yang dapat dilakukan algoritma ini dalam sesuatu yang biasa dilakukan mesyarakat modern, yaitu memilih spesifikasi komputer yang terbaik dengan budget maksimum tertentu seperti yang akan dibahas dalam makalah ini.

Algoritma Greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusann yang terbaik dalam menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.

A.   Algoritma Greedy ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Decrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

S ← {}   // inisialisasi S dengan kosong                                          1

 while (not SOLUSI(S)) and (C ≠ {} ) do                                          N+1

       x ← SELEKSI(C)        // pilih sebuah kandidat dari C                      1

       C ← C - {x}           // elemen himpunan berkurang satu                    1

 if LAYAK(S ∪ {x}) then                                                           1

        S ← S ∪ {x}                                                               1

       endif                                                                      1

     endwhile                                                                     1

{SOLUSI(S) or C = {} }                                                            1

if SOLUSI(S) then                                                                 1

   return S                                                                       1

else                                                                              1

   write(’tidak ada solusi’)                                                      1

endif                                                                             1

Tn = Cn * Cop

     = (1+N+1+1+1+1+1+1+1+1+1+1+1+1+1) * 14

     = (N + 14) * 14

     = 14N + 196

C.   Berikut Inisialisasi Oh-nya

 

ALGORITMA DJIKSTRA

Algoritma Dijkstra adalah sebuah algoritma greedyyang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah dengan bobot-bobot sisi yang bernilai tak-negatif.Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertexs dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertexu ke vertexv. Himpunan semua tepi disebut E.

A.   Algoritma Djikstra ini, merupakan algoritma yang dapat dikategorikan sebagai ConquerDecrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

function Dijkstra(G, w, s)                                                        1

for each vertex v in V[G]                    // Inisialisasi                     N+1

           d[v] := infinity                                                       1

           previous[v] := undefined                                              N+1

     d[s] := 0                                    // Jarak antar s          1

     S := empty set                                                               1

     Q := V[G]                                    // Mengisikan nilai vertex      1

while Q is not an empty set                  // Proses algoritma            N+1

           u := Extract_Min(Q)                                                    1

           S := S union {u}                                                       1

for each edge (u,v) outgoing from u                                         1

if d[u] + w(u,v) < d[v]         // Penyeleksian kondisi            1

                        d[v] := d[u] + w(u,v)                                     1

                        previous[v] := u                                    1

Tn = Cn + Cop

     = (1+N+1+1+N+1+1+1+1+N+1+1+1+1+1+1+1) * 14

     = (3N + 14) * 14

     = 42N + 196

C.   Berikut Inisialisasi Oh-nya