R. A. Algoritma

R. A. Algoritma Univ Trunojoyo

ª        Algoritma yang bagus adalah algoritma yang mangkus. Kemangkusan algoritma diukur dari berapa jumlah waktu dan ruang (space) memori yang dibutuhkan untuk menjalankannya. Algoritma yang mangkus ialah algoritma yang meminimumkan kebutuhan waktu dan ruang.

ª        Model perhitungan waktu dan ruang. Contoh:

Jumlah<^-0

k<-1

while k<=n do

jumlah<-jumlah+a(k)

k<-k+1

endwhile

r<-jumlah/n

§        operasi pengisian nilai (jumlah<-0, k<-1, jumlah<-jumlah+a(k), k<-k+1 dan r<-jumlah/n) jumlah seluruh pengisian nilainya adalah t(1)=1+1+n+n+1=3+2n

§        operasi penjumlahan (jumlah+a(k) dan k+1) jumlah seuruh operasi penjumlahan adalah t(2)=n+n=2n

§        operasi pembagian (jumlah/n) jumlah seluruh operasi pembagian adalah t(3)=1

§        total kebutuhan waktu algoritma HitungRerata: t=t(1)+t(2)+t(3)=(3+2n)a+2nb+c detik

ª        Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma. Ada dua macam kompleksitas algoritma, yaitu: kompleksitas waktu dan kompleksitas ruang.

§        Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n (T_max(n) = worst case, Y_min(n) = best case dan T_avg(n) = average case). Contoh:

i ← 0

while i < n and A[ i ] ≠ K do

i ← i + 1

if i < n return i

else return -1

¨        Cworst (n) = n

¨        Cbest (n) = 1

Average-case efficiency

Asumsi standar:

Probabilitas dari pencarian yang sukses adalah p (0 ≤ p ≤ 1).

Probabilitas dari pencocokan pertama yang muncul pada posisi ke i dari list adalah sama untuk setiap i.

Analisa efisiensi waktu sequential search:

Cavg (n) = [ 1.p/n + 2.p/n + … + i.p/n + … + n.p/n ] + n.(1-p )

= p/n [1+2+…+i + … + n ] + n(1-p )

                = p/n . n . (n+1)/ 2 + n(1-p)

                = p(n+1)/ 2 + n(1- p)

¨        Notasi “O” disebut notasi “O-Besar” (Big-O) yang merupakan notasi kompleksitas waktu asimptotik.

¨        Definisi: T(n)  £ C(f (n))

¨        f(n) adalah batas lebih atas (upper bound) dari T(n) untuk n yang besar.

Contoh 4. Tunjukkan bahwa T(n) = 3n + 2 = O(n).

Penyelesaian:

3n + 2 = O(n) karena

3n + 2 £ 3n+2n = 5n untuk semua n ³ 1 (C = 5 dan n₀ = 1).

Contoh 5. Tunjukkan bahwa T(n) = 2n² + 6n + 1 = O(n²).

Penyelesaian:

2n² + 6n + 1 = O(n²) karena

2n² + 6n + 1 £ 2n² + 6n² + n² = 9n² untuk semua n ³ 1 (C =9 dan n₀ = 1).

(a)  T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))

(b)  T₁(n)T₂(n) = O(f(n))O(g(n)) = O(f(n)g(n))

(c)  O(cf(n)) = O(f(n)), c adalah konstanta

(d)  f(n) = O(f(n))

Contoh:

read(x);    O(1)

x:=x+a[k];  O(1) + O(1) + O(1) = O(1)

writeln(x); O(1)

maka

Kompleksitas waktu asimptotik = O(1) + O(1) + O(1) = O(1)

Penjelasan: O(1) + O(1) + O(1) = O(max(1,1)) + O(1) = O(1) + O(1) = O(max(1,1)) = O(1)

contoh:

read(x);       O(1)

if x mod 2=0 then O(1)

begin

x:=x+1;        O(1)

writeln(x);           O(1)

end

else

writeln(x);           O(1)

maka

Kompleksitas waktu asimptotik:

= O(1) + O(1) + max(O(1)+O(1), O(1))

= O(1) + max(O(1),O(1))

= O(1) + O(1)

= O(1)

Contoh:

for i:=1 to n do

jumlah:=jumlah+a[i]; O(1)

maka

Kompleksitas waktu asimptotik  = n . O(1)

= O(n .1)=O(n)

Contoh:

for i:=1 to n do

for j:=1 to n do

a[i,j]:=0;       O(1)

maka

nO(n) = O(n.n) = O(n²)

jumlah pengulangan seluruhnya = 1 + 2 + … + n = n(n + 1)/2

kompleksitas waktu asimptotik = n(n + 1)/2 .O(1)

contoh:

i:=2;                  O(1)

while i <= n do        O(1)

begin

jumlah:=jumlah + a[i]; O(1)

i:=i+1;                O(1)

 end;

maka

Kompleksitas waktu asimptotiknya adalah

= O(1) +  (n-1) { O(1) + O(1) + O(1) }

= O(1) + (n-1) O(1)

= O(1) + O(n-1)

= O(1) + O(n)

= O(n)

Kelompok  Algoritma	Nama
O(1)                        O(log n)                     O(n)                        O(n log n)               O(n2)                       O(n3)                       O(2n)                       O(n!)	konstan logaritmik lanjar n log n kuadratik kubik eksponensial faktorial

§        Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.

ª        Note:

§        Buat definisi binary search (contoh), algoritmanya dalam bentuk pseudocode, tentukan worst case, best case, average case.

§        Buat definisi selection sort (contoh), algoritmanya dalam bentuk pseudocode, tentukan worst case, best case, average case.

Jawab:

§        Soal nomer 1:

Algorithm BinarySearch(A[0..n-1], K)

l ← 0; r ← n -1

while l ≤r do

m ←└(l+r)/2┘

if K = A[m] return m

else if  K < A[m]   r←m-1

else l←m+1

return -1

§        Soal moner 2:

Algorithm SelectionSort (A[0 .. n – 1])

for i ¬ 0 to n – 2 do

min ¬ i

for j ¬ i+1 to n – 1 do

if A[j] < A[min]    min ¬ j

swap A[i]  and  A[min]

ª        Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way).

ª        Contoh brute force:

§        Menghitung an (a > 0, n adalah bilangan bulat tak-negatif)

§        Menghitung n! (n bilangan bulat tak-negatif)

§        Mengalikan dua buah matrik yang berukuran n × n.

procedure PerkalianMatriks(input A, B : Matriks,                            input n : integer,                            output C : Matriks)

Deklarasi   i, j, k : integer

Algoritma    for i¬1 to n do      for j¬1 to n do         C[i,j]¬0    { inisialisasi penjumlah }         for k ¬ 1 to n do            C[i,j]¬C[i,j] + A[i,k]*B[k,j]         endfor      endfor    endfor

Kompleksitas = O(n)

§        Menemukan semua faktor dari bilangan bulat n selain dari 1 dan n itu sendiri.

procedure CariFaktor(input n : integer)

Deklarasi

k : integer 

Algoritma:

k¬1

ketemu ¬ false

for k¬2 to n - 1 do

if n mod k = 0 then

write(k)

endif          

endfor

§        Sequential Search

procedure PencarianBeruntun(input a₁, a₂, ..., a_n : integer, x : integer, output idx : integer)

Deklarasi

  k : integer

Algoritma:

  k¬1

  while (k < n) and (a_k ¹ x) do

     k ¬ k + 1

  endwhile

  { k = n or a_k = x }

  if a_k = x then   { x ditemukan }

     idx¬k

  else

     idx¬ 0       { x tidak ditemukan }

  endif

§        Bubble Sort

procedure BubbleSort (input/output L : TabelInt, input n : integer)

Deklarasi    i    : integer    k    : integer    temp : integer

Algoritma: for i ¬ 1 to n - 1 do  for k ¬  n downto i + 1 do    if L[k] < L[k-1] then      temp ¬  L[k]    L[k] ¬  L[k-1]    L[k-1] ¬ temp    endif  endfor endfor

Kompleksitas = O(n²)

ª        Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).  Contoh:

§        Pencocokan string (string matching)

Pattern: NOT

Teks: NOBODY NOTICED HIM

 

  NOBODY NOTICED HIM

1 NOT

2  NOT

3   NOT

4    NOT

5     NOT

6      NOT

7       NOT

8        NOT

procedure PencocokanString(input P : string, T : string, n, m : integer, output idx : integer)

Deklarasi

  i : integer

  ketemu : boolean

Algoritma:

  i¬0

  ketemu¬false

  while (i £ n-m) and (not ketemu) do

    j¬1

    while (j £ m) and (P_j = T_i+j ) do

      j¬j+1

    endwhile

    { j > m or P_j ¹ T_i+j }

    if j = m then

      ketemu¬true

Kompleksitas algoritma: O(nm) pada kasus terburuk

                                    O(n) pada kasus rata-rata.

§        Mencari Pasangan Titik yang Jaraknya Terdekat

procedure CariDuaTitikTerdekat(input P : SetOfPoint, n : integer, output P1, P2 : Point)

Deklarasi

  d, dmin : real

  i, j : integer

Algoritma:

  dmin¬9999

  for i¬1 to n-1 do

    for j¬i+1 to n do

      d¬Ö((P_i.x-P_j.x)² + ((P_i.y-P_j.y)²)  

      if d < dmin then

        dmin¬d

        P1¬P_i  

        P2¬P_j

      endif 

    endfor

  endfor

kompleksitas algoritma = O(n²)

ª        Kelebihan metode brute force:

§        Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability).

§        Metode brute force sederhana dan mudah dimengerti.

§        Metode brute force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks.

§        Metode brute force menghasilkan algoritma baku (standard) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).

ª        Kelemahan metode brute force:

§        Metode brute force jarang menghasilkan algoritma yang mangkus.

§        Beberapa algoritma brute force lambat sehingga tidak dapat diterima.

§        Tidak sekontruktif/sekreatif  teknik pemecahan masalah lainnya.

ª        Exhaustive search adalah teknik pencarian solusi secara solusi brute force untuk masalah yang melibatkan pencarian elemen dengan sifat khusus. Contoh:

§        Travelling Salesperson Problem  (TSP): Persoalan TSP tidak lain adalah menemukan sirkuit Hamilton dengan bobot minimum.

§        Knapsack: Bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sedemikian sehingga memaksimumkan keuntungan. Total bobot objek yang dimasukkan ke dalam knapsack tidak boleh melebihi kapasitas knapsack.

Himpunan Bagian	Total Bobot	Total keuntungan
{} {1} {2} {3} {4} {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4} {1, 2, 3, 4}	0 2 5 10 5 7 12 7 15 10 15 17 12 17 20 22	0 20 30 50 10 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak

Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80. Solusi: X = {0, 1, 1, 0}

ª        Exhaustive Search dalam Bidang Kriptografi: Di dalam bidang kriptografi, exhaustive search merupakan  teknik yang digunakan penyerang untuk menemukan kunci enkripsi dengan cara mencoba semua kemungkinan kunci. Serangan semacam ini dikenal dengan nama exhaustive key search attack atau brute force attack. Contoh: Panjang kunci enkripsi pada algoritma DES (Data Encryption Standard) = 64 bit. Dari 64 bit tersebut, hanya 56 bit yang digunakan (8 bit paritas lainnya tidak dipakai). Jumlah kombinasi kunci yang harus dievaluasi oleh pihak lawan adalah sebanyak (2)(2)(2)(2)(2) … (2)(2) = 256 = 7.205.759.403.7927.936

ª        Mempercepat Algoritma Exhaustive Search: Salah satu teknik yang digunakan untuk mempercepat pencarian solusi adalah teknik heuristik (heuristic). Contoh: Contoh: Masalah anagram. Anagram adalah penukaran huruf dalam sebuah kata atau kalimat sehingga kata atau kalimat yang baru mempunyai arti lain.

Contoh-contoh anagram (semua contoh dalam Bahasa Inggris):

lived => devil; tea => eat; charm => march

ª        Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes. Sekarang strategi tersebut  menjadi strategi fundamental di dalam ilmu komputer dengan nama 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), dan Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

procedure DIVIDE_and_CONQUER(input n : integer)

Deklarasi

     r, k : integer

Algoritma

  if n £ n₀ then                  

     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)

Deklarasi

     r, k : integer

Algoritma

  if n £ n₀ then               

     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

Contoh: Mencari nilai maksimum dan nilai minimum

procedure MinMaks1(input A : TabelInt, n : integer, output min, maks : integer)

Deklarasi

    i : integer

Algoritma:

    min¬ A₁    

    maks¬A₁  

    for i¬2 to n do

      if A_i < min then

          min¬A_i

      endif

      if A_i > maks then

          maks¬A_i

      endif

   endfor

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

a