๐งฎ MATEMATIKA & ALGORITMA โ Fondasi Semua CS
Tiga pilar matematika yang menopang seluruh ilmu komputer: Algoritma & DS (cara berpikir efisien), Matematika Diskrit (bahasa logika komputer), Linear Algebra (bahasa machine learning). Tidak ada jalan pintas โ ini fondasinya.
Cara Baca
Bukan hafalan rumus โ tapi cara berpikir. Setiap konsep di sini punya koneksi langsung ke topik praktis di vault ini. Gunakan kolom koneksi untuk motivasi belajar.
Sheet 1 โ Algoritma & Struktur Data
| ๐งฉ Level & Konsep | โก Isi & Sweet Spot | โ ๏ธ Jebakan Umum | ๐ Koneksi ke Topik Lain |
|---|---|---|---|
| Level 0 โ Kompleksitas & Big-O (O(1), O(log n), O(n), O(n log n), O(nยฒ), O(2โฟ)) | Ukuran โseberapa lambat kode tumbuh seiring input membesar.โ O(1): konstan, terbaik. O(log n): binary search, sangat baik. O(n log n): sort optimal. O(nยฒ): nested loop, berbahaya di data besar. O(2โฟ): eksponensial, praktis unusable di n>30. | Mengoptimasi kode O(nยฒ) yang dipanggil sekali vs membiarkan O(n) yang dipanggil jutaan kali. Premature optimization. Average case vs worst case. | Fondasi semua keputusan engineering, analisis performa exploit, kompleksitas kriptografi |
| Level 1 โ Array & Linked List (dynamic array, singly/doubly linked, skip list) | Array: O(1) random access, O(n) insert/delete di tengah. Linked list: O(1) insert/delete, O(n) access. Dynamic array (ArrayList/vector): amortized O(1) append via doubling strategy. Skip list: linked list berlapis untuk O(log n) search. | Linked list di cache-unfriendly โ pointer chasing = banyak cache miss. Array lebih cepat dalam praktik meski kompleksitas sama karena locality. | Koneksi ke cache hierarchy (Architecture), fondasi implementasi buffer di kernel |
| Level 2 โ Tree & Graph (BST, AVL, Red-Black, B-tree, trie, DFS, BFS, Dijkstra, A)* | BST: O(log n) average, O(n) worst (degenerate). AVL/Red-Black: self-balancing, O(log n) guaranteed. B-tree: dioptimasi untuk disk I/O (dipakai database dan filesystem). Trie: prefix search O(m) dimana m = panjang string. Graph: DFS/BFS untuk traversal, Dijkstra untuk shortest path. | Lupa base case di recursive DFS โ stack overflow. Dijkstra tidak bekerja untuk negative weight edge (pakai Bellman-Ford). | B-tree = fondasi Database Internals, Trie = fondasi DNS/routing table, Graph = fondasi OSINT network analysis |
| Level 3 โ Hash Table (hash function, collision, chaining, open addressing, consistent hashing) | O(1) average untuk insert/search/delete. Hash function map key โ index. Collision: dua key โ index sama. Chaining: collision ditangani linked list. Open addressing: probe slot berikutnya. Load factor: ratio isi/kapasitas, trigger resize. Consistent hashing: distribusi key di distributed system. | Worst case O(n) jika hash function buruk โ semua collision. Hash DoS: attacker kirim payload yang sengaja collision (mitigasi: randomized hash seed). | Fondasi DNS cache, fondasi blockchain (Merkle tree), consistent hashing = fondasi distributed database |
| Level 4 โ Sorting & Searching (quicksort, mergesort, heapsort, binary search, radix sort) | Quicksort: O(n log n) average, O(nยฒ) worst, in-place, cache-friendly โ praktik tercepat. Mergesort: O(n log n) guaranteed, stable, butuh O(n) extra space โ dipakai untuk external sort (data > RAM). Heapsort: O(n log n) guaranteed, in-place tapi cache-unfriendly. Radix: O(nk) linear untuk integer โ kalahkan comparison-based sort. | Quicksort dengan pivot buruk (selalu max/min) โ O(nยฒ). Mergesort untuk linked list, quicksort untuk array. Stable sort penting jika sort by multiple key. | Fondasi database query execution, fondasi file system directory listing |
| Level 5 โ Dynamic Programming & Greedy (memoization, tabulation, knapsack, LCS, Dijkstra) | DP: pecah masalah jadi sub-problem yang overlap, simpan hasil (memoize) agar tidak hitung ulang. Greedy: pilihan lokal optimal di setiap step โ harap optimal global (tidak selalu benar). Overlapping subproblem + optimal substructure = tanda DP cocok. | Greedy tidak selalu optimal (contoh: coin change dengan denominasi tertentu). DP dengan state besar = memory explosion. Bingung top-down vs bottom-up โ keduanya equivalen, pilih yang lebih intuitif. | Fondasi network routing optimization, fondasi compiler optimization, fondasi sequence alignment bioinformatika |
| Level 6 โ Advanced Structures (segment tree, Fenwick tree, union-find, bloom filter, HyperLogLog) | Segment tree: range query + update O(log n). Fenwick/BIT: prefix sum update/query O(log n), simpler implementasi. Union-Find: konektivitas graph, O(ฮฑ(n)) โ O(1) dengan path compression. Bloom filter: probabilistic set membership, O(1), no false negative tapi ada false positive. HyperLogLog: count distinct element dengan O(log log n) memory. | Bloom filter tidak bisa delete element (gunakan Counting Bloom Filter). Segment tree vs Fenwick: segment tree lebih general, Fenwick lebih simple untuk sum query. | Bloom filter = dipakai Cassandra, Redis, browser safe browsing. HyperLogLog = dipakai Redis, Spark untuk analytics |
| โ ๏ธ Level 7 โ Algorithm Design Paradigms (divide & conquer, randomization, approximation, amortized analysis) | Divide & conquer: bagi masalah jadi sub-problem independen (quicksort, FFT, closest pair). Randomization: Las Vegas (selalu benar, random waktu) vs Monte Carlo (random benar, selalu cepat). Approximation: untuk NP-hard problem, cari solusi yang โcukup baikโ dengan guarantee ratio. Amortized: analisis biaya operasi rata-rata across sequence, bukan worst case per operasi. | NP-hard โ tidak bisa diselesaikan โ bisa dengan approximation atau heuristic. Bingung polynomial reduction. Randomized algorithm yang deterministic equivalent lebih disukai di security-critical system. | Fondasi cryptographic algorithm design, fondasi ML optimization, fondasi compiler theory |
Sheet 2 โ Matematika Diskrit
| ๐ Topik | โก Isi & Sweet Spot | ๐ Koneksi Langsung |
|---|---|---|
| Logika Proposisional & Predikat | AND, OR, NOT, implication, biconditional. Tautologi, kontradiksi, satisfiability. Predicate logic: quantifier โ (untuk semua) dan โ (ada). Dasar formal verification dan SAT solver. | Fondasi AI Level 0 (IF-THEN), fondasi formal verification software |
| Teori Himpunan | Union, intersection, complement, power set, Cartesian product. Relasi: reflexive, symmetric, transitive, equivalence relation. Fungsi: injective, surjective, bijective. | Fondasi database (relational algebra), fondasi type theory |
| Kombinatorik & Counting | Permutasi, kombinasi, pigeonhole principle, inclusion-exclusion. Generating function. Dasar analisis probabilitas algoritma. | Fondasi kriptografi (ukuran keyspace), fondasi complexity theory |
| Teori Graf | Graph, digraph, tree, spanning tree, Euler path, Hamiltonian cycle, planar graph, coloring. Network flow. Matching. | Fondasi network routing, fondasi OSINT link analysis, fondasi compiler (control flow graph) |
| Teori Bilangan | Divisibility, GCD (Euclidean algorithm), modular arithmetic, Fermatโs little theorem, Eulerโs theorem, Chinese Remainder Theorem. Bilangan prima, uji primalitas. | Fondasi langsung kriptografi RSA, DH, ECC โ tanpa ini crypto jadi magic |
| Probabilitas Diskrit | Sample space, event, conditional probability, Bayesโ theorem, random variable, expected value, variance. Distribusi: Bernoulli, binomial, geometric. | Fondasi ML (naive Bayes, probabilistic model), fondasi analisis algoritma randomized |
| Relasi Rekurensi | T(n) = aT(n/b) + f(n) โ Master Theorem untuk analisis divide & conquer. Fibonacci, Catalan number. | Fondasi analisis algoritma, fondasi DP |
| Logika Boolean & Rangkaian | Minimisasi fungsi Boolean (Karnaugh map, Quine-McCluskey). Sum of products, product of sums. | Fondasi digital circuit design (Computer Architecture Level 0) |
Sheet 3 โ Linear Algebra untuk CS
| ๐ Topik | โก Isi & Sweet Spot | ๐ Koneksi Langsung |
|---|---|---|
| Vektor & Operasi | Vector addition, scalar multiplication, dot product, cross product, norm (L1, L2). Cosine similarity = dot product normalized. | Fondasi information retrieval, TF-IDF, word embedding (NLP) |
| Matriks & Operasi | Matrix multiplication, transpose, inverse, determinant. Kenapa matrix multiply tidak commutative. Strassen algorithm O(n^2.807) vs naive O(nยณ). | Fondasi neural network (weight matrix), fondasi computer graphics (transformation) |
| Sistem Persamaan Linear | Gaussian elimination, LU decomposition. Overdetermined system (lebih banyak persamaan dari variable) โ least squares. | Fondasi regression, fondasi computer vision (camera calibration) |
| Eigenvalue & Eigenvector | Av = ฮปv. Matriks transformasi yang hanya scale vektor tertentu (eigenvector) tanpa rotate. Diagonalisasi. | Fondasi PCA (dimensionality reduction), fondasi Google PageRank, fondasi quantum computing |
| Dekomposisi Matriks | SVD (Singular Value Decomposition): setiap matriks bisa didekomposisi jadi UยทฮฃยทVแต. QR decomposition. Cholesky. | Fondasi recommender system (collaborative filtering), fondasi data compression, fondasi pseudoinverse |
| Ruang Vektor & Transformasi Linear | Span, basis, dimension, rank, nullspace. Linear map: preserves addition dan scalar multiplication. Change of basis. | Fondasi semua deep learning (setiap layer = linear transformation + non-linearity) |
| Norma & Jarak | L1 norm (Manhattan), L2 norm (Euclidean), Lโ norm. Matrix norm. Frobenius norm. | Fondasi regularization (L1=Lasso, L2=Ridge), fondasi distance metric dalam clustering |
Peta Koneksi ke Semua Hierarki
MATEMATIKA DISKRIT
โ
โโโ Teori Bilangan โโโโโโโโโโโโโโโโโโโบ Kriptografi (RSA, DH, ECC)
โโโ Teori Graf โโโโโโโโโโโโโโโโโโโโโโโบ OSINT (network analysis)
โ โบ Algoritma (DFS, BFS, Dijkstra)
โโโ Kombinatorik โโโโโโโโโโโโโโโโโโโโโบ Kriptografi (keyspace size)
โ โบ Algoritma (complexity analysis)
โโโ Probabilitas โโโโโโโโโโโโโโโโโโโโโบ AI Level 1-2 (ML foundation)
โบ Research Methodology (statistics)
ALGORITMA & DS
โ
โโโ B-tree โโโโโโโโโโโโโโโโโโโโโโโโโโโบ Database Internals
โโโ Hash Table โโโโโโโโโโโโโโโโโโโโโโโบ Blockchain, DNS, Cache
โโโ Graph โโโโโโโโโโโโโโโโโโโโโโโโโโโโบ Network routing, OSINT
โโโ DP / Greedy โโโโโโโโโโโโโโโโโโโโโโบ Compiler, Network optimization
LINEAR ALGEBRA
โ
โโโ Matrix multiply โโโโโโโโโโโโโโโโโโบ Neural Network (setiap layer)
โโโ Eigenvalue/SVD โโโโโโโโโโโโโโโโโโโบ PCA, Recommender System
โโโ Cosine similarity โโโโโโโโโโโโโโโโบ NLP, Search Engine
โโโ Transformasi linear โโโโโโโโโโโโโโบ Computer Graphics, Computer Vision
Urutan Belajar yang Direkomendasikan
- Matematika Diskrit dulu โ teori bilangan langsung unlock pemahaman kriptografi
- Algoritma & DS โ langsung praktek di LeetCode/HackerRank sambil belajar teori
- Linear Algebra โ mulai saat mulai menyentuh ML/AI Level 2 ke atas
Resource terbaik: 3Blue1Brown (YouTube) untuk visual intuisi Linear Algebra sebelum formal. MIT OCW 6.042J untuk Matematika Diskrit. CLRS (Introduction to Algorithms) sebagai referensi Algoritma.
Jebakan Mahasiswa IT
Belajar syntax framework AI (TensorFlow, PyTorch) tanpa paham matematika di baliknya = bisa pakai tapi tidak bisa debug ketika hasilnya aneh. Model yang overfit, gradient explode, atau hasil tidak masuk akal โ semua butuh math untuk diagnosis.
๐ Lihat Juga
- Master Index
- Computer Science Foundations โ OS & Architecture
- Kriptografi & Biometrik โ aplikasi teori bilangan
- AI Levels Hierarchy โ aplikasi linear algebra
- Research Methodology โ aplikasi probabilitas & statistik
Matematika & Algoritma | Algoritma & DS + Matematika Diskrit + Linear Algebra ยท Fondasi Semua CS