BAB I
PENDAHULUAN
A. LATAR BELAKANG MASALAH
Matematika
Diskrit merupakan cabang matematika yang mempelajari tentang obyek-obyek
diskrit. Diskrit itu sendiri adalah sejumlah berhingga elemen yang berbeda atau
elemen-elemen yang tidak bersambungan. Dimana data diskrit merupakan data yang
satuannya selalu bulat dalam bilangan asli, tidak berbentuk pecahan. Matematika
Diskrit itu sendiri meliputi kombinatorik, relasi dan fungsi, relasi rekursif
(relasi berulang), prinsip sangkar burung merpati dan juga teori graf.
Relasi
berulang mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang
dikaitkan dengan suku-suku sebelumnya. Untuk mendefinisikan sebuah barisan,
relasi ulang memerlukan nilai awal yang sudah ditentukan.
B. RUMUSAN MASALAH
Memperhatikan latar belakang diatas maka
penulis menetapkan rumusan masalah sebagai berikut :
1. Apa pengertian relasi berulang?
2. Bagaimana penyelesaian
relasi berulang?
3. Bagaimana
contoh aplikasi relasi berulang dalam komputer?
C. BATASAN MASALAH
Agar pembahasan lebih terarah, maka penulis
memberikan batasan-batasan pembahasan masalah yaitu :
1. Pembahasan mengenai pengertian relasi berulang.
2. Contoh dan juga aplikasi relasi berulang.
D. TUJUAN
Adapun tujuan dari pembuatan makalah ini adalah
:
1. Memenuhi tugas mata kuliah Matematika Diskrit.
2. Mengetahui definisi dan fungsi relasi berulang
beserta contoh dan penyelesaiannya.
E. MANFAAT
Adapun manfaat yang ingin di capai penulis dalam
pembuatan makalah ini adalah :
1. Dapat mengetahui apa itu relasi berulang.
2. Dapat mengetahui penyelesaian
relasi berulang.
3. Dapat
mengetahui contoh aplikasi relasi berulang dalam komputer.
F.
SUMBER
PENGUMPULAN DATA
BAB II
PEMBAHASAN
A. Pengertian
Relasi Berulang
Relasi, dalam ”MATEMATIKA”
adalah hubungan antara dua buah elemen himpunan. Hubungan ini bersifat abstrak,
dan tidak perlu memiliki arti apapun baik secara konkrit maupun secara
matematis. Relasi biner R antara A dan B adalah himpunan bagian dari A x
B. Himpunan A disebut daerah asal (domain) dari R dan himpunan B disebut
daerah hasil (range) dari R. Relasi pada himpunan A adalah relasi dari A x A.
Relasi rekursif sering juga
disebut relasi berulang. Relasi berulang
merupakan sebuah barisan dengan memberikan nilai ke-n yang dikaitkan
dengan suku-suku sebelumnya. Untuk mendefinisikan sebuah barisan, relasi
ulang memerlukan nilai awal yang sudah ditentukan. Secara formal relasi
berulang ini didefinisikan sebagai berikut.
Sebuah relasi berulang untuk
barisan a0,
a1, ... merupakan sebuah
persamaan yang mengaitkan an dengan a0, a1, ..., an−1. Syarat awal untuk barisan a0, a1, ... adalah nilai-nilai yang diberikan secara eksplisit pada beberapa
suku dari barisan tersebut.
Contoh
1 :
Barisan
3, 7, 11, 15, ... didefinisikan
dengan relasi berulang
, untuk
dengan syarat awal a0 = 3
Contoh 2 :
Carilah sebuah relasi berulang
dan syarat awal yang membentuk sebuah barisan 1, 1, 2, 4, 16, 128, 4096, ....
2 = 2 × 1
× 1
4 = 2 × 2
× 1
16 = 2 × 4
× 2
128 = 2 × 16
× 4
4096 = 2 × 128
× 16
Dengan demikian relasi berulangnya adalah
, untuk
dengan syarat awal a0 = 1 dan a1 = 1.
Contoh 3 :
Seseorang
mendepositokan uang sebesar Rp. 1.000.000,- pada sebuah bank dengan bunga
majemuk 12% per tahun. Jika An menyatakan jumlah uang pada akhir tahun ke-n,
carilah sebuah relasi berulang dan syarat awal yang mendefinisikan barisan An!
Penyelesaian :
Pada akhir tahun ke-1, jumlah
uangnya adalah A1 sama dengan jumlah awal ditambah bunga. Jika jumlah
awal dinyatakan dengan A0,
Maka,
Pada akhir tahun ke-2, jumlah
uangnya adalah A2 sama dengan jumlah uang pada akhir tahun ke-1 ditambah
bunga.
Sehingga
Pada akhir tahun ke-n,
jumlah uangnya adalah An sama dengan jumlah uang pada akhir tahun ke-n
− 1 ditambah bunga.
Sehingga
Karena A0 merupakan jumlah awal,
maka
. Dengan demikian relasi
berulangnya adalah
¸ untuk
dengan syarat awal
B. Penyelesaian
Relasi Berulang
Menyelesaikan
relasi berulang yang melibatkan barisan a0, a1, ... sama halnya
dengan mencari sebuah rumus eksplisit untuk bentuk umum an. Pada bagian
ini kita hanya akan membahas penyelesaian relasi berulang dengan menggunakan metode
iterasi. Untuk menyelesaikan relasi berulang dengan metode iterasi ini,
kita menuliskan bentuk ke-n, yaitu an dalam bentuk-bentuk suku sebelumnya,
yaitu an−1, an−2, ..., a0. Kemudian secara berurutan kita
gunakan relasi berulang untuk menempatkan setiap an−1, ... dengan
ketentuan pendahulunya. Kita lakukan terus sampai sebuah rumus eksplisit
diperoleh.
Contoh :
Selesaikan relasi berulang an =
an−1 + 4, n ¸ 1 dengan syarat
awal a0 = 3!
Penyelesaian :
Dengan mengganti n dengan n
− 1 pada rumus diatas, kita peroleh an−1 = an−2 + 4 Sehingga
an =
an−1 + 4
= (an−2 + 4) + 4
= ((an−3 + 4) + 4) + 4
...
= a0 + n × 4
Karena a0
= 3, maka kita peroleh
an =
3 + 4n
Latihan
1. Jika
Pn menyatakan banyaknya permutasi dari n objek yang berbeda,
carilah sebuah relasi berulang dan syarat awal untuk barisan P1, P2,
....
6.2. Seseorang mendepositokan Rp.
3.000.000 pada sebuah bank dengan bunga majemuk 12% per tiga bulan. Misalkan An
menyatakan jumlah uang pada akhir tahun ke-n.
a. Carilah relasi berulang dan
syarat awalnya.
b. Tentukan nilai A1,A2,A3
dan A4.
c. Carilah sebuah rumus
eksplisitnya.
d. Berapa lama waktu yang dibutuhkan
oleh orang tersebut agar jumlah uang di bank tersebut dua kali jumlah awalnya.
6.3. Selesaikan relasi berulang
an =
2 × an−1 × an−2 n ¸ 2
dengan syarat awal a0 = 1
dan a1 = 1.
6.4. Andaikan seorang mempunyai n
dollar dan setiap hari digunakan untuk membeli jus 1 dollar, susu 2 dollar
ataupun teh 2 dollar. Jika Rn adalah banyaknya cara membelanjakan semua
uang, tunjukkan bahwa
Rn =
Rn−1 + 2Rn−2
dimana urutan diperhatikan.
Misalnya, terdapat 11 cara untuk membelanjakan 4 dollar, yaitu ST, TS, JJS,
JJT, JSJ, JTJ, SJJ, TJJ, JJJJ,
SS, TT.
6.5. Misalkan Sn menyatakan
banyaknya untai n-bit yang tidak mengandung pola 00.
a. Carilah sebuah relasi ulang dan
syarat awalnya.
b. Tunjukkan bahwa Sn = fn+1,
n = 1, 2, ... dimana f adalah barisan
Fibonacci.
Referensi
6.1. R. Johnsonbaugh, Discrete
Mathematics, Fourth Edition, 1997, Prentice Hall.
C.
Contoh Aplikasi dalam
Komputer
1.
Masalah kombinatorial
dapat dimodelkan dengan relasi berulang.
Dalam menaiki
anak tangga,ada dua pilihan yaitu satu atau dua anak tangga sekaligus.Ada
berapa cara untuk sampai
ke anak tangga
ke- n?
a1= 1 dan a2 =
2 sehingga
an = an-1 an-2
dimana an adalah banyaknya cara untuk sampai ke anak tangga ke-n
2.
Menara Hanoi
Untuk
memindahkan n objek diperlukan berapa langkah?
an= an-1 + 1 + an-1 atau berarti
an = 2 an-1 + 1 dimana a1 = 1
3. Bilangan
Fibonacci
Relasi berulangnya : fn = fn-1 fn-2
dimana n >= 2 dan f0 = 1 dan f1 = 1
Bilangan Fibonacci sering muncul dalam
berbagai masalah kombinatorial seperti pada algoritma Euclid untuk menghitung
Greatest Common Divisor dari dua integer a dan b.
Sifat-sifat bilangan Fibonacci :
1.
f0 + f1 + ……….+ fn =
fn+2 – 1 Coba buktikan dengan induksi
2.
fn+1 fn 1 1 n+1= fn
fn-1 1 0
3.
fn+1fn-1 - fn 2 = ( -1
)n+1 Dapat dibuktikan dengan induksi atau dengan menghitung determinan dari
matriks pada 2.
4.
fn dan fn+1 adalah
prima relative
Pemecahan Relasi berulang
Fibonacci :
fn = x n
fn = fn-1 + fn-2
xn = xn-1 + xn-2
x2 – x – 1 = 0
maka akar2 x1 dan x2 dapat
dihitung yaitu
( 1 +√5 )/2 dan ( 1 -
√5
)/2 sehingga solusi umum
fn = A1 [( 1 +√5 )/2] n + A2[(
1 - √5
)/2] n
A1 dan A2 dapat dihitung dengan
menggunakan nilai awal
0 komentar:
Posting Komentar