Implementasi Induksi matematika dalam Pemrograman

Aplikasi 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 Kalag 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 :

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 :

1. 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.

2. 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.

3. 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.

4. 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.