Matematika Informasi : Relasi Rekursif

Barisan yang Didefinisikan Secara Rekursif
Sebuah barisan (sequence) dapat dinyatakan dalam beberapa cara. Cara pertama adalah dengan menuliskan beberapa suku pertama barisan itu, dengan harapan pembaca dapat dmengerti kelanjutan suku-suku barisan tersebut.
Misalnya, barisan 3, 5, 7, …
Cara itu sangat sederhana dan sering dilakukan. Akan tetapi, cara itu memiliki kelemahan, kadang-kadang pembaca dibuat slah mengerti terhadap kelanjutan suku-sukunya. Sebagai contoh, pada barisan 3, 5, 7, … di atas, sering diartikan bahwa pasangan tersebut adalah barisan-barisan bilangan ganjil yang lebih besar dari 2 sehingga suku-suku selanjutnya adalah 9, 11, 13, 15, … . Akan tetapi mungkin pula diartikansebagai barisan bilangan prima sehingga suku-suku selanjutnya adalah 11, 13, 17, … . Untuk sedapat mungkin menghindari salah pengertian seperti itu, suku-suku dapat dituliskan lebih panjang. Jadi, penulisan tidak hanya 3, 5, 7, …, tetapi diperpanjang menjadi 3, 5, 7, 9, 11, … (untuk menyatakan barisan bilangan ganjil yang lebih besar dari 2).
Cara kedua adalah menyatakan barisan dalam rumus eksplisit suku-sukunya. Misalnya, barisan bilangan ganjil lebih besar dari 2 dapat dinyatakan dengan rumus:
an = 2n + 1 (n bilangan bulat ≥ 1)
Dengan rumus tersebut, suku-suku setiap barisan dapat ditentukan dengan cepat. Sebagai contoh, dalam rumus an = 2n + 1 (n ≥ 1), maka :
a0 = 2.1 + 1 = 3
a1 = 2.2 + 1 = 5
a2 = 2.3 + 1 = 7 dst
Keuntungan mendefinisikan barisan dengan cara kedua adalah bahwa tiap-tiap suku barisan ditentukan secara tunggal dan penentuan suku ke-n (misal suku ke 51 = a50) dapat dilakukan secara cepat.
Cara ketiga untuk menyatakan barisan adalah secara rekursif. Suatu barisan didefinisikan secara rekursif jika kondisi awal barisan ditentukan, dan suku-suku barisan selanjutnya dinyatakan dalam hubungannya dengan sejumlah suku-suku yang sudah dinyatakan sebelumnya. Persamaan yang menyatakan hubungan antara beberapa suku tersebut dinamakan relasi rekurensi. Sebagai contoh, barisan bilangan ganjil lebih besar dari 2 yaitu 3, 5, 7, … dapat dinyatakan sebagai berikut :
Untuk semua bilangan bulat k ≥ 1,
ak = ak-1 + 2 (relasi rekurensi ) dan
a0 = 3 (kondisi awal)
Dengan relasi rekurensi dan kondisi awal, suku-suku barisan selanjutnya dapat dihitung sebagai:
a1 = a0 + 2 = 3 + 2 = 5
a2 = a1 + 2 = 5 + 2 = 7
a3 = a2 + 2 = 7 + 2 = 9

… dst

Contoh soal :

1. Diketahui : Suatu barisan c0, c1, c2, … didefinisikan secara rekursif sebagai berikut :
Untuk semua bilangan bulat k ≥ 2,
Ck = ck-1 + k ck-2 + 1
Dengan kondisi awal c0 = 1 dan c1 = 2.
Ditanya : Hitunglah c5!
Penyelesaian :
Oleh karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3 dan c4.
A.c2 = c1 + 2 c0 + 1 = 2 + 2.1 + 1       = 5
c3= c2 + 3 c1 + 1 = 5 + 3.2 + 1  = 12
c4= c3 + 4 c2 + 1 = 12 + 4.5 + 1 = 33
c5= c4 + 5 c3 + 1 = 33 + 5.12 + 1        = 94

Jadi, c5 = 94

B. c5 = 95

C. c5 = 96

D. c5= 93

2. Diketahui : Misalkan a1, a2, … ; b1, b2, … dan c1, c2, … adalah 3 barisan yang semua sukunya memenuhi relasi rekurensi. Nilai suatu suku sama dengan 3 kali nilai suku sebelumnya.
Jadi, ak = 3ak-1; bk=3bk-1; ck=3 ck-1.
Tetapi kondisi awal ketiga barisan tersebut berbeda :
a1= 0 ; b1 = 1 ; c1= 2
Ditanya : Nyatakan barisan-barisan terebut dengan cara menuliskan beberapa suku awal barisannya !
A. barisan a1 adalah :0,0,0 …
barisan b1 adalah: 3,6,9…
barisan c1 adalah: 1,6,18,…
B. barisan a1 adalah :1,1,1 …
barisan b1 adalah: 3,9,81…
barisan c1 adalah: 6,18,54…
C. barisan a1 adalah :0,1,2 …
barisan b1 adalah: 3,9,27…
barisan c1 adalah: 6,18,54…
D. Pada barisan a1, a2….
a2 = 3a1 =3.0 = 0
a3 = 3a2 = 3.0 = 0
a4 = 3a3 = 3.0 = 0
pada barisan b1, b2….
b2 = 3b1 = 3.1 = 3
b3 = 3b2 =3.3 = 9
b4 = 3b3 = 3.9 = 27
pada barisan c1, c2….
c2 = 3c1 = 3.2 = 6
c3 = 3c2 = 3.6 =18
c4 = 3c3 = 3.18 = 54
dengan demikian , barisan a1 adalah :0,0,0 …
barisan b1 adalah: 3,9,27…
barisan c1 adalah: 6,18,54…
3. Diketahui : mk = 2mk-1 + 1 untuk bilangan bulat k ≥ 2
m1 = 1
Ditanya : Carilah rumus eksplisit barisan m1 , m2 ,…yang menyatakan masalah menara Hanoi.
penyelesaian :
A. mk = 3k – 1 untuk bilangan bulat k < 1


B. mk = 2mk-1 + 1
= 2 ( 2mk-2 + 1 ) + 1 = 22 mk-2 + 2.1 + 1
= 22 ( 2mk-3 + 1 ) + 2.1 + 1 = 23 mk-3 + 22.1 + 2.1 + 1
= 23 ( 2mk-4 + 1 ) + 22.1 + 2.1 + 1 = 24 mk-4 + 23.1 + 22.1 + 2.1 + 1
= 24 ( 2mk-5 + 1 ) + 23.1 + 22.1 + 2.1 + 1 = 25 mk-5 + 24.1 + 23.1 + 22.1 + 2.1 + 1
= ……….
= 2k-1mk-(k-1) + 2k-2.1 + … + 23.1 + 22.1 + 21 + 1
= 2k-1m1 + 2k-2 + … + 23 + 22 + 21 + 1
Oleh karena m1 = 1, maka :
mk = 2k-1 + 2k-2 + 2k-3 + … + 23 + 22 + 21 + 1
mk merupakan deret geometri dengan r = 2 yang besarnya = (2^((k-1)+1)-1)/(2-1) = 2k – 1

jadi, mk = 2k – 1 untuk bilangan bulat k ≥ 1

C. mk = 2k + 1 untuk bilangan bulat k > 1

D. mk = 2k – 2 untuk bilangan bulat k ≥ 2

Relasi rekursif homogen linear :

Definisi

Relasi rekursif homogen linear berderajat dua dengan koefisien konstanta merupakan relasi rekursif yang memiliki bentuk,

Definisi I

untuk setiap bilangan bulat k ≥ bilangan bulat tertentu, di mana A dan B merupakan suatu konstanta bilangan real, dengan B ≠ 0.

Relasi rekursif tersebut dikatakan “berderajat dua” karena ak dinyatakan dalam dua suku sebelumnya, ak – 1 dan ak – 2, dikatakan “linear” karena ak – 1 dan ak – 2 muncul pada suku yang berbeda dan masing-masing memiliki pangkat satu, dikatakan “homogen” karena total derajat dari masing-masing sukunya sama (sehingga tidak ada suku konstanta), dan “koefisien konstanta” karena A dan B merupakan suatu konstanta yang tidak bergantung terhadap k.

Contoh soal :

Nyatakan apakah masing-masing relasi rekursif berikut merupakan relasi rekursif homogen linear berderajat dua dengan koefisien konstanta atau bukan:

1.     ak = (–4)ak – 1 + (k + 1)ak – 2

A.   Iya; A = 1 = B.

B.    Bukan; tidak linear.

C.    Bukan; tidak berderajat dua.

D.   Bukan; tidak homogen.

2.     bk = bk – 1 + bk – 2

A. Bukan; tidak berderajat dua.

B. Iya; A = 0 dan B = 2.

C. Bukan; tidak linear.

D. Bukan; tidak homogen.

3.     ck = (ck – 1)2 + ck – 1 ∙ ck – 2

A. Bukan; tidak berderajat dua.

B. Iya; A = 0 dan B = 2.

C. Bukan; tidak linear.

D. Bukan; tidak homogen.

4.     dk = dk – 1 + dk – 2 + dk – 3

A. Bukan; tidak berderajat dua.

B. Iya; A = 0 dan B = 2.

C. Bukan; tidak linear.

D. Bukan; tidak homogen.

Nama kelompok :

Dilan Kusuma         52413460  Dilankusuma95.blogspot.com

Ibnu Wildan            54413182  ibnuwildann.blogspot.com

Rully Saputra          56413647  rullysaputra02.wordpress.com

Andhika Rangga P 50413890

Tugas File Sequential

Keuntungan Sequential File :

• Merupakan organisasi file yang sederhana

• Jarak setiap aplikasi yang tersimpan sangat jelas

• Metode penyimpanan didalam memory sangat sederhana, sehingga efisien untuk menyimpan record yang besar

• Sangat murah untuk digunakan, sebab medianya cukup menggunakan magnetic tape.

• Kemampuan untuk mengakses record berikutnya secara cepat.

Kerugian Sequential File :

• Jika diperlukan perubahan data, maka seluruh record yang tersimpan didalam master file, harus semuanya diproses.

• Data yang tersimpan harus sudah urut (sorted).

• Posisi data yang tersimpan sangat susah untuk uptodate, sebab master file hanya  bisa berubah saat proses selesai dilakukan.

• Tidak bisa dilakukan pembacaan secara langsung.

Berikut adalah contoh dari file sequential :

1. Inti logika dari program ini adalah sebagai berikut :
   1. Data dimasukkan tiap – tiap record.
   2. Data yang dimasukkan akan ditanyakan apakah sudah benar atau belum. Hal ini diperlukan sebagai verifikasi terhadap data yang akan direkamkan. Data yang akan direkamkan harus sudah benar.
   3. Setelah data yang dimasukan sudah benar, maka data tersebut akan direkamkan di file.
   4. Setiap selesai merekam data, akan ditanyakan apakah akan memasukkan data lagi atau tidak.
   5. Kalau akan memasukkan data lagi, proses diulangi lagi dari butir a.
   6. Kalau sudah tidak akan memasukkan data lagi, maka file ditutup dan proses selesai.