FREEDOM

TUGAS 6

Algoritma Greedy

1 Definisi Algoritma Greedy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah:

1. mengambil pilihan yang terbaik yang dapat diperoleh saat itu

2. berharap bahwa dengan memilih optimum loklal pada setiap langkah akan mencapai optimum global. Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global. Prinsip algoritma greedy adalah: “take what you can get now!” Ambil apa yang anda peroleh sekarang! Prinsip ini juga dipakai dalam pemecahan masalah optimasi. Dalam kehidupan sehari-hari, kita juga pernah menggunakan prinsip greedy, misalnya: a. Memilih jurusan di Perguruan Tinggi b. Memilih jalur tersingkat dari Bandung ke Jakarta.

1.1 Skema Umum Algoritma Greedy Persoalan optimasi dalam konteks algoritma greedy disusun oleh elemen elemen sebagai berikut :

1. Himpunan kandidat, C. Himpunan ini berisi elemen-elemen pembentuk solusi. Pada setiap langkah, satu buah kandidat diambil dari himpunannya.
2. Himpunan solusi, S. Himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari himpunan kandidat.

3. Fungsi seleksi (selection function) Fungsi ini dinyatakan dengan predikat seleksi. Merupakan fungsi yang pada setiap langkah memilih kandidat yang paling memungkinkan

1.2 Elemen-elemen algoritma greedy:

1. Himpunan kandidat, C.
2. Himpunan solusi, S
3. Fungsi seleksi (selection function)
4. Fungsi kelayakan (feasible)
5. Fungsi obyektif

Dengan kata lain: algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini,S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.

TUGAS 5

Analisis Algoritma Rekursif

1. Algorithm S(n)

//Input: A positive integer n

//Output: The sum of the first n cubes

if n = 1 return 1

else return S(n − 1) + n ∗ n ∗ n

Operasi Dasar Utama : Perkalian

M(n) = M(n − 1) + 2, M(1) = 0

Subtitusi :

M(n) = M(n − 1) + 2

= [M(n − 2) + 2] + 2 = M(n − 2) + 2 + 2

= [M(n − 3) + 2]+2+2 = M(n − 3)+2+2 + 2

= ...

= M(n − i) + 2i

= ...

= M(1) + 2(n − 1) = 2(n − 1)

2. Algorithm Power(n)

//Computes 2n recursively by the formula 2n = 2n−1 + 2n−1

//Input: A nonnegative integer n

//Output: Returns 2n

if n = 0 return 1

else return Power(n − 1) + Power(n − 1)

Operasi Dasar Utama : Pengurangan

A(n) = 2A(n − 1) + 1, A(0) = 0.

Subtitusi :

A(n) = 2A(n − 1) + 1

= 2[2A(n − 2) + 1] + 1 = 2^(2)A(n − 2) + 2+ 1

= 2^(2)[2A(n − 3) + 1] + 2 + 1 = 2^(3)A(n − 3) + 2^(2) + 2+ 1

= ...

= 2^(i)A(n − i) + 2^(i−1) +2^(i−2) + ... + 1

= ...

= 2^(n)A(0) + 2^(n−1) + 2^(n−2) + ... + 1 = 2^(n−1) + 2^(n−2) + ... + 1 = 2n − 1.

3. Algorithm Min2 (A[l..r])

if l= r return A[l]

else temp1 ← Min2 (A[l.. (l + r)/2 ])

temp2 ← Min2 (A[ (l + r)/2 +1..r])

if temp1 ≤ temp2 return temp1

else return temp2

Operasi Dasar Utama : Pembagian

C(n) = C( n/2 ) + C( n/2 ) + 1 untuk n > 1, C(1) = 0

n = 2^(k)

Subsitusi :

C(2^(k)) = 2C(2^(k−1)) + 1

= 2[2C(2^(k−2))+1]+1 = 2^(2)C(2^(k−2)) + 2 + 1

= 2^(2)[2C(2^(k−3)) + 1] + 2 + 1 = 2^(3)C(2^(k−3)) + 2^(2) + 2 + 1

= ...

= 2^(i)C(2^(k−i)) + 2^(i−1) +2^(i−2) + ... + 1

= ...

= 2^(k)C(2^(k−k)) + 2^(k−1) +2^(k−2) + ...+1 = 2^(k) −1 = n − 1

TUGAS 3

Mencari Kompleksitas Waktu Tmin, Tmax dan Tavg

1.      Procedure Beberapa_Bil_Genap ( input n = integer; output x = integer)

Kamus

 x = integer

 n = integer

Algoritma

 Input(n)

 x := 1

 while  x <= n  do

  if (x mod 2) = 0 then

    output(x)

    x := x + 1

  endif

 endwhile

-------------------------------------------------------------------------------------------------------

output

Tmin = 1

Tmax = n

Tavg = (1+2+3+...+n)/n = 1/2(n(n+1) = (n+1)/2

2.      Program Beberapa_Bil_Ganjil

Kamus

 a = integer

Algoritma

 a := 1

 repeat

  if (a mod 2) = 1

   output(a)

   a := a + 1

  endif

 until a = 20

-------------------------------------------------------------------------------------------------------

output

Tmin = 1

Tmax = n

Tavg = (1+2+3+...+n)/n = 1/2(n(n+1) = (n+1)/2

3. Procedure Tampilkan_derat_angka(input baris = integer, kolom = integer; output baris = integer)

Algoritma

Input (baris,kolom)

Akhir := 4
for baris := 1 to akhir do
for kolom := 1 to baris do
output(baris);
endfor

Endfor

-------------------------------------------------------------------------------------------------------

output

Tmin = 1

Tmax = n

Tavg = (1+2+3+...+n)/n = 1/2(n(n+1) = (n+1)/2

4. Procedure CariMaks (input a₁,a₂,...,a_n : integer, output maks : integer)

Kamus

i, n : integer

Algoritma

input(n)

i := 1

While i <= n do

If a_i > maks then

maks := a_i

endif

i := i +1

endwhile

-------------------------------------------------------------------------------------------------------

Tmin = 1

Tmax = n

Tavg = (1+2+3+...+n)/n = 1/2(n(n+1) = (n+1)/2

5. Procedure Menentukan_JumBil (input y : integer; output jumlah : real)

Kamus

x = integer

Algoritma

Input (y)

x := 1

for x := 1 to y do

Jumlah := Jumlah + x

endfor

Output (Jumlah)

-------------------------------------------------------------------------------------------------------

Tmin = 1

Tmax = n

Tavg = (1+2+3+...+n)/n = 1/2(n(n+1) = (n+1)/2

TUGAS 2

Kompleksitas Algoritm

1. Program Nilai_Mata_Kuliah

Deklarasi

UAS, UTS, Tugas, Nilai = Real

Algoritma

Input (UAS)

Input (UTS)

Input (Tugas)

Nilai ← ((UASx0.5) + (UTSx0.3) + (Tugasx0.2))

Output (Nilai)

Mencari T(n) ?

- Operasi Input Data : 3n + 1

- Operasi Perkalian : 3

- Operasi Penjumlahan : 2

- Operasi Output : 1

Maka T(n)= (3n+1)a + 3b + 2c +d

2. Penjumlahan dua buah bilangan bulat

Deklarasi

a,b,c = integer

Algoritma

Input (a)

Output (a)

Input (b)

Output (b)

c ← a+b

Output (c)

Mencari T(n) ?

- Operasi Input Data : 2n + 1

- Operasi Penjumlahan : 1

- Operasi Output : 3

Maka T(n)= (2n+1)a + b + 3c

3. Perpangkatan

Deklarasi

a = Real

n = integer

p = real

I = integer

Algoritma

Input (a,n)

P ← 1

For I ← 1 to n do

P ← p * a

Endfor

Output (p)

Mencari T(n) ?

- Operasi Input Data : 3n + 1

- Operasi Perkalian : n

- Operasi Output : 1

Maka T(n)= (3n+1)a + nb + c

4. Program Luas_Persegi_Panjang

Deklarasi

Panjang, Lebar, Luas = Real

Algoritma

Input (Panjang)

Input (Lebar)

Luas ← Panjang x Lebar;

Output (Luas)

Mencari T(n) ?

- Operasi Input Data : 2n + 1

- Operasi Perkalian : 1

- Operasi Output : 1

Maka T(n)= (2n+1)a + b + c

5. Program Luas Lingkaran;

Deklarasi

Jari_Jari, Phi, Luas = Real

Algoritma

Input (Jari_Jari)

Phi ← 3.14

Luas ←Phi x Jari_Jari x Jari_Jari

Output (Luas)

Mencari T(n) ?

- Operasi Input Data : n + 2

- Operasi Perkalian : 2

- Operasi Output : 1

Maka T(n)= (n+2)a + 2b + c

TUGAS 1

Analisis Algoritma

Pembahasan Tentang

Sorting

Searching

String Matching

Combinatorial problem

Graph problem

Geometry problem

Numerical Problem