LKPD Koding dan Kecerdasan Artifisial Kelas 10: Algoritma Pencarian (Sequential & Binary Search) dan Pengurutan (Selection & Insertion Sort)

INFORMASI UMUM

TUJUAN PEMBELAJARAN

1. Murid mampu memahami dan menerapkan algoritma pencarian sequential search dan binary search untuk menemukan data dalam kumpulan data. (elemen: Algoritma Pemrograman)
2. Murid mampu membandingkan algoritma pengurutan selection sort dan insertion sort berdasarkan logika dan efisiensinya. (elemen: Algoritma Pemrograman)

PETUNJUK UMUM

• Bacalah petunjuk setiap kegiatan dengan saksama.
• Siapkan alat tulis, kertas, dan penggaris untuk menggambar jika diperlukan.
• Diskusikan dengan teman sebangkumu pada bagian yang diminta, namun tulis jawaban pada LKPD secara mandiri.
• Jika ada istilah yang belum jelas, tanyakan kepada guru.
• Simpan semua hasil simulasi dan perbandingan sebagai bahan belajar untuk ujian.

KEGIATAN

Kegiatan 1: Menyelidiki Kinerja Algoritma Pencarian

Estimasi: 25 menit

Alat & Bahan:

• Data set [7, 12, 3, 9, 5, 1, 8] (diberikan guru)
• Kertas dan alat tulis
• Kalkulator sederhana (opsional untuk log2)

Petunjuk Pengerjaan:

1. Bentuk kelompok kecil (2-3 orang). Setiap kelompok akan berperan sebagai “komputer” yang menjalankan algoritma pencarian.
2. Siapkan data berikut sebagai kumpulan data tidak terurut: [7, 12, 3, 9, 5, 1, 8]. Urutkan data tersebut terlebih dahulu secara manual (ascending) untuk digunakan pada binary search.
3. Tentukan satu orang sebagai pemimpin (yang mengikuti langkah algoritma) dan satu orang sebagai pencatat.
4. Lakukan simulasi sequential search untuk mencari nilai 9 pada data tidak terurut. Catat setiap perbandingan yang dilakukan sampai nilai ditemukan atau selesai.
5. Lanjutkan simulasi binary search untuk mencari nilai 9 pada data yang sudah diurutkan. Perhatikan syarat: data harus terurut. Catat langkah-langkahnya hingga nilai ditemukan.
6. Amati perbedaan jumlah langkah, dan diskusikan kapan sebaiknya menggunakan masing-masing algoritma.

Pertanyaan:

1. Simulasikan sequential search untuk mencari angka 9 pada data tidak terurut [7, 12, 3, 9, 5, 1, 8]. Tuliskan setiap iterasi perbandingan dalam tabel berikut (indeks array dimulai dari 0).

2. Urutkan data menjadi [1, 3, 5, 7, 8, 9, 12]. Simulasikan binary search untuk mencari 9. Tuliskan langkah perbandingan dengan format: “Cek elemen tengah di indeks = ..., nilainya = ..., karena 9 ? ... maka lanjut ke bagian ...”. Lanjutkan hingga ditemukan.

3. Berdasarkan simulasi di atas, lengkapi tabel perbandingan sequential search vs binary search (pada data yang sudah terurut) untuk mencari angka 9: jumlah perbandingan, syarat data, dan jumlah langkah maksimal jika data berukuran N. Kemudian jawab: Kapan binary search sangat tidak efisien dibanding sequential search?

Tulis tabel simulasi dan perbandingan di buku latihan. Gambarlah tabel dengan rapi menggunakan penggaris.

Kegiatan 2: Mengurutkan dengan Strategi yang Berbeda

Estimasi: 30 menit

Alat & Bahan:

• Kertas, pulpen, penggaris
• Potongan kertas kecil bertuliskan angka (opsional untuk simulasi fisik)

Petunjuk Pengerjaan:

1. Kamu akan mensimulasikan dua algoritma pengurutan pada data yang sama. Bekerjalah sendiri, lalu diskusikan hasilnya dengan teman sebangkumu.
2. Gunakan array awal: [6, 3, 8, 5, 2]. Tujuan: mengurutkan secara ascending (dari kecil ke besar).
3. Lakukan selection sort: pada setiap putaran, cari elemen terkecil dari bagian yang belum terurut, lalu tukar dengan posisi yang tepat. Catat kondisi array setelah setiap penukaran.
4. Lakukan insertion sort: mulai dari elemen kedua, ambil elemen tersebut dan sisipkan ke posisi yang tepat di bagian kiri yang sudah terurut. Catat array setelah setiap penyisipan.
5. Bandingkan jumlah “pergeseran” atau “penukaran” yang terjadi pada kedua algoritma.

Pertanyaan:

1. Untuk selection sort, isi tabel berikut: Putaran ke-, Subarray belum terurut, Elemen terkecil ditemukan, Array setelah penukaran. Mulai dari array [6, 3, 8, 5, 2].

2. Untuk insertion sort, isi tabel berikut: Langkah ke-, Bagian terurut sementara, Elemen yang disisipkan, Proses pergeseran (jika ada), Array setelah penyisipan. Mulai dari [6, 3, 8, 5, 2].

3. Setelah simulasi, diskusikan dengan teman: (a) Dari segi logika, algoritma mana yang menurutmu lebih mudah diingat dan dijelaskan? (b) Untuk data berukuran kecil seperti ini, mana yang lebih cepat selesai? (c) Apa kelemahan utama masing-masing algoritma jika data sangat besar (misal 10.000 angka)? Tulis hasil diskusimu dalam bentuk uraian singkat.

Buat tabel di kertas A4; untuk uraian gunakan halaman terpisah. Sertakan nama dan kelas.

Kegiatan 3: Tantangan Algoritma dalam Kehidupan Sehari-hari

Estimasi: 25 menit

Alat & Bahan:

• Kertas folio, HVS, alat tulis, penggaris
• Akses internet (opsional, di bawah pengawasan guru)

Petunjuk Pengerjaan:

1. Bacalah skenario berikut: 'Kamu bekerja sebagai asisten di perpustakaan sekolah yang memiliki ribuan buku. Buku-buku di rak sudah terurut rapi berdasarkan kode buku. Hari ini ada 15 buku yang dikembalikan siswa, masih dalam keadaan acak.'
2. Jawablah pertanyaan dengan menerapkan pengetahuanmu tentang algoritma pencarian dan pengurutan. Berpikirlah seperti seorang programmer yang mencari solusi efisien.
3. Untuk soal ketiga, gambarlah flowchart atau tuliskan pseudocode. Gunakan simbol flowchart standar atau tulis dengan jelas.
4. Jika perlu, gunakan internet atau buku untuk mencari referensi tentang efisiensi algoritma (big O notation).
5. Sajikan jawabanmu dengan rapi dan logis.

Pertanyaan:

1. Untuk mencari sebuah buku dengan kode tertentu di rak, algoritma pencarian mana yang paling tepat? Jelaskan alasanmu, kaitkan dengan syarat data dan efisiensi waktu.

2. Untuk mengurutkan 15 buku yang dikembalikan sebelum disusun ke rak, kamu dihadapkan pilihan: selection sort atau insertion sort. Mana yang akan kamu pilih? Berikan dua alasan kuat berdasarkan logika dan efisiensi yang telah kamu pelajari.

3. Buatlah algoritma dalam bentuk pseudocode atau flowchart untuk proses pencarian buku tadi (jawaban nomor 1). Sertakan asumsi bahwa rak adalah array berindeks dan kode buku adalah angka unik.

Untuk uraian, tulis di kertas folio bergaris. Untuk pseudocode/flowchart, gunakan kertas HVS kosong. Gunakan pensil terlebih dahulu agar mudah diperbaiki.

REFLEKSI

1. Setelah mencoba sendiri simulasi, menurutmu algoritma mana yang paling “cerdas” – binary search atau insertion sort? Mengapa?

2. Pelajaran apa yang bisa kamu petik dari pentingnya memilih algoritma yang tepat untuk masalah sehari-hari? Beri contoh lain di luar perpustakaan!

3. Bagaimana perasaanmu saat berhasil menelusuri langkah demi langkah algoritma? Kesulitan apa yang kamu hadapi, dan bagaimana kamu mengatasinya?