Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep Dynamic Programming dalam Matematika Diskrit, di mana masalah dibagi menjadi submasalah yang lebih kecil untuk dicari solusinya sebelum digabungkan kembali. Contoh aplikasinya adalah optimalisasi jadwal seminar untuk meningkatkan kehadiran peserta. Metode ini membutuhkan penjadwalan yang tidak saling tumpang tindih antara pembicara. Dengan menggunakan notasi Pj, dapat dihitung nilai optimal untuk setiap submasalah. Algoritma ini penting untuk mencari jadwal optimal dengan jumlah peserta yang maksimal.

Problem terakhir yang kita akan bahas adalah Dynamic Programming.

Dynamic Programming ini adalah satu cara dimana menyelesaikan masalahnya itu dengan membagi problemnya menjadi beberapa problem yang lebih kecil,

kemudian nanti dia mencari solusinya untuk masing-masing yang kecil-kecil, biasanya lebih mudah, baru nanti digabungkan lagi.

Jadi masalahnya tentunya bukan masalah sederhana kalau mau dibagi-bagi, di sini adalah masalah yang cukup kompleks,

tapi ada syarat bahwa problem yang tadi dibagi kecil-kecil ini tidak boleh saling overlapping atau tumpang tindih.

Misalnya contoh aplikasinya adalah penjatuhan seminar, ini untuk optimalisasi penggunaan ruangan sehingga pembicara itu mendapat giliran di suatu ruang kuliah,

tapi kita bisa menampung sebanyak mungkin peserta dengan asumsi itu peserta itu sebetulnya ingin mendengarkan semua pembicara di situ.

Jadi misalkan di sini ada N pembicara, kemudian pembicara J itu dimulai pada waktu Tj dan berakhir pada waktu Ej dan dia akan diikuti sebanyak Wj mahasiswa.

Caranya adalah untuk mengoptimalkan jadwal tadi supaya jumlah mahasiswa yang datang juga banyak,

kita lihat atau kita notasikan Tj itu maksimum dari banyaknya kehadiran total pembicara dari J pembicara pertama,

jadi Tn itu adalah maksimum kehadiran dari seluruh pembicara mulai dari N1 sampai N tadi.

Dan E tadi kita pakai untuk berakhirnya waktu dari pembicara itu, disini kita asumsikan bahwa E1 itu lebih kecil sama dengan E2, lebih kecil sama dengan E3 dan seterusnya sampai lebih kecil sampai EN.

Di sini ada lagi notasi yang kita pakai yaitu Pj, Pj itu adalah bilangan bulat terbesar kalau I lebih kecil dari J dan EI lebih kecil sama dengan SJ,

jadi waktu selesainya si I itu sebelum mulainya si pembicara J, dan Pj sama dengan 0 untuk kasus yang lain.

Jadi disini kira-kira ada ilustrasinya, ada beberapa TOC, disini TOC 7,

jadi kita lihat TOC 1 misalnya mulai dari jam 8 sampai jam 10, TOC 2 nya jam 9 sampai jam 11 dan seterusnya,

dan kita tadi asumsinya adalah setiap TOC, TOC 1 itu selesai sebelum TOC 2, selesai sebelum TOC 3, TOC 3 sebelum TOC 4 dan seterusnya,

boleh selesai bersamaan seperti contohnya disini TOC 5, 6 dan 7 itu bareng.

Dan kita lihat disini P1 nya itu 0, P1 tadi adalah bilangan bulat terbesar sedemikian sehingga I nya lebih kecil dari J,

karena J nya itu 1 berarti kita tidak punya bilangan bulat yang lebih kecil makanya disini P1 nya 0.

Kemudian untuk P2 itu adalah bilangan bulat terbesar yang lebih kecil dari 2,

di mana si EI itu selesai lebih dulu daripada startnya yang sebelumnya.

Disini kita lihat bahwa dia selesai sesudah TOC 1 tapi dia mulainya sebelum TOC 1 selesai sehingga dia disini juga 0.

P3 itu adalah bilangan bulat yang terbesar sedemikian sehingga si P3 itu lebih besar dari bilangan bulat tersebut

di mana si I tadi kegiatannya atau TOC nya itu selesai sebelum si SJ, jadi sebelum si TOC 3.

Disini kita lihat ada TOC 1 yang selesai sebelum TOC 2 dimulai, jadi P3 nya 1.

Dan seterusnya kita akan bisa dapat seluruh P dari P1 sampai P7.

Seperti yang saya jelaskan tadi kita akan dapat Pj untuk Jnya 1-7 dengan P2 nya 0 karena belum ada yang sudah selesai.

P3 nya sudah ada yang selesai, P4 dan P5 juga belum ada yang selesai karena ini lebih panjang.

Kemudian P6 itu 2 dan P7 itu 4, nah pembicaraan 7 dan 4 itu kompatibel tapi pembicaraan 7 tidak kompatibel dengan pembicaraan 5 dan 6.

Artinya dia kalau kita lihat gambarnya di sini pembicaraan 7 itu mulai setelah pembicaraan 4 selesai, tapi kalau pembicaraan 5 dan 6 dia bersamaan.

Ini bisa dicari kalau ada yang tertarik tentang algoritma nya itu bisa dicari source code nya seperti ini.

Jadi untuk scheduling talk nya itu prosedur untuk mencari maksimum attendees yang hadir

S1, S2, S3, S4, S5, S6, S7, S8, S9 itu merupakan waktu dimulai, E1-EN waktu selesai talk nya, terus week nya itu banyaknya mahasiswa yang hadir kalau tadi kasusnya mahasiswa.

Terus disini suruh short talk nya dengan end time, jadi artinya waktu selesai dan di label lagi sehingga E1 lebih kecil sama dengan E2 lebih kecil sama dengan sampai EN.

Jadi kalau tadinya kan cuma pembicaraan 1 dari jam sekian sampai jam sekian terus nanti kita atur lagi supaya waktu selesainya itu naik, E1 lebih kecil sama dengan E2 dan seterusnya.

Dan nanti dicari nilai PJ nya itu dengan loop yang pertama dan untuk TJ nya kita pakai loop yang kedua, nanti kita akan dapat nilainya.

Nah itu sekilas tentang relasi recurrence.