Algoritma Greedy

ALGORITMA GREEDY

Algoritma adalah langkah dalam mencari solusi atas sebuah masalah. banyak sekali algoritma yang dapat kita gunakan dalam membangun sebuah program , salah satunya adalah algoritma greedy.

Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Greedy sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.

Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum. Persoalan optimasi ada dua macam: Maksimasi (maximization) dan Minimasi (minimization)

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

Elemen persoalan optimasi: kendala (constraints) dan fungsi objektif (atau fungsi optiamsi).

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

Studi kasus Algoritma Greedy

Mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta:

Algoritma Rekursif

Mencari T(n) Untuk Algoritma Rekursif

MEMBALIKKAN URUTAN ANGKA BILANGAN BULAT (REKURSIF)

Seperti : 123 menjadi 321

ALGORITMA :

Procedure BalikAngka (input n: integer) { membalikkan urutan bilangan bulat n   K.Awal   : nilai n sudah terdefinisi   K.Akhir  : urutan angka bilangan n dicetak terbalik      basis      : jika n < 10, cetak (n)      rekurens   : jika n > 10 maka                      - cetak (n mod 10)                      - BalikAngka (n div 10) } Deklarasi  - Algoritma  if (n < 10) then      write(n)             { basis }  else                     { rekurens }      write(n mod 10);      BalikAngka(n div 10);  endif

MENGHITUNG T(n):

T_min(n) = 1

T_max(n) = 1

T_avg(n) = ( 1 + 1 ) / 2

= 2 / 2

= 1

Algoritma Pangkat Secara Rekursif

Kamus :

                m, n : integer

Algoritma :

                Function pangkat(m : integer, n : integer) : integer

                If (n = 0) then

                                Pangkat <-- 1

                Else

                                Pangkat <-- m * pangkat(m, n - 1)

                Endif

                Endfunction

               

                Input(m, n)

                Output pangkat(m, n)

Menghitung menggunakan <-- (Assignment)

T_min(n) = 1

T_max(n) = 1

T_avg(n)   = (1+1)/2

= 2 /2

= 1

function Faktorial(n:integer) : integer;
begin
 if n=0 then
   Faktorial ç1
else
    Faktorial ç n * Faktorial(n-1);
 end;
- See more at: http://emerer.com/algoritma-rekursif-dengan-pascal/#sthash.rCjJqUS4.dpuf

function Faktorial(n:integer) : integer;
begin
 if n=0 then
   Faktorial ç1
else
    Faktorial ç n * Faktorial(n-1);
 end;
- See more at: http://emerer.com/algoritma-rekursif-dengan-pascal/#sthash.rCjJqUS4.dpuf

Function Faktorial(n:integer) : integer;
begin

if n=0 then

Faktorial :=1

else

Faktorial := n * Faktorial(n-1);

end;

Menghitung T(n)

T_min(n)   = 1

T_max(n)   = 1

T_avg(n)    = (1+1)/2

   = 2 /2

               = 1


Sumber Referensi :
Munir, Rinaldi, Algoritma & Pemprograman Dalam Bahasa Pascal dan C Edisi Revisi, Informatika, 2011.

Kompleksitas Algoritma, Ken Kinanti Purnamasari

Notasi Asimtotik

NOTASI ASIMTOTIK

Algoritma Nilai Mahasiswa

T_min(n) = 2n

T_max(n) = 2n

T_avg(n) = 2n

Karena T_min, T_max  & T_avg  memiliki nilai yang sama maka akan dituliskan 1x

Big oh

2n < cg(n)

2n < 2n                 (untuk semua n > 0)

C = 2, n₀ = 0

Big omega

2n >  cg(n)

2n > n²                             (untuk semua n < 0)

2n > 2n²

C = 2, n₀ = 0

Big Theta

c₂g(n) < 2n < c₁g(n)

        Batar atas

          2n(n-1) = 2n² – 2n < 2n²                  (untuk  semua n > 0)

          Batas bawah

          2n(n-1) = 2n² – 2n

          2n² – 2n > 2n² – 2n 1/2n                  (untuk  semua n > 2)

c₂ = 2, c₁ = 2, n₀ = 2

MENGHITUNG PERPANGAKATAN

MENGHITUNG NILAI MINIMUM

Mencari Best, Worst dan Average dari Algoritma Percabangan

Mencari Best, Worst dan Average

Nilai Mahasiswa

{Menentukan nilai mahasiswa}

DEKLARASI

                I, n, nilai : integer

ALGORITMA :

                Input(nilai,n)

                For I ß 1 to n do

                                If (nilai >= 70)&&(nilai<=100) then

                                                Output(“Sangat Bagus”)

                                Else

                                                If (nilai >= 50)&&(nilai <= 69)

                                                                Output(“Bagus”)

                                                Else

                                                                If(nilai >= 0) &&(nilai <= 49)

                                                                                Output(“Tidak Bagus”)

                                                                Endif

                                                Endif

                                Endif

                Endfor

Menghitung Menggunakan Input Dan Output

T_min (n)= 2n

T_max (n)= 2n

T_avg (n)= (2n + 2n +2n) / 3

           = 6n / 3

           = n

Algoritma Dalam Limas Segitiga

Dekarasi :

                Panjang, lebar, tinggi, volume : integer

Algoritma:

                Input ( panjang )
                Input ( lebar )
                Input ( tinggi )

                Volume = 1/3 X (1/2 X panjang X lebar ) X tinggi

                Output ( Volume )

A ) Operasi Input

Sintak	Jumlah
Panjang	1
Lebar	1
Tinggi	1
Total	3

B ) Operasi Artimatika

Sintak	Jumlah
1/3 X 1/2	1
1/2 X Panjang	1
Panjang X Lebar	1
Lebar X Tinggi	1
Total	4

C ) Operasi Ouput

Sintak	Jumlah
Volume	1
Total	1

Total Volume Luas Segitiga Ini Adalah : 

Total Waktu = t1 + t2 + t3 = 3A + 4B + 1C

MENGHITUNG WAKTU EKSEKUSI ALGORITMA LUAS LAYANG LAYANG

MENGHITUNG WAKTU EKSEKUSI SUATU ALGORITMA

Kasus : Menghitung luas layang-layang.

Program Luas_layang_layang

Dekarasi :

d1,d2,luas : real

Algoritma:

  Output(“Program mencari luas layang-layang”)

  Output(“Masukkan panjang diagonal 1 =”)

  Input(d1)

  Output(“Masukkan panjang diagonal 2 =”)

  Input(d2)

  luas <-- (1/2*d1*d2);

  Output(“Luas layang-layang adalah ”,luas)

a. Operasi Input

SINTAK	JUMLAH
Input(d1)	1
Input(d2)	1
TOTAL	2

b. Operasi Output

SINTAK	JUMLAH
Output(“Program mencari luas layang-layang”)	1
Output(“Masukkan panjang diagonal 1 =”)	1
Output(“Masukkan panjang diagonal 2 =”)	1
Output(“Luas layang-layang adalah ”,luas)	1
TOTAL	4

c. Operasi Pengisian Nilai

SINTAK	JUMLAH
luas <-- (1/2*d1*d2);	1
TOTAL	1

d. Operasi Perkalian

SINTAK	JUMLAH
luas <-- (1/2*d1*d2);	2
TOTAL	2

Total kebutuhan waktu eksekusi algoritma ini adalah

Total Waktu (T(n)) = t1 + t2 + t3 + t4 = 2a + 4b + c + 2d

Sumber Referensi :

http://dewimatkom5a.blogspot.co.id/2010/10/mencari-luas-layang-layang_29.html