LKPD Informatika Kelas 11: Menganalisis Alternatif Solusi Tabel Memoisasi 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 persoalan dan aturan transisi langkah pada setiap aktivitas dengan cermat.
• Bekerjalah secara berpasangan atau mandiri sesuai instruksi pada setiap tahapan kegiatan.
• Gunakan tabel memoisasi yang disediakan untuk mencatat subproblem dan menelusuri pilihan langkah optimal.
• Fokuskan analisis pada perbandingan alternatif solusi yang mungkin muncul dari pembacaan tabel memoisasi.
• Tuliskan hasil analisis dan penelusuran balik (backtracking) pada ruang jawaban yang telah disiapkan.

KEGIATAN

Kegiatan 1: Analisis Pengisian Tabel Memoisasi Kasus Operasi Angka Menuju 1

Estimasi: 25 menit

Alat & Bahan:

• Lembar kerja/buku catatan
• Alat tulis/kalkulator sederhana

Petunjuk Pengerjaan:

1. Cermati persoalan 'Bermain Angka': Diberikan bilangan bulat n, tentukan jumlah langkah minimum L(n) untuk mengubah n menjadi 1.
2. Pilihan transisi operasi yang diperbolehkan:
3. 1. n -> n - 1 (biaya: 1 + L(n-1))
4. 2. n -> n / 2 jika n mod 2 == 0 (biaya: 1 + L(n/2))
5. 3. n -> n / 3 jika n mod 3 == 0 (biaya: 1 + L(n/3))
6. Analisis dan lengkapi nilai L(n) pada tabel memoisasi untuk nilai n = 1 sampai 12 secara bottom-up.
7. Identifikasi nilai n yang memiliki lebih dari satu pilihan transisi yang menghasilkan nilai minimum yang sama (alternatif solusi).

Pertanyaan:

1. Lengkapi nilai langkah minimum L(n) pada tabel memoisasi dari n = 1 hingga n = 12 berdasarkan rumus relasi rekurens L(n) = 1 + min(pilihan operasi yang valid). Tuliskan pilihan transisi yang menghasilkan nilai minimum tersebut.

2. Berdasarkan pengisian tabel tersebut, analisis bilangan n berapakah di antara 1 sampai 12 yang memiliki cabang alternatif pilihan transisi optimal (menghasilkan nilai L(n) yang sama)? Jelaskan alasan analisis Anda!

Format tabel pengisian: Buat tabel 4 kolom: [Nilai n] | [Kandidat Nilai dari Operasi Valid] | [Nilai Minimum L(n)] | [Alternatif Pilihan Operasi Optimal]. Format uraian: Tuliskan nomor bilangan n dan rincian cabang transisinya secara sistematis.

Kegiatan 2: Menganalisis Rute Alternatif Solusi Optimal Melalui Penelusuran Balik (Backtracking)

Estimasi: 35 menit

Alat & Bahan:

• Kertas grafik/lembar bergaris
• Penggaris dan pena warna (opsional untuk memperjelas cabang rute)

Petunjuk Pengerjaan:

1. Ambil persoalan n = 12 dari tabel memoisasi yang telah selesai dianalisis pada Kegiatan 1.
2. Lakukan penelusuran balik (backtracking) dari L(12) mundur hingga mencapai L(1) untuk merekonstruksi seluruh jalur urutan langkah.
3. Gambarkan pohon keputusan atau diagram urutan langkah yang menunjukkan setiap alternatif solusi yang valid.
4. Bandingkan urutan bilangan yang dilalui pada masing-masing alternatif solusi.

Pertanyaan:

1. Berapakah jumlah alternatif jalur solusi optimal yang dapat dibentuk untuk mengubah n = 12 menjadi 1 dengan total tepat 3 langkah? Uraikan seluruh alternatif urutan langkah bilangannya!

2. Lakukan analisis komparasi terhadap alternatif solusi yang Anda temukan: Mengapa tabel memoisasi pemrograman dinamis mampu menyimpan dan mengungkap keberadaan seluruh alternatif solusi tersebut dibandingkan pendekatan serakah (greedy) yang hanya memilih satu langkah lokal?

Format diagram alir/pohon urutan langkah: Gambar diagram pohon bercabang mulai dari node 12 menuju node 1. Format uraian: Tuliskan rincian jalur 1, jalur 2, dst., beserta penjelasan komparasi analisisnya.

Kegiatan 3: Analisis Alternatif Solusi Jalur Maksimum pada Grid Memoisasi 2D

Estimasi: 30 menit

Alat & Bahan:

• Lembar kerja murid
• Alat tulis

Petunjuk Pengerjaan:

1. Perhatikan tabel perolehan nilai panen pada grid 3x3 berikut: Baris 1: [2, 8, 3] Baris 2: [6, 4, 7] Baris 3: [1, 9, 5]
2. Aturan pergerakan: Dimulai dari salah satu petak di kolom 1, bergerak ke kanan atau ke bawah hingga mencapai petak di kolom 3. Nilai akumulasi adalah penjumlahan nilai petak yang dilalui.
3. Relasi rekurens memoisasi: Memo[r][c] = Nilai[r][c] + max(Memo[r-1][c], Memo[r][c-1]) untuk pergerakan dari atas/kiri.
4. Hitung nilai tabel memoisasi untuk grid tersebut dan analisis apakah terdapat petak tujuan di kolom 3 yang memiliki lebih dari satu alternatif jalur dengan nilai maksimum yang sama.

Pertanyaan:

1. Berdasarkan aturan pergerakan hanya boleh ke KANAN atau ke BAWAH dimulai dari petak (1,1) bernilai 2 menuju petak (3,3) bernilai 5, lengkapi nilai tabel memoisasi 3x3 berikut: Baris 1: [2, 10, 13], Baris 2: [8, 14, 21], Baris 3: [9, Memo(3,2), Memo(3,3)]. Tentukan nilai Memo(3,2) dan Memo(3,3)!

2. Analisis apakah terdapat alternatif jalur pada petak (2,2) jika petak (1,2) diubah nilainya menjadi 6 (sehingga Memo(1,2) = 8 dan Memo(2,1) = 8). Jika kedua pilihan dari atas dan kiri bernilai sama (8), jelaskan bagaimana alternatif solusi terbentuk dan tuliskan kedua alternatif rute tersebut!

Format isian: Tuliskan perhitungan Memo(3,2) dan Memo(3,3). Format analisis rute: Tuliskan tabel matriks hasil perubahan dan daftar rute alternatif 1 dan 2 beserta akumulasi nilainya.

REFLEKSI

1. Bagaimana pengamatan terhadap nilai-nilai yang sama pada tabel memoisasi membantu Anda menyadari keberadaan lebih dari satu solusi optimal dalam satu persoalan?

2. Dalam situasi nyata pembuatan keputusan, mengapa memiliki beberapa alternatif solusi optimal lebih menguntungkan dibandingkan hanya terpaku pada satu solusi tunggal?

3. Bagian mana dari analisis tabel memoisasi yang menurut Anda paling menantang ketika melakukan penelusuran balik (backtracking) untuk menemukan seluruh rute alternatif?