SATUAN ACARA PERKULIAHAN MATA KULIAH GRAPH & ANALISIS ALGORITMA (SI / S1) KODE / SKS : KK 011326 / 3 SKS Pertemuan ke 1 2
3
Pokok Bahasan dan TIU Pendahuluan 1. Dasar-dasar Teori Graph
2. Graph tidak Berarah
Sub Pokok Bahasan dan TIK Penjelasan mengenai ruang lingkup mata kuliah, sasaran, tujuan dan kompetensi lulusan 1.1. Kelahiran Teori Graph 1.2. Graph secara formal (konteks graph tak berarah) 1.3. Subgraph 1.4. Derajat pada Graph 1.5. Keterhubungan Graph 1.6. Operasi pada Graph 1.7. Matriks dan Graph Agar Mahasiswa : Mengetahui latar belakang lahirnya teori graph, Mampu menyajikan graph tak berarah secara formal Memahami pengertian subgraph, derajat dan keterhubungan graph. Mampu menentukan derajat simpul pada graph Mampu memeriksa keterhubungan dalam sebauh graph Mampu menentukan hasil operasi graph Mampu menyajikan graph dalam bentuk matriks dan mampu mengenali graph yang disajikan dalam bentuk matriks. 2.1. Penyajian Graph Tidak Berarah 2.2. Graph Berlabel 2.3. Pemodelan Masalah dengan Graph Tidak Berarah -. Masalah Lintasan Euler -. Masalah Pedagang Keliling (Travelling Salesman Problem) Agar Mahasiswa : Mengetahui hubungan antara matriks dan graph Memahami pengertian graph berlabel Mengenal beberapa masalah dalam konteks graph tidak berarah Mampu memeriksa keberadaan lintasan euler pd sebuah graph Mampu memeriksa keberadaan lintasan pedagang keliling dalam suatu graph
1
Teknik Pembelajaran Ceramah Ceramah
Ceramah
Media Pembelajaran Papan Tulis & OHP Papan Tulis & OHP
Papan Tulis & OHP
Tugas
Referensi
2 Bab 1, 2
2 Bab 1, 2
SATUAN ACARA PERKULIAHAN MATA KULIAH GRAPH & ANALISIS ALGORITMA (SI / S1) KODE / SKS : KK 011326 / 3 SKS 4
3.
Graph Planar
3.1. Penyajian Graph Planar 3.2. Dual dari Graph Planar 3.3. Formula Euler untuk Graph Planar
Ceramah
Papan Tulis & OHP
2 Bab 1, 5
Agar Mahasiswa : Mampu mengenali sebuah graph planar Mampu memberikan penyajian planar dari sebuah graph planar Mengenal sifat dari graph planar 4.
5
5.
Pewarnaan Graph
4.1. Pewarnaan Simpul Graph dan Bilangan Kromatik 4.2. Pemodelan Masalah sebagai Masalah Pewarnaan Simpul 4.3. Pewarnaan Region pada Graph Planar
Pohon (Tree)
Agar Mahasiswa : Mengenal dan memahami pewarnaan simpul pada sebuah graph Mampu menentukan bilangan kromatik dari sebuah graph Memahami pemodelan masalah ke dalam masalah pewarnaan simpul graph Memahami pewarnaan region pada graph planar 5.1. Pengertian Pohon pada Graph 5.2. Pohon Rentangan (Spanning Tree) 5.3. Pohon Berakar (Rooted Tree) 5.4. Pohon Biner (Binary Tree) 5.5. Pemodelan Masalah dengan Graph Pohon : -. Masalah Pohon Rentangan Minimal -. Penyelesaian Masalah Pohon Rentangan Minimal menggunakan Algoritma Solin dan Algoritma Kruskal -. Penerapan Pohon pada Sintaksis Kalimat Agar mahasiswa : Mengenal bentuk graph pohon (tree) & jenis-jenisnya Memahami beberapa sifat graph pohon Memahami pengertian pohon rentangan, pohon berakar dan pohon biner Mengenal beberapa masalah dalam konteks graph pohon
2
2 Bab 1, 8
Ceramah
Papan Tulis & OHP
2 Bab 1, 3
SATUAN ACARA PERKULIAHAN MATA KULIAH GRAPH & ANALISIS ALGORITMA (SI / S1) KODE / SKS : KK 011326 / 3 SKS
6
7
6.
7.
Graph Berarah
Algoritma
Mampu membuat model masalah ke dalam bentuk masalah dalam konteks graph pohon Mampu menerapkan algoritma Solin dan Kruskal dalam mencari solusi dari masalah pohon rentangan Mampu membangun pohon dari sintaks kalimat 6.1. Penyajian Graph Berarah (Pengertian simpul & panah) 6.2. Derajat Simpul pada Graph Berarah 6.3. Keterhubungan Graph Berarah 6.4. Matriks dan Graph Berarah 6.5. Pemodelan Masalah dengan Graph Berarah dan Penyelesaiannya -. Masalah Jalur Terpendek (Shortest Path) -. Masalah Aliran Maksimal (Flow Maximum) 6.6. Mesin Stata Hingga 6.7. Automata Hingga Agar mahasiswa : Mengenal konsep graph berarah Mampu menyajikan sebuah graph berarah Memahami pengertian derajat simpul dan keterhubungan dalam konteks graph berarah Mampu menyajikan graph berarah dalam bentuk matriks dan dapat mengenali graph berarah yang disajikan dalam bentuk matriks Mengenal masalah yang dapat dimodelkan dalam bentuk graph berarah Mampu menyelesaikan masalah Jalur Terpendek dan masalah Aliran Maksimal Dapat membuat diagram mesin Stata dan mesin Automata Mampu menentukan output dari mesin Stata Hingga 7.1. Pengertian Algoritma 7.2. Kriteria Algoritma yang Bagus 7.3. Analisis Suatu Algoritma Agar mahasiswa : Memahami apa yang dimaksud dengan algoritma
3
Ceramah
Ceramah
Papan Tulis & OHP
2 Bab 1, 9
Papan Tulis & OHP
3 Bab 1
SATUAN ACARA PERKULIAHAN MATA KULIAH GRAPH & ANALISIS ALGORITMA (SI / S1) KODE / SKS : KK 011326 / 3 SKS
8
9
10
8.
9.
Teknik Rekursif
Teknik Telusur Balik (Backtracking)
10. Teknik Divide & Conquer
Memahami apa yang dimaksud dengan analisis algoritma Memahami kriteria algoritma yang baik Mampu menganalisis sebuah algoritma 8.1. Pengertian Teknik Rekursif 8.2. Penerapan Teknik Rekursif pada -. Perhitungan Nilai Faktorial -. Pembentukan Barisan Fibonacci -. Permutasi Sekelompok Karakter -. Masalah Menara Hanoi 8.3. Perbedaan Teknik Rekursif dan Teknik Iteratif 8.4. Penerapan Teknik Iteratif pada -. Pembentukan Barisan Fibonacci Agar mahasiswa : Memahami teknik rekursif Memahami teknik iteratif Mampu membedakan teknik rekursif dan teknik iteratif Mampu mengenali algoritma yang menggunakan teknik rekursif maupun yang menggunakan teknik iteratif Mengenal beberapa penerapan teknik rekursif dalam penyusunan algoritma Mengenal penerapan teknik iteratif dalam penyusunan algoritma UJIAN TENGAH SEMESTER 9.1. Pengertian Teknik Telusur Balik 9.2. Algoritma Telusur Balik Secara Umum Penerapan Teknik Telusur Balik pada Perhitungan Banyaknya Himpunan Bagian dari Sebuah Himpunan (Sum of Subset) Agar mahasiswa : Mengetahui definisi dari teknik Backtraking Mampu menerapkan teknik backtracking dalam masalah Sum of subset 10.1. Pengertian Teknik Divide & Conquer 10.2. Algoritma Divide & Conquer Secara Umum
4
Ceramah
Papan Tulis & OHP
3 Bab 2
Ceramah
Papan Tulis & OHP
3 Bab 3
Ceramah
Papan Tulis & OHP
3 Bab 4
SATUAN ACARA PERKULIAHAN MATA KULIAH GRAPH & ANALISIS ALGORITMA (SI / S1) KODE / SKS : KK 011326 / 3 SKS 10.3. Penerapan Teknik Divide & Conquer pada masalah -. Pencarian (Searching) -. Pengurutan (Sorting)
11
12
11. Teknik Greedy
12. Pemrograman Dinamis
Agar mahasiswa : Mengenal teknik DANDC secara umum Mampu menerapkan algoritma DANDC dalam masalah searching dan sorting 11.1. Pengertian Teknik Greedy 11.2. Penyelesaian Masalah dengan Teknik Greedy : -. Masalah Pohon Rentangan Minimal -. Masalah Jalur Terpendek (Bandingkan dengan Algoritma Lain untuk Masalah yang Sama) Agar mahasiswa : Mengetahui definisi dari teknik Greedy Dapat menerapkannya dalam berbagai contoh masalah Mampu membandingkan penerapan teknik greedy dengan teknik lain terhadap sebuah masalah 12.1. Metode Umum 12.2. Multistage Graf
Ceramah
Papan Tulis & OHP
3 Bab 5
Ceramah
Papan Tulis & OHP
3 Bab 5
Agar mahasiswa : Mengenal teknik dalam pemrograman dinamis & dapat menerapkannya. UJIAN AKHIR SEMESTER Sumber Bacaan : 1. Deo, Narsingh. 1974. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall Inc. Englewood Cliffs, N.J. USA. 2. D. Suryadi H.S., 1995, Pengantar Teori dan Algoritma Graph, Edisi Ke-1, Seri Diktat Kuliah, Gunadarma, Depok. 3. Suryadi M.T., 1996, Pengantar Analisis Algoritma, Seri Diktat Kuliah, Gunadarma, Depok.
5
