Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/900
Title: Χρήση μεθόδων επίλυσης (resolution) στη μελέτη κατωφλικών φαινομένων
Authors: Παρασκευάς, Αναστάσιος
Issue Date: 2008-08-29T08:06:01Z
Keywords: Κατωφλικά φαινόμενα
Πρόβλημα ικανοποιησιμότητας
Keywords (translated): SAT
Goerdt
Abstract: Στην παρούσα εργασία θα αναφερθούμε στο κατωφλικό φαινόμενο που εμφανίζεται στο k-SAT. Κύρια προσφορά της διπλωματικής είναι μια νέα απόδειξη του κάτω φράγματος στην περίπτωση του προβλήματος 2-SAT, όπου εκμεταλλευόμενοι γνωστά θεωρήματα από τη θεωρία τυχαίων γραφημάτων επιτυγχάνουμε μια ευκολότερη απόδειξη. Ξεκινάμε κάνοντας μια γενική παρουσίαση του προβλήματος της ικανοποιησιμότητας. Στο επόμενο κεφάλαιο παρουσιάζουμε κάποιους βασικούς ορισμούς και κάνουμε μια σύντομη αναδρομή στα αποτελέσματα που έχουν προκύψει. Αντικείμενο του τρίτου και τέταρτου κεφαλαίου είναι το 2-SAT όπου παρουσιάζονται αντιστοίχως η απόδειξη που δόθηκε από τον Goerdt[24] και μια νέα απόδειξη για το κάτω φράγμα με χρήση resolution. Στο τελευταίο κεφάλαιο στρέφουμε το ενδιαφέρον μας στην περίπτωση του 3-SAT και εξετάζουμε τις αποδείξεις ενός άνω και ενός κάτω κατωφλίου.
Abstract (translated): -
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Diplomatiki.pdf648.95 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.