LKPD Informatika Kelas 11: Menganalisis Subpersoalan yang Tumpang Tindih pada Strategi Algoritmik Pemrograman Dinamis

INFORMASI UMUM

TUJUAN PEMBELAJARAN

1. Menganalisis persoalan yang bisa menghasilkan lebih dari satu solusi dengan pemahamannya terhadap strategi algoritmik pemrograman dinamis untuk menghasilkan beberapa alternatif solusi

PETUNJUK UMUM

• Bacalah pengantar kasus persoalan optimasi pada setiap kegiatan dengan cermat.
• Bekerjalah secara mandiri atau berpasangan sesuai arahan guru untuk membedah struktur persoalan.
• Gunakan kemampuan berpikir komputasional untuk memetakan subpersoalan dan menemukan alternatif solusi pemrograman dinamis.
• Tuliskan analisis dan hasil penalaranmu pada format ruang jawaban yang disediakan.

KEGIATAN

Kegiatan 1: Aktivitas 1: Menganalisis Struktur Pohon Keputusan dan Subpersoalan Tumpang Tindih (Overlapping Subproblems)

Estimasi: 25 menit

Alat & Bahan:

• Lembar kerja/buku catatan murid
• Alat tulis / pulpen

Petunjuk Pengerjaan:

1. Perhatikan kasus 'Bermain Angka / Penukaran Koin': Anda ingin mencapai nilai target N = 7 dengan pilihan nilai koin/langkah yang tersedia: {1, 3, 4}.
2. Jika diselesaikan secara rekursif biasa, nilai target akan dipecah menjadi pemanggilan subpersoalan: f(N) = min(f(N-1), f(N-3), f(N-4)) + 1.
3. Gambarkan atau petakan cabang penguraian subpersoalan dari f(7) ke bawah hingga menemukan nilai-nilai cabang yang berulang.
4. Jawablah pertanyaan analisis mengenai subpersoalan mana saja yang muncul berulang kali di berbagai cabang.

Pertanyaan:

1. Berdasarkan penguraian relasi rekursif f(7) dengan langkah {1, 3, 4}, tuliskan subpersoalan f(k) mana saja yang dihitung berulang lebih dari satu kali pada cabang pohon keputusan level 1 dan level 2!

2. Analisis apa dampak komputasi jika subpersoalan yang tumpang tindih tersebut dihitung berulang-ulang tanpa strategi pemrograman dinamis (memoization/tabulasi)?

Tuliskan daftar subpersoalan berulang pada format teks ringkas (misal: 'f(3) muncul di cabang A dan B'). Untuk nomor 2, tuliskan penjelasan analisis dampak efisiensi dalam 2-3 kalimat pada kolom uraian yang disediakan.

Kegiatan 2: Aktivitas 2: Menganalisis dan Membangun Alternatif Solusi Pemrograman Dinamis (Tabel Tabulasi)

Estimasi: 35 menit

Alat & Bahan:

• Lembar kerja berformat tabel
• Alat tulis

Petunjuk Pengerjaan:

1. Gunakan tabel pemrograman dinamis (pendekatan bottom-up/tabulasi) untuk menganalisis solusi mencapai nilai 1 hingga 7 dengan pilihan koin/langkah {1, 3, 4}.
2. Isilah tabel nilai minimum koin/langkah untuk tiap nilai target i (dari i=0 hingga i=7), serta catat kombinasi koin yang membentuk solusi tersebut.
3. Analisis apakah terdapat target i yang memiliki LEBIH DARI SATU alternatif kombinasi solusi optimal (jumlah langkah sama minimumnya, tetapi kombinasi langkah berbeda).

Pertanyaan:

1. Lengkapilah tabel pemrograman dinamis berikut untuk nilai target i = 0 sampai 7: tentukan DP[i] (jumlah koin minimum) dan alternatif pilihan koin yang digunakan!

2. Berdasarkan tabel di atas, analisislah pada target nilai berapa saja persoalan ini menghasilkan lebih dari satu alternatif solusi urutan/kombinasi langkah yang sama-sama mencapai nilai optimal minimum!

Isilah tabel 3 kolom: [Nilai i (0-7)] | [DP[i] (Jumlah Langkah Minimum)] | [Kombinasi Langkah/Koin]. Di bawah tabel, tuliskan paragraf analisis berisi identifikasi target nilai yang menghasilkan alternatif solusi ganda beserta penjelasannya.

Kegiatan 3: Aktivitas 3: Analisis Komparasi Alternatif Transisi Subpersoalan dan Justifikasi Solusi

Estimasi: 30 menit

Alat & Bahan:

• Lembar diskusi LKPD
• Buku catatan Informatika Kelas XI

Petunjuk Pengerjaan:

1. Diskusikan bersama rekan sebangku mengenai dua alternatif strategi dalam pemrograman dinamis: Top-Down dengan Memoization vs Bottom-Up dengan Tabulasi.
2. Analisis bagaimana kedua pendekatan tersebut mengidentifikasi dan menyimpan solusi dari subpersoalan yang tumpang tindih.
3. Bandingkan bagaimana alternatif penelusuran balik (backtracking) pada tabel DP memungkinkan kita menampilkan SELURUH variasi alternatif solusi optimal yang mungkin terjadi.

Pertanyaan:

1. Bagaimanakah cara tabel pemrograman dinamis mengenali bahwa suatu persoalan memiliki beberapa alternatif solusi optimal yang berbeda tanpa harus menghitung ulang dari awal?

2. Analisis kelebihan dan keterbatasan antara menghasilkan HANYA SATU solusi optimal versus menghasilkan SEMUA alternatif solusi optimal pada persoalan pemrograman dinamis!

Tuliskan hasil diskusi kelompok berpasangan pada format uraian 2 bagian sesuai nomor pertanyaan di lembar folio/LKPD yang tersedia.

REFLEKSI

1. Bagaimana pemahaman tentang 'subpersoalan yang tumpang tindih' membantu kalian melihat bahwa persoalan yang tampak rumit sebenarnya hanya terdiri dari pengulangan bagian-bagian kecil yang sama?

2. Dalam kehidupan sehari-hari atau pembuatan program, mengapa memiliki beberapa alternatif solusi optimal sering kali lebih menguntungkan daripada hanya terpaku pada satu solusi tunggal?

3. Bagian mana dari analisis pemrograman dinamis (membuat relasi rekurens, mengisi tabel, atau melacak balik solusi alternatif) yang paling menantang bagi kalian, dan strategi apa yang membantu kalian mengatasinya?