Το πρόβλημα ικανοποιησιμότητας

Καΐκα, Θεοδώρα

dc.contributor.advisor	Τασούλας, Ιωάννης
dc.contributor.author	Καΐκα, Θεοδώρα
dc.date.accessioned	2024-08-01T10:18:27Z
dc.date.available	2024-08-01T10:18:27Z
dc.date.issued	2024
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/16648
dc.identifier.uri	http://dx.doi.org/10.26267/unipi_dione/4070
dc.description	ΠΡΟΒΛΗΜΑ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ SAT-SATISFIABILITY PROBLEM-Π20068	el
dc.description.abstract	Η παρούσα πτυχιακή εργασία επικεντρώνεται στο πρόβλημα ικανοποιησιμότητας (satisfiability problem - SAT). Στο κεφάλαιο της εισαγωγής, δίνονται μια ιστορική αναδρομή για το πρόβλημα SAT και η επεξήγηση βασικών όρων που αφορούν αυτό. Στο δεύτερο κεφάλαιο, αναλύονται κάποια από τα προβλήματα που ανάγονται στο SAT και παρουσιάζονται οι αντίστοιχες αναγωγές καθώς και οι υλοποιήσεις τους. Τέλος, στο τρίτο κεφάλαιο, περιγράφονται διάφοροι αλγόριθμος επίλυσης του SAT. Πιο συγκεκριμένα, παρουσιάζονται τρεις βασικές προσεγγίσεις σχεδίασης αλγορίθμων επίλυσης του SAT: με τη βοήθεια της αρχής της απόφασης (DPP), με χρήση της τεχνικής backtracking (DPLL) και με εκμάθηση παρενθέσεων μέσω συγκρούσεων (CDCL). Επίσης εξετάζεται ή αποτελεσματικότητα και η ικανότητά τους στην επίλυση προβλημάτων SAT. Αυτή η πτυχιακή εργασία ανοίγει το δρόμο για περαιτέρω έρευνα του συγκεκριμένου θέματος.	el
dc.format.extent	67	el
dc.language.iso	el	el
dc.publisher	Πανεπιστήμιο Πειραιώς	el
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/gr/	*
dc.title	Το πρόβλημα ικανοποιησιμότητας	el
dc.title.alternative	Satisfiability (SAT) Problem	el
dc.type	Bachelor Dissertation	el
dc.contributor.department	Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής	el
dc.description.abstractEN	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.	el
dc.subject.keyword	Πρόβλημα ικανοποιησιμότητας	el
dc.subject.keyword	SAT	el
dc.subject.keyword	Προτασιακή λογική	el
dc.subject.keyword	Λογική παράσταση	el
dc.subject.keyword	Εκτίμηση	el
dc.subject.keyword	Λογική μεταβλητή	el
dc.subject.keyword	Αληθής	el
dc.subject.keyword	Ψευδής	el
dc.subject.keyword	Λογικοί σύνδεσμοι	el
dc.subject.keyword	Ικανοποιήσιμος τύπος	el
dc.subject.keyword	Μη ικανοποιήσιμος τύπος	el
dc.subject.keyword	Κανονική διαζευκτική μορφή (DNF)	el
dc.subject.keyword	Κανονική συζευκτική μορφή (CNF)	el
dc.subject.keyword	Αναγωγές	el
dc.subject.keyword	Πρόβλημα της κλίκας	el
dc.subject.keyword	Πρόβλημα ανεξαρτήτου συνόλου	el
dc.subject.keyword	Πρόβλημα κάλυψης κορυφών	el
dc.subject.keyword	Πρόβλημα 3-DM	el
dc.subject.keyword	Κύκλος Hamilton	el
dc.subject.keyword	Πρόβλημα χρωματισμού γραφήματος	el
dc.subject.keyword	Πρόβλημα κάλυψης συνόλου	el
dc.subject.keyword	Πρόβλημα 3-SAT	el
dc.subject.keyword	Πρόβλημα αντιστοίχισης	el
dc.date.defense	2024-07

Αρχεία σε αυτό το τεκμήριο

Name:: kaika-20068.pdf
Μέγεθος:: 21.83Mb
Τύπος:: PDF
Description:: Πτυχιακή εργασία

Προβολή/Άνοιγμα

Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές

Τμήμα Πληροφορικής

Εμφάνιση απλής εγγραφής

Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα

Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα