Analisis Algoritma

Selasa, 06 Desember 2016

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

Baca selengkapnya »

Selasa, 29 November 2016

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

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

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

Selasa, 01 November 2016

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

Baca selengkapnya »

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

Baca selengkapnya »

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

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

Baca selengkapnya »

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)

O (n⁰)

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

c = 3 , n₀ = 1

Baca selengkapnya »

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

Baca selengkapnya »

Selasa, 25 Oktober 2016

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