Matematika Diskret

📚 Ringkasan Konten

Kursus pengantar matematika diskret untuk mahasiswa matematika dan ilmu komputer. Kursus ini mencakup topik dasar seperti logika, himpunan, teknik pembuktian, algoritma, teori bilangan, kombinatorika, teori graf, dan otomata. Kursus ini menekankan kemampuan berpikir matematis dan pemecahan masalah yang diperlukan untuk studi lanjutan di bidang ilmu komputer.

Menguasai logika dan struktur yang menjadi dasar dari ilmu komputer.

Penulis: Richard Johnsonbaugh

Ucapan Terima Kasih: Para reviewer termasuk Venkata Dinavahi, Matthew Elsey, Christophe Giraud-Carrier, Yevgeniy Kovchegov, Filix Maisch, Tyler McMillen, Christopher Storm, Donald Vestal, dan Guanghua Zhao. Dukungan dari staf Pearson: Deirdre Lynch, Jeff Weidenaar, Lauren Morse, dan lainnya.

🎯 Tujuan Pembelajaran

1. Melakukan operasi pada himpunan, termasuk selisih dan komplemen, serta memverifikasi identitas himpunan menggunakan diagram Venn dan Teorema 1.1.22.
2. Membuat dan mengevaluasi tabel kebenaran untuk proposisi yang melibatkan negasi, disjungsi, dan pernyataan bersyarat.
3. Menerapkan aturan inferensi dan penalaran deduktif untuk menentukan validitas argumen logika.
4. Mendefinisikan dan menerapkan komponen sistem matematis, termasuk aksioma, definisi, dan teorema.
5. Membangun bukti langsung, bukti kontradiksi, dan bukti kasus untuk proposisi aljabar dan teori himpunan.
6. Menggunakan Prinsip Induksi Matematis dan Induksi Kuat untuk membuktikan identitas, sifat pembagian, dan kebenaran algoritma.
7. Mendefinisikan dan mengklasifikasikan fungsi (injektif, surjektif, bijektif) serta melakukan operasi seperti komposisi dan inversi.
8. Menerapkan notasi barisan, konkatenasi string, dan aturan rekursif untuk memodelkan himpunan data diskret.
9. Menganalisis relasi biner terhadap sifat-sifat seperti refleksivitas, simetri, dan transitivitas menggunakan digraf dan representasi matriks.
10. Mendefinisikan algoritma dan memverifikasi tujuh properti intinya (Masukan, Keluaran, Presisi, Determinisme, Finitas, Keberhasilan, dan Umumitas).

🔹 Pelajaran 1: Dasar-Dasar Logika dan Teori Himpunan

Gambaran Umum: Pelajaran ini membangun blok-blok dasar matematika diskret, dengan fokus pada manipulasi ketat himpunan dan struktur formal logika. Siswa akan berkembang dari operasi himpunan dan identitas ke pembuatan argumen logika, evaluasi proposisi bersyarat, dan analisis kuantifikasi bersarang. Konsep-konsep ini menyediakan kerangka esensial untuk desain algoritma, teori basis data, dan verifikasi formal dalam ilmu komputer dan teknik.

Hasil Pembelajaran:

• Melakukan operasi pada himpunan, termasuk selisih dan komplemen, serta memverifikasi identitas himpunan menggunakan diagram Venn dan Teorema 1.1.22.
• Membuat dan mengevaluasi tabel kebenaran untuk proposisi yang melibatkan negasi, disjungsi, dan pernyataan bersyarat.
• Menerapkan aturan inferensi dan penalaran deduktif untuk menentukan validitas argumen logika.

🔹 Pelajaran 2: Teknik Pembuktian Matematis

Gambaran Umum: Pelajaran ini membahas metodologi formal yang digunakan untuk menetapkan validitas pernyataan matematis dan ketelitian logika yang diperlukan dalam ilmu komputer dan matematika. Siswa akan berkembang dari sistem matematis dasar dan bukti langsung hingga teknik canggih seperti bukti resolusi, induksi matematis (termasuk induksi kuat), dan aplikasi invarian loop dalam verifikasi algoritma.

Hasil Pembelajaran:

• Mendefinisikan dan menerapkan komponen sistem matematis, termasuk aksioma, definisi, dan teorema.
• Membangun bukti langsung, bukti kontradiksi, dan bukti kasus untuk proposisi aljabar dan teori himpunan.
• Menggunakan Prinsip Induksi Matematis dan Induksi Kuat untuk membuktikan identitas, sifat pembagian, dan kebenaran algoritma.

🔹 Pelajaran 3: Fungsi, Barisan, dan Relasi

Gambaran Umum: Pelajaran ini membahas struktur matematis dasar yang digunakan untuk memodelkan data dan proses dalam ilmu komputer. Pelajaran ini bergerak dari definisi fungsi dan berbagai jenisnya (injektif, surjektif, bijektif) menuju studi barisan, string, dan sifat formal relasi biner. Siswa akan menjelajahi aplikasi praktis seperti fungsi hash, digit cek ISBN, penjadwalan tugas melalui urutan parsial, serta representasi relasi melalui matriks dan basis data.

Hasil Pembelajaran:

• Mendefinisikan dan mengklasifikasikan fungsi (injektif, surjektif, bijektif) serta melakukan operasi seperti komposisi dan inversi.
• Menerapkan notasi barisan, konkatenasi string, dan aturan rekursif untuk memodelkan himpunan data diskret.
• Menganalisis relasi biner terhadap sifat-sifat seperti refleksivitas, simetri, dan transitivitas menggunakan digraf dan representasi matriks.

🔹 Pelajaran 4: Analisis Algoritma dan Kompleksitas

Gambaran Umum: Pelajaran ini membahas definisi dasar dan sifat algoritma, implementasinya dalam pencarian dan pengurutan (khususnya Pencarian Teks dan Pengurutan Sisipan), serta kerangka matematis ketat yang digunakan untuk menganalisis efisiensinya. Siswa akan mengeksplorasi notasi asimtotik, tingkat pertumbuhan fungsi, dan mekanisme pemecahan masalah rekursif, termasuk strategi bagi dan taklukkan seperti pemolesan papan dan barisan berbasis Fibonacci.

Hasil Pembelajaran:

• Mendefinisikan algoritma dan memverifikasi tujuh properti intinya (Masukan, Keluaran, Presisi, Determinisme, Finitas, Keberhasilan, dan Umumitas).
• Menerapkan notasi Big-O, Omega, dan Theta untuk menyatakan kompleksitas waktu dan ruang algoritma.
• Menganalisis skenario terbaik, terburuk, dan rata-rata menggunakan teknik seperti pembagian dua berulang dan pengurutan polinomial.

🔹 Pelajaran 5: Pengantar Teori Bilangan dan Kriptografi

Gambaran Umum: Pelajaran ini mengeksplorasi prinsip-prinsip dasar teori bilangan, mulai dari sifat dasar pembagi dan bilangan prima hingga algoritma rumit yang menjadi dasar komunikasi aman modern. Siswa akan menguasai mekanisme matematis GCD (Faktor Persekutuan Terbesar), konversi basis, dan eksponensiasi modular untuk memahami dan menerapkan sistem kriptografi publik RSA.

Hasil Pembelajaran:

• Mendefinisikan dan menerapkan konsep divisibilitas, primality, dan Teorema Fundamental Arithmetika.
• Melakukan konversi efisien antara sistem bilangan desimal, biner, dan heksadesimal.
• Menjalankan Algoritma Euclidean dan bentuk ekstensinya untuk mencari GCD dan kombinasi linear (sa + tb).

🔹 Pelajaran 6: Metode Menghitung dan Probabilitas Diskret

Gambaran Umum: Pelajaran ini mengeksplorasi teknik dasar untuk menghitung struktur hingga dan penerapannya dalam probabilitas diskret. Siswa akan berkembang dari prinsip dasar penjumlahan dan perkalian hingga konsep canggih seperti angka Catalan, angka Stirling, dan Teorema Binomial. Pelajaran ini berakhir dengan Prinsip Sarang Burung dan berbagai bentuknya, memberikan kerangka ketat untuk membuktikan keberadaan konfigurasi tertentu dalam sistem diskret.

Hasil Pembelajaran:

• Menerapkan Prinsip Penjumlahan, Perkalian, dan Inklusi-Eksklusi untuk menyelesaikan masalah perhitungan kompleks.
• Membedakan dan menghitung permutasi serta kombinasi, termasuk kasus objek identik dan pengulangan.
• Menggunakan algoritma generatif untuk permutasi dan kombinasi secara urutan leksikografis.

🔹 Pelajaran 7: Relasi Rekurens

Gambaran Umum: Pelajaran ini mengeksplorasi teori dan aplikasi relasi rekurens dalam matematika dan ilmu komputer. Siswa akan belajar menyelesaikan relasi ini menggunakan iterasi dan persamaan karakteristik baik untuk bentuk homogen maupun non-homogen. Selain itu, pelajaran ini menunjukkan bagaimana relasi rekurens merupakan alat penting untuk menganalisis kompleksitas waktu algoritma rekursif seperti Pengurutan Seleksi, Pencarian Biner, dan Pengurutan Gabungan.

Hasil Pembelajaran:

• Menyelesaikan relasi rekurens menggunakan Metode Iterasi dan Persamaan Karakteristik (untuk akar-akar berbeda dan sama).
• Memodelkan dan menyelesaikan masalah matematis klasik, termasuk Menara Hanoi, Deret Fibonacci (Rasio Emas), dan Derangement.
• Menganalisis kompleksitas waktu terburuk algoritma rekursif menggunakan relasi rekurens.

🔹 Pelajaran 8: Teori Graf dan Algoritma Jalur Terpendek

Gambaran Umum: Pelajaran ini mengeksplorasi prinsip dasar Teori Graf, mulai dari definisi dasar graf sederhana dan berbobot hingga solusi algoritmik kompleks untuk jalur terpendek dan identifikasi siklus. Siswa akan menganalisis sifat-struktur seperti planaritas, konektivitas, dan isomorfisme, sambil menerapkan konsep-konsep ini ke masalah klasik seperti Masalah Jembatan Königsberg, Masalah Penjual Keliling (TSP), dan teka-teki Instant Insanity.

Hasil Pembelajaran:

• Mendefinisikan dan membedakan jenis-jenis graf, termasuk graf sederhana, berbobot, lengkap, bipartit, dan n-kubus.
• Menganalisis konektivitas graf untuk mengidentifikasi siklus Euler, siklus Hamiltonian, dan menentukan jalur terpendek menggunakan Algoritma Dijkstra.
• Menerapkan representasi matriks (adjacency dan incidence) dan invarian graf untuk memverifikasi isomorfisme dan planaritas.

🔹 Pelajaran 9: Pohon dan Algoritma Pencarian

Gambaran Umum: Pelajaran ini membahas sifat, karakterisasi, dan aplikasi pohon dalam ilmu komputer dan matematika. Siswa akan menjelajahi pohon bercabang dan pohon biner, algoritma pohon rentang (BFS/DFS), teknik optimasi seperti Algoritma Prim untuk pohon rentang minimal, serta kerangka pengambilan keputusan termasuk backtracking, pengurutan turnamen, dan pohon permainan dengan prosedur minimaks.

Hasil Pembelajaran:

• Mendefinisikan dan mengidentifikasi pohon bercabang, tingkatnya, tinggi, dan struktur hierarkis dalam sistem dunia nyata.
• Karakterisasi pohon berdasarkan konektivitas, tanpa siklus, dan rasio tepi terhadap simpul.
• Menerapkan dan melacak algoritma untuk pohon rentang (BFS, DFS), Pohon Rentang Minimal (Prim), dan pembuatan Pohon Pencarian Biner.

🔹 Pelajaran 10: Model Jaringan dan Optimasi Aliran

Gambaran Umum: Pelajaran ini membahas pemodelan matematis jaringan transportasi, dengan fokus pada bagaimana sumber daya (aliran) bergerak melalui graf berarah dari sumber ke tujuan. Pelajaran ini menjelaskan aturan konservasi aliran, langkah-langkah algoritmik untuk memaksimalkan throughput, hubungan antara potongan jaringan dan kapasitas aliran, serta penerapan prinsip-prinsip ini untuk menyelesaikan masalah pencocokan dalam graf bipartit.

Hasil Pembelajaran:

• Mendefinisikan dan memverifikasi properti jaringan transportasi dan alokasi aliran yang valid.
• Menjalankan Algoritma Aliran Maksimum (Algoritma 10.2.4) untuk menemukan throughput optimal.
• Menerapkan Teorema Aliran Maksimum–Potongan Minimum untuk membuktikan optimalitas aliran menggunakan partisi jaringan.

🔹 Pelajaran 11: Aljabar Boolean dan Sirkuit Logika

Gambaran Umum: Pelajaran ini mengeksplorasi fondasi matematis logika digital, dengan fokus pada bagaimana aljabar Boolean menyediakan bahasa formal untuk merancang dan menyederhanakan sirkuit kombinasional. Siswa akan belajar menerjemahkan antara gerbang logika, rangkaian saklar, dan ekspresi Boolean, akhirnya menerapkan alat-alat ini untuk mensintesis fungsi kompleks dan membuat komponen aritmetika penting seperti penjumlah dan logika komplemen 2.

Hasil Pembelajaran:

• Merancang dan menganalisis sirkuit kombinasional menggunakan gerbang logika standar (AND, OR, NOT) dan konfigurasi saklar.
• Menerapkan hukum aljabar Boolean dan Teorema Dual untuk membuktikan ekuivalensi sirkuit dan menyederhanakan ekspresi.
• Mensintesis fungsi Boolean dari tabel kebenaran ke Bentuk Normal Disjungtif (DNF) dan Bentuk Normal Konjungtif (CNF).

🔹 Pelajaran 12: Otomata, Tata Bahasa, dan Bahasa Formal

Gambaran Umum: Pelajaran ini mengeksplorasi fondasi matematis komputasi, dimulai dari rangkaian urutan dan mesin state hingga model memori internal melalui keterlambatan waktu satuan. Pelajaran ini mencakup definisi formal dan klasifikasi tata bahasa struktur frasa (Tipe 1, 2, dan 3), penerapan Bentuk Normal Backus (BNF), serta penggunaan khusus tata bahasa Lindenmayer untuk generasi fraktal. Akhirnya, pelajaran ini menetapkan hubungan kritis antara otomata state hingga deterministik dan nondeterministik serta bahasa formal yang mereka terima.

Hasil Pembelajaran:

• Menganalisis dan merancang mesin state hingga (FSM) dan otomata (FSA/NFA) menggunakan diagram transisi dan fungsi state.
• Mengklasifikasikan tata bahasa dalam hierarki Chomsky dan menurunkan string menggunakan aturan produksi dan notasi BNF.
• Memodelkan struktur self-similar seperti salju von Koch menggunakan tata bahasa Lindenmayer dan aturan penggantian simultan.