Penerapan Algoritma 2-Satisfiability Dengan Pendekatan Strongly Connected Components: Studi Kasus SPOJ 10589-KING

Wijaya, Calvin (2022) Penerapan Algoritma 2-Satisfiability Dengan Pendekatan Strongly Connected Components: Studi Kasus SPOJ 10589-KING. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000086-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (1MB) | Request a copy

Abstract

Permasalahan 2-SAT atau 2-satisfiability adalah permasalahan komputasi dalam menetapkan nilai boolean ke variabel, yang masing-masing memiliki dua kemungkinan nilai (True atau False), untuk memenuhi batasan pada pasangan variabel. Pada tugas akhir ini, akan dirancang penyelesaian permasalahan 2-SAT dalam menentukan apakah mungkin untuk memenuhi setidaknya satu dari dua permintaan setiap warga yang ada di kerajaan Nlogonia pada studi kasus SPOJ 10589 – King, menggunakan pendekatan Strongly Connected Components. Tugas akhir ini berhasil menyelesaikan permasalahan di atas dengan efisien, dengan rata-rata waktu penyelesaian 0.04 detik dengan menggunakan memori 4.5 MB.
================================================================================================
2-SAT or 2-satisfiability problem is a computational problem of assigning boolean values to variables, each of which has two possible values (True or False), to satisfy a system of constraints on pairs of variables. In this thesis, a special solution will be designed to determine is it possible to fulfil at least one of two requests of every citizen in Nlogonia kingdom in case study SPOJ 10589 – King using the Strongly Connected Component approach. This thesis has successfully solved te aforementioned problem efficiently, by an average completion time of in 0.04 seconds by using 4.5 MB of memory usage.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	boolean, strongly connected components, 2-satisfiability
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.74 Linear programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Calvin Wijaya
Date Deposited:	02 Feb 2022 07:18
Last Modified:	02 Feb 2022 07:18
URI:	http://repository.its.ac.id/id/eprint/92660

Actions (login required)

View Item