LKPD Informatika Kelas 11: Menerapkan Perancangan Struktur Data Terstruktur Kompleks untuk Menghasilkan Solusi Paling Efisien

INFORMASI UMUM

TUJUAN PEMBELAJARAN

1. Menerapkan solusi terbaik, paling efisien, dan optimal dengan merancang struktur data yang lebih kompleks dan abstrak

PETUNJUK UMUM

• Bacalah skenario persoalan optimasi rute logistik dan antrean pengiriman barang dengan saksama.
• Bekerjalah secara kolaboratif dalam kelompok untuk merancang struktur data graf dan antrean prioritas (priority queue/heap) yang sesuai.
• Lakukan penelusuran (tracing) efisiensi perancangan struktur data yang kalian buat guna memastikan tercapainya solusi paling optimal.
• Tuliskan hasil rancangan, representasi simpul/sisi, dan analisis efisiensi pada format ruang jawaban yang disediakan.

KEGIATAN

Kegiatan 1: Aktivitas 1: Menganalisis Kebutuhan Struktur Data Kompleks pada Jaringan Distribusi

Estimasi: 25 menit

Alat & Bahan:

• Lembar Kerja
• Alat tulis
• Kalkulator (opsional)

Petunjuk Pengerjaan:

1. Cermati skenario: Perusahaan logistik melayani 5 titik gudang (A, B, C, D, E). Terdapat jalur jalan berbobot (jarak km) antar-gudang: A-B (4), A-C (2), B-C (1), B-D (5), C-D (8), C-E (10), D-E (2).
2. Bandingkan dua pilihan struktur data representasi graf: Matriks Ketetanggaan (Adjacency Matrix) berukuran 5x5 dan Senarai Ketetanggaan (Adjacency List).
3. Terapkan pemilihan struktur data yang paling efisien memori dan waktu untuk memeriksa tetangga langsung pada graf berkepadatan rendah (sparse graph) ini.

Pertanyaan:

1. Berdasarkan data jaringan 5 titik gudang di atas, susunlah rancangan representasi struktur data menggunakan Senarai Ketetanggaan (Adjacency List) lengkap dengan bobot jalurnya!

2. Terapkan perbandingan efisiensi ruang memori antara Matriks Ketetanggaan (V x V) dan Senarai Ketetanggaan (V + E) untuk jaringan 5 simpul dan 7 sisi di atas, serta tentukan mana yang menghasilkan representasi paling efisien!

Tuliskan daftar relasi Adjacency List untuk simpul A hingga E pada baris teks terstruktur, lalu buat paragraf penjelasan komparasi efisiensi memori (V^2 vs V+E).

Kegiatan 2: Aktivitas 2: Merancang Struktur Data Kombinasi (Graf + Priority Queue) untuk Solusi Rute Terpendek

Estimasi: 35 menit

Alat & Bahan:

• Kertas buram/grafik untuk simulasi penelusuran heap
• Alat tulis

Petunjuk Pengerjaan:

1. Perusahaan ingin mencari rute dengan total jarak paling minimal dari Gudang A menuju Gudang E.
2. Rancang struktur data gabungan yang mengombinasikan Senarai Ketetanggaan (Adjacency List) dengan Min-Heap (Priority Queue) untuk memproses pencarian simpul berjarak terkecil secara optimal.
3. Lakukan penelusuran (tracing) langkah demi langkah pengisian antrean prioritas hingga mencapai simpul tujuan E.

Pertanyaan:

1. Rancanglah elemen data yang harus disimpan dalam setiap node antrean prioritas (Min-Heap) agar algoritma dapat menentukan simpul berikutnya dengan biaya minimum secara optimal!

2. Lakukan simulasi penelusuran (tracing) rute terpendek dari A ke E dengan melengkapi tabel status jarak kumulatif dan urutan simpul yang dikunjungi!

Isi tabel pelacakan 4 kolom: [Langkah Ke-, Simpul Diekstrak dari Heap, Jarak Kumulatif, Isi Antrean Prioritas Tersisa]. Di bawah tabel, tuliskan urutan rute final beserta total bobot.

Kegiatan 3: Aktivitas 3: Justifikasi Efisiensi Solusi dan Optimasi Desain Struktur Data

Estimasi: 30 menit

Alat & Bahan:

• Lembar refleksi dan rangkuman kelompok
• Alat tulis

Petunjuk Pengerjaan:

1. Diskusikan dalam kelompok: Mengapa penggunaan struktur data kombinasi (Adjacency List + Min-Heap) memberikan efisiensi yang lebih unggul dibandingkan struktur linier array biasa saat jumlah gudang berkembang menjadi 10.000 titik?
2. Susun kesimpulan penerapan desain struktur data terstruktur kompleks yang telah dirancang.
3. Selesaikan pengisian LKPD, lakukan refleksi diri, dan persiapkan penutupan pembelajaran.

Pertanyaan:

1. Bandingkan kompleksitas waktu pencarian simpul berjarak minimum jika menggunakan struktur Array Linier dibandingkan dengan Min-Heap untuk skala graf besar (V simpul, E sisi). Jelaskan mengapa Min-Heap menghasilkan solusi paling optimal!

Tuliskan hasil diskusi analisis kompleksitas (O-Notation) beserta argumentasi penentuan struktur data optimal dalam 1-2 paragraf terstruktur.

REFLEKSI

1. Bagaimana merancang struktur data abstrak (seperti Graf dan Heap) membantu kamu memecahkan persoalan optimasi dunia nyata secara lebih sistematis?

2. Bagian mana dari perancangan struktur data hari ini yang paling menantang dan bagaimana kamu mengatasinya?

3. Prinsip efisiensi apa yang kamu pelajari hari ini yang dapat kamu terapkan dalam menyelesaikan masalah komputasi lainnya?