Topic outline

  • MSH2A3 Matematika Diskrit A (Program Studi S1 Informatika)

         
         

    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:

    1. Logika Matematika A (semester satu, tahun pertama).
    2. 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:

    1. Kuliah wajib: Teori Bahasa dan Automata (semester satu, tahun kedua).
    2. Kuliah wajib: Desain dan Analisis Algoritma (semester dua, tahun kedua).
    3. Kuliah wajib: Kecerdasan Buatan (semester satu, tahun ketiga).
    4. Kuliah wajib: Dasar Pemodelan dan Simulasi (semester dua, tahun ketiga).
    5. Kuliah pilihan: Kriptografi.
    6. Kuliah pilihan: Metode Formal.
    7. 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):

    1. 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.
    2. CLO 2: mahasiswa memiliki kemampuan dalam mengidentifikasi masalah kombinatorika dasar dan menerapkan metode matematis yang sesuai untuk menyelesaikan masalah-masalah tersebut.
    3. CLO 3: mahasiswa mampu mengidentifikasi karakteristik graf dan pohon serta mendemonstrasikan algoritma yang terkait dengan struktur-struktur tersebut.
    4. 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:

    1. 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.
    2. 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).
    3. Topik 3: Relasi Rekurensi: definisi relasi rekurensi dan solusinya, pemodelan sederhana untuk relasi rekurensi, serta solusi umum dari relasi rekurensi linier berkoefisien konstan.
    4. 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.
    5. Topik 5: Prinsip Sarang Merpati: definisi prinsip sarang merpati, penerapan prinsip sarang merpati, dan penyelesaian masalah kombinatorika dengan prinsip sarang merpati.
    6. Topik 6: Permutasi, Kombinasi, dan Generalisasinya: permutasi dan penerapannya, kombinasi dan penerapannya, permutasi yang diperumum dan aplikasinya, serta kombinasi yang diperumum dan aplikasinya.
    7. 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).
    8. Topik 8: Graf 2: isomorfisma graf, keterhubungan pada graf, lintasan dan sirkuit Euler, serta lintasan dan sirkuit Hamilton.
    9. 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.
    10. Topik 10: Graf 4: masalah lintasan terpendk, algoritma Dijsktra, masalah pedanganh keliling, dan masalah tukang pos Tiongkok.
    11. Topik 11: Pohon 1: definisi pohon, hutan, dan hal-hal terkait, terminologi pada pohon berakar, dan sifat-sifat dasar pohon berakar.
    12. Topik 12: Pohon 2: definisi pohon perentang dan pohon perentang minimum, algoritma Prim, algoritma Kruskal, dan aplikasi pohon.
    13. Topik 13: Teori Bilangan 1: teorema pembagian dan penerapannya, bilangan prima dan algoritma terkait, serta representasi bilangan bulat dalam basis tertentu.
    14. 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:
    1. berhati-hati dalam memahami konsep yang dijelaskan di slide kuliah dan mengaitkannya dengan materi di bahan perkuliahan lainnya (buku teks),
    2. berhati-hati dan serius dalam mengerjakan kuis sebelum batas waktu yang ditentukan,
    3. menyelesaikan dan mengumpulkan tugas (PR) yang diberikan untuk setiap topik, dan
    4. 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):

    1. S. S. Epp. Discrete Mathematics with Applications, 4th Edition. Brooks/ Cole Cengage Learning, 2011 (referensi pendukung utama).
    2. T. Jenkyns, B. Stephenson. Fundamentals of Discrete Math for Computer Science. Springer, 2013 (referensi latihan dan penyelesaian masalah).
    3. K. L. Bogart, R.L. Drysdale, and C. Stein. Discrete Mathematics for Computer Science. Key College Pub., 2006.
    4. D. Liben-Nowell. Discrete Mathematics for Computer Science. John Wiley & Sons, 2017.
    5. 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

    1. Muhammad Arzaki (koordinator).
    2. Bambang Ari Wahyudi.

  • Topik 1: Relasi

    ArrowDiagram


    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.

  • Topik 2: Fungsi

    Functions


    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).

  • Topik 3: Relasi Rekurensi

    Recurrence


    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.

  • Topik 4: Teknik Berhitung (Pencacahan) Dasar

    Counting


    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.

  • Topik 5: Prinsip Sarang Merpati

    Pigeons


    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.

  • Topik 6: Permutasi, Kombinasi, dan Perumumannya

    Combination


    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).

  • Topik 7: Graf (Bagian 1)

    Digraph


    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.

  • Topik 8: Graf (Bagian 2)

    Isomorphism


    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.

  • Topik 9: Graf (Bagian 3)

    K_4


    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).

  • Topik 10: Graf (Bagian 4)

    Dijkstra


    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).

  • Topik 11: Pohon (Bagian 1)

    RootedTrees


    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.

  • Topik 12: Pohon (Bagian 2)

    MinimumSpanningTree


    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).

  • Topik 13: Teori Bilangan Elementer (Bagian 1)

    PrimalityTesting


    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).

  • Topik 14: Teori Bilangan Elementer (Bagian 2)

    Euclid'sAlgorithm


    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.