Induction dan Recurtion

Kali ini saya ingin berbagi tentang materi kuliah Matematika Diskrit, yaitu tentang Induction dan Recurtion, berikut adalah rangkumannya :

I.                   Induction

Induction adalah salah satu  method dari proofing. Dengan menggunakan induction kita dapat membuktikan sebuah propositional function ( P(n) for example) benar untuk setiap nilai n . Induction can’t tidak dapat menghasilkan jawaban, it can only proof whether the statement is true or false.

Agar lebih jelas saya beri visualisasi:

                  Misalkan kita mempunyai suatu tangga yang   

                  Mempunyai anak tangga tak terbatas. Lalu kita mengetahui: 
1.       Kita dapat melewati anak tangga pertama. 
2.      Jika kita bisa melewati suatu anak tangga, kita pasti bisa melewati anak tangga berikutnya. 

Dengan begitu kita bisa membuktikan bahwa kita bisa melewati seluruh anak tangga. Saat ingin melewati anak tangga pertama,kita pakai aturan no.1.

Jika ingin melewati tangga ke 2 kita memakai aturan no.2, demikian pula jika kita ingin melewati anak tangga ke 3 dst, kita memakai aturan no.2. Itulah kira kira contoh yang menggambarkan apa itu induction.

Proofing secara induction memiliki 3 langkah,yaitu :

1.      Base case : menunjukkan function itu benar untuk kasus pertama P(1).

2.      Inductive hypothesis : menganggap bahwa function itu benar untuk setiap k P(k).

3.      Inductive step : buktikan bahwa P(k+1) adalah benar.

Contoh:

—  Show that n! < nⁿ for all n > 1

—  Base case: n = 2

                                    2! < 2²

                                    2 < 4

—  Inductive hypothesis: assume k! < k^k

—  Inductive step: show that (k+1)! < (k+1)^k+1

—  (k+1)! = (k+1) × k! < (k+1) k^k < (k+1) (k+1)^k = (k+1)^k+1

II.               Recurtion

Rekursif merupakan alat/cara untuk memecahkan masalah dalam suatu fungsi atau procedure yang memanggil dirinya sendiri. Dalam suatu algoritma, rekursif digunakan untuk mengurangi kompleksitas algoritma tersebut. Contoh dari rekursif adalah barisan Fibonacci dan faktorial.

•          Bilangan Fibonacci dapat didefinisikan sebagai berikut:

                  f_n = f_n-1 + f_n-2 untuk n > 2

                  f₁ = 1

                  f₂ = 1

      Berikut ini adalah barisan bilangan Fibonacci mulai dari n=1

                  1   1    2    3    5    8    13    21   34

•          Fungsi factorial dari bilangan bulat positif n didefinisikan sebagai berikut:

                  n!= n.(n-1)! , jika n>1

                  n!= 1          , jika n=0, 1

•          contoh :

                  3!= 3. 2!

                  3!= 3. 2. 1!

                  3!= 3. 2. 1

                  3!= 6

Dalam pemrograman rekursif sangat berguna dan sering dipakai, contoh source code yang menggunakan rekursif adalah:

1.    int Faktorial(int n)
2. {
3.               if ((n == 0) || (n == 1 ))
4.                           return (1);
5.               else
6.                           return (n * Faktorial(n-1));

Ciri ciri dari sebuah source code yang menggunakan rekursif adalah ada fungsi yang didalamnya memanggil fungsi itu sendiri. Pada source code diatas fungsi Faktorial memanggil fungsi itu sendiri pada baris ke 6 tetapi dengan nilai yang berbeda ((n-1)).