Tugas mandiri

Algoritma dan struktur data

Solving Recurrences

INDAH AYUSTINA

H12111251

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PEGETAHUAN ALAM

UNIVERSITAS HASNUDDIN

2012/2013

Nama : Indah Ayustina

NIM : H12111251

Alamat blog :ayundahindahamid.blogspot.com

1. MERGE SORT

Merge sort merupakan algoritma pengurutan dalam ilmu komputer

yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian

data yang tidak memungkinkan untuk ditampung dalam memori komputer

karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von

Neumann pada tahun 1945.(sumber : id.wikipedia.org/wiki/Merge_sort)

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari

terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak

daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk

mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait

telah menurun, karena banyak aplikasi algoritma merge yang mempunyai

alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga

semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya

ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan

memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama

besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian

digabungkan kembali untuk membentuk tabel yang terurut. Implementasi

dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk

menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk

menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga

dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori

yang dibutuhkan.

Algoritma Merge umumnya memiliki satu set pointer p0..n yang

menunjuk suatu posisi di dalam satu set daftar L0..n . Pada awalnya mereka

menunjuk item yang pertama pada setiap daftar.

(sumber:learning.upnjatim.ac.id/courses/E1234/work/

480232e1ad23aTugas_yang_harus_di_upload.doc pengertian merge sort)

Prinsip mendasar yang di gunakan pada algoritma merge sort sering

disebut atau mengikuti pola pecah belah dan taklukan (divide and conquer).

Pola divide and Conquer, adalah banyak diadopsi oleh beberapa alogirtma

yang pada dasarnya mengimplementasikan konsep rekursi (adalah cara untuk

menetapkan proses dengan dirinya sendiri) untuk memecahkan permasalahan.

Caranya adalah permasalahan utama dipecah menjadi sub-masalah, kemudian

solusi dari sub masalah akan di gabungkan untuk mendapatkan solusi dari

masalah utama. Pada setiap tingkat rekursi pola tersebut terdiri atas 3

langkah :

1. Devide, yakni memilih masalah menjadi sub-masalah.

2. Conquer, yakni menyelesaikan sub-masalah tersebut secara rekursi.

3. Kombinasi/Penggabungan, menggabungkan solusi dari sub-masalah untuk

mendapatkan solusi dari masalah utama.

(sumber: aslamhadi.wordpress.com/2008/07/15/algoritma-merge-sort/)

2. REKURSIF

Metode umum dari penyederhanaan adalah dengan membagi suatu

permasalah menjadi beberapa sub-permasalahan dengan tipe yang sama.

Sebagai sebuah teknik dalam pemrograman komputer, hal ini disebut dengan

divide and conquer dan merupakan kunci dari perancangan berbagai algoritma

penting. Divide and conquer menyediakan pendekatan atas-bawah dalam

pemecahan masalah, di mana permasalahan diselesaikan dengan

menyelesaikan instansi yang lebih kecil. Pendekatan sebaliknya yaitu

pemrograman dinamis. Pendekatan ini menyelesaikannya secara bawah-atas,

di mana permasalahan diselesaikan dengan menyelesaikan instansi yang lebih

besar, sampai ukuran yang diinginkan dicapai.

Contoh klasik dari rekursi adalah definisi dari fungsi faktorial, diberikan

dalam kode C:

unsigned int factorial(unsigned int n)

{

if (n <= 1)

return 1;

else

return n * factorial(n-1);

}

Fungsi tersebut memanggil dirinya sendiri secara rekursif terhadap

versi input yang lebih kecil (n-1) dan mengkalikan hasil dari pemanggilan

rekursif dengan n, sampai pada kasus dasar, sama analoginya dengan definisi

matematika dari faktorial. Rekursi dalam pemrograman komputer

dicontohkan saat sebuah fungsi didefinisikan dalam bentuk sederhana,

bahkan versi terkecil dari dirinya. Solusi dari permasalahan kemudian

dirancang dengan menggabungkan solusi-solusi yang didapat dari versi

sederhana dari permasalahan. Salah satu contoh aplikasi rekursi yaitu dalam

parsing untuk bahasa pemrograman. Keuntungan utama dari rekursi adalah

suatu himpunan tak-terbatas dari kalimat yang memungkinkan, perancangan

atau data lainnya dapat didefinisikan, diurai atau dihasilkan dengan suatu

program komputer yang terbatas.

Relasi perulangan adalah persamaan-persamaan untuk menentukan

satu atau lebih urutan-urutan secara rekursif. Beberapa relasi perulangan

tertentu dapat "diselesaikan" untuk mendapatkan definisi bukan-

rekursif.Penggunaan rekursi dalam suatu algoritma memiliki kelebihan dan

kekurangan. Kelebihan utamanya adalah biasanya kesederhanaan.

Kekurangan utamanya adalah terkadang algoritma tersebut membutuhkan

memori yang sangat banyak jika kedalaman rekursi sangat besar.

(sumber: http://id.wikipedia.org/wiki/Rekursi).

Bentuk rekursif :

a. Suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri.

b. Bentuk dimana pemanggilan subrutin terdapat dalam body subrutin

c. Dengan rekursi, program akan lebih mudah dilihat

Bentuk rekursi bertujuan untuk :

a. menyederhanakan penulisan program

b. menggantikan bentuk iterasi

Syarat bentuk rekursif:

a. ada kondisi terminal (basis)

b. subroutine call yang melibatkan parameter yang nilainya menuju

kondisi terminal (recurrence).

Langkah-langkah dalam mendefinisikan suatu himpunan secara rekursif:

1. Langkah basis:

Spesifikasi koleksi awal dari anggota

2. Langkah rekursif:

Mendefinisikan aturan konstruksi anggota baru dari anggota yang

telah diketahui .

(Sumber: www.math.itb.ac.id/~diskrit/Kuliah5baru.ppt).

3. IMPLEMENTASI MERGE SORT

program MergeSort;

uses crt;

type mrg = array [1..100] of integer;

var

mrgslh,mrgbnr : mrg;

n,m : integer;

procedure merge(Left:mrg; pjgL:integer; Right : mrg; pjgR:integer; var

ArrMerge : mrg);

{IS : Menerima array left dan array right untuk dibandingkan dan disusun

kembali ke array merge}

{FS : Hasil penggabungan akan dikembalikan melalui variabel output

ArrMerge}

var

i,j,k,m,panjang: integer;

hasil : mrg;

begin

i:=1;

j:=1;

k:=1;

panjang:=pjgL+pjgR;

{membandingkan 2 array Left dan Right hingga panjang salah satu array

mencapai 0 }

while ((pjgL>0) and (pjgR>0)) do

begin

{jika elemen pertama array Left lebih kecil dari elemen array Right

maka elemen pertama pada array hasil diisi oleh elemen pertama array

Left}

if(Left[i]<= Right[j]) then

begin

hasil[k]:=Left[i];

i:=i+1;

k:=k+1;

pjgL:=pjgL-1;

end

{jika elemen pertama array Left lebih besar dari elemen array Right

maka elemen pertama pada array hasil diisi oleh elemen pertama array

Right}

else

begin

hasil[k]:=Right[j];

j:=j+1;

k:=k+1;

pjgR:=pjgR-1;

end;

end;

{Jika array Left belum kosong dan array Right sudah kosong,

maka sisa dari Left dimasukkan ke array Hasil}

while (pjgL>0) do

begin

hasil[k]:=Left[i];

i:=i+1;

k:=k+1;

pjgL:=pjgL-1;

end;

{Jika array Left belum kosong dan array Right sudah kosong,

maka sisa dari Left dimasukkan ke array Hasil}

while (pjgR>0) do

begin

hasil[k]:=Right[j];

j:=j+1;

k:=k+1;

pjgR:=pjgR-1;

end;

{Mengembalikan nilai ke variabel output ArrMerge}

ArrMerge:=hasil;

for m:= 1 to panjang do

writeln('Array Merge ke-',m,' : ',hasil[m]);

end;

procedure msort(pjg:integer;A : mrg;var ArrHasil : mrg);

{IS : Menerima Array yang akan dibagi menjadi 2 array yaitu array Left dan

array Right}

{FS : Mengembalikan array yg terurut melalui variabel output ArrHasil}

var

middle,i,pjgLeft,pjgRight : integer;

ArrLeft,ArrRight : mrg;

begin

if pjg <= 1 then

ArrHasil := A

else

begin

middle := pjg div 2;

for i:=1 to middle do

ArrLeft[i]:=A[i];

for i:=(middle+1) to pjg do

ArrRight[i-middle]:=A[i];

pjgLeft := pjg div 2;

pjgRight := (pjg+1) div 2;

for m:= 1 to pjgLeft do

writeln('Array Left ke-',m,' : ',ArrLeft[m]);

for m:= 1 to pjgRight do

writeln('Array Right ke-',m,' : ',ArrRight[m]);

{rekursif procedure mergesort dengan output akan disimpan di ArrLeft}

msort(pjgLeft,ArrLeft,ArrLeft);

{rekursif procedure mergesort dengan output akan disimpan di ArrRight}

msort(pjgRight,ArrRight,ArrRight);

{memanggil procedure merge untuk menyatukan ArrLeft dan ArrRight

dan mengembalikan 1 array terurut melalui ArrHasil}

merge(ArrLeft,pjgLeft,ArrRight,pjgRight,ArrHasil);

end;

end;

begin

clrscr;

write('Jumlah array : ');readln(n);

for m := 1 to n do

begin

write('Array ke-',m,' : ');

readln(mrgslh[m]);

end;

writeln;

writeln('PROSES MERGE SORT');

writeln('-------------------');

msort(n,mrgslh,mrgbnr);

writeln;

writeln('HASIL ARRAY YANG TERURUT');

writeln('---------------------');

for m:= 1 to n do

writeln('Array Urut ke-',m,' : ',mrgbnr[m]);

readln;

end.

INPUT :

OUTPUT :

Prosesnya dapat dilihat seperti pada gambar di bawah

KOMPLEKSITAS WAKTU

Asumsi : n=2k

T(n) = jumlah perbandingan pada pengurutan 2 buah table + jumlah

perbandingan pada procedure merge.

T(n)= a ,n=1

2 T ( n2 )+cn , n>1

9 6 7 248

9

9 6 7 248

6 7 4 28

6 7 4 2

6 7 2 49 8

6 7 9 2 4 8

2 4 6 987

Proses :

T (n )=2 T ( n2 )+cn

¿2(2 T ( n4 )+ cn

2 )+cn=4 T ( n4 )+2cn

¿4 (2 T ( n8 )+ cn

4 )+2 cn=8 T ( n8 )+3cn

Berhenti jika ukuran tabel terkecil ,n =1:

n

2k=1→ k=¿2 log n

Sehingga

T(n)=nT(1)+cn 2log n

= na +cn 2log n

= O(n 2log n)

4. SOLVING RECCURENCES

Metode pembuktian kebenaran dilakukan dangan 2 cara yaitu:

a. Metode subtitusi

Langkahnya ada dua yaitu pertama menentuka bentuk solusi,dan yang

kedua d kita gunakan induksi matematika untuk menunjukkan bahwa

solusi benar untuk semua input.sebagai contoh

Selesaikan

T(n) = 2T ([n/2]) + n, T(1)=1

Misalnya digunakan tebakan : O(n log n)

T(n) = 2 T([n/2]) + n , T(1) = 1

T(n) ≤ 2(c[n/2]log([n/2])) + n

≤ c.n.lg([n/2]) + n

≤ c.n.lg n - c.n.lg 2 + n

≤ c.n.lg n - c.n + n

≤ c.n.lg n

yang berlaku untuk c ≥ 1

Induksi matematika mengharuskan untuk menunjukkan bahwa

solusi kita berlaku untuk syarat batas. Biasanya, kita melakukannya

dengan menunjukkan bahwa syarat batas yang cocok digunakan

sebagai kasus dasar untuk pembuktian induktif.

b. Metode iterasi

Metode iterasi tidak memerlukan tebakan solusinya, tetapi

memerlukan manipulasi aljabar yang lebih intensif dari pada metode

substitusi. Ide dasarnya adalah dengan mengembangkan bentuk

rekursif tersebut serta merepresentasi-kannya dalam bentuk jumlah.

Teknik untuk mengevaluasi bentuk jumlah dapat digunakan untuk

mendapatkan nilai batas dari solusinya.

Contoh: Contoh: T(n) = 3T([n/4])+ n

Bila bentuk rekursif diuraikan:

T(n) = n + 3T([n/4])

= n + 3([n/4]) + 3T(n/4[/4]))

= n + 3([n/4]+ 3([n/16]+ 3T(n/64)))

= n + 3n/4+ 9n/16+ 27T(n/64)

Suku ke-i berbentuk 3in/4i

Oleh karena n berkurang sebesar 4 pada setiap iterasi, maka proses

berlangsung sampai log4N langkah .

T(n) ≤ n + 3n/4 + 9n/16 + 27n/64 + . . .+ 3log4N N / N

≤ n . ∑i=0

log4 N−134

i

+O ¿¿

≤ n .∑i=0

∞34

i

+O¿¿

≤ 4 n+O ( n )≤ 5 n

¿O(n)

Contoh: T(n) = aT([n/4])+ n

a=3: n, (3/4)n, (3/4)2n, ...

a=4: n, (4/4)n, (4/4)2n, ...

a=5: n, (5/4)n, (5/4)2n, ...

c. Metode master

Metode utama adalah metode untuk memecahkan kambuh. Meskipun tidak dapat menyelesaikan semua kambuh, itu adalah tetap sangat berguna untuk berurusan dengan kambuhnya banyak dilihat dalam praktek. Misalkan Anda memiliki kekambuhan bentuk

T (n) = aT (n / b) + f (n),

dimana a dan b adalah konstanta sembarang dan f adalah beberapa fungsi dari n. Kekambuhan ini akan muncul dalam analisis dari algoritma rekursif bahwa untuk masukan besar ukuran n istirahat masukan menjadi sebuah subproblem masing-masing berukuran n / b, rekursif memecahkan submasalah, kemudian recombines hasilnya. Pekerjaan untuk membagi masalah menjadi submasalah bergabung kembali hasilnya adalah f (n).

Kita dapat membayangkan ini sebagai pohon kambuh, di mana node di pohon memiliki faktor percabangan dari. Simpul atas memiliki f kerja (n) terkait dengan itu, tingkat berikutnya memiliki pekerjaan f (n / b) yang berhubungan dengan masing-masing dari node, tingkat berikutnya memiliki f kerja (n / b 2) terkait dengan masing-masing dari 2 node , dan sebagainya. Pada daun adalah kasus dasar yang sesuai untuk beberapa 1 ≤ n <b. Pohon itu memiliki log b tingkat n, sehingga jumlah total daun adalah log

b n = n log

b a.

Total waktu yang diambil hanya jumlah waktu yang dibutuhkan pada setiap tingkat. Waktu yang dibutuhkan pada tingkat ke-i adalah f i (n / b i), dan total waktu adalah jumlah kuantitas ini karena saya berkisar dari 0 sampai log b n-1, ditambah waktu yang dibutuhkan pada daun, yang konstan untuk setiap kali daun jumlah daun, atau O (n log

b a). Demikian

T (n) = Σ 0 ≤ i <log b a n i f (n / b i) + O (n log b a).

Apa jumlah ini terlihat seperti tergantung pada bagaimana pertumbuhan asimtotik dari f (n) dibandingkan dengan pertumbuhan asimtotik jumlah daun. Ada tiga kasus:

Kasus 1: f (n) adalah O (n log b a - ε). Karena daun tumbuh lebih cepat dari f,

asimtotik semua pekerjaan dilakukan pada daun, sehingga T (n) adalah Θ (n log

b a).

Kasus 2: f (n) adalah Θ (n log b a). Daun tumbuh pada tingkat yang sama seperti

f, sehingga urutan yang sama dari pekerjaan yang dilakukan di setiap tingkat pohon. Pohon ini memiliki O (log n) tingkat, kali kerja yang dilakukan pada satu tingkat, menghasilkan T (n) adalah Θ (n log

b log n).

Kasus 3: f (n) adalah Ω (n log b a + ε). Dalam hal ini f tumbuh lebih cepat dari

jumlah daun, yang berarti bahwa asimtotik jumlah total pekerjaan didominasi oleh kerja yang dilakukan di simpul akar. Untuk batas atas, kita juga perlu kondisi kelancaran ekstra pada f dalam hal ini, yaitu bahwa af (n / b) ≤ cf (n) untuk beberapa <1 dan besar n konstan c. Dalam hal ini T (n) adalah Θ (f (n)).

Seperti disebutkan, metode utama tidak selalu berlaku. Misalnya, contoh kedua yang dipertimbangkan di atas, di mana ukuran subproblem yang tidak sama, tidak tercakup oleh metode master.

Mari kita lihat beberapa contoh di mana metode utama tidak terapkan.

Contoh 1 Pertimbangkan pengulangan

T (n) = 4T (n / 2) + n.

Untuk kekambuhan ini, ada = 4 subproblems, masing-masing membagi masukan dengan b = 2, dan kerja yang dilakukan pada setiap panggilan adalah f (n) = n. Jadi n log

b a adalah n 2, dan f (n) adalah O (n 2-ε) untuk ε = 1,

dan Kasus 1 berlaku. Jadi T (n) adalah Θ (n 2).

Contoh 2 Perhatikan pengulangan

T (n) = 4T (n / 2) + n 2.

Untuk kekambuhan ini, ada lagi = 4 subproblems, masing-masing membagi masukan dengan b = 2, tapi sekarang kerja yang dilakukan pada setiap panggilan adalah f (n) = n 2. Lagi n log

b a adalah n 2, dan f (n) dengan demikian

Θ (n 2), sehingga Kasus 2 berlaku. Jadi T (n) adalah Θ (n 2 log n). Perhatikan bahwa peningkatan kerja pada setiap panggilan rekursif dari linear ke kuadrat telah meningkatkan waktu berjalan keseluruhan asimtotik hanya dengan faktor logaritmik.

Contoh 3 Pertimbangkan pengulangan

T (n) = 4T (n / 2) + n 3.

Untuk kekambuhan ini, ada lagi = 4 subproblems, masing-masing membagi masukan dengan b = 2, tapi sekarang kerja yang dilakukan pada setiap panggilan adalah f (n) = n 3. Lagi n log

b a adalah n 2, dan f (n) dengan demikian

Ω (n 2 + ε) untuk ε = 1. Selain itu, 4 (n / 2) 3 ≤ kn 3 untuk k = 1/2, sehingga Kasus 3 berlaku. Jadi T (n) adalah Θ (n 3).

Contoh: Yet Another Algoritma Sorting

Jenis-jenis fungsi berikut pertama dua-pertiga dari daftar, maka kedua dua-pertiga, maka pertama dua-pertiga lagi:

class="google-src-text" style="direction: ltr; text-align: left">let rec sort3 (a : 'a list) : 'a list = biarkan rec sort3 (a: 'daftar):' daftar = class="google-src-text" style="direction: ltr; text-align: left">match a with sesuai dengan class="google-src-text" style="direction: ltr; text-align: left">[] -> [] [] -> [] class="google-src-text" style="direction: ltr; text-align: left">| [x] -> [x] | [X] -> [x] class="google-src-text" style="direction: ltr; text-align: left">| [x; y] -> [(min xy); (max xy)] | [X; y] -> [(min xy); (max xy)] class="google-src-text" style="direction: ltr; text-align: left">| _ -> | _ -> class="google-src-text" style="direction: ltr; text-align:

left">let n = List.length a in biarkan n = daftar.length dalamclass="google-src-text" style="direction: ltr; text-align:

left">let m = (2*n + 2)/3 in biarkan m = (2 * n + 2) / 3 diclass="google-src-text" style="direction: ltr; text-align:

left">let res1 = sort3 (take am) @ (drop am) in biarkan RES1 = sort3 (mengambil am) @ (penurunan am) diclass="google-src-text" style="direction: ltr; text-align:

left">let res2 = (take res1 (nm)) @ sort3 (drop res1 (nm)) in biarkan res2 = (mengambil RES1 (nm)) @ sort3 (drop RES1 (nm)) di class="google-src-text" style="direction: ltr; text-align:

left">sort3 (take res2 m) @ (drop res2 m) sort3 (mengambil res2 m) @ (drop res2 m)

Berikut take am adalah daftar yang terdiri dari pertama m elemen dari a , dan drop am adalah daftar yang terdiri dari semua tapi yang pertama m elemen dari a . Mungkin mengejutkan, algoritma ini tidak mengurutkan daftar. Kami meninggalkan bukti bahwa jenis dengan benar sebagai latihan. Kuncinya adalah untuk mengamati bahwa dua yang pertama melewati memastikan bahwa sepertiga terakhir dari daftar berisi unsur-unsur yang benar dalam urutan yang benar.

Kita dapat memperoleh waktu berjalan dari algoritma dari kekambuhan dengan menggunakan metode master. Rutin melakukan O (n) pekerjaan selain tiga panggilan rekursif pada daftar panjang 2 n / 3. Oleh karena itu kambuh adalah:

T (n) = cn + 3 T (2 n / 3)

Jika kita menerapkan metode utama untuk sort3 algoritma, kita melihat bahwa kita berada dalam kasus 1, sehingga algoritma ini adalah O (n log

3/2 3) =

O (n 2,71), membuatnya bahkan lebih lambat dari insertion sort! Perhatikan bahwa berada di Kasus 1 berarti bahwa meningkatkan f (n) tidak akan meningkatkan waktu keseluruhan. Misalnya, mengganti daftar dengan array meningkatkan f (n) untuk konstan dari waktu linier, tetapi kompleksitas asimtotik keseluruhan masih O (n 2.71).