Το πρόβλημα ικανοποιησιμότητας
Satisfiability (SAT) Problem
View/
Keywords
Πρόβλημα ικανοποιησιμότητας ; SAT ; Προτασιακή λογική ; Λογική παράσταση ; Εκτίμηση ; Λογική μεταβλητή ; Αληθής ; Ψευδής ; Λογικοί σύνδεσμοι ; Ικανοποιήσιμος τύπος ; Μη ικανοποιήσιμος τύπος ; Κανονική διαζευκτική μορφή (DNF) ; Κανονική συζευκτική μορφή (CNF) ; Αναγωγές ; Πρόβλημα της κλίκας ; Πρόβλημα ανεξαρτήτου συνόλου ; Πρόβλημα κάλυψης κορυφών ; Πρόβλημα 3-DM ; Κύκλος Hamilton ; Πρόβλημα χρωματισμού γραφήματος ; Πρόβλημα κάλυψης συνόλου ; Πρόβλημα 3-SAT ; Πρόβλημα αντιστοίχισηςAbstract
This thesis focuses on the satisfiability (SAT) problem. In the introduction, the historical background about the SAT problem is given, and the related key terms are explained. In the second chapter, several problems that are reduced to SAT are presented, as well as the corresponding reductions and their implementations. In the third chapter, some of the algorithms used for the efficient solution of SAT problems are described. More specifically, the three main approaches for designing a SAT solver are presented: using the resolution principle (DPP), using backtracking (DPLL) and conflict driven clause learning (CDCL). Their effectiveness or efficiency and ability in solving SAT problems is also examined. This thesis paves the way for further research on this topic.
Department
Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα ΠληροφορικήςNumber of pages
67Language
GreekDescription
ΠΡΟΒΛΗΜΑ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ SAT-SATISFIABILITY PROBLEM-Π20068Collections
Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα