ALGORITMA GREEDY

         ALGORITMA GREEDY

     Algoritma Greedy merupakan metode yang paling popular dalam memecahkan persoalan optimasi. Hanya ada dua macam persoalan optimasi, yaitu maksimasi dan minimasi. Algoritma Greedy adalah algoritma yang memcahkan masalah langkah perlangkah (step by step). Algoritma Greedy membentuk solusi langkah perlangkah. Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh Karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkahnya merupakan pilihan untuk membuat langkah optimum local ( local optimum) dengan harapan bahwa langkah sisanya mengarah ke solusi optimasi global (global optimum). Prinsip Greedy adalah “take what you can get now”, mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan kosekuensi ke depan.

Contoh masalah sehari-hari yang menggunakan prinsip greedy:

·           Memilih beberapa jenis investasi (penanaman modal)

·           Mencari jalur tersingkat / terpendek

·           Memilih jurusan di Perguruan Tinggi

·           Bermain kartu remi

·           Memecah uang 

Analisis Matematis Algoritma Rekursif Fungsi Fibonacci

function fibonacci(Input n:integer)→integer

Kamus

Algoritma

  If (n=0)

    Then

       fibonacci ← 1

    Else

       If (n=1)

         Then

                fibonacci ← 1

         Else

                Fibonacci ← (fibonacci(n-1) + fibonacci(n-2))

      Endif

   Endif

Endfunction

Operasi Dasar Utama : Penjumlahan

T(n) = T(n-1) + T(n-2)      dimana n > 2

T(n) = 1 + 1 (1 + T(n-2) + T(n-3))

T(n) = 1 + 2(1 + T(n-3) + T(n-4))

T(n) = 1 + 3(1 + T(n-4) + T(n-5))

T(n) = ...

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

T(n) = n + 1 +  T(0) + T(n – (n-2))

T(n) = n + T(n – (n-2))

T(n) = n + (n-(n-2))                         

Jadi, T(n) =  n + (n-(n-2))

Analisis Matematis Algoritma Rekursif Fungsi Menghitung Deret Aritmatika

Function S(input n:integer)→integer

Kamus

Algoritma

    If (n=1)

         Then

               Hasil ←1

         Else

              Hasil←n + S(n-1)

  Endif

Endfuction

Operasi Dasar Utama : Penjumlahan

T(n) = n + T(n-1)                               dimana n > 1

T(n) = 1 + T(n-1)

T(n) = 1 + 1 + T(n-2) = 2 + T(n-2)

T(n) = 2 + 1 + T(n-3) = 3 + T(n-3)

T(n) = ...

T(n) = n + T(n-n)

T(n) = n + T(0)

T(n) = n + 0

T(n) = n                               

Jadi, T(n) = n

Analisis Matematis Algoritma Rekursif Fungsi Faktorial

function faktorial(Input n:integer)→ integer

Kamus

Algoritma

  If (n=1) or (n=0)

    Then

       Fak← 1

   Else

       If  (n>1)        

          then

               Fak← Faktorial(n-1)*n

          Else

               Fak←0

      Endif

  Endif

Endfunction

Operasi Dasar Utama : Perkalian

T(n) = T(n-1) * n                               dimana n > 1

T(n) = 1 + T(n-1)

T(n) = 1 + 1 + T(n-2) = 2 + T(n-2)

T(n) = 2 + 1 + T(n-3) = 3 + T(n-3)

T(n) = ...

T(n) = n + T(n-n)

T(n) = n + T(0)

T(n) = n + 0

T(n) = n                               

Jadi, T(n) = n

Notasi Asimtotik dari worst case, best case dan average case program segitiga pascal

Program Segitiga_pascal

kamus 

i,j,n : Integer

    p   : array [1..50,1..50] of integer

Algoritma

  read(n);

  for i ß 1 to n do

       for j ß 1 to i do

           if (j =1) or (j = i)
                then
                                p[i,j] ß 1

                else

                                p[i,j] ß p[i-1,j] + p[i-1,j-1]

           write(p[i,j],'    ')

       Endif

  Endfor  Endfor

Terdalam (+)

Tmin  = 0

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
0 ≤ n
n = 0               0 _≤ 0
n = 1               0 ≤ 1
n = 6               0 ≤  6
n = 100                            0  ≤  100  

n₀ = 0
C = 1

Notasi Asimtotik Dari Worst case, Best case,dan Average case Program Faktorial

program Faktorial

kamus

   n,fak,i : integer

Algoritma

       read(n)

       fak ß 1

       for i ß n downto 1 do

                fak ß fak * i 

                write(i)

                if   i = 1

                   then

                            write('')

                   else

                            write('*')

                endif

           endfor

terdalam (write)

TMin   = 2n ≈ n

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
2n ≤ 3n
n = 0               0 _≤ 0
n = 1               2 ≤ 3
n = 3               6 ≤ 9
n = 100    200  ≤  300                    

n₀ = 0
C = 3 

Notasi Asimtotik dari Worst case, Best case, Average case Algoritma Menghitung Persegi

Menghitung_persegi

Deklarasi

I,j,n : integer

Algoritma

Input(n)

For i← 1 to n do

   For j← 1 to n do

         If (i>j)

                        then

                                    output(“*”)

                        else

                                    output(“ “)

               endif

     endfor

endfor

Worst case, Best case, Average case

T_min(n) = n²

O (Big Oh)

      n²    O (n²)

      n²  ≤  2n²                  (untuk semua n ≥ 0)

      c = 2, n₀ = 0

Ω (Big Omega)

      n²    Ω (n²)

      n²   ≥  ½ n²               (untuk semua n ≥ 1)

      c = ½ , n₀ = 1

Notasi Asimtotik dari worst case, best case, average case algoritma mencari bilngan prima

bil_prima

Deklarasi

 i,bil,b :interger

Algoritma

b←0

input(bil)

for i ←1 to bil do

                if (bil mod i = 0)

                                then

                                                b←b+1

                endif

endfor

                if b = 2 

                                then

                                                output(bil,”bilangan prima”)

                                else

                                                output(bil,”bukan bilangan prima”)

                endif

                

Worst case, Best case, Average case

T_min(n) = 2

O (Big Oh)     

      2   O (n⁰)

      2  ≤  3n⁰                   (untuk semua n ≥ 1)   

      c = 3 , n₀ = 1

Notasi Asimtotik dari Worst case, Best case dan Average case algoritma mencari nilai minimum

procedure NilaiTerrendah (Input N:integer a₁,. . .,a_n:integer)

Deklarasi

   i:integer;

   terrendah:real;

Algoritma:

    terrendah ← a₁

    for i ←2 to N do

      if (a_i< terrendah)

        terrendah ← a₁

      endif

    endfor

    Output('Nilai Akhir Terrendah : ',terrendah:0:2);

Endprocedure

Worst case, Best case, Average case

Yang di hitung adalah < (perbandingan)                                

T_min(n)  = n -1

O (Big Oh)     

      n – 1     O (n)

      n – 1   ≤  2n             (untuk semua n ≥ 1)   

      c = 2, n₀ = 1

Ω (Big Omega)

      n – 1     Ω (n)

      n – 1   ≥ ½ n             (untuk semua n ≥ 2)

      c = ½ , n₀ = 2

Menghitung worst case, best case dan average case dari program segitiga pascal

Program Segitiga_pascal

kamus

i,j,n : Integer

    p   : array [1..50,1..50] of integer

Algoritma

  read(n);

  for i ß 1 to n do

       for j ß 1 to i do

           if (j =1) or (j = i)
                then
                                p[i,j] ß 1

                else

                                p[i,j] ß p[i-1,j] + p[i-1,j-1]

           write(p[i,j],'    ')

       Endif

  Endfor
  Endfor

Terdalam (+)

Tmin  = 0

Tmax = n - 2

Tavg  = (n – 2) / 2

          ≈  n – 2

Menghitung Worst case, Best case,dan Average case Program Faktorial

program Faktorial

kamus

   n,fak,i : integer

Algoritma

       read(n)

       fak ß 1

       for i ß n downto 1 do

                fak ß fak * i

                write(i)

                if   i = 1

                   then

                            write('')

                   else

                            write('*')

                endif

           endfor

terdalam (write)

TMin   = 2n ≈ n

TMax  = 2n ≈ n

Tavg    = (2n + 2n)/2
            = 2n

            ≈ n

Menghitung Worst case, Best case, Average case Algoritma Menghitung Persegi

Menghitung_persegi

Deklarasi

I,j,n : integer

Algoritma

Input(n)

For i← 1 to n do

   For j← 1 to n do

         If (i>j)

                        then

                                    output(“*”)

                        else

                                    output(“ “)

               endif

     endfor

endfor

Worst case, Best case, Average case

T_min(n) = n²

T_max(n) = n²

T_avg(n) = n² ≈ n

Menghgitung Worst case, Best case dan Average case algoritma mencari nilai minimum

procedure NilaiTerrendah (Input N:integer a₁,. . .,a_n:integer)

Deklarasi

   i:integer;

   terrendah:real;

Algoritma:

    terrendah ← a₁

    for i ←2 to N do

      if (a_i< terrendah)

        terrendah ← a₁

      endif

    endfor

    Output('Nilai Akhir Terrendah : ',terrendah:0:2);

Endprocedure

Worst case, Best case, Average case

Yang di hitung adalah < (perbandingan)                                

T_min(n)  = n -1

T_max(n) = n -1

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

              ≈ n -1 / 2

              ≈ n

Menghitung worst case, best case, average case dari algoritma mencari bilngan prima

bil_prima

Deklarasi

 i,bil,b :interger

Algoritma

b←0

input(bil)

for i ←1 to bil do

                if (bil mod i = 0)

                                then

                                                b←b+1

                endif

endfor

                if b = 2

                                then

                                                output(bil,”bilangan prima”)

                                else

                                                output(bil,”bukan bilangan prima”)

                endif

               

Worst case, Best case, Average case

 

T_min(n) = 2

T_max(n) = n +1

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

      ≈  n+1 /2

                    ≈ n

Efisiensi Waktu Dalam Algoritma

Menghitung_lama_proyek

{I.S. : masukkan waktu dalam hari}

{F.S. : menampilkan keterangan tahun, bulan, dan hari}

Kamus :

                Waktu, tahun, sisa, bulan, hari : integer

Algoritma :

                Input(waktu)                            //input dalam hari

                Tahun ß waktu div 365

                Sisa ß waktu Mod 365  

                Bulan ß sisa div 30

                Hari ß sisa Mod 30

                Output(tahun, bulan, hari)

Operasi pengisian

Sintaks	Jumlah
Input(waktu)	1
Tahun ß waktu div 365	1
Sisa ß waktu Mod 365	1
Bulan ß sisa div 30	1
Hari ß sisa Mod 30	1
Total	5

Operasi pembagian

Sintaks	Jumlah
waktu div 365	1
waktu Mod 365	1
sisa div 30	1
sisa Mod 30	1
Total	4

Operasi pengeluaran

Sintaks	Jumlah
Output(tahun)	1
Output(bulan)	1
Output(hari)	1
Total	3

Total T(n)=CopC(n)

C(n)	Cop	T(n)
5	A	5a
4	B	4b
3	C	3c

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 =  5a+4b+4c

PenjumlahanDeret

Kamus :

n,I,jumlah : integer

algoritma :

input(n)

                jumlah ß 0

                i ß 1

while (i <= n) do

jumlah ß jumlah + i

i ß i + 1

endwhile                output(jumlah)

Oprasi pengisian

Sintaks	Jumlah
input(n)	1
jumlah ß 0	1
jumlah ß jumlah + i	n
i ß i + 1	n
total	2n +2

Operasi perbandingan

Sintaks	Jumlah
i <= n	n + 1
total	n + 1

Operasi penjumlahan

Sintaks	Jumlah
jumlah + i	n
i ß i + 1	n
total	2n

Opersi pengeluaran

Sintaks	Jumlah
output(jumlah)	1
total	1

Total T(n)=CopC(n)

C(n)	Cop	T(n)
2n + 2	A	(2n+2)a
n + 1	B	(n+1)b
2n	C	2nc
1	D	D

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 + t4 =  (2n+2)a + (n+1)b + 2nc+d

Massa_Jenis_Benda

Kamus :

m,v,r : integer

algoritma :

input(m)

input(v)

                r ßm/v

output(r)

Oprasi pengisian

Sintaks	Jumlah
input(m)	1
Input(v)	1
r ß m/v	1
total	3

Operasi penjumlahan

Sintaks	Jumlah
r ß m/v	1
total	1

Opersi pengeluaran

Sintaks	Jumlah
output(r)	1
total	1

Total T(n)=CopC(n)

C(n)	Cop	T(n)
3	A	3a
1	B	b
1	C	c

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3  =  3a + b + c

Menghitung_hasil_Pangkat

{I.S :}

{F.S:}

Deklarasi

Angka, pangkat, hasil: integer

Algoritma

                Input(angka)                                      //angka yang ingin di pangkatkan

                Input(pemangkat)                           //jumlah pemangkat

                hasil←angka

                for i ← 1 to pemangkat-1 do

                                hasil ←hasil *a

                endfor

                output(hasil)

operasi pengisian

Sintaks	Jumlah
Input(angka)	1
Input(pemangkat)	1
hasil←angka	1
for i ← 1 to pemangkat-1 do	n
hasil ←hasil *a	N
Total	3 + 2n

Operasi Perkalian

Sintaks	Jumlah
hasil ←hasil *a	N
Total	N

Operasi pengeluaran

Sintaks	Jumlah
output(hasil)	1
Total	1

TOTAL T(n)=CopC(n)

C(n)	Cop	T(n)
3 + 2n	A	(3 + 2n)a
n	B	(n)b
1	C	C

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 = (3 + 2n)a + (n)b  + c

Luas_Permukaan_Kerucut

Deklarasi :

                Const

                Phi : 3.14

                r, t, v : real

Algoritma :

                Input (r)

                Input (t)

                V := phi * r * (r + t)

                Output (v)

Operasi Pengisian

Sintaks	Jumlah
Input(r)	1
Input(t)	1
V := phi * r * (r + t)	1
Jumlah	4

Operasi Aritmatika

Sintaks	Jumlah
phi * r	1
R* ( r+t)	1
R+t	1
Total	3

Operasi Pengeluaran

Sintaks	Jumlah
Output (v)	1
Total	1

TOTAL T(n)=CopC(n)

C(n)	Cop	T(n)
4	A	4a
3	b	3b
1	C	c

Total kebutuhan waktu eksekusi algoritma Luas Permukaan Kerucut :

Total Waktu = t1 + t2 + t3 = 4a + 3b + c