Izzuddin, Muhammad (2016) Desain Dan Analisis Algoritma Penyelesaian Permasalahan Penugasan Bersyarat Dengan Representasi Bipartite Graph. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5112100012-Undergraduate_Thesis.pdf - Accepted Version Download (2MB) | Preview |
Preview |
Text
5112100012-Paper.pdf - Accepted Version Download (344kB) | Preview |
Preview |
Text
5112100012-Presentation.pdf - Presentation Download (1MB) | Preview |
Abstract
Masalah penugasan adalah salah satu masalah optimasi
untuk menemukan susunan penugasan pada sebuah bipartite
graph. Permasalahan dalam tugas akhir ini adalah permasalahan
penugasan bersyarat “Yet Another Assignment Problem” yang
terdapat pada situs penilaian daring SPOJ dengan nomor soal
6819 dan kode soal ASSIGN5. Dalam permasalahan ini,
diilustrasikan terdapat beberapa pekerjaan dan beberapa orang
pekerja. Setiap pekerjaan harus dilakukan oleh semua orang yang
ada serta setiap orang memiliki waktu yang dibutuhkan tersendiri
dalam menyelesaikan pekerjaan tersebut. Setiap orang hanya
dapat mengerjakan sebuah pekerjaan dan sebuah pekerjaan hanya
dapat dikerjakan oleh satu orang dalam satu waktu. Pekerjaan
yang dimaksud juga bersifat independen dalam artian dapat
dilakukan kapanpun oleh setiap orang. Semua orang juga dapat
berhenti kapanpun untuk melakukan sebuah pekerjaan tersebut.
Tugas akhir ini akan mengimplementasikan metode
pencarian maximum-size matching pada sebuah bipartite graph
yang mengacu pada permasalahan penugasan bersyarat. Metode
pencarian maximum-size matching yang digunakan adalah
algoritma Hopcroft-Karp.
Dalam buku ini akan dibahas algoritma Hopcroft-Karp
untuk menyelesaikan permasalahan penugasan bersyarat tersebut
dengan menggunakan bahasa pemrograman C++. Dari
serangkaian proses penelitian yang telah dilakukan, didapatkan
kesimpulan bahwa algoritma yang dirancang sesuai dengan
permasalahan ini dipengaruhi secara kuadratik baik oleh jumlah
pekerjaan ataupun pekerjanya. Secara umum Algoritma ini
memiliki kompleksitas
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.133 Izz d 3100016067313 |
| Uncontrolled Keywords: | algoritma Hopcroft-Karp, graf bipartite, masalah penugasan bersyarat, perfect matching, teori graf, bipartite graph, conditional assignment problem, graph theory, Hopcroft-Karp algorithm, perfect matching. |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | - Davi Wah |
| Date Deposited: | 21 Feb 2020 04:11 |
| Last Modified: | 21 Feb 2020 04:11 |
| URI: | http://repository.its.ac.id/id/eprint/74903 |
Actions (login required)
 |
View Item |