Menerapkan Berpikir Komputasional: Memilih Jalur Terpendek

Menerapkan Berpikir Komputasional


Memilih Jalur Terpendek

Informatika Kelas IX
Ela Budiati Bano, S.Pd

Word Cloud

Bagaimana perasaanmu hari ini? (Jawab menggunakan emoji)

Jika kamu ingin pergi ke suatu tempat, ada beberapa alternatif rute yang dapat kamu pilih.

Bagaimana rute dari sekolah ke menara limboto?

Ada dua cara yang dapat digunakan untuk menentukan jalur terpendek.

Algoritme greedy adalah suatu teknik dalam ilmu komputer yang digunakan untuk memecahkan masalah optimasi dengan cara memilih solusi terbaik pada setiap tahapnya hingga mencapai solusi optimal secara keseluruhan.

​

Algoritme greedy

Pada setiap langkahnya, algoritme greedy bekerja dengan dua dasar prinsip berikut.
1. Jika dalam setiap langkah yang dilakukan memberikan hasil terbaik, maka hasil keseluruhan adalah yang terbaik.
2. Alrogitme greedy tidak mengenal adanya proses iterasi (perulangan) atau mengubah keputusan yang sudah dibuat.

Algoritme greedy

Multiple Choice

Algoritme greedy adalah suatu teknik dalam ilmu komputer yang digunakan untuk memecahkan masalah optimasi dengan cara _________________________ hingga mencapai solusi optimal secara keseluruhan.

• memilih solusi terbaik pada setiap tahapnya

• memilih solusi alternatif pada setiap tahapnya

• memaksimalkan solusi terbaik pada setiap tahapnya

• memilih solusi tertentu pada setiap tahapnya

Multiple Select

Dua dasar prinsip algoritme greedy dibawah ini adalah....

• Jika dalam setiap langkah yang dilakukan memberikan hasil terbaik, maka hasil keseluruhan adalah yang terbaik.

• Alrogitme greedy tidak mengenal adanya proses iterasi (perulangan) atau mengubah keputusan yang sudah dibuat.

• Keputusan yang sudah dibuat dapat diubah dengan ketentuan tertentu

• Jika dalam setiap langkah yang dilakukan memberikan hasil terbaik, maka hasil disepakati adalah yang terbaik.

​Jika kamu ingin pergi dari A ke H, rute mana yang harus diambil?

Multiple Choice

Melalui jalur dari A - C - E - H, berapa jarak yang harus ditempuh?

• 37 km

• 38 km

• 39 km

• 40 km

Algoritme dinamis bertujuan untuk menemukan solusi optimal terbaik dari masalah yang ada. Cara yang dilakukan adalah dengan memecah masalah yang kompleks menjadi masalah yang lebih kecil dan sederhana, kemudian mencari solusi untuk setiap masalah kecil tersebut.

Algoritme dinamis

Word Cloud

Apa saja jalur alternatif dari A ke H?

Match

Hitunglah jarak yang perlu ditempuh untuk masing-masing jalur!

• A-B-F-H

• A-C-F-H

• A-C-E-H

• A-D-E-H

• A-D-G-H

36 km

38 km

38 km

33 km

29 km

• 36 km

• 38 km

• 38 km

• 33 km

• 29 km

Kesimpulan

Dari contoh di atas, dapat dilihat bahwa algoritme greedy tidak dapat menghasilkan solusi terbaik karena algoritme greedy tidak menghitung terlebih dahulu hasil akhir sebelum mengambil keputusan. Keputusan pada setiap langkahnya hanya berdasarkan pada informasi yang ada pada saat itu. Oleh karena itu, dapat disimpulkan bahwa pada kasus mencari jalur tercepat, algoritme dinamis dapat memberikan hasil yang lebih baik dibanding algoritme greedy.

Google maps menggunakan algoritme dinamis untuk mencari rute tercepat.

Waktunya menguji pemahamanmu!

Jika supir bus menerapkan algoritme greedy, jalur yang akan dilalui adalah.....

Open Ended

Tentukan semua jalur alternatif yang dapat dilalui!

Labelling

Hitunglah jarak tempuh untuk masing-masing jalur!

Drag labels to their correct position on the image

46 km

41 km

45 km

42 km

Draw

Gambarlah rute dari rumahmu ke sekolah!

Poll

Bagaimana perasaanmu setelah mempelajari materi ini?

• Aku sudah paham

• Ada sedikit materi yang membingungkan

• Ada banyak materi yang membingungkan

• Aku tidak mengerti sama sekali

Yasudah, babay dulu.

See you next week!