Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas teknik perhitungan lanjutan dalam Matematika Diskrit dengan topik "Banyak Bit String". Pembahasan mencakup relasi recurrence untuk menentukan banyaknya bit string dengan panjang tertentu yang tidak memiliki dua nol berurutan. Dengan menggunakan aturan penjumlahan, kita dapat menentukan bahwa banyaknya bit string yang dicari sama dengan jumlah bit string yang berakhir dengan 0 ditambah dengan yang berakhir dengan 1. Dengan memanfaatkan relasi recurrence, kita dapat menemukan pola untuk mencari banyaknya string dengan panjang tertentu tanpa dua nol berurutan.

Di sini relasi recurrence itu bisa memodelkan hal-hal yang sangat berbeda gitu ya,

dari tadi pertumbuhan bakteri, kemudian yang kelinci, kemudian di sini ada gamenya.

Dia juga bisa kalau terkait sama komputer atau sains komputer,

itu kita bisa melihat banyaknya bit string dengan panjang n dan tidak mempunyai dua nol berurutan.

Gimana caranya ini bisa nyambung ke relasi recurrence?

Kita misalkan a n itu banyaknya bit string yang panjangnya n tapi dia tidak punya dua nol yang berurutan.

Kalau misalnya n nya itu sama dengan 1 maka kita dapat dua nol dan satu karena nol itu kan tidak dua nol berurutan,

tapi kalau n nya sama dengan 2 kita punya 0 1 1 0 dan 1 1 kita tidak punya 0 0 karena itu tadi tidak boleh.

Sekarang kita kembali tadi a n adalah banyaknya bit string dengan panjang n yang tidak mempunyai dua nol berurutan.

Kalau kita lihat dari aturan penjumlahan nanti kita lihat banyaknya bit string yang dicari itu

ternyata sama dengan banyaknya bit string yang berakhir dengan 0 ditambah dengan banyaknya bit string yang berakhir dengan 1.

Tentu saja keduanya itu tidak boleh ada nilai 2 nol yang berurutan.

Panjang bit stringnya kita buat minimalnya 3 jadi tidak boleh 2, tadi sudah tahu jawabannya kalau n nya sama dengan 2.

Sekarang dari kasus yang pertama tadi yang banyaknya bit string dengan panjang n berakhir dengan 1

dan tidak mempunyai nol berurutan itu sama banyaknya dengan bit string dengan panjang n-1 tanpa dua nol yang berurutan

karena kan di sini belakangnya itu kan 1 jadi kalau satunya ini kita hilangkan kan sebetulnya sama saja dengan mencari n-1

bit string ya maksudnya panjangnya n-1 yang tidak punya 2 nol nanti kalau kita sudah dapat tambahin saja 1 belakangnya

ada berapa kemungkinannya tambahin 1 semuanya tidak ada masalah dengan jumlah kemungkinannya.

Terus ditambah dengan yang tadi yang banyaknya bit string yang panjangnya n tadi dengan digit terakhirnya itu nol di paling belakang di akhir string.

Kalau itu ada kemungkinan kan di belakang nol-nol jadi sekarang melihatnya bukan dengan panjang n-1 tapi panjang n-2

panjang n-2 yang tidak memuat 2 nol berurutan dengan menambahkan yang di belakangnya adalah 1 sama nol di akhir string

kita tidak menambahkan 1-1 karena ini kasus yang ujung akhirnya itu nol

sehingga nanti kita akan dapat an nya itu adalah an-1 tadi banyaknya string dengan panjang n-1

kemudian ditambah dengan banyaknya string dengan panjang n-2 yang kita tambahin 1 nolnya

jadi kita sekarang sudah mendapatkan relasi recurrence untuk mencari banyaknya string dengan panjang n dan tidak mempunyai 2 nol berurutan

ini soalnya bisa diganti-ganti mau tidak punya 1-2-1 berurutan atau yang lain

ini adalah gambarannya jadi kalau kita punya ada 2 kasus tadi kan ya yang belakangnya adalah 1 sama belakangnya adalah nol

kalau yang belakangnya 1 ini kita punya n-1 dengan yang tidak punya 2 nol itu kita sebut sebagai n-1

sedangkan yang belakangnya nol itu sama saja bukan n-1 tapi disini n-2 karena yang kedua dari belakang itu cuma bisa ditaruh 1

makanya kita punya an-2 ya itu kira-kira gambaran untuk mendapatkan kenapa an nya itu sama dengan an-1 ditambah an-2