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

Video ini membahas konsep Divide and Conquer dalam Matematika Diskrit, di mana algoritma ini mengatasi masalah dengan membagi menjadi sub-masalah yang lebih kecil, menyelesaikan masing-masing, lalu menggabungkan solusinya. Konsep ini mirip dengan politik memecah belah dari Davy D. Atimpera. Dengan menggunakan relasi recurrence Fn = A * Fn/B + Gn, algoritma ini memperhitungkan jumlah operasi yang dibutuhkan untuk menyelesaikan masalah berukuran N.

Sekarang kita bicarakan tentang Divide and Conquer.

Ini algoritma yang punya nama Divide and Conquer.

Kalau waktu belajar sejarah dulu, Davy D. Atimpera itu adalah politik memecah belah.

Kemudian setelah dipecah belah, baru diurusin masing-masingnya karena kelompoknya sudah kecil-kecil.

Jadi kita misalkan punya algoritma yang problemnya itu berukuran N.

Kemudian setiap sub-masalah itu ukurannya misalnya N per B.

Jadi nanti kita akan mendapatkan problem-problem.

Itu masing-masing kan ukurannya lebih kecil.

Jadi diharapkan lebih mudah mencari solusinya.

Setelah sudah dapat solusinya nanti di-conquer.

Untuk menggabungkan hasilnya itu kita butuhkan operasi ekstra.

Jadi kalau Fn itu menyatakan banyaknya operasi yang dibutuhkan untuk menyelesaikan masalah berukuran N.

Maka si F ini ternyata bisa dituliskan dalam bentuk relasi recurrence.

Jadi bentuknya adalah Fn sama dengan A dikali Fn per B ditambah Gn.

Jadi kan masing-masing, tadi dibagi A ya.

Masing-masing itu ada Fn per B, Fn per B.

Jadi ada A dikali Fn per B ditambah ada operasi ekstranya tadi Gn.

Nah ini relasi yang kita sebut sebagai kalau bahasa Inggrisnya divide and conquer recurrence relation.