M&M's Candy

Selasa, 15 November 2011

Relasi Rekurensi



·         Relasi rekurensi adalah sebuah formula rekursif dimana setiap bagian dari suatu barisan dapat ditentukan menggunakan satu atau lebih bagian sebelumnya
·         Jika adalah banyak cara untuk menjalankan prosedur dengan  objek, untuk , maka relasi rekurensi adalah sebuah persamaan yang menyatakan sebagai sebuah fungsi dari  untuk  

Contoh:          
o  
o     dengan  konstanta
o    dengan  sembarang fungsi dari
o  
o  

Nilai  tidak akan pernah dapat dicari jika suatu nilai awal tidak diberikan. Jika suatu relasi rekurensi melibatkan buah , maka  buah nilai awal harus diketahui. Sebagai contoh, pada relasi rekurensi , tidak cukup hanya diketahui sebuah nilai , akan tetapi butuh sebuah nilai lagi yaitu misal . Dengan demikian   dan seterusnya dapat diketahui.

Jika model relasi rekurensi dapat ditemukan untuk menyatakan sebuah permasalahan ”counting” serta kondisi nilai awal diberikan, maka biasanya masalah tersebut dapat diselesaikan untuk jumlah n yang tidak terlalu besar, misalkan . Jika masalah terlalu besar, maka dibutuhkan alat bantu seperti kalkulator atau komputer.

Untuk beberapa bentuk relasi rekurensi tertentu, formula eksplisit untuk  dapat ditentukan. Akan tetapi biasanya akan lebih mudah menemukan nilai yang diinginkan secara rekursif ketimbang menggunakan formula eksplisit.
Contoh 1: (Arrangements)
Tentukan relasi rekurensi untuk menentukan banyaknya cara menyusun n buah objek yang berbeda dalam suatu barisan. Tentukan banyaknya cara untuk menyusun 8 buah objek.
Jawab:
Misalkan  menyatakan banyaknya cara menyusun n objek yang berbeda, maka ada n cara meletakan n objek pada urutan pertama di barisan. Dengan cara yang sama untuk , maka ada n-1 cara. Oleh karena itu formula relasi rekurensi dapat dinyatakan sebagai
                       
Jadi  
Contoh 2: (Climbing Stairs)
Sebuah rumah memiliki tangga dengan n buah anak tangga untuk dinaiki. Setiap langkah dapat melewati satu atau dua anak tangga. Tentukan relasi rekurensi untuk , banyaknya cara berbeda sesorang dapat menaiki n buah anak tangga.

Jawab:
            ,
, yaitu 1,1 atau 2
, yaitu 1,1,1 atau 1,2 atau 2,1
, yaitu 1,1,1,1 atau 1,2,1 atau 1,1,2 atau 2,2 atau 2,1,1

Apakah dapat ditentukan cara yang sistematik dalam mengenumerasi cara untuk menaiki empat anak tangga dimana banyak cara menaiki tiga atau kurang anak tangga dilibatkan?
Sangat jelas terlihat bahwa ketika sebuah langkah dijalankan, maka akan ada tiga atau kurang anak tangga lagi yang tersisa untuk dinaiki. Dengan demikian setelah langkah pertama menaiki sebuah anak tangga, akan ada cara untuk meneruskan menaiki tiga anak tangga berikutnya. Jika langkah pertama menaiki dua anak tangga, maka akan ada  cara untuk meneruskan menaiki dua anak tangga yang tersisa. Dengan demikian .
Secara umum dapat dikatakan bahwa  à Relasi Fibonacci. Jika , maka 1, 1, 2, 3, 5, 8, 13,21, 34, 55, 89, ... disebut bilangan Fibonacci  
Contoh 3: (Dividing the Plane)
Misalkan akan digambarkan n buah garis pada selembar kertas demikian sehingga setiap pasang garis berpotongan (tetapi tidak boleh ada tiga garis berpotongan pada titik yang sama). Berapa daerah yang dapat dibuat jika n buah garis membagi bidang datar dengan cara tersebut?
Jawab:
Seperti sebelumnya, akan dicoba menggunakan kasus n kecil.
Dengan satu garis, kertas tadi dapat dibagi menjadi dua daerah, berarti
Dengan dua garis, kertas tadi dapat dibagi menjadi empat daerah, berarti .
Pada gambar (b) terlihat menggunakan tiga garis dapat dibuat tujuh daerah, berarti . Pertanyaannya adalah apakah dengan menggunakan tiga garis selalu diperoleh tujuh daerah?
Jawabnya adalah, karena garis ketiga harus memotong kedua garis yang lain dan tidak boleh memotong pada titik yang sama, berarti garis ketiga tadi akan selalu membagi tiga daerah yang terbentuk dari dua garis sebelumnya. Oleh karena itu dapat dipastikan bahwa garis ketiga akan selalu membentuk tiga daerah baru, berarti .
Dengan cara yang sama, garis ke empat akan membentuk empat daerah baru setelah memotong tiga garis tidak pada satu titik yang sama. Dapat dilihat pada gambar (c). Sehingga diperoleh .
Secara umum diperoleh relasi rekurensi .


Contoh 4: (Tower of Hanoi)
Tower of Hanoi adalah sebuah pemainan yang terdiri dari n buah lingkaran dengan berbagai ukuran dan terdapat tiga buah pasak/tiang tempat meletakan lingkaran-lingkaran tadi. Pada awalnya seluruh lingkaran diletakan pada salah satu pasak dengan lingkaran terbesar berada pada posisi terbawah baru diikuti oleh lingkaran lain yang lebih kecil secara terurut. Lingkaran-lingkaran pada pasak pertama akan dipindahkan ke pasak ketiga dengan susunan yang sama. Persoalannya adalah ketika lingkaran tadi akan dipindahkan, maka susunan lingkaran harus selalu terurut dari besar ke kecil (dari bawah ke atas).
Tentukan relasi rekurensi untuk , yaitu banyak langkah minimum yang dibutuhkan untuk memindahkan n buah lingkaran. Berapa banyak langkah yang dibutuhkan untuk bermain dengan 6 buah lingkaran?

Jawab:
Ke enam lingkaran yang ada pada pasak pertama akan dipindahkan seluruhnya pada pasak ketiga dengan aturan mula-mula mainkan ”permainan Tower of Hanoi untuk lima lingkaran terkecil” dimana lima lingkaran terkecil dipindahkan dari pasak pertama ke pasak kedua. Kemudian lingkaran keenam dipindahkan dari pasak pertama ke pasak ketiga. Permainan yang sama dilakukan ketika akan memindahkan lima linkaran terkecil yang ada pada pasak kedua ke pasak ketiga. Jadi ketika akan memindahkan n buah lingkaran dari pasak pertama ke pasak ketiga, mula-mula pindahkan (n-1) lingkaran terkecil dari pasak pertama kepasak kedua, kemudian memindahkan lingkaran terbesar (ke-n) dari pasak pertama ke pasak ketiga, baru (n-1) lingkaran terkecil yang ada pada pasak kedua dipindahkan seluruhnya ke pasak ketiga.
Jika  adalah banyaknya langkah yang dibutuhkan untuk memindahkan lingkaran dari satu pasak ke pasak yang lai, maka relasi rekurensi yang terbentuk adalah . Dengan kondisi awal , maka     dan
Jadi untuk memindahkan enam buah lingkaran dibutuhkan minimal 63 langkah.
Formula eksplisit untuk relasi rekurensi ini adalah  à akan dibuktikan kemudian

Contoh 5: (Money Growing in a Savings Account)
Sebuah Bank membayar 8 persen bunga setiap tahun untuk uang yang tersimpan disetiap account. Tentukan relasi rekurensi untuk jumlah uang yang diterima setelah n tahun jika strategi investasinya sebagai berikut:
a.         Investasi $ 1000 dan menyimpannya di Bank selama n tahun
b.         Investasi $ 100 pada setiap akhir tahun

Jawab:
Jika sebuah account berisi $ x pada awal tahun, maka pada akhir tahun (pada awal tahun berikutnya) akan menjadi $ x ditambah bunga dari $ x, dengan asumsi tidak ada uang yang ditambahkan ataupun diambil dari account tersebut selama setahun.
a.       Relasi rekurensinya adalah   dengan kondisi awal
b.      Relasi rekurensinya adalah  dengan kondisi awal

Contoh 6: (Making Change)
Tentukan relasi rekurensi untuk banyak cara membagikan permen karet (seharga 1 sen) atau permen (seharga 10 sen) atau donat (seharga 20 sen) dalam beberapa hari yang berturutan sampai makanan seharga n sen telah diberikan.

Jawab:
Persoalan ini mirip dengan stair climbing problem. Jika pada hari pertama dibagikan permen karet seharga 1 sen, maka akan tersisa makanan seharga (n-1) sen pada hari berikutnya. Jika pada hari pertama dibagikan permen seharga 10 sen, maka akan tersisa makanan seharga (n-10) sen pada hari berikutnya. Dan jika pada hari pertama dibagikan donat seharga 20 sen, maka akan tersisa makanan seharga (n-20) sen pada hari berikutnya. Jadi relasi rekurensi yang terjadi adalah  dengan  (suatu cara untuk tidak memberikan satupun, atau nol buah untuk setiap jenis makanan), dan secara implisit dapat dikatakan  untuk k < 0

Contoh 7: (Selection Without Repetition)
Misal menyatakan banyaknya cara untuk memilih sebuah sub himpunan dari k objek dari himpunan n buah objek yang berbeda. Tentukan relasi rekurensi untuk
Jawab:
Misalkan  berarti . Persoalan ini dpecah menjadi dua bagian tergantung apakah objek pertama digunakan atau tidak. Ada  k-subhimpunan yang tidak menggunakan objek pertama, dan ada  k-subhimpunan yang menggunakan objek pertama. Maka akan diperoleh . Bentuk ini adalah formula segitiga pascal dengan kondisi awal  untuk semua  (dan )

Contoh 8: (Distribution)
Tentukan relasi rekurensi dari cara mendistribusikan n buah bola identik kedalam k kotak yang berbeda dimana setiap kotak akan berisi antara 2 dan 4 bola. Ulangi masalah yang sama untuk bola dengan 3 warna

Jawab:
Jika terdapat 2 bola dalam kotak pertama, maka akan ada  cara untuk meletakan n-2 sisa bola identik kedalam k-1 kotak. Teruskan pembahasan ini akan diperoleh  dengan kondisi awal  dan
Untuk bola dengan 3 warna, terdapat  = 6 cara untuk meletakan sebuah subhimpunan dari dua bola pada kotak pertama dengan 3 tipe warna dengan pengulangan. Dengan cara yang sama terdapat  = 10 cara untuk meletakan 3 bola dengan 3 tipe warna dan  = 15 cara untuk meletakan 4 bola dengan 3 tipe warna. Maka  dengan kondisi awal  dan
Contoh 9: (Placing Parentheses)
Tentukan relasi rekurensi untuk , banyaknya cara untuk meletakan tanda kurung pada perkalian n bilangan  pada kalkulator
Jawab:
Terdapat satu cara untuk perkalian ; berarti . Ada 2 cara untuk perkalian  , yaitu  dan , berarti . Tidak begitu jelas untuk kondisi  dan , akan tetapi agar bentuk relasi rekurensi menjadi sederhana dapat ditetapkan  dan . Untuk menentukan relasi rekurensi  dapat dilihat pada bentuk berikut , dimana i bernilai dari 0 sampai (n-1). Banyaknya cara untuk memberi tanda kurung dua subproblem tersebut adalah  dan  dan terdapat  cara untuk memberi tanda kurung pada kedua subproblem tersebut ()

Tidak ada komentar:

Posting Komentar