Algoritma rekursif dan relasi rekurensi

Deskripsi Materi ini membahas tentang algoritma rekursif beserta relasi rekurensnya

Tujuan Instruksional Khusus (TIK) Menjelaskan algoritma rekursif dengan studi kasus menara hanoi dan faktorial beserta perhitungan kompleksitasnya Menyelesaikan relasi rekurens linier dan koefisien konstan Meyelesaikan relasi rekurens dengan teorema master

Rekursif Bentuk rekursif : Suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri. Bentuk dimana pemanggilan subrutin terdapat dalam body subrutin Dengan rekursi, program akan lebih mudah dilihat Bentuk rekursi bertujuan untuk : menyederhanakan penulisan program menggantikan bentuk iterasi Syarat bentuk rekursif: ada kondisi terminal (basis) subroutine call yang melibatkan parameter yang nilainya menuju kondisi terminal (recurrence)

Menghitung kompleksitas : Studi kasus Faktorial Function Faktorial (input n : integer) integer {menghasilkan nilai n!, n tidak negatif} Algoritma If n=0 then Return Else Return n*faktorial (n-1) Endif Kompleksitas waktu : untuk kasus basis, tidak ada operasi perkalian (0) untuk kasus rekurens, kompleksitas waktu diukur dari jumlah perkalian (1) ditambah kompleksitas waktu untuk faktorial (n-1)

Kompleksitas waktu 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) = … = n+T(0) = n + 0 Jadi T(n) = n T(n) O(n)

Kasus 2 : Menara hanoi Bagaimana memindahkan seluruh piringan tersebut ke sebuah tiang yang lain (dari A ke B); setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Ada tiang perantara C. Kata pendeta, jika pemindahan berhasil dilakukan, maka DUNIA KIAMAT !!! A B C

Algoritma Procedure Hanoi (input n, A, B, C:integer) Algoritma If n=1 then Write (Pindahkan piringan dari,A,ke,B) Else Hanoi(n-1,A,C,B) Writeln(Pindahkan piringan dari,A,ke,B) Hanoi(n-1,C,B,A) Endif Relasi Rekurens

T(n)=2 n +1 adalah jumlah seluruh perpindahan piringan dari satu tiang ke tiang lainnya. Bila terdapat 64 tumpukan piringan da perpindahan 1 piringan butuh waktu 1 detik, maka waktu yang dibutuhkan : detik detik = detik = kira-kira 600 milyar tahun (???!!!)

Kompleksitas algoritma rekursif Untuk mengetahui kompleksitas bentuk rekursif, maka T(n) harus diubah dalam bentuk yang bukan rekursif Bagaimana mengubah bentuk rekursif ke non rekursif ? Ada dua macam cara untuk menyelesaikan masalah ini, yaitu cara coba-coba dan dengan relasi rekurens

Contoh cara coba coba Cara ini agak sulit dan perlu pengalaman. Dalam beberapa problem Yang sederhana bisa diselesaikan dengan mudah.

Cara Relasi Rekurensi Merubah T(n) x n T(n-1) x n-1 Contoh T(n)=T(n-1)+T(n-2) x n =x n-1 +x n-2 x n -x n-1 -x n-2 =0 Klasifikasi Linier vs non linier Homogen vs non homogen Koefisien konstan vs non konstan

Klasifikasi Linier vs non linier Homogen vs non homogen Koefisien konstan vs non konstan Yang akan dibahas Relasi rekurens Linier dan koefisien konstan

Klasifikasi Relasi Rekurensi : homogen vs non homogen Relasi rekurensi a 0 x n + a 1 x n1 + + a k x nk = f(n) untuk n k untuk suatu fungsi f(n) dan (k + 1) buah bilangan real a 0, a 1, a 2, …, a k dan a k 0. Tergolong homogen jika f(n) = 0 Tergolong tidak homogen jika f(n) 0

Klasifikasi relasi rekurensi Contoh: 1. 2x n + x n1 = 0 2. x n x n4 = n x n = x n2 +x n x n = x n2 +nx n-1 2 Relasi Rekurensi linier homogen dengan koefisien konstan, berderajat 1 Relasi Rekurensi linier nonhomogen dengan koefisien konstan, berderajat 4 Relasi Rekurensi nonlinier homogen dengan koefisien konstan, berderajat 2 Relasi Rekurensi nonlinier homogen dengan koefisien tidak konstan, berderajat 2

Solusi Relasi Rekurensi Linier Homogen Perhatikan relasi rekurensi berikut: x n = x n-1 + x n-2, untuk n > 1 dengan x 1 =1, x 0 = 1 Jika Anda ingin mencari x 1000, maka perlu mencari x 999, x 998, dan seterusnya sampai x 1, x 0 Untuk mencari nilai x n dengan cepat, relasi tersebut perlu diubah ke bentuk eksplisit. Bentuk eksplisit ini merupakan solusi relasi rekurensi tersebut. Cara mencari solusi relasi rekurensi linier homogen dan nonhomogen berbeda

Solusi Relasi Rekurensi Linier Homogen Tahapan: 1. Bentuk: a 0 x n + a 1 x n1 + … + a k x nk = 0, n k diubah ke bentuk persamaan karakteristik: a 0 λ k + a 1 λ k-1 + … + a k-1 λ + a k = 0 2. Cari akar-akar karakteristiknya: r 1, r 2, r 3 …dst berikut multiplisitasnya (m 1, m 2,.. dst) 3. Solusi yang dicari adalah 4. b 1,1, b 1,2 … dicari dengan melakukan substitusi persamaan dengan syarat awal yang diketahui

Contoh Tentukan solusi umum untuk relasi rekurensi x n = x n-1 + x n-2, untuk n > 1 Persamaan karakteristik dari relasi rekurensi: = 0 Didapatkan akar-akar karakteristiknya: 1 = (1+ 5)/2 dengan pengulangan m 1 = 1 dan 2 = (1- 5)/2 dengan pengulangan m 2 = 1 Maka solusi umumnya:

Contoh Tentukan solusi untuk relasi rekurensi x n = x n-1 + x n-2, untuk n > 1 dengan syarat awal x 1 =1 dan x 0 =0 Dari solusi umum: dimasukkan syarat awal x 1 =1 dan x 0 =0. Diperoleh: dan A + B = 0 Dari kedua persamaan ini diperoleh A=1/5 dan B=-1/5 Maka solusi yang dicari adalah

Contoh 9 Tentukan solusi umum untuk relasi rekurensi 4x n = 20x n x n-2 + 4x n-3, untuk n > 3 Persamaan karakteristik dari relasi rekurensi: = 0 (2 -1) (2 -1) ( -4) = 0 Didapatkan akar-akar karakteristiknya: 1 = 1/2 dengan pengulangan m 1 = 2 dan 2 = 4 dengan pengulangan m 2 = 1 Maka solusi umumnya:

Solusi Relasi Rekurensi Linier Nonhomogen Jika t n memenuhi relasi rekurensi linear tak homogen (*) a 0 x n + a 1 x n–1 + … + a k x n–k = f(n) untuk n k dan h n adalah solusi umum untuk relasi rekurensi linear homogen yang bersangkutan (**) a 0 x n + a 1 x n–1 + … + a k x n–k = 0 untuk n k, maka x n = h n + t n adalah solusi umum untuk (*). h n disebut solusi homogen untuk (*) dan t n disebut sebuah solusi partikulir (particular solution) untuk (*)

Solusi Relasi Rekurensi Linier Nonhomogen Solusi partikulir serupa dengan bentuk f(n) Ada dua bentuk f(n): dengan A i, i=1,2,… p,b merupakan konstanta

Contoh Tentukan solusi untuk relasi rekurensi x n = 2 x n-1 + 5, untuk n > 0 dengan syarat awal x 0 =1 Tahap 1 mencari solusi homogen: Persamaan karakteristik: - 2 = 0 Akar karakteristik: = 2 Solusi homogen h n = A 2 n Tahap 2 mencari solusi non homogen

Contoh Dari persamaan x n = 2 x n didapatkan f(n) = 5 Solusi partikulir mengikuti bentuk f(n), dengan p = 0. Maka solusi partikulir t j = Dari hasil substitusi diperoleh persamaan - 2 = 5 Persamaan ini memberikan = -5 Jadi solusi partikulir t n = -5 Solusi umum : x n = h n + t n = A 2 n - 5 Dengan memasukkan syarat awal x 0 = 1 didapatkan A = 6 sehingga solusi yang dicari adalah x n = 6(2 n ) - 5

Master Theorem Jika diketahui suatu relasi rekurens Dimana f(n) O(n d ) dimana d0 maka

Master theorem (contoh) Diketahui suatu relasi rekurens Dari relasi rekurens di atas, diperoleh a = 2, b = 2, d = 0. sehingga a>b d sehingga T(n) O(n log 2 2 ) atau T(n) O(n)

Latihan Diketahui suatu algoritma rekursif dengan relasi rekurens T(n) =2T(n-1)-T(n-2) untuk n>= 0 =4 untuk n=0 =1 untuk n=1 Carilah solusi non rekursifnya