Download - Kontrak Perkuliahan
![Page 1: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/1.jpg)
1
Kontrak PerkuliahanKontrak Perkuliahan Kehadiran : > 80%Kehadiran : > 80% Evaluasi: Setiap materi ada Evaluasi: Setiap materi ada
penilaianpenilaian
Design and Analysis Design and Analysis AlgorithmAlgorithm
![Page 2: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/2.jpg)
2
Materi I : Pertemuan 1 – 4Materi I : Pertemuan 1 – 4
1.1. ReviewReview landasan matematika landasan matematika
2.2. Kriteria kebaikan suatu Kriteria kebaikan suatu algoritmealgoritme
3.3. NotasiNotasi asimtotik dan laju asimtotik dan laju pertumbuhan fungsipertumbuhan fungsi
4.4. Fungsi-fungsi rekursif dan Fungsi-fungsi rekursif dan metode penyelesaiannyametode penyelesaiannya
![Page 3: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/3.jpg)
3
Materi II (tentative) : Materi II (tentative) : Pertemuan 5 - 9Pertemuan 5 - 9
Teknik perancangan algoritme : Teknik perancangan algoritme : Divide and conquer, dynamic Divide and conquer, dynamic
programmingprogramming
Materi III (tentative) : Materi III (tentative) : Pertemuan 10 - 14Pertemuan 10 - 14 Teknik perancangan Teknik perancangan algoritme : algoritme : greedy, greedy,
backtracking, graphbacktracking, graph
Teori NP-Teori NP-completecomplete dan algoritme- dan algoritme-algoritme pendekatanalgoritme pendekatan
![Page 4: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/4.jpg)
4
Analisis Analisis AlgoritmeAlgoritme
TIU :TIU :Setelah menyelesaikan mata kuliah ini, Setelah menyelesaikan mata kuliah ini, mahasiswa dapat merancang suatu mahasiswa dapat merancang suatu algoritme yang efisien serta mampu algoritme yang efisien serta mampu membuat hasil analisisnyamembuat hasil analisisnya..
TIK :TIK :
1.1. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan konsep2 dasar dalam konsep2 dasar dalam menganalisis suatu algoritmemenganalisis suatu algoritme (Minggu I)(Minggu I)
![Page 5: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/5.jpg)
5
2.2. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan kriteria kebaikan suatu kriteria kebaikan suatu algoritme dan menganalisis algoritme dan menganalisis suatu algoritme sederhana suatu algoritme sederhana (Minggu II)(Minggu II)
3.3. MahasiswaMahasiswa dapat menjelaskan dapat menjelaskan notasi asimtotik dan notasi asimtotik dan menggolongkan fungsi berdasar menggolongkan fungsi berdasar laju pertumbuhannya (Minggu laju pertumbuhannya (Minggu III)III)
4.4. Mahasiswa memahami teknik Mahasiswa memahami teknik rekursif serta mampu rekursif serta mampu menggunakan teknik tersebut menggunakan teknik tersebut untuk menganalisis suatu untuk menganalisis suatu algoritme (Minggu IV)algoritme (Minggu IV)
![Page 6: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/6.jpg)
6
6.6. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan karakteristik algoritme karakteristik algoritme divide and divide and conquerconquer serta menggunakannya serta menggunakannya untuk jenis masalah yang sesuaiuntuk jenis masalah yang sesuai (Minggu V-VI)(Minggu V-VI)
7.7. MahasiswaMahasiswa dapat menjelaskan dapat menjelaskan karakteristik algoritme karakteristik algoritme pemrograman dinamis serta pemrograman dinamis serta menggunakannya untuk jenis menggunakannya untuk jenis masalah yang sesuaimasalah yang sesuai (Minggu VI- (Minggu VI-VII)VII)
8.8. Review paperReview paper (Minggu VIII) (Minggu VIII)9.9. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan
karakteristik algoritme karakteristik algoritme greedygreedy serta menggunakannya untuk serta menggunakannya untuk jenis masalah yang sesuaijenis masalah yang sesuai (Minggu (Minggu IX-X)IX-X)
![Page 7: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/7.jpg)
7
9.9. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan karakteristik algoritme karakteristik algoritme backtrackingbacktracking serta serta menggunakannya untuk jenis menggunakannya untuk jenis masalah yang sesuaimasalah yang sesuai (Minggu X-XI) (Minggu X-XI)
10.10. Review paper (Minggu XII)Review paper (Minggu XII)
11.11. Mahasiswa dapat menjelaskan Mahasiswa dapat menjelaskan konsep konsep NP-Complete problemNP-Complete problem dalam menganalisis suatu dalam menganalisis suatu algoritme algoritme (Minggu XIII)(Minggu XIII)
12.12. MahasiswaMahasiswa dapat menggunakan dapat menggunakan algoritme pendekatan dalam algoritme pendekatan dalam menyelesaikan masalah menyelesaikan masalah NP-NP-completecomplete (Minggu XIV)(Minggu XIV)
![Page 8: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/8.jpg)
8
Tujuan yang ingin dicapai:Tujuan yang ingin dicapai:
1.1. Mengukur kompleksitas suatu Mengukur kompleksitas suatu algoritmealgoritme
2.2. Mempelajari teknik-teknik dasar Mempelajari teknik-teknik dasar algoritme untuk menyelesaikan algoritme untuk menyelesaikan masalah-masalah real.masalah-masalah real.
3.3. Membiasakan diri untuk selalu Membiasakan diri untuk selalu merespon setiap algoritme baru merespon setiap algoritme baru dengan pertanyaan:dengan pertanyaan:
Seberapa baik algoritme ini?Seberapa baik algoritme ini? Apakah ada yang lebih baik?Apakah ada yang lebih baik?
![Page 9: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/9.jpg)
9
Referensi:Referensi:1.1. Cormen, T. H, E.L. Charles & Cormen, T. H, E.L. Charles &
L.R. Roland. 2003. L.R. Roland. 2003. Introduction to Algorithms. Introduction to Algorithms. MIT Press, Cambridge.MIT Press, Cambridge.
2.2. Buku rujukan lain yang Buku rujukan lain yang relevanrelevan
![Page 10: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/10.jpg)
10
Tujuan yang ingin dicapai:Tujuan yang ingin dicapai:
1.1. Mengukur kompleksitas suatu Mengukur kompleksitas suatu algoritmealgoritme
2.2. Mempelajari teknik-teknik dasar Mempelajari teknik-teknik dasar algoritme untuk menyelesaikan algoritme untuk menyelesaikan masalah-masalah real.masalah-masalah real.
3.3. Membiasakan diri untuk selalu Membiasakan diri untuk selalu merespon setiap algoritme baru merespon setiap algoritme baru dengan pertanyaan:dengan pertanyaan:
Seberapa baik algoritme ini?Seberapa baik algoritme ini? Apakah ada yang lebih baik?Apakah ada yang lebih baik?
![Page 11: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/11.jpg)
11
Perbandingan kompleksitas Perbandingan kompleksitas algoritmealgoritme
![Page 12: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/12.jpg)
12
Penjelasan besaranPenjelasan besaran
![Page 13: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/13.jpg)
13
Beberapa istilah yang Beberapa istilah yang digunakan:digunakan:
Algoritme:Algoritme:Satu set aturan untuk menyelesaikan Satu set aturan untuk menyelesaikan masalah dalam jumlah langkah yang masalah dalam jumlah langkah yang terbatas.terbatas.
Program:Program:Implementasi algoritme pada komputer menggunakan bahasa pemrograman tertentu
Analisis:Analisis:Untuk mengetahui seberapa banyak Untuk mengetahui seberapa banyak sumber daya yang diperlukan oleh sumber daya yang diperlukan oleh algoritmealgoritme
![Page 14: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/14.jpg)
14
Anggapan::Terdapat masalah yang diharapkan dapat Terdapat masalah yang diharapkan dapat diselesaikan menggunakan program komputerdiselesaikan menggunakan program komputer
Terhadap masalah ini, cari algoritme yang Terhadap masalah ini, cari algoritme yang sesuai serta efektif dan efisiensesuai serta efektif dan efisien
Catatan:Masalah yang secara teoritis dapat diselesaikan dengan komputer belum tentu dapat dikerjakan secara praktis (solvable algorithmically), artinya:Program dapat dituliskan serta menghasilkan output yang benar untuk setiap input yang diberikan, dengan asumsi, disediakan sumber daya yang tidak terbatas.
![Page 15: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/15.jpg)
15
Metode matematika secara efektif dapat Metode matematika secara efektif dapat digunakan untuk memprediksi digunakan untuk memprediksi banyaknya ruang dan waktu yang banyaknya ruang dan waktu yang diperlukan oleh suatu algoritme tanpa diperlukan oleh suatu algoritme tanpa harus mengimplementasikan-nya dalam harus mengimplementasikan-nya dalam bahasa pemrograman tertentu.bahasa pemrograman tertentu.
Konsep matematika yang diperlukan, al:Konsep matematika yang diperlukan, al:
Logika matematika, aljabar, kalkulus: fungsi, Logika matematika, aljabar, kalkulus: fungsi, limit, turunan, integral, sekuens, deret, limit, turunan, integral, sekuens, deret, prinsip2 pembuktian, modular aritmatika, prinsip2 pembuktian, modular aritmatika, peluang, graf, tree, dsb.peluang, graf, tree, dsb.
![Page 16: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/16.jpg)
16
Logika matematika:Logika matematika: ProposisiProposisi Perangkai dasarPerangkai dasar Tabel kebenaranTabel kebenaran Kesetaraan proposisi kompleksKesetaraan proposisi kompleks Dalil-dalil kesetaraanDalil-dalil kesetaraan ArgumenArgumen Kaidah inferensia : modus ponen, Kaidah inferensia : modus ponen,
modus tolens, kaidah silogismamodus tolens, kaidah silogisma
![Page 17: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/17.jpg)
17
Aljabar, mis: eksponen, Aljabar, mis: eksponen, logaritmalogaritma1.1. xxaaxxbb = x = xa+ba+b
2.2. xxaa/x/xbb = x = xa-ba-b
3.3. (x(xaa))bb = x = xabab
4.4. xxaa+x+xaa = 2 x = 2 xaa ≠ x≠ x2a2a
5.5. log (ab) = log a + log blog (ab) = log a + log b
6.6. loglogaab = logb = logkkb/logb/logkkaa
7.7. log alog ann= n log a= n log a
![Page 18: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/18.jpg)
18
Kalkulus:Kalkulus: Fungsi : TentukanFungsi : Tentukan
Df dan Wf dari fungsiDf dan Wf dari fungsi
Limit: Tentukan Limit: Tentukan
Turunan:Turunan:Tentukan turunan Tentukan turunan fungsifungsi
Integral: Tentukan Integral: Tentukan integral fungsiintegral fungsi
12
22
)( .4)3ln()( .3
4)( .232)( .1
xexfxxf
xxfxxxf
2
4Lim .4
1
2Lim .3
4Lim.2143Lim .1
2
221
2
2
2
2
x
x
x
x
xxx
xx
xx
12
22
)( .4)3ln()( .3
4)( .232)( .1
xexfxxf
xxfxxxf
1
02
1
2
1 .2
)(ln 1. dx
x
xdx
x
xe
![Page 19: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/19.jpg)
19
Sekuens dan Sekuens dan KekonvergenannyaKekonvergenannya
Konvergen ke 1
konvergen ke 1
divergen
![Page 20: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/20.jpg)
20
Deret: Deret: ∑ a∑ ann 1.1. ∑ ∑ aaii = 1/(1-a) jika 0 < a < = 1/(1-a) jika 0 < a <
1 1 dan n dan n → ∞→ ∞
2.2. ∑ ∑ i = n(n+1)/2 ≈ ½ ni = n(n+1)/2 ≈ ½ n22
3.3. ∑ ∑ ii22 = n(n+1)(2n+1)/6 ≈ = n(n+1)(2n+1)/6 ≈ 1/3 n1/3 n33
4.4. ∑ ∑ iikk ≈ ( n ≈ ( nk+1k+1)/|k+1|, k ≠ -)/|k+1|, k ≠ -11
![Page 21: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/21.jpg)
21
Metode pembuktian:Metode pembuktian:
Counter exampleCounter example KontradiksiKontradiksi Induksi matematikaInduksi matematika
Counter exampleCounter example::
Membuktikan bahwa suatu Membuktikan bahwa suatu pernyataan salah cukup dengan pernyataan salah cukup dengan mengambil salah satu contoh yang mengambil salah satu contoh yang mendukung pernyataan tersebut.mendukung pernyataan tersebut.
![Page 22: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/22.jpg)
22
Kontradiksi: Mula-mula Kontradiksi: Mula-mula diasumsikan salah. Biladiasumsikan salah. Bila ini ini berakibat pada suatu berakibat pada suatu kemustahilan,kemustahilan,berarti yang berlaku adalah berarti yang berlaku adalah sebaliknya (benar).sebaliknya (benar).Contoh:Contoh:
Buktikan bahwa bilangan prima itu Buktikan bahwa bilangan prima itu tidak terbatas.tidak terbatas.
Catatan:Catatan:
Setiap bilangan adalah prima atau Setiap bilangan adalah prima atau perkalian primaperkalian prima
![Page 23: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/23.jpg)
23
Induksi Matematika:Induksi Matematika:
Buktikan bahwa :Buktikan bahwa :
1.1. Untuk n ≥ 1 berlaku:Untuk n ≥ 1 berlaku:∑ i∑ i22 = [n(n+1) = [n(n+1)
(2n+1)]/6(2n+1)]/6
2.2. Bilangan Fibonacci ke-i memenuhi Bilangan Fibonacci ke-i memenuhi sifatsifat Fi < (5/3) Fi < (5/3)ii untuk i ≥ 1 untuk i ≥ 1
Catatan : FCatatan : Fii = F = Fi-1i-1 + F + Fi-2i-2
![Page 24: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/24.jpg)
24
Modular Aritmatika:Modular Aritmatika:
a = b mod n jjk n membagi (a-b) a = b mod n jjk n membagi (a-b)
Secara intuitif dapat dikatakan bahwa Secara intuitif dapat dikatakan bahwa akan diperoleh sisaan yang sama pada akan diperoleh sisaan yang sama pada pembagian: a dibagi n atau b dibagi npembagian: a dibagi n atau b dibagi n
Contoh : 5 = 1 mod 2, 11 = 2 mod 3Contoh : 5 = 1 mod 2, 11 = 2 mod 3
TeoremaTeoremaJika a = b mod n, maka a+c = b+c Jika a = b mod n, maka a+c = b+c mod nmod n
Jika a = b mod n, maka ad = bd mod nJika a = b mod n, maka ad = bd mod n
![Page 25: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/25.jpg)
25
KombinatorikaKombinatorika Hukum penjumlahanHukum penjumlahan Hukum perkalianHukum perkalian KombinasiKombinasi PermutasiPermutasi
Setiap pengguna suatu sistem komputer Setiap pengguna suatu sistem komputer memiliki sebuah memiliki sebuah passwordpassword, yang terdiri , yang terdiri atas 6 sampai 8 karakter, dengan setiap atas 6 sampai 8 karakter, dengan setiap karakter adalah huruf kapital atau digit karakter adalah huruf kapital atau digit bilangan desimal. bilangan desimal. Jika setiap password Jika setiap password
harus memuat minimal satu digit harus memuat minimal satu digit bilangan desimalbilangan desimal, ada berapa banyak , ada berapa banyak
passwordpassword yang mungkin? yang mungkin?
![Page 26: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/26.jpg)
26
Diagram PohonDiagram PohonAda berapa string biner dengan panjang empat Ada berapa string biner dengan panjang empat yang tidak memiliki dua 1 secara berurutan?yang tidak memiliki dua 1 secara berurutan?
bit ke-1bit ke-1 bit ke-2 bit ke-3 bit ke-4bit ke-2 bit ke-3 bit ke-4
00
0000
00
1111
0011 00 00
11
11 0000 00
1111
00
Jadi, terdapat 8 string.
![Page 27: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/27.jpg)
27
Permutasi dan Permutasi dan kombinasi dengan kombinasi dengan
pengulanganpengulanganTipeTipe PengulangaPengulanga
n?n?RumusRumus
rr-permutasi-permutasi TidakTidak
rr--kombinasikombinasi
TidakTidak
rr-permutasi-permutasi YaYa
rr--kombinasikombinasi
YaYa
)!(
!
rn
n
)!1(!
)!1(
nr
rn
)!(!
!
rnr
n
rn
![Page 28: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/28.jpg)
28
Peluang DiskritPeluang Diskrit
Abad 18: Laplace mempelajari perjudian dan mendefinisikan peluang suatu kejadian.
Pencacahan menjadi landasan bagi perhitungan peluang berlangsungnya suatu kejadian.
Abad 17: Pascal menentukan kemungkinan untuk memenangkan suatu taruhan yang didasarkan pada keluaran dari dua buah dadu yang dilemparkan berulang-ulang.
![Page 29: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/29.jpg)
29
Sebuah dadu dilempar 6 kali berturut-Sebuah dadu dilempar 6 kali berturut-turut. Carilahturut. Carilah
(a)(a) p(muncul tepat empat angka 1).p(muncul tepat empat angka 1).
(b) (b) p(tidak ada angka 6 yang p(tidak ada angka 6 yang muncul).muncul).
SoalSoal
![Page 30: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/30.jpg)
30
(a) Ini adalah contoh dari suatu barisan dengan enam (a) Ini adalah contoh dari suatu barisan dengan enam percobaan Bernoulli yang saling bebas, di mana percobaan Bernoulli yang saling bebas, di mana peluang sukses adalah 1/6 dan peluang gagal 5/6. peluang sukses adalah 1/6 dan peluang gagal 5/6. Karena itu, peluang muncul tepat empat angka 1 Karena itu, peluang muncul tepat empat angka 1 pada saat dadu dilemparkan 6 kali adalahpada saat dadu dilemparkan 6 kali adalah
SolusiSolusi
008,06
5
6
1)4,6(
24
C
335,06
1
6
5)6,6(
06
C
(b) Dalam kasus ini sukses adalah kemunculan angka selain 6, yang memiliki peluang 5/6 dan gagal adalah kemunculan angka 6, yang peluangnya 1/6. Maka peluang tidak ada angka 6 yang muncul pada saat dadu dilemparkan 6 kali adalah
![Page 31: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/31.jpg)
31
Graf Graf
Graf G = (V,E) denganGraf G = (V,E) dengan
V = himpunan V = himpunan vertexvertex/ simpul/ simpul
E = himpunan E = himpunan edgeedge/ sisi/ sisi
Contoh:Contoh:
1 2 3
654
V = {1, 2, 3, 4, 5, 6}E = {(1, 2), (1, 5), (2, 5), (3, 6)}
![Page 32: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/32.jpg)
32
Digraf Digraf
Graf G = (V,A) denganGraf G = (V,A) dengan
V = himpunan V = himpunan vertexvertex/ simpul/ simpul
A = himpunan A = himpunan archarch/ sisi berarah/ sisi berarah
Contoh:Contoh:
1 2 3
654
V = {1, 2, 3, 4, 5, 6}A = {(1, 2), (1, 5), (5,2), (3, 6)}
![Page 33: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/33.jpg)
33
Suatu graf G disebut terhubungkan Suatu graf G disebut terhubungkan ((connectedconnected) jika setiap pasang ) jika setiap pasang vertexvertex terhubungkan oleh suat terhubungkan oleh suatu lintasan (path).
Lintasan :
Jalur :
Trayek :
A
B
C
A
B D
C B
E
A
B
C
B
D
![Page 34: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/34.jpg)
34
TreeTree dan dan ForestForest
TreeTree : :
Adalah graf tak berarah, Adalah graf tak berarah, terhubungkan dan tanpa terhubungkan dan tanpa cyclecycle
Forest:Forest:
Adalah graf tak berarah, tanpa Adalah graf tak berarah, tanpa cycle cycle dan tak terhubungkandan tak terhubungkan
![Page 35: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/35.jpg)
35
v4
v6
2
1031
7
6
4
1
5
4
2
8
v5v3
v7
v2v1
Contoh: tentukan MST dari graf berikut:
![Page 36: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/36.jpg)
36
v4
v6
2
1
4
1
2
v5v3
v7
v2v1
Algoritme Prim:
4
6
MST: 16
![Page 37: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/37.jpg)
37
v4
v6
2
1
4
1
2
v5v3
v7
v2v1
Algoritme Kruskal:
6
MST: 16
![Page 38: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/38.jpg)
38
TugasTugas
1.1. Baca buku Cormen Baca buku Cormen bab : Sbab : Summationummation
2.2. ReviewReview landasan landasan matematika yang lainmatematika yang lain
![Page 39: Kontrak Perkuliahan](https://reader035.vdokumen.com/reader035/viewer/2022062723/56813b77550346895da48aa5/html5/thumbnails/39.jpg)
39