Intro Assalamualaikum warahmatullahi wabarakatuh Kembali lagi di pelajaran informatika kelas 11 Masih di materi strategi algoritmik dan pemrograman Berpikir komputasional pada sebab pemrograman dinamis Saat menyelesaikan sebuah permasalahan optimasi, yaitu mencari nilai terbesar atau terkecil, terkadang kita harus memperhitungkan beberapa kemungkinan pengambilan langkah untuk menyelesaikan permasalahan tersebut. Kemungkinan-kemungkinan tersebut mungkin memiliki akibat atau konsekuensi terhadap langkah-langkah selanjutnya Sehingga pendekatan seperti teknik greedy mungkin tidak akan menghasilkan kemungkinan menghasilkan jawaban yang optimal dalam hal ini teknik pemrograman dinamis atau dynamic programming atau DP mungkin akan lebih sesuai diterapkan teknik DP mengandung dua unsur utama yaitu yang pertama optimasi atau mencari nilai terkecil atau terbesar melalui serangkaian pilihan Serupa dengan teknik greedy, kita harus menentukan rangkaian langkah apa yang akan menghasilkan nilai optimal di akhir. Namun, beberapa dengan permasalahan yang dapat diselesaikan dengan teknik greedy, permasalahan yang sesuai untuk teknik DP memiliki struktur sedemikian rupa, sehingga pilihan langkah terbaik saat ini belum tentu merupakan pilihan terbaik secara keseluruhan.
Sehingga prinsipnya, prinsip greedy belum tentu dapat diterapkan dan semua kemungkinan kombinasi pilihan langkah harus diperhitungkan yang kedua nilai optimal yang diinginkan untuk permasalahan tersebut biasanya dapat dinyatakan sebagai kombinasi optimal dari sub-sub permasalahan yang sama tapi dengan ukuran yang lebih kecil atau dengan kata lain dapat dinyatakan secara rekursif namun sub-sub permasalahan yang harus dipertimbangkan biasanya memiliki overlap atau persinggungan sehingga dalam dalam proses perhitungannya diperlukan cara yang efisien untuk menghitung solusi untuk sup-sup permasalahan yang diperlukan agar tidak terjadi perulangan atau duplikasi dalam proses perhitungan cara yang umum digunakan adalah dengan menyimpan semua solusi dari subproblem yang sudah diketahui dalam sebuah tempat penyimpanan atau tabel teknik ini diperlukan biasa disebut dengan teknik memorisasi. Contoh, Agria ingin memanen tanaman cabai di halaman rumahnya. Tanaman tersebut ditata dalam bentuk kotak-kotak persegi seperti ilustrasi pada gambar. Angka berikutnya adalah tanaman cabai yang diperlukan untuk memanen tanaman cabai.
pada setiap kotak memiliki jumlah cabai yang ada di masing-masing tanaman berikut tabelnya kotak-kotaknya yang sebelah kiri nol berarti tidak ada cabainya kemudian sebelah kanannya ada 123 itu melambangkan cabai yang ada pada tanaman di kotak tersebut kemudian dibawahnya ada 10 2 10 10 5 hai hai Agria tidak punya banyak waktu karena ia harus segera pergi ke kampus. Oleh karena itu, ia tidak bisa memetik seluruh cabai tersebut. Ia hanya bisa mulai dari kotak manapun di kolom paling kiri.
dan berhenti di kotak manapun di kolom paling kanan Agria hanya bisa bergerak ke kotak tepat setelah kanannya atau bawahnya Berikut adalah salah satu dari sekian banyak kemungkinan jalur yang dapat dilalui oleh agria untuk memetik cabai pada gambar agria mulai dari baris yang ketiga disitu yang berwarna kuning kemudian bergerak ke kanan tiga kotak kemudian lanjut ke bawah terus lanjut ke kanan dan selesai selamat menikmati Pertanyaannya adalah, berapakah jumlah cabai terbanyak yang bisa digumpulkan oleh agria? Berikut jawabannya, pertama perlu dipahami bahwa penggunaan teknik greedy pada permasalahan ini tidak akan menghasilkan jawaban yang benar atau optimal dapat dilihat bahwa jika kita menggunakan prinsip greedy maka kita akan memilih untuk memulai dari kolom pertama baris terakhir Dengan nilai jumlah cabai terbesar yaitu 20 Namun jika kita memulai dari sini Maka tidak ada pilihan lain untuk langkah-langkah selanjutnya Selain bergerak terus ke kanan Maka nilai total cabai yang akan didapatkan adalah 20 ditambah 5 ditambah 1 tambah 0 tambah 0 Sehingga menghasilkan 26 cabai Jelas bahwa ada pilihan-pilihan jalur lain yang akan menghasilkan total nilai cabai lebih dari 26 Misalnya langkah sebagai berikut Akan menghasilkan jumlah total cabai 0 ditambah 10, tambah 2, tambah 10, tambah 10, tambah 5 Sehingga menghasilkan 37 cabai Menurut saya, ini adalah pilihan yang terbaik Metode berikutnya yang bisa kita pikirkan solusinya adalah mencoba semua kemungkinan jalur, lalu menghitung berapa nilai total cabai yang bisa didapatkan, dan terakhir mencari nilai terbesarnya. Namun dengan metode ini kita menemukan kendala lainnya, yaitu akan ada terlalu banyak kemungkinan yang harus kita perhitungkan.
Nah, satu hal yang dapat kita segera pahami adalah adalah bahwa ada banyak sekali persinggungan antara jalur-jalur yang berbeda. Sedemikian rupa, sehingga akan ada banyak sekali perulangan yang tidak perlu. Ketika kita menghitung nilai total 0 cabai dari semua kemungkinan jalur yang ada, sebagai contoh, kedua jalur di bawah ini, yaitu jalur merah dan jalur biru, akan melalui empat kotak yang sama. dan menghitung penjumlahan dari nilai di keempat kotak yang sama tersebut yaitu pada kotak yang berwarna kuning misalkan pada jalur biru yaitu dari kotak pojok kiri atas ke bawah kemudian ke kanan 4 kali dan jalur yang berwarna kuning warna merah dari pocok kiri atas ke kanan kemudian ke bawah dan selanjutnya ke kanan tiga kali tentunya pada jalur merah dan jalur biru sama-sama melalui jalur yang berwarna kuning Dengan menggunakan prinsip Dynamic Programming atau DP yang perlu kita lakukan adalah pertama-tama menyatakan solusi atau penyelesaian dari permasalahan awal sebagai kombinasi dari supermasalah.
yang lebih kecil dalam hal ini kita dapat membuat argumentasi bahwa nilai jumlah cabai terbanyak yang bisa kita kumpulkan sampai dengan suatu kotak tertentu dimanapun kolom tergantung dari nilai terbaik jumlah cabai sampai dengan kotak diatasnya atau kotak di sebelah kirinya jika ada dan tinggal kita jumlahkan saja dengan nilai banyaknya cabai di kotak akhir tersebut hal ini tentunya karena kita hanya bisa bergerak ke kanan atau ke bawah saja Jika nilai terbaik yang bisa kita dapatkan akan berakhir pada kotak warna hitam, seperti pada gambar, dapat dihitung dengan cara menghitung nilai terbaik yang didapatkan sampai dengan kotak merah. Misalkan nilainya adalah A dan sampai dengan kotak berwarna biru misalkan nilainya adalah B maka untuk mendapatkan nilai terbaik sampai dengan kotak warna hitam kita hanya mencari manakah jumlah yang tertinggi antara nilai A dan B kemudian nilai tersebut dijumlahkan dengan nilai C Proses di atas mengubah permasalahan ini menjadi lebih rekursif, di mana kita bisa menggunakan hasil perhitungan pada kotak-kotak sebelumnya untuk menghitung nilai terbaik pada kotak-kotak selanjutnya yang berada di atas. di posisi lebih ke kanan atau lebih ke bawah sehingga dengan cara ini kita bisa menghindari perulangan atau duplikasi proses perhitungan proses ini biasanya menggunakan sebuah tabel perhitungan yang biasa disebut dengan tabel memoisasi atau tabel DP istilah memoisasi berasal dari bahasa latin yaitu memorandum yang berarti mengingat yang kemudian bisa disingkat sebagai memo dalam bahasa inggris mohon dibedakan istilah memoisasi ini dengan memorisasi atau memorandum yang juga memiliki arti yang serupa yaitu proses mengingat namun memoisasi memiliki arti yang khusus dalam dunia komputasi yaitu menyimpan atau mengingat hasil perhitungan yang telah dilakukan sebelumnya sehingga tidak perlu mengulang perhitungan yang sama dua kali Untuk soal ini, kita buat tabel memoisasi tersebut sebagai berikut Yang pertama, kotak paling kiri atas kita berikan nilai sama dengan nilai kotak tersebut, yaitu 0 Kemudian Untuk setiap kotak lainnya, misalkan A adalah nilai yang sudah dihitung pada tabel memoisasi untuk kotak yang ada diatasnya Atau 0 jika kotak saat ini ada di baris tersebut Dan B adalah nilai yang sudah dihitung pada tabel memoisasi untuk kotak yang ada di sebelah kirinya Atau 0 jika kotak saat ini ada di kolom paling kiri Serta misalkan C adalah nilai cabai yang ada pada kotak saat ini Maka kita isi kotak saat ini pada tabel memoisasi dengan nilai maksimal dari A atau B Oke Kemudian ditambahkan C Langkah berikutnya kita lakukan proses di atas sampai tabel memoisasi terisi penuh Sesuai ukuran tabel nilai cabai di awal Nilai paling besar pada tabel memoisasi menunjukkan nilai total jumlah cabai terbesar yang bisa digumpulkan Hasil tabel memoisasi yang sudah terisi penuh untuk soal di atas adalah sebagai Berikut Tabel di atas adalah Kotak tanaman cabai Kemudian tabel di bawah adalah Tabel hasil memoisasi Pada kotak paling kiri atas yaitu 0 tidak ada cabainya, kemudian bergerak satu kolom ke kanan menghasilkan 1. Kemudian bergerak satu kolom ke kanan yang ada isi cabainya yaitu 2. Sehingga pada...
Tabel hasil memoisasi menghasilkan 3 Kemudian jika ke kanan yang berisi 3 Maka disitu tabel memoisasinya adalah 6 Dan jika ke kanan lagi yang ada cabainya yang berisi 10 Maka tabel memoisasi menghasilkan 16 Kembali ke sebelah kiri lagi, pada baris kedua, di situ ada cabai yang berisi 10, maka tabel memoisasinya adalah 10, karena di atasnya adalah 0. Kemudian di sebelah kanannya, masih pada baris kedua, di situ ada... Kotak tanaman cabainya adalah 2 cabai, sehingga pada tabel hasil memoisasi adalah 12. Kemudian di sebelah kanannya, kotaknya yaitu ada 10, sehingga pada tabel memoisasi adalah 22. Kemudian di sebelah kanannya lagi adalah 3. 32 karena 22 ditambah 10 Kemudian di sebelah kanannya adalah hasil tabel memoisasinya adalah 37 Karena 32 ditambah 5 sama dengan 37 Pada baris yang ketiga yaitu tabel memoisasi menghasilkan 15 itu dari 10 diatasnya ditambahkan isi dari kotak tanaman tabel yaitu 5 kemudian di sebelah kanannya adalah 18 berasal dari 15 ditambah 3 hasilkan 18 kemudian di sebelah kanannya kotak tanaman cabainya berisi 6 yang kita tambahkan adalah yang paling banyak yaitu 22 ditambah 6 sehingga menghasilkan 28 kemudian di sebelah kanannya adalah 5 sehingga menghasilkan tabel momisasi adalah 37 karena 32 ditambah 5 kemudian di sebelah kanannya lagi tetap 37 karena kotak tanaman cabainya adalah 0 Pada baris yang keempat, di situ kotak tanaman sabi nya adalah 0, maka tabel memo nya adalah 15. Kemudian di sebelah kanannya, dari 15 dan 18 kita pilih. pilih 18 yang paling banyak ditambah 4 sehingga menghasilkan 22 kemudian sebelah kanannya tentunya kita pilih yang 28 karena lebih banyak dari 22 sehingga tabel memo nya adalah 28 kemudian di sebelah kanannya lagi menghasilkan 39 yaitu 37 ditambah 2 kemudian di sebelah kanan lagi menghasilkan 39 yaitu 37 ditambah 2 kemudian di sebelah kanannya lagi dari 39 dan 37 kita pilih 39 sehingga tabel memonya adalah 39 ditambah 3 menghasilkan 42 pada baris yang terakhir disini hasil tabel memonya adalah 35 didapat dari 15 ditambah 20 kemudian di sebelah kanannya tabel kotak tanaman kanannya adalah 5 kita pilih dari 35 dan 22 kita pilih 35 ditambah 5 sama dengan 40 kemudian sebelah kanannya adalah 41 yaitu 40 ditambah 1 kemudian sebelah kanannya lagi yaitu 41 masih tetap kemudian kotak yang terakhir menghasilkan 42 didapat dari hasil pilihan antara 42 dan 41 kita pilih 42 sehingga tabel memonya pada kotak terakhir adalah 42 Ayo berlatih aktivitas bermain angka Selanjutnya deskripsi tugasnya yaitu Ani dan Budi sedang bermain sebuah permainan angka Pertama, Ani akan memilih sebuah angka bilangan bulat positif n selanjutnya Budi harus mengubah bilangan n ini menjadi angka 1 dengan menerapkan serangkaian langkah sebagai berikut Budi boleh mengganti bilangan n dengan n-1 jika bilangan saat ini adalah genap atau habis dibagi 2 maka Budi boleh menggantinya dengan n dibagi 2 jika bilangan saat ini habis dibagi 3 maka Budi boleh menggantinya dengan n dibagi 3 proses ini harus dilakukan oleh Budi secara terus menerus sampai bilangan yang dimilikinya menjadi 1 Misalnya Ani memilih N adalah 5 Maka Budi dapat melakukan proses mengubah 5 menjadi 1 sebagai berikut Dari 5 menjadi 4 menjadi 2 dan menjadi 1 Di sini kita lihat ada 3 langkah Pertanyaannya adalah tentukan berapa jumlah langkah minimum yang diperlukan jika Ani memilih N N sama dengan 25 Setelah selesai melakukan aktivitas tersebut, jawablah pertanyaan berikut ini dalam buku refleksi Menurut kalian, apakah permasalahan penukaran uang pada aktivitas sebelumnya yaitu menukarkan uang untuk topik algoritma greedy sebelumnya yaitu pecahan yang tersedia hanya 1000 2000 dan 10.000 dan kita ingin menukarkan nilai 15.000 dapatkah diselesaikan dengan teknik pemrograman dinamis dan bagaimana caranya kemudian apakah ada contoh permasalahan yang lain dalam kehidupan sehari-hari yang dapat diselesaikan dengan teknik pemrograman dinamis atau setidaknya dimana teknik memoisasi dapat diterapkan Kemudian, menurut Anda, apakah yang menjadi perbedaan penting antara algoritma greedy dan pemrograman dinamis?
Adakah kekurangan dan kelebihannya masing-masing? Selanjutnya, manakah pelajaran yang diperlukan? pelajaran yang paling berkesan dari topik ini demikian tadi materi pemrograman dinamis pada bagian berpikir komputasional pada bab strategi algoritmik dan pemrograman Terima kasih semoga bermanfaat Selamat belajar dan tetap semangat