Merupakan suatu teknik yang di kembangkan untuk:
a.Membuktikan pernyataan
b.Membuktikan universial statment..........(n)
dengan ACN dan N adalah himpunan bilangan (+)atau himpunan bilangan asli
c.Mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu
Tahapan Induksi Matematika
>Basis step:Tunjukan bahwa S(I)benar
>Inductive step:Asumsikan S(K) benar akan di buktikan dengan S(K)- S(K+I) benar
>Conclusion:S(n) adalah benar untuk setiap n bilangan integer positif
^Pembuktian Induksi Matematika
Contoh 1:
buktikan bahwa
1+2+3+....+n =1/2 n (n+1) > untuk setiap n bilangan integer positif.
Jawab
.Basis > bentuk n=1 akan di peroleh 1=1/2.1(1+1) > 1=1
.Induksi > untuk n=k diamsumsikan 1+2+3+...k=1/2.k(k+1)
.utuk n = k+1 berlaku
>1+2+3+...+(k+1)=(k+1) (k+2)/2
1+2+3......+k+(k+1) = (k+1) (k+2)/2
k(k+1)/2+(k+1)=(k+1)(k+2)/2
(k+1)(k/2+1)=(k+1)(k+2)2
(k+1)1/2(k+2)=(k+1)(k+2)2
(k+1)(k+2)2 = (k+1)(k+2)/2
>Kesimpulan 1+2+3+..+n=1/2n(n+1) untuk setiap bilangan buat positif n
contoh 2:Buktikan Bahwa
1+3+5+...+n=(2n-1)=n² > untuk setiap bilangan bulat positif.
Jawaban
-Basis:untuk n=1 akan diperoleh 1=1²>1=1
induksi untuk n=t asumsikan 1+3+5+...+n(2k-1)k² untuk n=k+1 berlaku
1+3+5+...+(2(k+1)-1)=(k+1)²
1+3+5+...+(2k+1)=(k+1)²
1+3+5+...+((2k+1)-2)+(2k+1)=(k+1)²
1+3+5+...+(2k-1)+(2k+1)=(k+1)²
k²+(2k+1)=(k+1)²
k²+2k+1=k²+2k+1
Kesimpulan
1+3+5+...+n=(2n-1)=n²
untuk setiap bilangan bulat positif
contoh 3:Buktikan bahwa
n³+2n adalah kelipatan 3 ~ untuk setiap bilangan bulat positif
Jawaban
-Basis :untuk n=1 akan diperoleh 1=1³+2(1) ~ 1=3,kelipatan 3
-induksi= untuk n=k asumsikan k³+2k=3x
untuk n=k+1 berlaku
(k+1)³+2(k+1) ~ kelipatan 3
(k³+3k³+3k+1)+2k+2
(k³+2k)+(3k²+3k+3)
(k³+2k)+3(k²+k+1)
k³+2k~ (induksi)
3x+3(k²+k+1) ~ (x+k²+k+1)
>Kesimpulan k1³+2n adalah kelipatan 3 u/setiap bil bulat positif
~Metode Greedy
Untuk memperoleh solusi yang optimal dari suatu masalah yang mempunyai indikator yaitu fungsi tujuan dan pembatas.beberapa masalah yang diselesaikan dengan metode grrendy adalah
a.TSP(Travelling Sallesperson problem)
b.MST(Minimum spanning Tree)*
c.Minimasi Waktu (Penjadwalan)
~Graph:merupakan kumpulan dari titik dengan garis dimana pasangan-pasangan titik(simpul)tersebut di hubungkan oleh sebuah garis.Simpul ini biasa di sebut Node(Verteks) dan segment garis tersebut sebagai tuas(edge)
~Tree:Merupakan graph terhubung tak berarah yang tidaak mempunyai sirkuit.(simple sirkuit)
~Algoritma yang digunakan untuk menentukan Minimum spenning Tree adalah:
-Algoritma solin
-Algoritma kruskal*
-Algoritma Primis
Syarat graph yang membentuk pohon atau spanning tree adalah:
-Graph harus terhubung
-Tuas punya bobot nilai
-Graphnya tidak berarah
 |
|
|
0 komentar:
Posting Komentar