Welcome to Spada Indonesia
Courses Images
MATEMATIKA DISKRIT A
Universitas Telkom

MATEMATIKA DISKRIT A

COURSE INSTRUCTOR

Teachers Images

MUHAMMAD ARZAKI

Universitas Telkom
AREAS:
Program Studi PJJ Informatika

Course Description

https://telkomuniversityofficial.sharepoint.com/CELOE/msh2a3/Shared%20Documents/Opening%20Video%20Matematika%20Diskrit-MZI.mp4 Identitas Mata Kuliah Nama Mata Kuliah: Matematika Diskret A Kode: MSH2A3 Semester (Tahun): 2 (tahun pertama). SKS: 3 SKS. Program Studi: S1 Informatika. Fakultas: Fakultas Informatika. Profil dan Sejarah Mata Kuliah Mata kuliah Matematika Diskret A memberikan paparan yang rinci terkait struktur diskret dan sifat-sifatnya yang relevan untuk ilmu komputer. Kuliah ini mendukung materi struktur diskrit yang digunakan pada struktur data dan fondasi relevan lain dalam algoritma. Ada tempat topik utama dalam kuliah ini yang berkaitan dengan empat capaian pembelajaran (course learning outcomes, CLO), yaitu: CLO 1: relasi, fungsi, dan rekurensi , CLO 2: kombinatorika , CLO 3: graf dan pohon , dan CLO 4: teori bilangan elementer . Topik pertama membahas relasi, fungsi, dan relasi rekurensi homogen sederhana. Mahasiswa mempelajari definisi relasi dan fungsi beserta representasi dan karakteristik matematisnya. Selain itu mahasiswa juga mempelajari relasi rekurensi yang akan digunakan selanjutnya dalam analisis algoritma. Topik kedua terkait matematika kombinatorika. Mahasiswa mempelajari dasar teknik berhitung, prinsip sarang merpati, serta permutasi dan kombinasi beserta perumumannya. Tingkat kepahaman mahasiswa terkait CLO 1 dan CLO 2 akan dievaluasi secara komprehensif pada UTS. Topik ketiga terkait graf dan pohon. Pada topik ini mahasiswa akan mengkaji definisi formal graf, sifat-sifat graf, dan beberapa algoritma graf elementer (pencarian lintasan terpendek, pewarnaan graf, dan konstruksi pohon perentang minimum). Terakhir, pada topik ke empat mahasiswa mengkaji teori bilangan elementer, yang meliputi keterbagian, faktor persekutuan terbesar dan kelipatan persekutuan terkecil beserta aplikasinya, dan aritmetika modular elementer. Materi pada CLO 3 dan CLO 4 diuji secara komprehensif pada UAS. Sebelum penerapan kurikulum 2016, Matematika Diskret A dikenal sebagai Matematika Diskret untuk Program Studi S1 Informatika di Fakultas Informatika, Telkom University. Kuliah ini diberikan di semester kedua pada tahun kedua dengan kode MUG2A3. Sebelum tahun 2014, kuliah ini tidak mencakup materi teori bilangan elementer. Materi teori bilangan elementer ditambahkan karena materi tersebut relevan dengan Kriptografi - yang merupakan salah satu mata kuliah pilihan yang ditawarkan di tahun ketiga. Selain itu, sebelum penerapan kurikulum 2016, kuliah ini mencakup teori himpunan dan tidak mengkaji relasi rekurensi. Sejak semester pertama pada 2016-2018, materi teori himpunan elementer dibahas di kuliah Logika Matematika dan relasi rekurensi ditambahkan setelah kajian relasi dan fungsi. Penambahan materi dilakukan karena relasi rekurensi penting dan relevan dalam kajian algoritma rekursif pada analisis algoritma, yang diberikan pada kuliah Desain dan Analisis Algoritma. Dibandingkan dengan Matematika Diskret pada kurikulum 2012, kuliah ini mengalami perubahan signifikan pada kurikulum 2016 untuk membuatnya sesuai dengan ACM Computing Curricula. Saat ini Matematika Diskret A mencakup 27 topik, 89% di antaranya diklasifikasikan sebagai topik tier 1. Relevansi Matematika Diskret A dalam Program Studi S1 Informatika Matematika Diskrit A adalah mata kuliah wajib yang fundamental untuk program studi S1 Informatika. Berdasarkan ACM Computing Curricula tahun 2013 untuk bidang Ilmu Komputer, sekitar 13% dari waktu perkuliahan pada program Ilmu Komputer harus dialokasikan untuk kajian struktur diskrit atau yang terkait. Bersama dengan Logika Matematika A dan mata kuliah lain yang terkait struktur diskrit, Matematika Diskrit A mencakup hampir 12% dari jam perkuliahan pada kurikulum 2016. Matematika Diskrit A mencakup 27 topik pada ACM Computing Curricula, 89% termasuk dalam kategori tier 1, dan sisanya termasuk dalam tier 2. Keterkaitan dengan Mata Kuliah Lain Matematika Diskrit A adalah mata kuliah fundamental pada program studi S1 Teknik Informatika. Prasyarat dari mata kuliah ini adalah: Logika Matematika A (semester satu, tahun pertama). Kalkulus 1 B (semester satu, tahun pertama). Matematika Diskrit A adalah co-syarat dari mata kuliah Matriks dan Ruang Vektor (yang diberikan di semester yang sama), dan merupakan prasyarat dari mata kuliah berikut: Kuliah wajib: Teori Bahasa dan Automata (semester satu, tahun kedua). Kuliah wajib: Desain dan Analisis Algoritma (semester dua, tahun kedua). Kuliah wajib: Kecerdasan Buatan (semester satu, tahun ketiga). Kuliah wajib: Dasar Pemodelan dan Simulasi (semester dua, tahun ketiga). Kuliah pilihan: Kriptografi. Kuliah pilihan: Metode Formal. Kuliah pilihan: Topik Khusus 2 ICM: Pemrograman Logika. Capaian Program dan Capaian Pembelajaran Capaian Program (Program Outcome): PO 5: kemampuan menerapkan pengetahuan matematika, ilmu pengetahuan alam, bahasa, teknologi informasi, dan keteknikan untuk mendapatkan pemahaman menyeluruh tentang prinsip-prinsip informatika. Capaian Pembelajaran (Course Learning Outcome, CLO): CLO 1: mahasiswa memiliki kemampuan dalam mengidentifikasi karakteristik relasi, fungsi, dan relasi rekurensi serta menerapkan teknik baku dalam menyelesaikan masalah-masalah matematika yang terkait dengan hal-hal tersebut. CLO 2: mahasiswa memiliki kemampuan dalam mengidentifikasi masalah kombinatorika dasar dan menerapkan metode matematis yang sesuai untuk menyelesaikan masalah-masalah tersebut. CLO 3: mahasiswa mampu mengidentifikasi karakteristik graf dan pohon serta mendemonstrasikan algoritma yang terkait dengan struktur-struktur tersebut. CLO 4: mahasiswa mampu melakukan kalkulasi terkait teori bilangan elementer, seperti: kalkulasi faktor persekutuan terbesar, kelipatan persekutuan terkecil, dan melakukan operasi aritmetika modular elementer. Setiap CLO relatif independen satu sama lain. Meskipun begitu, beberapa konsep elementer pada CLO 1 digunakan pada CLO 2, CLO 3, dan CLO 4. Hubungan dan kebergantungan antar capaian pembelejaran digambarkan sebagai berikut: Beberapa konsep elementer pada materi relasi, fungsi, dan rekurensi digunakan di kajian kombinatirka, graf dan pohon, serta teori bilangan elementer. Materi pada CLO 2 dan CLO 3 relatif independent, meskipun beberapa (tapi tidak semua) masalah pada graf dan pohon memerlukan penyelesaian masalah kombinatorial. Materi pada CLO 4 relatif tidak terkait dengan materi pada CLO 2 dan CLO 3. Topik Pokok Bahasan per Pekan Empat capaian pembelajaran (CLO) dibagi ke dalam 14 topik mingguan sebagai berikut: Topik 1: Relasi: produk kartesius, relasi biner dan representasinya (dengan matriks dan digraf), sifat-sifat relasi biner (refleksif, irefleksif, simetris, antisimetris, asimetris, dan transitif), dan relasi komposisi. Topik 2: Fungsi: definisi dan representasi fungsi, sifat-sifat fungsi total (injektif, surjektif, dan bijektif), komposisi fungsi, fungsi invers, serta fungsi lantai (floor) dan atap (ceiling). Topik 3: Relasi Rekurensi: definisi relasi rekurensi dan solusinya, pemodelan sederhana untuk relasi rekurensi, serta solusi umum dari relasi rekurensi linier berkoefisien konstan. Topik 4: Teknik Berhitung (Pencacahan) Dasar: relevansi kombinatorika dalam ilmu computer, aturan penjumlahan dan penerapannya, aturan perkalian dan penerapannya, aturan pengurangan (prinsip inklusi-eksklusi) dan penerapannya, serta aturan pembagian dan penerapannya. Topik 5: Prinsip Sarang Merpati: definisi prinsip sarang merpati, penerapan prinsip sarang merpati, dan penyelesaian masalah kombinatorika dengan prinsip sarang merpati. Topik 6: Permutasi, Kombinasi, dan Generalisasinya: permutasi dan penerapannya, kombinasi dan penerapannya, permutasi yang diperumum dan aplikasinya, serta kombinasi yang diperumum dan aplikasinya. Topik 7: Graf 1: definisi informal dan formal dari graf, terminologi elementer pada graf (ketetanggaan, lingkungan, derajat, dan graf sederhana), subgraf, subgraf perentang, graf komplemen, graf gabungan, serta representasi graf dengan matriks dan daftar (list). Topik 8: Graf 2: isomorfisma graf, keterhubungan pada graf, lintasan dan sirkuit Euler, serta lintasan dan sirkuit Hamilton. Topik 9: Graf 3: graf planar, formula Euler untuk graf planar, penentuan planaritas dengan teorema Kuratowski, pewarnaan graf, algoritma Welsh-Powell, dan aplikasi dari pewarnaan graf. Topik 10: Graf 4: masalah lintasan terpendk, algoritma Dijsktra, masalah pedanganh keliling, dan masalah tukang pos Tiongkok. Topik 11: Pohon 1: definisi pohon, hutan, dan hal-hal terkait, terminologi pada pohon berakar, dan sifat-sifat dasar pohon berakar. Topik 12: Pohon 2: definisi pohon perentang dan pohon perentang minimum, algoritma Prim, algoritma Kruskal, dan aplikasi pohon. Topik 13: Teori Bilangan 1: teorema pembagian dan penerapannya, bilangan prima dan algoritma terkait, serta representasi bilangan bulat dalam basis tertentu. Topik 14: Teori Bilangan 2: faktor persekutuan terbesar, kelipatan persekutuan terkecil, algoritma Euclid untuk mencari faktor persekutuan terbesar, serta kongruensi linier dan solusinya. Navigasi Perkuliahan Mandiri Berbasis E-learning Diagram berikut menggambarkan sebuah navigasi pembelajaran mandiri berbasis e-learning untuk mata kuliah Matematika Diskrit A: CLO 1 harus diselesaikan sebelum CLO lainnya. Setelah itu, mahasiswa dapat memilih untuk mempelajari CLO 2, CLO 3, atau CLO 4. Ada beberapa penerapan materi CLO 2 dalam CLO 3. Materi pada CLO 4 relatif independent dari materi pada CLO 2 dan CLO 3. Best Practice (Tips and Tricks) Untuk menyelesaikan kuliah ini dengan baik, Anda perlu: berhati-hati dalam memahami konsep yang dijelaskan di slide kuliah dan mengaitkannya dengan materi di bahan perkuliahan lainnya (buku teks), berhati-hati dan serius dalam mengerjakan kuis sebelum batas waktu yang ditentukan, menyelesaikan dan mengumpulkan tugas (PR) yang diberikan untuk setiap topik, dan aktif berdiskusi terkait materi dengan asisten perkuliahan di forum yang disediakan di CeLoE. Sertifikasi Terkait Mengingat mata kuliah Matematika Diskit A adalah mata kuiah teori fundamental dalam bidang informatika, maka tidak ada sertifikasi khusus yang terkait dengan perkuliahan ini. Meskipun demikian, mata kuliah ini mendukung pola pikir logis dan kritis yang diperlukan dalam beberapa sertifikasi tertentu, contohnya Graduate Record Examination (GRE). Referensi Perkuliahan Referensi utama (buku): K. H. Rosen, Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill, 2012. Referensi pendukung (buku): S. S. Epp. Discrete Mathematics with Applications, 4th Edition. Brooks/ Cole Cengage Learning, 2011 (referensi pendukung utama). T. Jenkyns, B. Stephenson. Fundamentals of Discrete Math for Computer Science. Springer, 2013 ( referensi latihan dan penyelesaian masalah ). K. L. Bogart, R.L. Drysdale, and C. Stein. Discrete Mathematics for Computer Science. Key College Pub., 2006. D. Liben-Nowell. Discrete Mathematics for Computer Science. John Wiley & Sons, 2017. R. Munir, Matematika Diskrit (5th edition [revised]), Informatika, 2012 (in Bahasa Indonesia). Buku elektronik gratis: E. Lehman, T. Leighton, and A. R. Meyer. Mathematics for Computer Science. Lecure notes at MIT, 2017. Tim Pengajar Muhammad Arzaki (koordinator). Bambang Ari Wahyudi.

Course Syllabus

https://telkomuniversityofficial.sharepoint.com/CELOE/msh2a3/Shared%20Documents/Opening%20Video%20Matematika%20Diskrit-MZI.mp4 Identitas Mata Kuliah Nama Mata Kuliah: Matematika Diskret A Kode: MSH2A3 Semester (Tahun): 2 (tahun pertama). SKS: 3 SKS. Program Studi: S1 Informatika. Fakultas: Fakultas Informatika. Profil dan Sejarah Mata Kuliah Mata kuliah Matematika Diskret A memberikan paparan yang rinci terkait struktur diskret dan sifat-sifatnya yang relevan untuk ilmu komputer. Kuliah ini mendukung materi struktur diskrit yang digunakan pada struktur data dan fondasi relevan lain dalam algoritma. Ada tempat topik utama dalam kuliah ini yang berkaitan dengan empat capaian pembelajaran (course learning outcomes, CLO), yaitu: CLO 1: relasi, fungsi, dan rekurensi , CLO 2: kombinatorika , CLO 3: graf dan pohon , dan CLO 4: teori bilangan elementer . Topik pertama membahas relasi, fungsi, dan relasi rekurensi homogen sederhana. Mahasiswa mempelajari definisi relasi dan fungsi beserta representasi dan karakteristik matematisnya. Selain itu mahasiswa juga mempelajari relasi rekurensi yang akan digunakan selanjutnya dalam analisis algoritma. Topik kedua terkait matematika kombinatorika. Mahasiswa mempelajari dasar teknik berhitung, prinsip sarang merpati, serta permutasi dan kombinasi beserta perumumannya. Tingkat kepahaman mahasiswa terkait CLO 1 dan CLO 2 akan dievaluasi secara komprehensif pada UTS. Topik ketiga terkait graf dan pohon. Pada topik ini mahasiswa akan mengkaji definisi formal graf, sifat-sifat graf, dan beberapa algoritma graf elementer (pencarian lintasan terpendek, pewarnaan graf, dan konstruksi pohon perentang minimum). Terakhir, pada topik ke empat mahasiswa mengkaji teori bilangan elementer, yang meliputi keterbagian, faktor persekutuan terbesar dan kelipatan persekutuan terkecil beserta aplikasinya, dan aritmetika modular elementer. Materi pada CLO 3 dan CLO 4 diuji secara komprehensif pada UAS. Sebelum penerapan kurikulum 2016, Matematika Diskret A dikenal sebagai Matematika Diskret untuk Program Studi S1 Informatika di Fakultas Informatika, Telkom University. Kuliah ini diberikan di semester kedua pada tahun kedua dengan kode MUG2A3. Sebelum tahun 2014, kuliah ini tidak mencakup materi teori bilangan elementer. Materi teori bilangan elementer ditambahkan karena materi tersebut relevan dengan Kriptografi - yang merupakan salah satu mata kuliah pilihan yang ditawarkan di tahun ketiga. Selain itu, sebelum penerapan kurikulum 2016, kuliah ini mencakup teori himpunan dan tidak mengkaji relasi rekurensi. Sejak semester pertama pada 2016-2018, materi teori himpunan elementer dibahas di kuliah Logika Matematika dan relasi rekurensi ditambahkan setelah kajian relasi dan fungsi. Penambahan materi dilakukan karena relasi rekurensi penting dan relevan dalam kajian algoritma rekursif pada analisis algoritma, yang diberikan pada kuliah Desain dan Analisis Algoritma. Dibandingkan dengan Matematika Diskret pada kurikulum 2012, kuliah ini mengalami perubahan signifikan pada kurikulum 2016 untuk membuatnya sesuai dengan ACM Computing Curricula. Saat ini Matematika Diskret A mencakup 27 topik, 89% di antaranya diklasifikasikan sebagai topik tier 1. Relevansi Matematika Diskret A dalam Program Studi S1 Informatika Matematika Diskrit A adalah mata kuliah wajib yang fundamental untuk program studi S1 Informatika. Berdasarkan ACM Computing Curricula tahun 2013 untuk bidang Ilmu Komputer, sekitar 13% dari waktu perkuliahan pada program Ilmu Komputer harus dialokasikan untuk kajian struktur diskrit atau yang terkait. Bersama dengan Logika Matematika A dan mata kuliah lain yang terkait struktur diskrit, Matematika Diskrit A mencakup hampir 12% dari jam perkuliahan pada kurikulum 2016. Matematika Diskrit A mencakup 27 topik pada ACM Computing Curricula, 89% termasuk dalam kategori tier 1, dan sisanya termasuk dalam tier 2. Keterkaitan dengan Mata Kuliah Lain Matematika Diskrit A adalah mata kuliah fundamental pada program studi S1 Teknik Informatika. Prasyarat dari mata kuliah ini adalah: Logika Matematika A (semester satu, tahun pertama). Kalkulus 1 B (semester satu, tahun pertama). Matematika Diskrit A adalah co-syarat dari mata kuliah Matriks dan Ruang Vektor (yang diberikan di semester yang sama), dan merupakan prasyarat dari mata kuliah berikut: Kuliah wajib: Teori Bahasa dan Automata (semester satu, tahun kedua). Kuliah wajib: Desain dan Analisis Algoritma (semester dua, tahun kedua). Kuliah wajib: Kecerdasan Buatan (semester satu, tahun ketiga). Kuliah wajib: Dasar Pemodelan dan Simulasi (semester dua, tahun ketiga). Kuliah pilihan: Kriptografi. Kuliah pilihan: Metode Formal. Kuliah pilihan: Topik Khusus 2 ICM: Pemrograman Logika. Capaian Program dan Capaian Pembelajaran Capaian Program (Program Outcome): PO 5: kemampuan menerapkan pengetahuan matematika, ilmu pengetahuan alam, bahasa, teknologi informasi, dan keteknikan untuk mendapatkan pemahaman menyeluruh tentang prinsip-prinsip informatika. Capaian Pembelajaran (Course Learning Outcome, CLO): CLO 1: mahasiswa memiliki kemampuan dalam mengidentifikasi karakteristik relasi, fungsi, dan relasi rekurensi serta menerapkan teknik baku dalam menyelesaikan masalah-masalah matematika yang terkait dengan hal-hal tersebut. CLO 2: mahasiswa memiliki kemampuan dalam mengidentifikasi masalah kombinatorika dasar dan menerapkan metode matematis yang sesuai untuk menyelesaikan masalah-masalah tersebut. CLO 3: mahasiswa mampu mengidentifikasi karakteristik graf dan pohon serta mendemonstrasikan algoritma yang terkait dengan struktur-struktur tersebut. CLO 4: mahasiswa mampu melakukan kalkulasi terkait teori bilangan elementer, seperti: kalkulasi faktor persekutuan terbesar, kelipatan persekutuan terkecil, dan melakukan operasi aritmetika modular elementer. Setiap CLO relatif independen satu sama lain. Meskipun begitu, beberapa konsep elementer pada CLO 1 digunakan pada CLO 2, CLO 3, dan CLO 4. Hubungan dan kebergantungan antar capaian pembelejaran digambarkan sebagai berikut: Beberapa konsep elementer pada materi relasi, fungsi, dan rekurensi digunakan di kajian kombinatirka, graf dan pohon, serta teori bilangan elementer. Materi pada CLO 2 dan CLO 3 relatif independent, meskipun beberapa (tapi tidak semua) masalah pada graf dan pohon memerlukan penyelesaian masalah kombinatorial. Materi pada CLO 4 relatif tidak terkait dengan materi pada CLO 2 dan CLO 3. Topik Pokok Bahasan per Pekan Empat capaian pembelajaran (CLO) dibagi ke dalam 14 topik mingguan sebagai berikut: Topik 1: Relasi: produk kartesius, relasi biner dan representasinya (dengan matriks dan digraf), sifat-sifat relasi biner (refleksif, irefleksif, simetris, antisimetris, asimetris, dan transitif), dan relasi komposisi. Topik 2: Fungsi: definisi dan representasi fungsi, sifat-sifat fungsi total (injektif, surjektif, dan bijektif), komposisi fungsi, fungsi invers, serta fungsi lantai (floor) dan atap (ceiling). Topik 3: Relasi Rekurensi: definisi relasi rekurensi dan solusinya, pemodelan sederhana untuk relasi rekurensi, serta solusi umum dari relasi rekurensi linier berkoefisien konstan. Topik 4: Teknik Berhitung (Pencacahan) Dasar: relevansi kombinatorika dalam ilmu computer, aturan penjumlahan dan penerapannya, aturan perkalian dan penerapannya, aturan pengurangan (prinsip inklusi-eksklusi) dan penerapannya, serta aturan pembagian dan penerapannya. Topik 5: Prinsip Sarang Merpati: definisi prinsip sarang merpati, penerapan prinsip sarang merpati, dan penyelesaian masalah kombinatorika dengan prinsip sarang merpati. Topik 6: Permutasi, Kombinasi, dan Generalisasinya: permutasi dan penerapannya, kombinasi dan penerapannya, permutasi yang diperumum dan aplikasinya, serta kombinasi yang diperumum dan aplikasinya. Topik 7: Graf 1: definisi informal dan formal dari graf, terminologi elementer pada graf (ketetanggaan, lingkungan, derajat, dan graf sederhana), subgraf, subgraf perentang, graf komplemen, graf gabungan, serta representasi graf dengan matriks dan daftar (list). Topik 8: Graf 2: isomorfisma graf, keterhubungan pada graf, lintasan dan sirkuit Euler, serta lintasan dan sirkuit Hamilton. Topik 9: Graf 3: graf planar, formula Euler untuk graf planar, penentuan planaritas dengan teorema Kuratowski, pewarnaan graf, algoritma Welsh-Powell, dan aplikasi dari pewarnaan graf. Topik 10: Graf 4: masalah lintasan terpendk, algoritma Dijsktra, masalah pedanganh keliling, dan masalah tukang pos Tiongkok. Topik 11: Pohon 1: definisi pohon, hutan, dan hal-hal terkait, terminologi pada pohon berakar, dan sifat-sifat dasar pohon berakar. Topik 12: Pohon 2: definisi pohon perentang dan pohon perentang minimum, algoritma Prim, algoritma Kruskal, dan aplikasi pohon. Topik 13: Teori Bilangan 1: teorema pembagian dan penerapannya, bilangan prima dan algoritma terkait, serta representasi bilangan bulat dalam basis tertentu. Topik 14: Teori Bilangan 2: faktor persekutuan terbesar, kelipatan persekutuan terkecil, algoritma Euclid untuk mencari faktor persekutuan terbesar, serta kongruensi linier dan solusinya. Navigasi Perkuliahan Mandiri Berbasis E-learning Diagram berikut menggambarkan sebuah navigasi pembelajaran mandiri berbasis e-learning untuk mata kuliah Matematika Diskrit A: CLO 1 harus diselesaikan sebelum CLO lainnya. Setelah itu, mahasiswa dapat memilih untuk mempelajari CLO 2, CLO 3, atau CLO 4. Ada beberapa penerapan materi CLO 2 dalam CLO 3. Materi pada CLO 4 relatif independent dari materi pada CLO 2 dan CLO 3. Best Practice (Tips and Tricks) Untuk menyelesaikan kuliah ini dengan baik, Anda perlu: berhati-hati dalam memahami konsep yang dijelaskan di slide kuliah dan mengaitkannya dengan materi di bahan perkuliahan lainnya (buku teks), berhati-hati dan serius dalam mengerjakan kuis sebelum batas waktu yang ditentukan, menyelesaikan dan mengumpulkan tugas (PR) yang diberikan untuk setiap topik, dan aktif berdiskusi terkait materi dengan asisten perkuliahan di forum yang disediakan di CeLoE. Sertifikasi Terkait Mengingat mata kuliah Matematika Diskit A adalah mata kuiah teori fundamental dalam bidang informatika, maka tidak ada sertifikasi khusus yang terkait dengan perkuliahan ini. Meskipun demikian, mata kuliah ini mendukung pola pikir logis dan kritis yang diperlukan dalam beberapa sertifikasi tertentu, contohnya Graduate Record Examination (GRE). Referensi Perkuliahan Referensi utama (buku): K. H. Rosen, Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill, 2012. Referensi pendukung (buku): S. S. Epp. Discrete Mathematics with Applications, 4th Edition. Brooks/ Cole Cengage Learning, 2011 (referensi pendukung utama). T. Jenkyns, B. Stephenson. Fundamentals of Discrete Math for Computer Science. Springer, 2013 ( referensi latihan dan penyelesaian masalah ). K. L. Bogart, R.L. Drysdale, and C. Stein. Discrete Mathematics for Computer Science. Key College Pub., 2006. D. Liben-Nowell. Discrete Mathematics for Computer Science. John Wiley & Sons, 2017. R. Munir, Matematika Diskrit (5th edition [revised]), Informatika, 2012 (in Bahasa Indonesia). Buku elektronik gratis: E. Lehman, T. Leighton, and A. R. Meyer. Mathematics for Computer Science. Lecure notes at MIT, 2017. Tim Pengajar Muhammad Arzaki (koordinator). Bambang Ari Wahyudi.
Course Modules
Announcements
Pengumuman Perkuliahan
Dokumen Pendukung
RPS Matematika Diskrit A
Pendahuluan Perkuliahan
EN: Course Introduction
Selamat datang di Topik 1 mengenai Relasi. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: menuliskan hasil produk Kartesius dari beberapa himpunan berhingga dengan notasi yang benar. LO-02: menuliskan relasi biner dengan notasi yang benar. LO-03: merepresentasikan relasi biner dengan matriks dan digraf. LO-04: dapat menentukan sifat-sifat yang terdapat pada relasi biner, yaitu sifat refleksif dan irefleksif sifat simetris, antisimetis, dan asimetris, dan sifat transitif LO-05: menentukan komposisi dua atau lebih relasi.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 1
EN: Course Materials 1
Online Quiz
Online Quiz 1: Relasi
Assignments
Assignment 1: Relation
Discussion Forum
Forum Diskusi Materi Topik 1: Relasi
External Links
Some important properties of a binary relation
Operations on binary relations
How to easily calculate Boolean product
Selamat datang di Topik 2 mengenai Fungsi. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi fungsi dan metode representasinya. LO-02: menentukan sifat-sifat fungsi total berdasarkan karakteristik pemetaannya, yaitu: fungsi injektif, fungsi surjekif, dan fungsi bijektif. LO-03: menentukan komposisi dari dua atau lebih fungsi. LO-04: menentukan invers dari suatu fungsi bijektif sederhana. LO-05: melakukan kalkulasi standar dengan fungsi lantai (floor) dan fungsi atap (ceiling).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 2
EN: Course Materials 2
Online Quiz
Online Quiz 2: Fungsi
Assignments
Assignment 2: Function
Discussion Forum
Forum Diskusi Materi Topik 2: Fungsi
External Links
Youtube video: injective, surjective, and bijective function
Floor and ceiling functions
Khan academy: composing functions
Selamat datang di Topik 3 mengenai Relasi Rekurensi. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi dari relasi rekurensi dan relevansinya dalam ilmu komputer. LO-02: mampu memodelkan masalah sederhana dengan relasi rekurensi. LO-03: memahami karakteristik relasi rekurensi linier homogen berkoefisien konstan. LO-04: mampu mencari solusi dari relasi rekurensi linier homogen berkoefisien konstan.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 3
EN: Course Materials 3
Online Quiz
Online Quiz 3: Relasi Rekurensi
Assignments
Assignment 3: Recurrence Relation
Discussion Forum
Forum Diskusi Materi Topik 3: Relasi Rekurensi
External Links
Khan academy: recursively defined function (sequence)
How to get characteristic equation from a recurrence relation
Solving recurrence relations
Selamat datang di Topik 4 mengenai Aturan Dasar Berhitung (Pencacahan). Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: menyadari relevansi kombinatorika dalam informatika. LO-02: mampu menerapkan aturan penjumlahan untuk menyelesaikan masalah kombinatorika. LO-03: mampu menerapkan aturan perkalian untuk menyelesaikan masalah kombinatorika. LO-04: mampu menerapkan aturan pengurangan (prinsip inklusi-eksklusi) untuk menyelesaikan masalah kombinatorika. LO-05: mampu menerapkan aturan pembagian untuk menyelesaikan masalah kombinatorika.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 4
EN: Course Materials 4
Online Quiz
Online Quiz 4: Teknik Berhitung (Pencacahan) Dasar
Assignments
Assignment 4: Basic Counting Techniques
Discussion Forum
Forum Diskusi Materi Topik 4: Teknik Berhitung (Pencacahan) Dasar
External Links
Rule of sum and rule of product: problem solving
Principle of inclusion and exclusion
Division rule: why and how
Selamat datang di Topik 5 mengenai Prinsip Sarang Merpati. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: memahami definisi prinsip sarang merpati. LO-02: mampu menentukan "merpati" dan "sarangnya" dalam masalah kombinatorika terkait prinsip sarang merpati. LO-03: dapat menyelesaikan masalah kombinatorika menggunakan prinsip sarang merpati yang diperumum.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 5
EN: Course Materials 5
Online Quiz
Online Quiz 5: Prinsip Sarang Merpati
Assignments
Assignment 5: Pigeonhole Principle
Discussion Forum
Forum Diskusi Materi Topik 5: Prinsip Sarang Merpati
External Links
Youtube video: Pigeonhole Principle from Math in CS (MIT)
Pigeonhole principle (by brilliant.org)
Problem solving practice: pigeonhole principle
Selamat datang di Topik 6 mengenai Permutasi, Kombinasi, dan Perumumannya. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mampu menerapkan permutasi untuk menyelesaikan masalah kombinatirika. LO-02: mampu menerapkan kombinasi untuk menyelesaikan masalah kombinatorika. LO-03: mampu menerapkan permutasi yang diperumum (dengan pengulangan, dengan objek identik) untuk menyelesaikan masalah kombinatorika. LO-04: mampu menerapkan kombinasi yang diperumum (dengan pengulangan, dengan objek identik) untuk menyelesaikan masalah kombinatorika. LO-05: mampu menerapkan kombinasi untuk menghitung koefisien binomial dari suatu ekspansi aljabar sederhana (suplemen).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 6.1
EN: Course Materials 6.1
Materi Kuliah Topik 6.2
EN: Course Materials 6.2
Materi Kuliah Topik 6.3 (Suplemen)
EN: Course Materials 6.3 (Supplementary)
Online Quiz
Online Quiz 6: Permutasi, Kombinasi, dan Perumumannya
Assignments
Assignment 6: Permutation and Combination
Discussion Forum
Forum Diskusi Materi Topik 6: Permutasi, Kombinasi, dan Perumumannya
External Links
Permutations (from brilliant.org)
Permutation with repetition (from brilliant.org)
Permutations with restrictions (from brilliant.org)
Combinations (from brilliant.org)
Youtube video: combinations with repetition
Permutations (concept quiz)
Combinations: concept quiz
Selamat datang di Topik 7 mengenai Graf Bagian 1. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui motivasi dan relevansi teori graf dalam informatika. LO-02: mengetahui beberapa definisi formal graf. LO-03: mengetahui terminology-terminologi dasar dalam teori graf. LO-04: mampu mementukan subgraf, subgraf perentang, graf komplemen, dan graf gabungan dari graf-graf sederhana. LO-05: mampu merepresentasikan graf dengan matriks dan daftar ketetanggaan.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 7
EN: Course Materials 7
Online Quiz
Online Quiz 7: Graf (Bagian 1)
Assignments
Assignment 7: Graphs (Part 1)
Discussion Forum
Forum Diskusi Materi Topik 7: Graf (Bagian 1)
External Links
Some basic definitions and terminologies in graph theory
Bipartite graph (from mathworld.wolfram.com)
Graph representation using adjacency matrix and adjacency list
Selamat datang di Topik 8 mengenai Graf Bagian 2. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mampu mengidentifikasi apakah dua graf sederhana bersifat isomorfik atau tidak. LO-02: mengetahui terminologi dasar terkait keterhubungan pada graf (lintasan dan sirkuit). LO-03: dapat menentukan banyaknya lintasan dengan panjang tertentu pada suatu graf sederhana. LO-04: dapat menentukan lintasan dan sirkuit Euler pada graf sederhana. LO-05: dapat menentukan lintasan dan sirkuit Hamilton pada gaf sederhana.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 8
EN: Course Materials 8
Online Quiz
Online Quiz 8: Graf (Bagian 2)
Assignments
Assignment 8: Graphs (Part 2)
Discussion Forum
Forum Diskusi Materi Topik 8: Graf (Bagian 2)
External Links
Youtube video: graph isomorphism
Youtube video: Euler paths and circuits
Euler path explanation (from brilliant.org)
Euler path practice problem sets (from brilliant.org)
Youtube video: Hamilton path and circuit
Hamilton path explanation (from brilliant.org)
Hamilton path practice problem sets (from brilliant.org)
Selamat datang di Topik 9 mengenai Graf 3 Bagian 3. Setelah menyelesaikan topik ini. Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi graf planar dan beberapa contoh graf planar. LO-02: mampu menentukan planaritas dari suatu graf menggunakan rumus Euler. LO-03: mampu menentukan planaritas dari suatu graf menggunakan Teorema Kuratowski. LO-04: mengetahui definisi pewarnaan graf (pewarnaan simpul) dan bilangan kromatik untuk graf sederhana. LO-05: mampu menerapkan algoritma Welsh-Powell untuk pewarnaan graf. LO-06: mampu menerapkan masalah pewarnaan graf untuk menyelesaikan masalah kombinatorial sederhana (contoh: penjadwalan).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 9
EN: Course Materials 9
Online Quiz
Online Quiz 9: Graf (Bagian 3)
Assignments
Assignment 9: Graphs (Part 3)
Discussion Forum
Forum Diskusi Materi Topik 9: Graf (Bagian 3)
External Links
Planar graphs: an introduction
Youtube video: an explanation of Euler formula for planar graph
Youtube video: characterization of planar graphs and Kuratowski's theorem
Youtube video: Welsh-Powell algorithm
Welsh-Powell algorithm (original paper)
Graph coloring materials (geeksforgeeks.org)
Selamat datang di Topik 10 mengenai Graf Bagian 4. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi malasah lintasan terpendek (shortest path problem) dari sebuah graf berbobot (weigthed graph) dengan bobot non-negatif. LO-02: mampu menerapkan algoritma Dijkstra untuk menentukan lintasan terpendek dari suatu simpul ke simpul tertentu yang lain. LO-03: mengetahui definisi masalah pedagang keliling (traveling salesperson problem). LO-04: mengetahui definisi masalah tukang pos Tiongkok (Chinese postman problem).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 10
EN: Course Materials 10
Online Quiz
Online Quiz 10: Graf (Bagian 4)
Assignments
Assignment 10: Graphs (Part 4)
Discussion Forum
Forum Diskusi Materi Topik 10: Graf (Bagian 4)
External Links
Dijkstra's algorithm (from geeksforgeeks.org)
Dijkstra's algorithm explanation (from medium.com)
Youtube video: Dijkstra's algorithm: tabular method
Travelling salesman problem (from geeksforgeeks.org)
Chinese postman problem (or route inspection problem)
Selamat datang di Topik 11 mengenai Pohon Bagian 1. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: memahami definisi pohon, hutan, dan teorema-teorema dasar terkait. LO-02: memahami definisi pohon berakar, terminology terkait pohon (contohnya orangtua, anak, derajat, tingkat, dan ketinggian, dan terminology lanjut seperti pohon m-ary, pohon regular, dan pohon seimbang). LO-03: memahami sifat-sifat dasar terkait pohon berarakar.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 11
Course Materials 11
Online Quiz
Online Quiz 11: Pohon (Bagian 1)
Assignments
Assignment 11: Trees (Part 1)
Discussion Forum
Forum Diskusi Materi Topik 11: Pohon (Bagian 1)
External Links
Binary tree data structure
Youtube video: introduction to tree.
Some theorems pertaining to tree
Selamat datang di Topik 12 mengenai Pohon Bagian 2. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi pohon perentang (spanning tree) dari suatu graf dan pohon perentang minimum (minimum spanning tree) dari suatu graf berbobot. LO-02: mampu menentukan pohon perentang minimum (minimum spanning tree) dari suatu graf berbobot menggunakan Algoritma Prim dan Kruskal. LO-03: mengetahui definisi traversal pada pohon dan jenis-jenisnya, yaitu traversal preorder, postorder, dan inorder (materi suplemen). LO-04: mengetahui penerapan pohon untuk pohon urai (parse tree) dan pohon keputusan (decision tree) (materi suplemen).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 12
EN: Course Materials 12
Online Quiz
Online Quiz 12: Pohon (Bagian 2)
Assignments
Assignment 12: Trees (Part 2)
Discussion Forum
Forum Diskusi Materi Topik 12: Pohon (Bagian 2)
External Links
Minimum spanning tree (explanation and source code, hackerearth.com, English version)
Minimum spanning tree (explanation and source code, hackerearth.com, Bahasa Indonesia version)
Youtube video: Prim's algorithm
Youtube video: Kruskal's algorithm
Tree traversal (from geeksforgeeks.org)
Selamat datang di Topik 13 mengenai Teori Bilangan Bagian 1. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui teorema keterbagian dan penerapannya untuk menghitung fungsi mod dan div. LO-02: mengetahui definisi bilangan prima, bilangan komposit, faktorisasi prima, dan algoritma untuk memeriksa primalitas bilangan. LO-03: merepresentasikan bilangan bulat dalam basis tertentu, terutama basis 2 (biner), basis 8 (oktal), dan basis 16 (heksadesimal).
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 13
EN: Course Materials 13
Online Quiz
Online Quiz 13: Teori Bilangan Elementer (Bagian 1)
Assignments
Assignment 13: Number Theory (Part 1)
Discussion Forum
Forum Diskusi Materi Topik 13: Teori Bilangan Elementer (Bagian 1)
External Links
Several primality testing algorithm (from brilliant.org)
Khan academy: sieve of Eratothenes
Khan academy: introduction to number system
Youtube video (TedEd): a history of numerical system (by Alessandra King)
Selamat datang di Topik 14 mengenai Teori Bilangan Bagian 2. Setelah menyelesaikan topik ini, Anda diharapkan menguasai capaian berikut: LO-01: mengetahui definisi gcd dan lcm serta kalkulasinya menggunakan faktorisasi prima LO-02: mampu menerapkan algoritma Euclid untuk menghitung gcd dari beberapa bilangan. LO-03: mengetahui definisi kongruensi linier sederhana. LO-04: mampu mencari solusi dari kongruensi linier sederhana. LO-05: mengetahui penerapan teori bilangan, yaitu penyelesaian masalah dengan Chinese Remainder Theorem dan model masalah matematis pada Diffie-Hellman Key Exchange.
Course Modules
Course Materials (Slides)
Materi Kuliah Topik 14.1
EN: Course Materials 14.1
Materi Kuliah Topik 14.2 (Suplemen)
EN: Course Materials 14.2 (Supplementary)
Online Quiz
Online Quiz 14: Teori Bilangan Elementer (Bagian 2)
Assignments
Assignment 14: Number Theory (Part 2)
Discussion Forum
Forum Diskusi Materi Topik 14: Teori Bilangan Elementer (Bagian 2)
External Links
Khan academy exercise: greatest common factor and least common multiple word problems
Euclidean algorithm (basic and extended, with source code)
Solving linear congruences
Modular arithmetic (by brilliant.org)
Chinese remainder theorem (from brilliant.org)