Analisis Dan Penyelesaian Spoj 10841 Supsup - Supplying The Suppliers Menggunakan Algoritma 2-Satisfiability Dengan Pendekatan Strongly Connected Components

Janitra, Calvin (2025) Analisis Dan Penyelesaian Spoj 10841 Supsup - Supplying The Suppliers Menggunakan Algoritma 2-Satisfiability Dengan Pendekatan Strongly Connected Components. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211020-Undergraduate _Thesis.pdf - Accepted Version Restricted to Repository staff only Download (4MB) | Request a copy

Abstract

Kasus SPOJ 10841 SUPSUP merupakan salah satu soal pemrograman yang dirancang untuk menguji kemampuan pemrograman di SPOJ, platform pemrograman kompetitif yang populer, dengan judul SUPSUP – Supplying the Suppliers. Kasus ini berbicara tentang seorang jenderal yang ingin menyuplai semua kebutuhan seluruh regunya. Tujuan dari kasus ini adalah untuk menentukan kemungkinan keberhasilan jenderal tersebut dalam melakukannya dengan ketentuan maupun aturan yang ada. Pada kasus ini, data yang diberikan sebagai input diolah menjadi informasi sebagai output berupa “March onward” jika memungkinkan atau “Coordination issue” jika tidak memungkinkan.
Dalam tugas akhir ini, dilakukan eksplorasi terhadap bagaimana permasalahan tersebut dapat dimodelkan secara logis dan diselesaikan secara algoritmik. Hasil analisis menunjukkan bahwa permasalahan ini dapat direduksi ke bentuk 2-Satisfiability (2-SAT), yakni bentuk khusus dari masalah pemenuhan logika proposisional. Untuk menyelesaikannya secara efisien, digunakan pendekatan berbasis Strongly Connected Components (SCC) dengan algoritma Tarjan, yang mampu mendeteksi konflik logika melalui struktur graf implikasi. Pendekatan ini dipilih karena menawarkan efisiensi waktu dan ruang, serta terbukti berhasil menyelesaikan seluruh test case dalam batasan waktu dan memori yang ditentukan pada kasus SUPSUP.
============================================================================================================================================
The SPOJ 10841 – SUPSUP case is one of the programming problems designed to test programming skills on SPOJ, a popular competitive programming platform, under the title SUPSUP – Supplying the Suppliers. This case describes a scenario in which a general must supply all the needs of his squads. The objective of the problem is to determine whether the general can successfully accomplish this task under certain constraints and rules. In this case, the input data is processed to produce an output of either "March onward" if it is feasible or "Coordination issue" if it is not.
In this thesis, an exploration is conducted to determine how the problem can be logically modeled and solved algorithmically. The analysis shows that the problem can be reduced to a form of 2-Satisfiability (2-SAT), a special case of propositional logic satisfiability. To solve it efficiently, a Strongly Connected Components (SCC) approach using Tarjan's algorithm is employed, which is capable of detecting logical conflicts through the structure of an implication graph. This approach is chosen because it offers time and space efficiency and has been proven to successfully solve all test cases within the specified time and memory limits for the SUPSUP problem.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	algoritma 2-satisfiability, strongly connected components 2-satisfiability algorithm, strongly connected components
Subjects:	T Technology > T Technology (General) > T58.62 Decision support systems
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Calvin Janitra
Date Deposited:	24 Jun 2025 04:55
Last Modified:	24 Jun 2025 04:55
URI:	http://repository.its.ac.id/id/eprint/119245

Actions (login required)

View Item