Aplikasi Induksi Matematik dalam program

Aplikasi Induksi Matematik dalam program

 Aplikasi Induksi Matematik dalam program
Aplikasi Induksi Matematik dalam program

 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.

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

  1. Kondisi penghentianSetelah sejumlah iterasi kalang yang berhingga, maka syarat kondisi S menjadi salah.
  1. 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 kalangwhile – do, nilai i dan j pada eksekusi ke n dinyatakan idan jn.

  1. a) Langkah 1 .

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

  1. b) Langkah induksi :

misal pernyataan p(n) benar, dengan asumsi bahwa j= i.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 = i+ 1

dan jn+1 = j+ d, dari hipotesa induksi jn= i.d maka

jn+1 = (in.d) + d

= (i+ 1 ).d

= in+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:

  1. i) p(n0) benar dan
  2. ii) jika p(n) benar maka p(n+1) benar untuk setiap n ≥ n0 ,akibatnya pernyataan p(n) benar untuk setiap bilangan bulat n ≥ n0

Sumber : https://belinda-carlisle.com/