DESAIN ANALISIS DAN ALGORITMAANALISIS ALGORITMA NONREKURSIF DAN REKURSIF

KELOMPOK 2AI GUSTI BAGUS HADI WIDHINUGRAHA(1208605010)NI PUTU SINTYA DEWI(1208605017)LUH GEDE PUTRI SUARDANI(1208605018)I PUTU INDRA MAHENDRA PRIYADI(1208605020)

PROGRAM STUDI TEKNIK INFORMATIKAJURUSAN ILMU KOMPUTERFAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS UDAYANA2013BAB IPENDAHULUAN

1.1 LATAR BELAKANGUntuk memenuhi tugas kelompok mata kuliah Desain Analisis Algoritma mengenai analisis algoritma Rekursif dan Non- Rekursif 1.2 RUMUSAN MASALAH1. Bagaimana menganalisis algoritma Rekursif ?2. Bagaimana menganalisis algoritma Non-Rekursif ?3. Bagaimana cara mencari kompleksitas waktu pada algoritma Rekursif dan Non- Rekursif ?4. Bagaimana cara menentukan notasi asimptotik dari algoritma Rekursif dan Non- Rekursif ?1.3 TUJUANAdapun tujuan dari yang membahasa tentang analisis algoritma Rekursif dan Non- Rekursif adalah :1. Untuk mengetahui gambaran yang jelas tentang analisis algoritma Rekursif dan Non- Rekursif.2. Untuk mengetahui keterkaitan antara analisis asimptotik untuk kompleksitas waktu dengan algoritma Rekursif dan Non- Rekursif .1.4 MANFAATMembahas tentang algoritma Rekursif dan Non- Rekursif adalah :1. Lebih mengetahui tentang algoritma Rekursif dan Non- Rekursif.2. Dapat menganalisa kompleksitas waktu dari algoritma Rekursif dan Non- Rekursif3. Mengetahui kaitan kompleksitas waktu dari algoritma Rekursif dan Non- Rekursif dengan notasi asimptotik

BAB IILANDASAN TEORI

2.1 MANIPULASI PENJUMLAHAN PENTING

2.2 ALGORITMA REKURSIFAlgoritma rekursif adalah sebuah fungsi, prosedur, metode yang memanggil dirinya sendiri dan bentuk dimana pemangilan subrutin terdapat dalam body subrutin, seperti halnya struktur pengulangan seperti for..loop, while.do, repeatuntil dan lain-lain yang memiliki kondisi awal dan akhir pengeksekusian,algoritma rekursif juga memiliki kondisi yaitu base case dan end case, Base case menunjukan batas bawah berapa kali algoritma rekursif akan memanggil dirinya sendiri.serta end case adalah kondisi berhentinya atau jumlah maksimal inputan yang akan diproses.Selain syarat kondisi basis diatas subrutin call yang melibatkan parameter yang nilainya menuju kondisi terminal (recurrence) harus terpenuhi. Efisiensi Waktu Algoritma RecursiveLangkah-langkah dalam analisis matematis dari algoritma rekursif:1. Tentukan parameter n yang menunjukkan ukuran input2. Tentukan operasi dasar algoritma (loop terdalam)3. Tentukan apakah untuk ukuran input yang sama banyaknya eksekusi basic operation sama atau berbeda.4. Tentukan relasi rekurens, dengan kondisi awal yang tepat untuk berapa kali algoritma akan dijalankan5. Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n))6. Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)), (g(n)), (g(n)).

2.3 ALGORITMA NON REKURSIFEfisiensi Waktu Algoritma Nonrecursive1. Tentukan parameter n yang menunjukkan ukuran input2. Tentukan operasi dasar algoritma (loop terdalam)3. Tentukan apakah untuk ukuran input yang sama banyaknya eksekusi basic operation bisa berbeda.4. Tentukan rumus sigma yang menunjukkan berapa kali operasi dasar dijalankan C(n)5. Selesaikan rumus sigma untuk menghitung banyaknya operasi dasar dijalankan6. Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)), (g(n)), (g(n)).

BAB III PEMBAHASAN SOAL

3.1 Algoritma Rekursifa. menghitung faktorialpembahasan :Function Faktorial (input n : integer) integer{menghasilkan nilai n!, n tidak negatif}Algoritma :If n=0 thenReturn 1ElseReturn ( n*faktorial (n-1) )Endif

analisis : Ukuran input = n Kompleksitas waktu:Untuk kasus basis, tidak ada operasi perkalian T(0) = 0 (kondisi awal) 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)

b. 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.

pembahasan :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

T(n)=2n+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 2641 detik = 10.446.744.073.709.551.615 detik= kira-kira 600 milyar tahun

3.2 Algoritma Non-Rekursif a. Perkalian Matrikspembahasan :Algoritma PerkalianMatrik(A[0n-1,0n-1], B[0n-1,0n-1])//mengalikan 2 matriks persegi berordo n //input: 2 matriks A dan B//output: Matriks C = ABAlgoritma :for i 0 to n - 1 do for j 0 to n 1 do C[i,j] 0,0for k 0 to n 1 do C[i,j] C[i,j] + A[i,k] * B[k,j]return C

analisis : Ukuran input = matriks ordo n Loop terdalam = perkalian dan penambahan calon operasi dasar Perkalian dan pertambahan dilakukan tepat sekali dalam setiap perulangan, sehingga kita tidak harus memilih antara dua operasi Jumlah dari total perkalian

Perkiraan waktu berjalannya algoritma pada mesin tertentu

Perkiraan yang lebih akurat (termasuk penambahan)

cm:waktu satu perkalianca:waktu satu tambahan

b. Max Elementpembahasan :Berikut adalah algoritma untuk mencari elemen terbesar dari sekumpulan n bilangan:ALGORITHM MaxElement (A[0..n-1])//Input: Array A[0..n-1] dari bilangan real//Output: Nilai dari elemen terbesar pada array Aalgoritma :max A[0]for i 1 to n-1 doif A[i] > maxmax A[i]return max

analisis : Ukuran input dari algoritma ini adalah jumlah elemen pada array, yaitu n. Operasi dasar yang paling banyak dieksekusi ada dalam loop for. Ada 2 operasi dalam loop: perbandingan A[i] >max dan assignment maxA[i]. Karena operasi perbandingan dieksekusi pada tiap iterasi (dan operasi assignment tidak), maka perbandingan dijadikan sebagai operasi dasar. Jumlah perbandingan pun tetap sama untuk semua variasi input array berukuran n, shingga tidak perlu menghitung worst case, best case, dan average misalnya C(n) adalah jumlah eksekusi operasi perbandingan. dalam tiap loop, terjadi 1 kali perbandingan. ini dieksekusi sebanyak (n-1) kali. sehingga C(n) berjumlah :

BAB IVKESIMPULANRekursif adalah sebuah teknik pemecahan masalah yang efisien untuk dipakai dalam definisi dan algoritma, yang mana dalam pemakaiannya hanya melakukan sekali pemanggilan. Tetapi akan menjadi sangat tidak efisien jika memanggil dua atau lebih pemanggilan karena akan diperoleh kompleksitas waktu yang eksponensial.

LAMPIRANPERTANYAAN DAN JAWABAN1. Penanya: Ni Putu Meri Sriyati (1208605026/Kelompok 6A)

Pertanyaan: Mengapa dalam T(n) O(n) memakai notasi O? Dan mengapa dalam manipulasi penjumlahan penting terdapat pernyataan?Jawaban: a. Pembuktian T(n) O(n)

Misalkan diberikan limit :

Sehingga

Jadi benar bahwa T(n) O(n)

b. PembuktianMisalkan diberikan limit:

Jika hasil:0 maka OoG TA(n) < OoG TB(n) notasi : OC maka OoG TA(n) = OoG TB(n) notasi : maka OoG TA(n) > OoG TB(n) notasi :

Sehingga

Jadi benar bahwa

2. Penanya: Eka Ayuningsih (1208605001/Kelompok 7A)Pertanyaan: Buktikan bahwac?Jawaban:

Pembuktian

Jadi benar bahwa

3. Penanya: Tutde Suputrawan (1208605007/Kelompok 5A)Pertanyaan : Apa maksud dari terminal dan body fungsi?Jawaban: Terminal adalah kondisi awal dari suatu fungsi rekursif, dimana kondisi terminal adalah tempat perhentian fungsi rekursif, sedangkan body fungsi mengandung fungsi rekursif . Pemanggilan fungsi yang berulang terdapat dalam bodi fungsi.Contoh:

If n=0 thenReturn 1ElseReturn ( n*faktorial (n-1) )Endif

Yang menjadi terminal adalah if (n=0) then return 1,Yang menjadi bodi fungsi adalah return (n*factorial(n-1))

DAFTAR PUSTAKA