suwarno matematika diskrit bab 4a 11

RELASI BERULANG

Bagian awal dari bab ini menyajikan sebuah pendahuluan tentang relasi berulang. Relasi berulang sangat berguna dalam masalah penghitungan tertentu. Relasi berulang mengaitkan unsur ke-n dari sebuah barisan dengan pendahulunya. Karena relasi berulang berkaitan erat dengan algoritma rekursif, relasi berulang muncul secara alami dalam analisis algoritma rekursif.

4.1 PENDAHULUAN

Untuk mengawali bab ini, sebagai ilustrasi perhatikan instruksi untuk membentuk sebuah barisan berikut:

1. Awali dengan 5.2. Jika diberikan sembarang suku, tambahkan 3 untuk mendapatkan

suku berikutnya.Jika kita buat daftar dari suku-suku barisan itu, kita dapatkan

5, 8, 11, 14, 17, … (4.1)

Suku pertamanya adalah 5 karena adanya instruksi 1. Suku keduanya adalah 8 karena instruksi 2 menyatakan tambahkan 3 pada 5 untuk mendapatkan suku berikutnya, 8. Suku ketiga adalah 11 karena instruksi 2 menyatakan tambahkan 3 pada 8 untuk mendapatkan suku berikutnya, 11. Dengan mengikuti instruksi 1 dan 2, kita bisa menghitung sembarang suku dalam barisan tersebut. Instruksi 1 dan 2 tidak memberikan sebuah rumus eksplisit untuk suku ke-n dari barisan tersebut yang menyediakan sebuah rumus yang kita bisa “pasangkan n ke dalam” untuk memperoleh nilai suku ke-n, tetapi dengan menghitung suku per suku yang akhirnya baru kita temukan sembarang suku dari barisan tersebut.

Jika kita nyatakan barisan (4.1) sebagai a1, a2, …, kita bisa menyatakan ulang instruksi 1 sebagai

a1 = 5 (4.2)

dan kita bisa menyatakan ulang instruksi 2 sebagai

an = an-1 + 3, n2 (4.3)

Dengan mengambil n = 2 dalam (4.3), kita dapatkan

Matematika Diskrit Suwarno 17

a2 = a1 + 3. Menurut (4.2), a1 = 5; sehingga

a2 = a1 + 3 = 5 + 3 = 8.

Dengan mengambil n=3 dalam (4.3), kita dapatkan

a3 = a2 + 3. Karena a2 = 8, maka

a3 = a2 + 3 = 8 + 3 = 11.

Dengan menggunakan (4.2) dan (4.3), kita bisa menghitung sembarang suku dalam barisan itu seperti halnya kita mel;akukan instruksi 1 dan 2. Kita lihat bahwa (4.2) dan (4.3) ekuivalen dengan instruksi 1 dan 2.

Persamaan (4.3) memberikan gambaran sebuah contoh dari sebuah relasi berulang. Relasi berulang mendefinisikan sebuah barisan dengan memberikan nilai ke-n dalam suku-suku dari pendahulunya. Pada (4.3), nilai ke-n diberikan dalam nilai yang mendahuluinya. Untuk keperluan sebuah relasi berulang seperti (4.3) untuk mendefinisikan sebuah barisan , nilai “awal” seperti pada (4.2) harus diberikan. Nilai-nilai awal ini disebut syarat awal. Definisi formalnya adalah sebagai berikut.

Definisi 4.1Sebuah relasi berulang untuk barisan a0, a1, …, merupakan sebuah persamaan yang mengkaitkan an dengan pendahulunya a0, a1, …, an-1. Syarat awal untuk barisan a0, a1, … adalah nilai-nilai yang diberikan secara eksplisit untuk sebuah bilangan terhingga dari suku-suku barisan tersebut.

Kita telah melihat bahwa mungkin saja untuk mendefinisikan sebuah barisan dengan sebuah relasi berulang bersama-sama dengan syarat awal tertentu. Berikut ini kita perhatikan beberapa contoh relasi berulang. Contoh 4.1

Barisan Fibonacci didefinisikan oleh relasi berulang

dan syarat awal

18 Suwarno Matematika Diskrit

Contoh 4.2

Seseorang menginvestasikan Rp 1.000.000,00 pada bunga majemuk tahunan sebesar 12%. Jika An menyatakan jumlah investasi pada akhir n tahun, carilah sebuah relasi berulang dan syarat awal yang mendefinisikan barisan {An}.

Pada akhir n-1 tahun, jumlah investasi adalah An-1. Setelah satu tahun lebih, kita akan mempunyai jumlah An-1 ditambah bunga. Sehingga

An=An-1 + (0.12)An-1=(1.12)An-1, n1 (4.4)

Untuk menerapkan relasi berulang untuk n=1, kita perlu mengetahui nilai dari A0. Karena A0 merupakan jumlah awal, kita mempunyai syarat awal

A0=1.000.000 (4.5).

Syarat awal (4.5) dan relasi berulang (4.4) memungkinkan kita untuk menghitung nilai An untuk n sembarang. Sebagai contoh,

A3=(1.12)A2=(1.12)(1.12)A1

=(1.12)(1.12) (1.12)A0=(1.12)3(1.000.000)=1.404.928. (4.6).

Sehingga, pada akhir tahun ketiga, jumlahnya adalah Rp 1.404.928,-

Perhitungan (4.6) bisa dilakukan untuk sebuah nilai n untuk memperoleh

An=(1.12)An-1

.

.

=(1.12)n(1.000.000).

Kita lihat bahwa kadang-kadang sebuah rumus eksplisit bisa diturunkan dari sebuah relasi berulang dan syarat awal. Menemukan rumus-rumus eksplisit dari relasi berulang merupakan topik yang akan dibahas tersendiri.

Meskipun mudah untuk mendapatkan sebuah rumus eksplisit dari relasi berulang dan syarat awal untuk barisan pada contoh 4.2, namun untuk mendapatkan rumus eksplisit pada barisan Fibonacci tidak begitu saja dapat kita peroleh. Pada topik yang akan datang kita akan bahas sebuah metode yang dapat menemukan rumus eksplisit untuk barisan Fibonacci.

Relasi berulang, algoritma rekursif, dan induksi matematika memang saling berkaitan. Pada ketiga metode ini, kejadian sebelumnya dari suatu kasus saat ini diasumsikan diketahui. Relasi berulang menggunakan nilai sebelumnya dalam suatu barisan untuk menghitung nilai saat ini. Algoritma rekursif menggunakan kejadian yang lebih kecil dari masukan saat ini untuk memproses masukan saat ini. Langkah induktif dalam sebuah pembuktian dengan induksi matematika mengasumsikan kebenaran dari kejadian


sebelumnya dari suatu pernyataan untuk membuktikan kebenaran pernyataan saat ini.

Relasi berulang yang mendefinisikan sebuah barisan bisa langsung dikonversikan ke sebuah algoritma untuk menghitung barisan tersebut. Sebagai contoh, Algoritma 4.1, yang diturunkan dari relasi berulang (4.4) dan syarat awal (4.5), menghitung barisan pada Contoh 4.2.

Algoritma 4.1 Bunga Majemuk

Algoritma rekursif ini menghitung jumlah uang pada akhir n tahun yang mengasumsikan jumlah awalnya adalah Rp 1.000.000,- dan tingkat bunga majemuk sebesar 12 persen per tahun.

Masukan: n, banyaknya tahun

Keluaran: Jumlah uang pada akhir n tahun

1. procedure bunga_majemuk(n)

2. if n=0 then

3. return(1000000)

4. return(1.12*bunga_majemuk(n-1)

5. end bunga_majemuk

Algoritma 4.1 merupakan translasi langsung dari persamaan (4.4) dan (4.5) yang mendefinisikan barisan A0, A1, …. Baris 2 dan 3 berhubungan denga syarat awal (4.5) dan baris 4 berhubungan dengan relasi berulang 4.4.

Contoh 4.3

Misalkan Sn menyatakan banyaknya subhimpunan dari himpunan n-unsur. Karena dari sebuah himpunan (n-1)-unsur ke himpunan n-unsur melipatgandakan banyaknya subhimpunan, kita dapatkan relasi berulang

Sn=2Sn-1.

Dengan syarat awalnya ialah S0=1.

Salah satu alasan utama mengapa menggunakan relasi berulang adalah bahwa kadang-kadang lebih mudah untuk menentukan suku ke-n dari sebuah barisan dengan menggunakan suku-suku pendahulunya daripada mencari sebuah rumus eksplisit untuk suku ke-n dalam bentuk n.


Contoh 4.4 Menara Hanoi

Menara Hanoi adalah teka-teki yang terdiri dari tiga tonggak yang berdiri di atas papan dan n cakram berbagai ukuran dengan lubang di tengahnya seperti terlihat pada Gambar 4.1. Diasumsikan bahwa jika sebuah cakram berada di tonggak, maka hanya sebuah cakram dengan ukuran lebih kecil bisa diletakkan di atas cakram sebelumnya tersebut. Diberikan semua cakram yang menancap pada satu tonggak seperti pada Gambar 4.1, masalahnya adalah memindahkan cakram-cakram itu ke tonggak lain dengan memindahkan cakram satu per satu.

Gambar 4.1 Menara Hanoi

Kita akan membahas solusinya dan kemudian menemukan relasi berulang dan syarat awal untuk barisan c1, c2, …, dengan cn menyatakan banyaknya gerakan yang diambil dalam solusi kita untuk memecahkan teka-teki dengan n cakram. Kemudian kita akan menunjukkan bahwa solusi kita adalah optimal; yakni, kita akan menunjukkan bahwa tidak ada solusi lain yang menggunakan gerakan yang lebih sedikit.

Kita awali dengan membahas algoritma rekursif. Jika hanya terdapat satu cakram, kita dengan mudah memindahkan cakram ke tonggak yang kita inginkan. Jika kita mempunyai n>1 cakram pada tonggak 1 seperti pada Gambar 4.1, kita mulai dengan menjalankan secara berulang algoritma kita untuk memindahkan n-1 cakram uncak ke tonggak 2 (lihat Gambar 4.2). Selama pemindahan ini, cakram dasar pada tonggak 1 tetap tinggal. Selanjutnya, kita pindahkan cakram yang tersisa pada tonggak 1 ke tonggak 3. Akhirnya, kita jalankan lagi secara berulang algoritma kita untuk memindahkan n-1 cakram pada tonggak 2 ke tonggak 3. Kita telah berhasil memindahkan n cakram dari tonggak 1 ke tonggak 3.

Jika n>1, kita selesaikan masalah (n-1) cakram dua kali dan secara eksplisit kita pindahkan satu cakram. Oleh karena itu,

cn=2cn-1 + 1, n>1.

Syarat awalnya adalah c1=1.


Pada subbab 4.2, kita akan menunjukkan bahwa cn=2n-1.

Selanjutnya kita tunjukkan bahwa solusi kita optimal. Kita misalkan dn adalah banyaknya pemindahan yang diperlukan oleh sebuah solusi yang optimal. Kita gunakan induksi matematika untuk menunjukkan bahwa

cn=dn, n>1. (4.7)

LANGKAH DASAR (n=1). Menurut pemeriksaan

c1=1=d1

sehingga persamaan (4.7) benar untuk n=1.

LANGKAH INDUKTIF. Asumsikan bahwa persamaan (4.7) benar untuk n-1. Pandang suatu saat dalam solusi optimal untuk masalah n-cakram jika cakram terbesar dipindahkan untuk pertama kali. Cakram terbesar harus berada pada tonggak sendirian (sehingga bisa dipindahkan dari tonggak tersebut) dan tonggak lain harus kosong (sehingga tonggak ini bisa menerima cakram terbesar). Maka n-1 cakram yang lebih kecil harus ditancapkan di tonggak ketiga (lihat Gambar 4.2). Dengan kata lain, n-1 masalah cakram harus diselesaikan, yang memerlukan paling sedikit dn-1 pemindahan. Selanjutnya cakram terbesar dipindahkan, yang memerlukan satu pemindahan tambahan. Akhirnya, pda suatu saat n-1 cakram dipindahkan di atas cakram terbesar, yang memerlukan dn-1 pemindahan tambahan. Hal ini mengakibatkan

dn2dn-1 + 1.

Berdasarkan asumsi induktif , cn-1=dn-1, sehingga

dn2dn-1 + 1=2cn-1 + 1. (4.8)

Gambar 4.2 Keadaan Menara Hanoi setelah pemindahan berulang n-1 ckram dari tonggak 1 ke tonggak 2


Persamaan terakhir mengikuti relasi berulang untuk barisan c1, c2, …. Menurut definisi, tidak ada solusi yang memerlukan pemindahan lebih sedikit daripada solusi optimal, sehingga

cndn (4.9)

Kombinasi pertidaksamaan (4.8) dan (4.9) tidak lain adalah

cn=dn.

Teka-teki Menara Hanoi ditemukan oleh matematikawan Perancis yang bernama Eduard Lucas pada akhir abad kesembilan belas. Lucas adalah orang pertama yang menyebut barisan 1, 2, 3, 5, 8, … sebagai barisan Fibonacci.

Contoh 4.5 Jaring Laba-laba dalam Ilmu Ekonomi

Kita asumsikan sebuah model ekonomi di mana penawaran dan permintaan digambarkan oleh persamaan linear (lihat Gambar 4.3). Secara khusus, permintaan diberikan oleh persamaan

p=a-bq,

dimana p adalah harga, q adalah jumlah (kuantitas), dan a serta b merupakan parameter positif. Gagasannya adalah bahwa jika harga naik, permintaan konsumen akan suatu produk berkurang. Penawaran diberikan oleh persamaan

p=kq

dimana p adalah harga, q kuantitas, dan k adalah parameter positif. Gagasannya adalah bahwa jika harga naik, produsen ingin menyediakan kuantitas lebih besar.

Gambar 4.3. Model Ekonomi


Harga

Kuantitas

Permintaan

Penawaran

Lebih jauh kita asumsikan terdapat kelambatan waktu ketika penawaran bereaksi terhadap perubahan. Sebagai contoh, perlu waktu untuk membuat barang dan menumbuhkan tanaman. Kita nyatakan selang waktu diskrit seperti n=0, 1, 2, …. Kita asumsikan bahwa permintaan diberikan oleh persamaan

pn=a-bqn;

yakni, pada saat n, kuantitas qn dari produk akan dijual dengan harga pn. Kita asumsikan bahwa penawaran diberikan oleh persamaan

pn=kqn+1; (4.10)

yakni, satu satuan waktu diperlukan oleh produsen untuk menyesuaikan kuantitas qn+1, pada saat n+1, untuk harga pn, pada waktu n sebelumnya.

Jika kita selesaikan persamaan (4.10) untuk qn+1 dan mensubtitusikannya ke dalam persamaan permintaan untuk waktu n+1,

pn+1 = a – bqn+1,

kita dapatkan relasi berulang

untuk harga. Kita akan menyelesaikan relasi berulang ini pada subbab 4.2.

Perubahan harga berdasrkan waktu bisa dilihat dengan grafik. Jika harga awal adalah p0, produsen akan menyediakan kuantitas q1, pada waktu n=1. Kita melokasikan kuantitas ini dengan bergerak secara horizontal ke kurva penawaran (lihat Gambar 4.4). Akan tetapi, kekuatan pasar menekan harga turun ke p1, seperti bisa kita lihat dengan bergerak secara vertikal ke kurva permintaan. Pada harga p1, produsen akan menginginkan untuk menyediakan kuantitas q2 pada waktu n=2, seperti biasa kita lihat dengan bergerak horizontal ke kurva penawaran. Pada saat ini kekuatan pasar mendorong harga naik menjadi p2, seperti biasa kita lihat dengan bergerak vertikal ke kurva permintaan.

Gambar 4.4. Jaring laba-laba dengan stabilisasi harga


Dengan meneruskan proses ini, kita dapatkan “jaring laba-laba” yangdiperlihatkan oleh Gambar 4.5.

Gambar 4.5. Jaring laba-laba dengan fluktuasi harga

Untuk fungsi penawaran dan permintaan pada Gambar 4.4, harga mendekatinya dengan interseksi (perpotongan) dari kurva penawaran dan permintaan. Akan tetapi, kasus ini tidak selalu terjadi. Sebagai contoh, pada Gambar 4.5, harga berfluktuasi antara p0 dan p1, sementara itu pada Gambar 4.6, harga berputar-putar naik dan naik. Perilaku ini ditentukan oleh kemiringan dari garis penawaran dan permintaan. Untuk menghasilkan perilaku yang berfluktuasi pada Gambar 4.5, jumlah sudut dan haruslah 180o. Kemiringan dari kurva penawaran dan permintaan masing-masing adalah tan dan tan ; sehingga pada Gambar 4.5, kita mempunyai

k = tan = - tan =b.

Kita telah memperlihatkan bahwa harga berfluktuasi antara dua nilai jika k=b.

Gambar 4.6 Jaring laba-laba dengan stabilitas harga

Analisis yang serupa menunjukkan bahwa harga cenderung pada yang diberikan oleh perpotongan kurva penawaran dan permintaan (lihat Gambar 4.4) jika b<k dan kasus perputaran harga yang naik (Gambar 4.6) terjadi jika


b>k. Pada subbab 4.2 kita bahas perilaku dari harga sepanjang waktu dengan menganalisis sebuah rumus skplisit untuk harga pn.

Contoh 4.6 Fungsi Ackermann

Fungsi Ackermann bisa didefinisikan dengan relasi berulang sebagai berikut:

A(m, 0) = A(m-1, 1), m = 1, 2, …, (4.11)

A(m, n) = A(m-1, A(m, n-1)), m = 1, 2, …,

n = 1, 2, …, (4.12)

Dengan syarat awal

A(0, n) = n+1, n= 0, 1, …. (4.13)

Fungsi Ackermann merupakan bentuk teoritis yang amat penting karena kecepatan pertumbuhannya. Fungsi-fungsi yang berkaitan dengan fungsi Ackermann muncul dalam kompleksitas waktu dari algoritma tertentu seperti misalnya waktu untuk mengeksekusi gabungan atau mencari algoritma.

Perhitungan

A(1, 1) = A(0, A(1, 0)) dengan (4.12)

= A(0, A(0, 1)) dengan (4.11)

= A(0, 2) dengan (4.13)

= 3 dengan (4.13)

menggambarkan penggunaan persamaan (4.11) – (4.13).

Latihan 4.1

Pada latihan 1-3, carilah sebuah relasi berulang dan syarat awal yang membentuk sebuah barisan yang berawal dengan suku-suku yang diberikan.

1. 3, 7, 11, 15, … 2. 3, 6, 9, 15, 24, 39, …

3. 1, 1, 2, 4, 16, 128, 4096, …

Pada latihan 4-8, asumsikan bahwa seseorang menginvestasikan Rp 2.000.000,- pada bunga majemuk 14 persen per tahun. Misalkan An mewakili jumlah uang di akhir n tahun.

4. Carilah sebuah relasi berulang untuk barisan A0, A1, …

5. Carilah sebuah rsyarat awal untuk barisan A0, A1, …


6. Carilah A1, A2, dan A3

7. Carilah rumus eksplisit untuk An.

8. Berapa lama waktu yang diperlukan orang itu untuk menggandaduakan investasi awalnya?

Latihan 9-12, asumsikan bahwa seseorang menginvestasikan Rp 2.000.000,- setiap tahun dalam simpanan perlindungan pajak dengan bunga majemuk 10 persen per tahun. Misalkan An menyatakan jumlah uang pada akhir n tahun

9. Carilah sebuah relasi berulang untuk barisan A0, A1, ….

10. Carilah sebuah syarat awal untuk barisan A0, A1, ….

11. Carilah A1, A2, dan A3.

12. Carilah rumus eksplisit untuk An.

Latihan 13-16 mengacu pada fungsi Ackermann A(m, n)

13. Hitunglah A(2, 2) dan A(2, 3).

14. Gunakan induksi matematika untuk menunjukkan bahwa

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

15. Gunakan induksi matematika untuk menunjukkan bahwa

A(2, n) = 3 +2n, n = 0, 1, ….

16. Perkirakan rumus untuk A(3, n) kemudian buktikan dengan menggu-nakan induksi matematika.

Latihan 17 dan 18 mengacu pada barisan Sn yang didefinisikan oleh:

S1=0, S2=1, , n= 3, 4, ….

17. Hitunglah S3 dan S4.

18. Tebaklah rumus untuk Sn dan tunjukkan bahwa rumus tersebut benar dengan menggunakan induksi matematika.

19. Barisan Lucas L1, L2, … (nama barisan ini diambil dari nama Eduard Lucas, penemu teka-teki Menara Hanoi) didefinisikan oleh relasi berulang:

dan syarat awal L1=1, L2=3.

a. Tentukan nilai-nilai dari L3, L4, dan L5.

b. Tunjukkan bahwa


dengan f1, f2, … menyatakan barisan Fibonacci.

20. Asumsikan bahwa seseorang menginvestasikan sejumlah uang dengan bunga majemuk tahunan r persen. Terangkan aturan: Untuk memperkirakan waktu yang diperlukan untuk mengggandaduakan investasi, bagilah 70 dengan r.

---ooOoo---


suwarno matematika diskrit bab 4a 11

Documents