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(n0) benar (berlaku)
Basis
induksi : Untuk mengeluarkan uang dengan jumlah Rp 40.000,- dapat digunakan 2
lembar uang Rp 20.000,-. f(n0) 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 k0 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 (im)
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 im) dan I (k)
benar sebelum iterasi kalang (k0), 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, im, i = k dan
kali = k.x
Karena
im, 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 in dan jn.
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 jn= in .d = 0
adalah benar.
b. Langkah
Induksi
misal
pernyataan p(n) benar, dengan asumsi bahwa jn = in .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 jn+1 = in+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 in+1
= in + 1
dan
jn+1 = jn + d,
dari hipotesa induksi jn= in .d maka
jn+1 = (in.d) + d
= (in + 1 ).d
= in+1 .d
maka terbukti bahwa
setiap kali eksekusi algoritma mencapai awal kalang while – do nilai j= i.d.1.