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 (Tmax(n) = worst case, Ymin(n) = best case dan Tavg(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 n0 = 1).
Contoh 5. Tunjukkan bahwa T(n) = 2n2 + 6n + 1 = O(n2).
Penyelesaian:
2n2 + 6n + 1 = O(n2) karena
2n2 + 6n + 1 £ 2n2 + 6n2 + n2 = 9n2 untuk semua n ³ 1 (C =9 dan n0 = 1).
(a)  T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))
(b)  T1(n)T2(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(n2)
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 a1, a2, ..., an : integer, x : integer, output idx : integer)
Deklarasi
  k : integer
Algoritma:
  k¬1
  while (k < n) and (ak ¹ x) do
     k ¬ k + 1
  endwhile
  { k = n or ak = x }
  if ak = 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(n2)
ª        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 (Pj = Ti+j ) do
      j¬j+1
    endwhile
    { j > m or Pj ¹ Ti+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¬Ö((Pi.x-Pj.x)2 + ((Pi.y-Pj.y)2)  
      if d < dmin then
        dmin¬d
        P1¬Pi  
        P2¬Pj
      endif 
    endfor
  endfor
kompleksitas algoritma = O(n2)
ª        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 £ n0 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 £ n0 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¬ A1    
    maks¬A1  
    for i¬2 to n do
      if Ai < min then
          min¬Ai
      endif
      if Ai > maks then
          maks¬Ai
      endif
   endfor
T(n) = (n – 1) + (n – 1) = 2n – 2  = O(n)
a

2 comments:

  1. gan, boleh tau contoh kasus untuk tiap O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n), O(n!)?
    misal O(1) bisa di pakai pada program apa gt. mohon sangat bantuannya gan. terimakasih

    ReplyDelete
  2. ini blog apaan bro? gajelas sama sekali

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...