Aku Ingin Jadi Pengajar karena Aku Bodoh

Wah sudah lebih dari setahun aku ga ngepost apa-apa di blog ini but yeah, aku masih hidup kok sampai sekarang :'). Rasanya udah pengen ngeblog beberapa kali tapi selalu aja kehalang sama rasa mager ini. Aku sudah nyiapin 3 topik yang 3-3 nya itu baru 1/4 jadi, setiap kali udah ngetik beberapa pasti rasanya mager dan jadinya diberhentikan dan ga pernah dilanjutkan lagi so i will try for this one untuk menyelesaikannya.

Judulnya kelihatan sangat clickbait sekali ya dan emang clickbait jadi kalian udah bisa close blog ini, alasan judulnya clickbait biar pengen jadi seperti media-media disana, ingin mengumpulkan para pembaca - pembaca baru (kalo ada) dan memperbanyak statistik view blog ini :p. Inspirasi menulis ini setelah tiba - tiba ditawarkan untuk mengajar. Lalu selama perjalanan pulang di gojek aku memikirkan sesuatu dan ingin menuangkannya di blog. Kurang lebih isi dari blog ini adalah menjelaskan bagaimana caraku mengajar suatu materi. Silahkan dinikmati.


Waktu Pelatnas 2 TOKI 2018 kebetulan aku jadi pengajar dan disuruh membawakan materi max flow dan bipartite matching. Memang aku bisa ngoding max flow dan bipartite matching tapi selama ini aku cuma makai saja dan ga pernah memahami konsepnya karena ga ngerti jadilah sekarang giliranku untuk belajar dan max flow dan bipartite matching biar bisa mengajarkannya ke mereka :v. Aku sendiri merasa menaruh banyak effort dalam membuat presentasi ini. Berikut akan kutunjukkan beberapa contohnya.

Awal - awal saat aku belajar max flow (waktu masih SMA) aku selalu bingung dengan backedge. Mengapa  harus ada backedge bagi beberapa orang mungkin jawaban bahwa itu digunakan untuk menarik balik flow yang telah digunakan tapi bagiku yang bodoh ini hal itu tidak cukup membuatku mengerti. Akhirnya setelah melihat contohnya aku baru mengerti

Graph awal dengan flow 1 semua, maaf kalo gambarnya gajelas

Augmenting path pertama yang didapatkan berupa path seperti tersebut, setelah augmenting path tersebut, tidak ada augmenting path lain, sehingga max flownya hanya 1

Padahal max flow pada graph tersebut ada 2 yaitu seperti gambar diatas

Setelah mendapatkan contoh tersebut akhirnya aku mengerti mengapa kita memerlukan backedge.


Setelah mengetahui mengapa kita memerlukan backedge sekarang kita tiba pada permasalahan selanjutnya. Bukankah dengan adanya backedge kompleksitas Ford Fulkerson akan menjadi sangat berat bahkan bisa infinite loop karena bisa aja backedge itu digunakan terus-menerus.

sedikit meme random dari fp di fb

Aku sendiri bingung cukup lama untuk mengerti mengapa ini tidak terajdi. Mungki bagi beberapa orang ini obvious tapi bagiku ini sesuatu yang mengganjal dalam pikiran. Akhirnya aku memiliki sebuah penjelasan terkati hal ini.

Sebelum itu, mari kita telusuri kembali algoritma Ford Fulkerson, kurang lebih algoritma dari Ford Fulkerson adalah "Dfs dari source dan berhenti apabila kita menemukan sink, setelah itu setiap edge-edge yang digunakan pada flow dikurangi dengan minimum capacity pada edge-edge yang dilalui, lalu backedgenya ditambahkan dengan minimum capacity pada edge-edge yang dilalui. Lalu apa hubungannya? Ada satu poin penting yang sangat berguna yaitu "Berhenti Apabila kita menemukan Sink"

src: visualgo.net

Gambar diatas adalah sebuah graf yang telah dilakukan algoritma max flow padanya. Apabila diperhatikan dengan baik ternyata backedge dari edge yang menuju ke sink tidak akan pernah dilalui. Mengapa? Ingat bahwa apabila kita tiba pada sink maka program kita akan berhenti sehingga edge yang berasal dari sink ke vertex lain tidak akan pernah digunakan. Bahkan apabila kita telaah lebih lanjut jumlahan hasil backedge pada vertex yang berasal dari sink (kita anggap bahwa edge directed pada awalnya dan tidak ada edge yang menghubungkan dari sink ke vertex lain) merupakan maxflownya. Cukup intuitif bukan?

yang dilingkari warna kuning adalah capacity dari backedge yang berasal dari edge yang menuju ke sink

Sebenarnya masih ada lagi hal-hal yang membingunkan seperti ini seperti mengapa kompleksitas edmonnds karp adalah O(V E^2) dan sebenarnya saat mengajar waktu itu aku sendiri masih belum mengerti dengan jelas proof mengapa kompleksitasnya seperti itu (Sekarang udah kok sekitara 2-3 hari yang lalu aku baru baca-baca lagi dan udah akhirnya ngerti) . Akhirnya dalam presentasi kuberikan link bacaan mengenai proof tersebut :') .


Kesimpulan: Menjadi orang bodoh itu kadang-kadang dapat berguna. Saat memahami suatu materi baru kadang memang memerlukan waktu yang lama apalagi apabila penjelasannya kadang kala agak tidak intuitif (terlalu teoritis kadang sangat membingungkanku). Tapi apabila kita telah mengerti materi itu maka kita bisa menjelaskannya dengan lebih intuitif kepada orang lain. Karena waktu dulu masih sering diajari, banyak hal yang tidak kumengerti dan aku cukup malu untuk bertanya mengenai hal tersebut (karena keliatannya semua pada ngerti dan aku ga ingin membuat mereka tertunda karenaku) jadinya harapanku saat mengajar adalah semuanya dapat mengerti jadi biasanya kujelaskan semua hal yang mungkin menurut beberapa orang trivial tapi sebenarnya tidak bagi beberapa orang lainnya.

Terima kasih telah membaca!