Aplikasi Induksi Matematik dalam program

B. Aplikasi Induksi Matematik dalam program

Salah satu aplikasi induksi matematik dalam pemrograman yaitu bentuk kalang (loop), dengan struktur sbb :

Keadaan sebelum menjumpai kalang( loop)

While s

Perintah-perintah dalam tubuh kalang .

semua perintah tidak boleh melompat keluar

kalang

End While

Keadaan setelah kalang(loop)

Perintah While akan dieksekusi terus menerus selama syarat kondisi S bernilai benar. Apabila dalam proses kalang dijumpai kondisi bernilai salah (tidak memenuhi syarat yang didefinisikan) eksekusi akan berhenti.

Kalang (loop)

Diberikan Kalang While dengan syarat kondisi S, kondisi sebelum dan sesudah kalang. Jika diberikan predikat I(n) yang disebut kalang invarian.

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

1. Langkah basis :

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

2. Langkah induksi :

Jika syarat kondisi S dan kalang invariant 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 variable akan sama dengan yang ditentukan dalam kondisi kalang.( tanpa menggunakan operasi perkalian langsung).

Contoh 3

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) exsekusi mencapai awal loop	Nilai i	Nilai j
Loop ke  1	0	0
2	1	1.d
3	2	2.d
4	3	3.d
:	:	:
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.     Prinsip Umum Induksi

Prinsip induksi sederhana dapat digeneralisir

sebagai berikut :

Misal p(n) adalah pernyataan tentang bilangan bulat dan akan membuktikan bahwa pernyataan p(n) benar untuk semua bilangan bulat n ≥ n₀ . Untuk membuktikan pernyataan tersebut kita hanya perlu menunjukkan bahwa:

i) p(n₀) benar dan

ii) jika p(n) benar maka p(n+1) benar untuk setiap n ≥ n_{0 ,} akibatnya pernyataan p(n) benar untuk setiap bilangan bulat n ≥ n₀