Modul Ajar: Struktur Data Graf dan Pohon (Kelas 9 SMP)

Identitas Penulis/Guru:

  • Nama: Prama
  • Jabatan: Guru Informatika
  • Institusi: SMP Negeri XX

Kompetensi Awal:

  • Memahami konsep dasar struktur data
  • Mampu merepresentasikan data dengan struktur data
  • Mampu menyelesaikan masalah dengan menggunakan struktur data

Profil Pelajar Pancasila:

  • Bernalar Kritis (memahami dan menganalisis struktur data)
  • Kreatif (merepresentasikan data dengan struktur data yang tepat)
  • Mandiri (menyelesaikan masalah dengan struktur data)
  • Bergotong Royong (bekerja sama dalam kelompok)

Sarana dan Prasarana:

  • Papan tulis/flipchart
  • Spidol
  • Laptop/komputer
  • Proyektor
  • Koneksi internet
  • Kertas
  • Alat tulis

Target Peserta Didik:

  • Siswa kelas 9 SMP

Model Pembelajaran:

Problem Based Learning (PBL)

Tujuan Pembelajaran:

  • Memahami definisi, jenis, representasi, operasi, dan penerapan struktur data graf dan pohon.
  • Mampu memilih struktur data graf dan pohon yang tepat untuk merepresentasikan data.
  • Mampu menyelesaikan masalah dengan menggunakan struktur data graf dan pohon secara efektif dan efisien.
  • Meningkatkan kemampuan bernalar kritis, kreatif, mandiri, dan bergotong royong.

Asesmen:

  • Observasi
  • Pertanyaan lisan dan tertulis
  • Kuis
  • Diskusi
  • Presentasi
  • Lembar kerja

Pemahaman Bermakna:

  • Siswa mampu menjelaskan konsep struktur data graf dan pohon dengan bahasa yang tepat dan logis.
  • Siswa mampu memilih struktur data yang tepat untuk merepresentasikan data secara optimal.
  • Siswa mampu menyelesaikan masalah dengan struktur data secara efektif dan efisien, serta mampu menjelaskan proses penyelesaiannya dengan logis.

Materi/Bahan Ajar:

Struktur Data Graf:

  • Definisi graf
  • Jenis-jenis graf (terarah, tidak terarah, berbobot, tidak berbobot)
  • Representasi graf (adjacency list, adjacency matrix)
  • Operasi pada graf (penambahan simpul, penghapusan simpul, penambahan sisi, penghapusan sisi)
  • Penerapan graf (pemetaan, jaringan sosial, scheduling)

Struktur Data Pohon:

  • Definisi pohon
  • Jenis-jenis pohon (akar, biner, terurut)
  • Representasi pohon (linked list, array)
  • Operasi pada pohon (penambahan simpul, penghapusan simpul, pencarian simpul)
  • Penerapan pohon (struktur organisasi, database, game)

Pertanyaan Pemantik:

  • Bagaimana cara merepresentasikan hubungan antar kota dalam sebuah peta dengan struktur data yang tepat?
  • Bagaimana cara merepresentasikan struktur organisasi dalam sebuah diagram dengan struktur data yang efisien?
  • Bagaimana cara mencari rute terpendek antara dua titik dalam sebuah peta dengan menggunakan struktur data yang optimal?
  • Bagaimana cara mencari data tercepat dalam sebuah database dengan memanfaatkan struktur data yang tepat?

Kegiatan Pembelajaran:

Langkah 1: Orientasi (10 menit)

  • Guru menyapa siswa dan menanyakan kesiapan mereka untuk mempelajari struktur data graf dan pohon.
  • Guru memberikan apersepsi dengan mengajukan pertanyaan pemantik.
  • Guru menjelaskan tujuan pembelajaran, model pembelajaran, dan skema penilaian.

Langkah 2: Mengorganisasikan Siswa (10 menit)

  • Guru membagi siswa menjadi kelompok-kelompok kecil (4-5 orang) dengan mempertimbangkan heterogenitas kemampuan dan karakteristik siswa.
  • Guru menunjuk seorang ketua kelompok untuk memimpin diskusi dan seorang notulis untuk mencatat hasil diskusi.

Langkah 3: Investigasi (60 menit)

  • Guru memberikan tugas kepada setiap kelompok untuk menyelesaikan sebuah kasus atau problematika yang berkaitan dengan struktur data graf dan pohon.
  • Siswa bekerja sama dalam kelompok untuk menyelesaikan tugas.
  • Guru berkeliling untuk memantau kemajuan kelompok, memberikan bimbingan dan arahan jika diperlukan.

Langkah 4: Presentasi dan Diskusi (45 menit)

  • Setiap kelompok mempresentasikan hasil kerja dan solusi mereka di depan kelas.
  • Presentasi diikuti dengan sesi tanya jawab dan diskusi interaktif antar kelompok dan guru.
  • Guru memberikan umpan balik konstruktif dan reinforcement terhadap hasil kerja dan presentasi setiap kelompok.

Langkah 5: Penutup (10 menit)

  • Guru melakukan refleksi dan kesimpulan pembelajaran, menekankan poin-poin penting dan mengaitkannya dengan tujuan pembelajaran.
  • Guru memberikan penguatan dan apresiasi terhadap
  • Guru memberikan tugas kepada setiap kelompok untuk menyelesaikan sebuah kasus atau problematika yang berkaitan dengan struktur data graf dan pohon.

Lembar Kerja Peserta Didik (LKPD)

Struktur Data Graf dan Pohon

Kelas: 9

Kelompok: ______

Anggota:

Kasus/Problematika:

Jaringan Sosial

Sebuah sekolah ingin membangun sebuah jaringan sosial untuk menghubungkan para siswanya. Jaringan sosial ini akan memungkinkan para siswa untuk saling berteman, berbagi pesan, dan berkolaborasi dalam proyek.

Pertanyaan:

Diskusi:

  1. Bagaimana struktur data graf dan pohon dapat membantu merepresentasikan jaringan sosial?
  2. Jelaskan keuntungan dan kekurangan menggunakan struktur data graf dan pohon untuk jaringan sosial.
  3. Bagaimana operasi-operasi pada struktur data graf dan pohon dapat diterapkan dalam jaringan sosial?
  4. Berikan contoh penerapan struktur data graf dan pohon dalam jaringan sosial untuk menyelesaikan masalah berikut:
    • Menambahkan/menghapus teman
    • Berbagi pesan
    • Mencari teman dengan minat yang sama
    • Merekomendasikan teman

Kesimpulan:

Berdasarkan diskusi, simpulkan struktur data yang paling tepat untuk merepresentasikan jaringan sosial dan jelaskan alasannya.

Catatan:

  • Diskusikan jawaban pertanyaan dengan anggota kelompok.
  • Tuliskan hasil diskusi pada lembar LKPD.
  • Lakukan presentasi hasil diskusi di depan kelas.

Kunci Jawaban LKPD

Struktur Data Graf dan Pohon

Kasus/Problematika:

Jaringan Sosial

Pertanyaan:

Diskusi:

  1. Struktur data graf:
    • Merepresentasikan hubungan antar siswa (simpul) yang terhubung melalui pertemanan (sisi).
    • Graf terarah: Menggambarkan arah pertemanan (misalnya, A berteman dengan B, tetapi B tidak berteman dengan A).
    • Berbobot: Nilai bobot pada sisi dapat merepresentasikan kekuatan hubungan pertemanan (misalnya, frekuensi interaksi).
  • Struktur data pohon:
    • Digunakan untuk merepresentasikan hierarki dalam jaringan sosial, seperti grup, kelas, dll.
    • Pohon akar: Memiliki satu simpul induk (root) yang merepresentasikan seluruh jaringan sosial.
    • Pohon biner: Setiap simpul maksimal memiliki dua simpul anak (misalnya, teman dekat dan teman biasa).
  1. Keuntungan graf:
    • Mudah merepresentasikan hubungan antar simpul.
    • Efisien dalam mencari jalur terpendek.
  • Kekurangan graf:
    • Membutuhkan ruang memori yang lebih besar dibandingkan pohon.
    • Sulit untuk merepresentasikan hierarki.
  • Keuntungan pohon:
    • Mudah merepresentasikan hierarki.
    • Efisien dalam operasi pencarian berdasarkan level.
  • Kekurangan pohon:
    • Sulit untuk merepresentasikan hubungan yang kompleks.
    • Membutuhkan waktu yang lebih lama untuk mencari jalur terpendek.

  1. Operasi:

    • Penambahan/Penghapusan Teman: Menambahkan/menghapus simpul dan sisi yang merepresentasikan pertemanan.
    • Berbagi Pesan: Menelusuri graf untuk menemukan jalur terpendek dari pengirim ke penerima pesan.
    • Mencari Teman: Melakukan operasi pencarian untuk menemukan simpul dengan kriteria tertentu.
    • Merekomendasikan Teman: Menganalisis graf untuk menemukan simpul yang memiliki kemungkinan besar untuk berteman.

  2. Contoh:

    • Menambahkan/Menghapus Teman:
      • Menambahkan simpul baru untuk siswa baru.
      • Menghubungkan simpul baru dengan simpul yang sudah ada melalui sisi berarah dengan bobot yang sesuai (misalnya, frekuensi interaksi).
      • Menghapus sisi yang menghubungkan dua simpul ketika pertemanan berakhir.
    • Berbagi Pesan:
      • Menemukan jalur terpendek dari simpul pengirim ke simpul penerima menggunakan algoritma seperti Breadth First Search (BFS) atau Depth First Search (DFS).
      • Mengirim pesan melalui sisi-sisi pada jalur terpendek.
    • Mencari Teman:
      • Mencari simpul dengan kriteria tertentu, seperti minat yang sama, kelas yang sama, dll.
      • Melakukan operasi traversal pada graf untuk menemukan semua simpul yang memenuhi kriteria.
    • Merekomendasikan Teman:
      • Menganalisis graf untuk menemukan simpul yang memiliki banyak teman dengan kriteria yang sama.
      • Merekomendasikan simpul yang memiliki nilai bobot yang tinggi pada sisi yang menghubungkannya dengan simpul lain.

Kesimpulan:

Struktur data yang paling tepat untuk merepresentasikan jaringan sosial adalah graf terarah berbobot. Alasannya:

  • Mudah merepresentasikan hubungan antar siswa (simpul) yang terhubung melalui pertemanan (sisi).
  • Efisien dalam mencari jalur terpendek untuk berbagi pesan.
  • Dapat merepresentasikan kekuatan hubungan pertemanan (misalnya, frekuensi interaksi) melalui nilai bobot pada sisi.

Catatan:

  • Jawaban di atas hanya contoh dan dapat dimodifikasi sesuai dengan diskusi kelompok.
  • Guru dapat menambahkan pertanyaan dan jawaban lain yang dianggap perlu.


Lembar Penilaian LKPD

Struktur Data Graf dan Pohon

Kelas: 9

Kelompok: ______

Anggota:

Kriteria Penilaian:

Aspek PenilaianIndikatorSkor
Pemahaman KonsepMampu menjelaskan definisi, jenis, dan representasi struktur data graf dan pohon dengan tepat dan logis.20
Pemilihan Struktur DataMemilih struktur data yang tepat untuk merepresentasikan kasus/problematika dengan alasan yang jelas.20
Operasi dan PenerapanMemahami operasi-operasi pada struktur data graf dan pohon dan mampu menerapkannya dalam menyelesaikan masalah pada jaringan sosial.20
Diskusi dan PresentasiAktif dalam diskusi, mampu menjelaskan hasil diskusi dengan jelas, dan mempresentasikan hasil kerja kelompok dengan baik.20
Kerjasama TimBekerja sama dengan baik dalam kelompok dan menyelesaikan tugas tepat waktu.20

Total: 100

Catatan:

  • Guru dapat menambahkan kriteria penilaian lain yang dianggap perlu.
  • Guru dapat memberikan penilaian individual kepada setiap anggota kelompok.

Rubrik Penilaian Diskusi dan Presentasi:

Aspek PenilaianKriteriaSkor
DiskusiAktif dalam diskusi, memberikan ide/gagasan, dan mendengarkan pendapat orang lain.10
Pemahaman KonsepMampu menjelaskan konsep struktur data graf dan pohon dengan tepat dan logis.5
KejelasanMampu menjelaskan hasil diskusi dengan jelas dan mudah dipahami.5

Total: 20

Rubrik Penilaian Presentasi:

Aspek PenilaianKriteriaSkor
KejelasanMempresentasikan hasil kerja kelompok dengan jelas dan mudah dipahami.10
Keterampilan PresentasiBerbicara dengan jelas, menggunakan bahasa yang tepat, dan menjaga kontak mata dengan audiens.5
Kerjasama TimBekerja sama dengan baik dalam kelompok dan menunjukkan kekompakan.5

Total: 20