Modul Ajar Informatika Kelas 11 SMA: Berpikir Komputasional Tingkat Lanjut: Greedy dan Pemrograman Dinamis (Bab 1)

Penerapan strategi algoritma Greedy (Fractional Knapsack, Aktivitas Seleksi), Dynamic Programming (Fibonacci Memoization, 0/1 Knapsack), representasi struktur data Graf/Pohon, dan analisis kompleksitas asimtotik Big-O.

Capaian dan tujuan pembelajaran

Peserta didik mampu menganalisis dan menerapkan paradigma Greedy dan Dynamic Programming dalam memecahkan masalah optimasi.
Peserta didik mampu memodelkan persoalan kontekstual menggunakan struktur data Graf dan algoritma pencarian rute.
Peserta didik mampu menghitung dan mengevaluasi kompleksitas waktu algoritma menggunakan notasi Big-O.

Materi pokok & uraian konsep pembelajaran

Berpikir Komputasional (*Computational Thinking*) pada Fase F menuntut kemampuan menganalisis dan memformulasikan solusi algoritmik yang efisien untuk masalah optimasi kombinatorial berskala besar. Dua paradigma penting dalam optimasi adalah algoritma *Greedy* dan *Dynamic Programming* (DP).

Algoritma *Greedy* mengambil keputusan lokal terbaik (*locally optimal choice*) pada setiap langkah dengan harapan mencapai solusi global optimal. Sebaliknya, Pemrograman Dinamis (*Dynamic Programming*) memecah masalah menjadi sub-masalah yang tumpang tindih (*overlapping subproblems*) dan menyimpan solusinya (*memoization/tabulation*) untuk menghindari komputasi berulang.

Struktur data non-linear seperti Graf (*Graph*) dan Pohon (*Tree*) dianalisis menggunakan algoritma pencarian lintasan terpendek (*Dijkstra*) dan pohon rentang minimum (*Prim/Kruskal*). Analisis kompleksitas waktu Big-$O$ ($\mathcal{O}(n)$, $\mathcal{O}(n\log n)$, $\mathcal{O}(n^2)$) digunakan untuk mengukur efisiensi komputasi algoritma.

Peta subtopik bahasan

Paradigma Algoritma Greedy dan Karakteristik Optimasi
Menerapkan pendekatan rakus pada masalah penukaran koin dan Fractional Knapsack Problem.
Pemrograman Dinamis (Dynamic Programming: Memoization vs Tabulation)
Menyelesaikan masalah bilangan Fibonacci, Longest Common Subsequence, dan 0/1 Knapsack.
Struktur Data Graf dan Algoritma Lintasan Terpendek
Menganalisis representasi matriks ketetanggaan dan algoritma Dijkstra pada jaringan rute.
Analisis Kompleksitas Asimtotik Waktu dan Ruang (Notasi Big-O)
Membandingkan efisiensi runtime algoritma brute force versus strategi pemrograman dinamis.

Istilah kunci dan glosarium

Algoritma Greedy: Pendekatan perancangan algoritma yang membuat pilihan terbaik saat itu juga di setiap langkah tanpa mempertimbangkan konsekuensi global jangka panjang.
Dynamic Programming: Metode penyelesaian masalah optimasi kompleks dengan membaginya menjadi sub-persoalan tumpang tindih dan menyimpan hasil solusinya dalam tabel memori.
Memoization: Teknik optimasi top-down pada pemrograman dinamis dengan menyimpan hasil pemanggilan fungsi yang mahal dalam cache/tabel asosiatif.
Notasi Big-O: Notasi matematika asimtotik yang digunakan untuk mengklasifikasikan batas atas laju pertumbuhan waktu eksekusi atau kebutuhan memori suatu algoritma.
Graf Berbobot (Weighted Graph): Struktur data graf di mana setiap sisi (edge) yang menghubungkan dua simpul (vertex) memiliki nilai numerik biaya/jarak.

Instrumen asesmen formatif & contoh soal pembelajaran

5 butir instrumen soal pilihan ganda berbasis HOTS untuk mengukur pemahaman konsep pada bab ini. Dilengkapi kunci jawaban dan uraian pembahasan analitis.

Soal 1

Perbedaan mendasar antara masalah 'Fractional Knapsack' dengan '0/1 Knapsack' adalah...

A. Fractional Knapsack memperbolehkan pengambilan pecahan bagian dari barang (bisa diselesaikan dengan Greedy), sedangkan 0/1 Knapsack mengharuskan barang diambil utuh atau tidak sama sekali (diselesaikan dengan Dynamic Programming)
B. 0/1 Knapsack hanya boleh mengambil barang yang bernilai nol
C. Fractional Knapsack tidak memiliki batasan kapasitas beban
D. Keduanya selalu menghasilkan solusi yang identik dengan algoritma Greedy