Anjar Dwi Rahmawati's Blog: PENERAPAN INDUKSI MATEMATIK

1. PENERAPAN INDUKSI MATEMATIKA DALAM ATM MULTI PECAHAN UANG

a. Konsep ATM Secara Umum di Indonesia

ATM, pada umumnya, hanya memiliki satu jenis nominal uang. Logikanya ialah sebuah ATM hanya memiliki satu cartridge uang, yang hanya dapat diisi oleh sebuah nominal (entah itu Rp 20.000,-, Rp 50.000,-, maupun Rp 100.000,-). Nah, pengolahan berapa jumlah uang yang dikeluarkan tidak secara langsung dihitung dari jumlah nominal uang yang ditarik, tapi dikonversikan dahulu, pecahan uang yang tersedia pada cartridge harus dikeluarkan sebanyak berapa lembar agar uang yang ingin ditarik pelanggan tercukupi4. Misal pelanggan ingin menarik uang sebanyak Rp 200.000,-. Maka ada tiga kemungkinan :

- Jika ATM tersebut berisi uang pecahan Rp 20.000,-, maka cartridge penyimpan uang akan diperintahkan menghitung dan mengeluarkan sebanyak 10 lembar.

- Jika ATM tersebut berisi uang pecahan Rp 50.000,-, maka cartridge penyimpanan uang akan diperintahkan menghitung dan mengeluarkan sebanyak 4 lembar.

- Jika ATM tersebut berisi uang pecahan Rp 100.000,-, maka cartridge penyimpanan uang akan diperintahkan untuk menghitung dan mengeluarkan uang sebanyak 2 lembar.

Terdapat beberapa kelemahan dalam ATM yang memiliki sistem seperti ini, antara lain : Pelanggan ingin menarik uang yang tidak genap (misal ingin menarik uang sebesar Rp 70.000,- ).

Pada kenyataannya, masalah ini memang sudah ditanggulangi dengan mengeluarkan pernyataan “Mesin ini hanya mengeluarkan uang dalam pecahan kelipatan Rp 20.000,- (atau Rp 50.000,- atau Rp 100.000,-). Masyarakat juga telah memaklumi keadaan ini. Namun, apakah tidak jauh lebih mudah jika dapat dilakukan penarikan tunai dengan nominal yang tidak genap seperti itu? Apa sebenarnya keistimewaan cara berpikir ATM Multi Pecahan Uang?

b. Penerapan Induksi Matematika dalam ATM Multi Nominal

Penerapan Induksi Matematik dalam ATM Multi Nominal yakni dengan penggunaan Prinsip Induksi yang Dirampatkan (prinsip pertama) pada proses penghitungan uang yang akan dikeluarkan dari cartrige penyimpanan uang.

Ada beberapa ketentuan dalam pengambilan uang pada ATM Multi Nominal ini. Ketentuan tersebut antara lain :

- jumlah minimal penarikan

- jumlah kelipatan penarikan dari jumlah minimalnya

- pecahan uang berapa yang ada di ATM tersebut

Jadi, bagaimana cara perhitungannya?

Ambil sebuah contoh, dalam satu ATM terdapat pecahan uang Rp 20.000,- dan Rp 50.000,-. Berapakah jumlah kelipatan penarikan dengan jumlah minimal yang dapat diambil pelanggan melalui ATM tersebut adalah Rp 40.000,-?

Penyelesaian :

1. tunjukkan bahwa f(n₀) benar (berlaku)

Basis induksi : Untuk mengeluarkan uang dengan jumlah Rp 40.000,- dapat digunakan 2 lembar uang Rp 20.000,-. f(n₀) jelas benar (berlaku) !!

2. Jika f(n) benar (berlaku) maka tunjukkan f(n+k) juga benar (berlaku) untuk semua bilangan bulat n ≥ n0. (k ialah kelipatan pengambilan uang di ATM)

Langkah induksi : Jika f(n) benar, yaitu untuk mengeluarkan uang dengan jumlah Rp 40.000 dapat digunakan e lembar uang Rp 20.000,- (hipotesis induksi). Kita harus menunjukkan bahwa f(n+k) juga benar, yaitu untuk mengeluarkan uang sebesar n+k juga dapat menggunakan pecahan uang Rp 20.000,- dan/atau Rp 50.000,-.

Ada dua kemungkinan yang perlu diperiksa:

a. Kemungkinan pertama, misalkan tidak ada uang pecahan Rp 50.000,- yang dikeluarkan, maka uang yang dikeluarkan senilai Rp n,- menggunakan pecahan Rp 20.000,- semuanya. Karena n ≥ Rp 40.000,-, setidaknya harus digunakan dua lembar pecahan Rp 20.000,-. Dengan mengganti dua lembar uang Rp 20.000,- dengan selembar uang Rp 50.000, akan menjadikan uang yang dikeluarkan ATM sebesar Rp n+k,- dengan k senilai Rp 10.000,-.

b. Kemungkinan kedua, misalkan ATM mengeluarkan uang senilai Rp n,- dengan sedikitnya satu lembar pecahan Rp 50.000,-. Dengan mengganti satu lembar pecahan Rp 50.000,- dengan tiga lembar uang pecahan Rp 20.000,- akan menjadikan uang yang dikeluarkan ATM sebesar Rp n+k,- dengan k senilai Rp 10.000,-

Dari penjelasan di atas,, dapat diketahui bahwa nilai k (kelipatan) uang yang dapat diambil dari ATM tersebut, dengan minimal jumlah pengambilan sebesar Rp 40.000,-, ialah sebesar Rp 10.000,-.

2. PENERAPAN INDUKSI MATEMATIKA DALAM PEMROGRAMAN

Dalam ilmu komputer, orang berusaha untuk membuat program yang benar. Program yang benar berarti akan menghasilkan keluaran yang benar yang sesuai dengan data masukan yang diberikan. Dan program akan menampilkan pesan kesalahan apabila pemakai memasukkan data yang tipenya tidak sesuai. Salah satu bentuk yang banyak digunakan dalam program adalah bentuk kalang (loop).

Struktur kalang adalah sebagai berikut :

[kondisi sebelum kalang]

While S

[perintah-perintah dalam tubuh kalang. Semua perintah tidak boleh melompat keluar kalang]

End While

[kondisi setelah kalang]

Kalang WHILE akan dieksekusi terus menerus selama syarat kondisi S bernilai benar. Sekali kondisi S bernilai salah, eksekusi pada kalang dihentikan.

Suatu kalang dikatakan benar terhadap kondisi sebelum dan setelah kalang bila dan hanya bila setiap kali variabel-variabel tersebut akan memenuhi kondisi setelah kalang. Kebenaran kalang dapat dibuktikan dengan Teorema Kalang Invarian sebagai berikut :

Teorema Kalang Invarian

Misal : diberikan kalang WHILE dengan syarat kondisi S, kondisi sebelum dan sesudah kalang. Dan predikat I(n) yang disebut kalang invarian

Apabila keempat syarat di bawah ini benar, maka kalang benar terhadap kondisi sebelum dan sesudahnya.

1. Basis

Kondisi sebelum kalang berarti bahwa I(0) benar sebelum iterasi pertama dalam kalang.

2. Induksi

Jika syarat kondisi S dan kalang invarian I(k) benar untuk suatu bilangan bulat k

0 sebelum iterasi kalang, maka I(k + 1) juga benar setelah iterasi kalang.

3. Kondisi Penghentian

Setelah sejumlah iterasi kalang yang berhingga, maka syarat kondisi S menjadi salah.

4. Kebenaran Kondisi setelah Kalang

Jika untuk suatu bilangan bulat tak negatif N, syarat kondisi S salah dan I(N) benar, maka harga variabel akan sama dengan yang ditentukan dalam kondisi akhir kalang.

Contoh 1 :

Perkalian m (bilangan bulat tak negatif) dengan x didefinisikan sebagai berikut :

Program untuk menghitung m.x sebagai berikut :

[kondisi sebelum kalang :

m := bilangan bulat tak negatif

x := bilangan riil

i := 0

kali := 0

]

While (i

kali := kali + x

i := i + 1

End While

[kondisi setelah kalang

kali := m * x

]

Misalkan kalang invarian I(n) adalah “i = m dan kali = m.x”

Gunakan kalang invarian tersebut untuk membuktikan bahwa kalang WHILE benar terhadap kondisi sebelum dansetelah kalang.

Penyelesaian :

Basis

Akan dibuktikan I (0) benar sebelum iterasi kalang yang pertama.

I (0) : “i = 0 dan kali = 0.x = 0”

Kondisi sebelum kalang : i = 0 dan kali = 0

Karena I (0) sama dengan kondisi sebelum kalang, maka basis benar.

Induksi

Akan dibuktikan bahwa jika syarat kondisi S (dalam hal ini i

m) dan I (k) benar sebelum iterasi kalang (k

0), maka I (k + 1) benar setelah iterasi kalang.

I (k + 1) berarti : “i = k + 1 dan kali = (k + 1).x”

Misal k adalah bilangan bulat tak negatif sedemikian hingga S dan I (k) benar sebelum iterasi kalang.

Di awal kalang, i

m, i = k dan kali = k.x

Karena i

m, maka kalang dieksekusi dan statemen – statemen di dalam kalang dieksekusi. Didapat :

(kali)_baru = (kali)_lama + x = k.x + x = (k + 1).x

(i)_baru = (i)_lama + 1 = k + 1

Sehingga setelah eksekusi kalang, I(k + 1) benar.

Kondisi Penghentian

Akan dibuktikan bahwa setelah sejumlah iterasi kalang (berhingga), maka kondisi S menjadi salah sehingga iterasi berhenti.

Setelah kalang diiterasi sebanyak m kali, maka i = m dan kali = m.x

Pada keadaan ini, syarat kondisi S salah sehingga iterasi berhenti.

Kebenaran kondisi setelah kalang

Akan dibuktikan :

Jika untuk suatu bilangan bulat tak negatif N, syarat kondisi S salah dan I(N) benar, maka harga variabel akan sama dengan kondisi yang ditentukan dalam kondisi akhir kalang.

Dalam algoritma di atas, syarat S menjadi salah setelah i = m.

Kondisi I(N) benar berarti : “i = N dan kali = N.x”

Karena kedua kondisi tersebut dipenuhi (S salah dan I(N) benar), maka

m = i =N dan kali = N.x = m.x

Hal tersebut sama dengan kondisi setelah kalang yang ditentukan dalam algoritma.

Contoh 2 :

Akan dihitung hasil kali dua buah bilangan bulat positip, atau nilai nol c dan d, dengan tanpa melalui operasi perkalian langsung. Berikut ini potongan algoritma pemrograman untuk menghitung hasil kali dua bilangan bulat tersebut, dengan cara menjumlahkan d sebanyak c kali yang hasilnya c.d sbb :

i ← 0

J ← 0

while i ≠ c do (1)

J ← J + d

i ← i+ 1

endwhile

( i = c, J = c.d )

Buktikan bahwa setiap kali eksekusi mencapai awal kalang while-do 1), ditemukan J = i.d.

Bukti :

Algoritma untuk enumerasi nilai i dan j untuk setiap kali eksekusi mencapai awal kalang while - do tersebut dapat diilustrasikan sbb :

Tabel eksekusi while – do

Setiap kali (n) eksekusi mencapai awal loop	Nilai i	Nilai j
Loop ke 1	0	0
2	1	1.d
3	2	2.d
4	3	3.d
Dst	Dst	Dst
c + 1	c	c.d

dari tabel tersebut tampak bahwa setiap kali eksekusi algoritma mencapai awal kalang while-do, nilai j = 1.d. Untuk mengetahui kebenaranya dapat digunakan induksi matematik. Misal p(n) merupakan pernyataan bahwa setiap kali yaitu n eksekusi algoritma mencapai awal kalang while – do, nilai i dan j pada eksekusi ke n dinyatakan i_n dan j_n.

a. Langkah 1

untuk n = 1, pernyataan p(1) benar karena pada saat n = 1 eksekusi mencapai awal kalang while – do i = 0 dan j = 0, serta nilai j_n= i_n .d = 0 adalah benar.

b. Langkah Induksi

misal pernyataan p(n) benar, dengan asumsi bahwa j_n = i_n .d saat eksekusi mencapai awal kalang while – do. Akan ditunjukkan bahwa p(n+1) benar yaitu saat eksekusi mencapai awal kalang while – do yang ke (n+1) yang berarti j_n+1 = i_n+1.d juga benar. Dari tabel dapat dilihat bahwa nilai i yang baru bertambah sebesar 1 dari nilai i yang lama dan j yang baru bertambah sebesar d dari nilai j yang lama sehingga i_n+1 = i_{n + 1}

dan j_n+1 = j_n + d, dari hipotesa induksi j_n= i_n .d maka

j_n+1 = (i_n.d) + d

= (i_{n + 1}).d

= i_n+1 .d

maka terbukti bahwa setiap kali eksekusi algoritma mencapai awal kalang while – do nilai j= i.d.1.