Matematika untuk Ilmu Komputer (2018) [PDF]

• Buku teks matematika untuk mahasiswa ilmu komputer dari MIT yang membahas konsep matematika inti secara sistematis, mulai dari logika dan pembuktian hingga probabilitas, rekurensi, dan teori graf
• Terdiri dari lima bagian: pembuktian, struktur, pencacahan, probabilitas, dan relasi rekurensi, dengan setiap bagian membahas fondasi teoretis sekaligus penerapannya dalam ilmu komputer
• Mencakup topik-topik penting untuk pemrograman dan analisis algoritma seperti rumus logika, induksi matematika, mesin status, graf, dan peubah acak
• Menunjukkan penerapan konsep matematika melalui contoh nyata dan soal aplikasi seperti enkripsi RSA, kode Turing, dan masalah Monty Hall
• Buku teks ini ditulis bersama oleh peneliti MIT dan Google, dan dirilis di bawah lisensi Creative Commons BY-SA 3.0 sehingga bebas dipelajari dan digunakan kembali

---

Gambaran umum buku

• Mathematics for Computer Science (MCS) adalah buku teks untuk mata kuliah sarjana ilmu komputer dan teknik elektro MIT (6.042), sebagai materi untuk membangun pemikiran logis dan kemampuan pemodelan matematis
• Penulisnya adalah Eric Lehman (Google Inc.), F. Thomson Leighton (MIT, Akamai Technologies), dan Albert R. Meyer (MIT)
• Edisi revisi tertanggal 6 Juni 2018, didistribusikan di bawah lisensi Creative Commons Attribution-ShareAlike 3.0

I. Proofs (Pembuktian)

• Membahas prinsip dasar pembuktian matematika seperti proposisi, predikat, metode aksiomatik, pembuktian dengan kontradiksi, dan pembuktian per kasus
• Menjelaskan hubungan antara Well Ordering Principle dan induksi, serta penerapannya melalui contoh seperti faktorisasi prima
• Mencakup rumus logika dan logika proposisional, masalah SAT, serta tipe data matematis (himpunan, fungsi, relasi)

II. Structures (Struktur)

• Menyajikan landasan matematis ilmu komputer dengan fokus pada teori bilangan, teori graf, dan struktur jaringan
  • Penerapan teori bilangan seperti bilangan prima, FPB, aritmetika modular, dan enkripsi RSA
  • Penjelasan model struktural seperti graf berarah, urutan parsial, routing jaringan, graf sederhana, dan graf planar
• Membahas kode Turing dan keterkaitannya dengan masalah SAT, menunjukkan hubungan antara teori komputasi dan kriptografi

III. Counting (Pencacahan dan kombinatorika)

• Membahas penjumlahan, perkalian, notasi asimtotik, aturan kombinatorial, dan fungsi pembangkit sebagai teknik perhitungan kombinatorial
• Mencakup contoh praktis seperti prinsip kandang merpati, prinsip inklusi-eksklusi, dan contoh susunan kartu poker
• Diterapkan pada analisis algoritma dan perhitungan deret melalui fungsi pembangkit dan metode penyelesaian relasi rekurensi linear

IV. Probability (Probabilitas)

• Mencakup spektrum penuh teori probabilitas, termasuk ruang probabilitas, probabilitas bersyarat, peubah acak, varians, estimasi sampel, dan random walk
• Termasuk kasus-kasus yang menguji intuisi seperti masalah Monty Hall, paradoks Simpson, dan masalah ulang tahun
• Menyediakan dasar analisis data melalui teorema Markov, teorema Chebyshev, dan sampling acak

V. Recurrences (Relasi rekurensi)

• Membahas topik inti analisis algoritma seperti Menara Hanoi, merge sort, dan relasi rekurensi divide-and-conquer
• Menjelaskan struktur perhitungan yang efisien melalui metode penyelesaian relasi rekurensi linear dan cara berpikir rekursif

Lampiran

• Mencakup daftar pustaka, penjelasan simbol, dan indeks sehingga memudahkan pembelajaran dan rujukan
• Seluruh buku tersedia gratis dalam bentuk PDF di situs web MIT CSAIL

[GN⁺]

Komentar Hacker News

• Menyebut bahwa Thomson Leighton adalah pendiri Akamai, lalu merekomendasikan seri kuliah yang ia bawakan
  Itu adalah salah satu konten kuliah tentang internet yang paling mengesankan yang pernah ia tonton

  • Sebagai materi tambahan, ia juga memperkenalkan video kuliah terbaru dari MIT OCW, serta kuliah Open Learning Library yang dibawakan Albert Meyer, salah satu penulis buku ini
  • Ia menambahkan harapan agar Akamai lebih memperhatikan masalah rentang IPv4 yang digunakan para scanner atau script kiddie

• Susunan tiap bagian cukup standar, tetapi ia menyukai fakta bahwa setiap kutipan disertai rujukan balik ke semua sumbernya
  Ia berharap akan ada lebih banyak buku yang dibuat seperti ini

  • Justru pemilihan materinya terasa tidak standar, sehingga menarik, dan ada humor khas MIT di dalamnya
    Namun, ia menyayangkan bahwa penulisannya terhenti setelah 2018

• Ia sangat menyukai buku ini. Tingkat kesulitannya tinggi, tetapi ia masih bisa memahami sekitar 1–2 halaman di setiap paragraf
  Ia mendapatkan wawasan bahwa fungsi adalah daftar input dan output yang tak berujung, dan humor dalam notasi matematisnya juga membekas
  Ia ingin benar-benar memahaminya sebelum meninggal

  • Ungkapan “memahami 1–2 halaman per paragraf” terasa lucu karena mengingatkan pada kalimat panjang ala Victor Hugo
  • “1–2 halaman”? Sebagai lelucon, katanya mungkin sekitar “-1 halaman”

• Mengajukan pertanyaan apakah orang bisa memilih hanya 5 buku yang wajib dibaca dalam ilmu komputer

  • Katanya mustahil jika hanya 5 buku, lalu ia membagikan daftar Top 10 versinya sendiri
    Termasuk Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson, Russell & Norvig, dan lainnya
    Python pada dasarnya telah menjadi lingua franca, dan ia juga merekomendasikan Python Crash Course 3rd Edition karya Matthes
  • Jika bukan lulusan ilmu komputer, ia merekomendasikan TeachYourselfCS.com
    Di sana juga ada panduan 2 buku inti untuk dibaca ketika waktu terbatas
  • Katanya ini bergantung pada bidang yang ditekuni. Pertanyaannya mirip dengan “bahasa apa yang harus dipelajari?”
  • Menurutnya, buku ini tampaknya kurang berfokus pada relasi daripada bilangan, dan ia menyarankan untuk mempelajari type theory atau category theory juga
  • Katanya tidak ada daftar yang akan disetujui semua orang. Yang penting adalah mengeksplorasi sendiri dan menemukan buku yang cocok di algoritma, automata, bahasa, sistem operasi, machine learning, dan sebagainya

• Ia sangat menyukai bagian probabilitas dari buku ini
  Penjelasan masalah Monty Hall dengan ‘metode 4 langkah’ terasa sangat jernih dan jauh lebih mudah dipahami daripada film

  • Ia menemukan bahwa edisi 2017 bisa didapatkan di Inggris lewat print-on-demand
    Cocok untuk mempelajari sebagian isi buku dalam bentuk cetak

• Saat melihat daftar isi, ia terkejut karena bab 2 adalah Well-Ordering Principle
  Berbeda dari teorema Zermelo, pendekatan yang mengasumsikan urutan bilangan asli terasa asing baginya
  Ini karena biasanya ia belajar dengan mendefinisikan urutan dari aksioma Peano, lalu baru membuktikan prinsip tersebut

  • Ia menjelaskan bahwa Well-Ordering Principle, Axiom of Choice, dan Zorn’s Lemma saling ekuivalen
    Menarik bahwa himpunan bilangan real juga memiliki well-ordering, tetapi urutan itu tidak dapat benar-benar diekspresikan
    Ia juga mengutip lelucon, “aksioma pilihan jelas benar, prinsip pengurutan jelas salah, dan lemma Zorn saya tidak tahu”
  • Dalam pendidikan CS, ini biasanya hanya dibahas sebagai dasar induksi matematika, lalu hampir tidak pernah disebut lagi di kelas algoritma setelahnya

• Ia menjelaskan kembali prinsip pigeonhole di bagian 15.8 dengan pendekatan Dijkstra
  Jika 500 ribu orang di Boston memiliki 1 hingga 200 ribu helai rambut, maka karena rata-ratanya 2,5 orang, setidaknya ada 3 orang yang memiliki jumlah rambut yang sama
  Menarik bahwa ini bisa diselesaikan dengan fakta sederhana bahwa rata-rata tidak melebihi nilai maksimum

• Ini pertama kalinya ia melihat buku berbentuk kumpulan soal, dan ia penasaran apakah tersedia jawaban
  Ia sudah mencoba mengerjakan beberapa soal, tetapi tidak bisa memeriksa apakah jawabannya benar

  • Kursus Discrete Math dari Math Academy akan menampilkan pembahasan setelah jawaban dikirim, dan juga memiliki fitur latihan berulang
  • Tanpa jawaban, ia merasa belajar mandiri jadi sulit. Discrete Mathematics With Applications karya Susanna Epp juga merupakan alternatif yang baik
  • Katanya, soal-soal seperti ini mudah diselesaikan dengan LLM
  • Ia juga membagikan pengalaman bahwa LLM benar-benar membantu menemukan kesalahan dalam pembuktian. Gemini berguna karena menunjukkan pembuktian yang salah
  • Alasan universitas tidak membuka buku jawaban adalah karena soal-soal itu digunakan ulang. Kumpulan soal yang terbatas dipakai berulang selama beberapa tahun

• Mengucapkan terima kasih karena ini adalah materi yang sangat berguna

• Senang karena berkat Hacker News ia menemukan PDF yang selama ini ia cari
  Ia meminta rekomendasi screen reader yang bisa membaca PDF

  • Ia mempertanyakan apakah ada pembaca yang bisa membaca PDF yang berisi rumus LaTeX
    Katanya ia sendiri juga tidak bisa membaca sebagian besar simbol rumus