ΜΕΛΕΤΗ ΨΕΥΔΟΜΠΟΥΛΙΑΝΩΝ ΑΝΙΣΟΕΞΙΣΩΣΕΩΝ ΚΑΙ ΣΥΣΤΗΜΑΤΩΝ

Abstract

IN THIS THESIS, NOTIONS OF PSEUDO-BOOLEAN ALGEBRA ARE STUDIED WHICH DEAL WITH NONLINEAR PSEUDO-BOOLEAN EQUATION AND INEQUALITY. THREE ALGORITHMS OF IMPLICIT ENUMERATION TYPE ARE DEVELOPED WHICH CREATE THE FAMILY OF SOLUTION OF THESE PROBLEMS. THESE ARE EXPONENTIAL TIME COMPLEXITY PROBLEMS AND FOR THEIR EFFECTIVE RESOLUTION, IT IS NECESSARY TO DEVELOP POWERFUL BOUND CONDITIONS IN THE VERTICES OF THE SEARCHING TREE. IN ORDER TO SOLVE THE LINEAR PSEUDO-BOOLEAN EQUATION (INEQUALITY) THE EQUIVALENT LINEAR EQUATION (INEQUALITY) IS USED. WITH THE AID OF AN APPROPRIATE SOLUTIONS' SUBSET OF THE LATTER EQUATION, SYSTEMS OF BOOLEAN EQUATIONS ARE DEVELOPED THAT LEAD TO THE SOLUTIONS' FAMILIES. THREE THEOREMS ARE STATED ON WHICH IS BASED THE EFFECTIVENESS OF THE USED BOUND CONDITIONS OF THE PROPOSED ALGORITHMS. FINALLY, FOR AN EVALUATION OF THE ALGORITHMS' EFFECTIVENESS, A LARGE NUMBER OF PROBLEMS OF DIFFERENT CATEGORIES HAS BEEN SOLVED TO THE EXTENT OF 2000 VARIABLES GIVING VERY SATISFACTORY RESULTS.

ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΜΕΛΕΤΩΝΤΑΙ ΘΕΜΑΤΑ ΤΗΣ ΨΕΥΔΟ-BOOLE ΑΛΓΕΒΡΑΣ ΠΟΥ ΑΝΑΦΕΡΟΝΤΑΙ ΣΤΗ ΜΗ ΓΡΑΜΜΙΚΗ ΨΕΥΔΟ-BOOLE ΕΞΙΣΩΣΗ ΚΑΙ ΑΝΙΣΟΕΞΙΣΩΣΗ ΚΑΙ ΠΡΟΤΕΙΝΟΝΤΑΙ ΤΡΕΙΣ ΑΛΓΟΡΙΘΜΟΙ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ ΠΟΥ ΔΙΝΟΥΝ ΤΙΣ ΟΙΚΟΓΕΝΕΙΕΣ ΛΥΣΕΩΝ ΤΩΝ ΠΡΟΒΛΗΜΑΤΩΝ ΑΥΤΩΝ. ΤΑ ΠΡΟΒΛΗΜΑΤΑ ΑΥΤΑ ΕΙΝΑΙ ΕΚΘΕΤΙΚΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ ΧΡΟΝΟΥ ΚΑΙ ΓΙΑ ΤΗΝ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΕΠΙΛΥΣΗ ΤΟΥΣ ΑΠΑΙΤΕΙΤΑΙ Η ΑΝΑΠΤΥΞΗ ΙΣΧΥΡΩΝ ΣΥΝΘΗΚΩΝ ΦΡΑΓΜΟΥ ΣΤΙΣ ΚΟΡΥΦΕΣ ΤΟΥ ΔΕΝΔΡΟΥ ΑΝΙΧΝΕΥΣΗΣ ΛΥΣΕΩΝ. ΓΙΑ ΤΗΝ ΕΠΙΛΥΣΗ ΤΗΣ ΓΡΑΜΜΙΚΗΣ ΨΕΥΔΟ-BOOLE ΕΞΙΣΩΣΗΣ (ΑΝΙΣΟΕΞΙΣΩΣΗΣ) ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ Η ΑΝΤΙΣΤΟΙΧΗ ΓΡΑΜΜΙΚΗ ΕΞΙΣΩΣΗ (ΑΝΙΣΟΕΞΙΣΩΣΗ). ΜΕ ΒΟΗΘΕΙΑ ΚΑΤΑΛΛΗΛΟΥ ΥΠΟΣΥΝΟΛΟΥ ΛΥΣΕΩΝ ΤΗΣ ΤΕΛΕΥΤΑΙΑΣ ΔΗΜΙΟΥΡΓΟΥΝΤΑΙ ΣΥΣΤΗΜΑΤΑ ΕΞΙΣΩΣΕΩΝ BOOLE ΠΟΥ ΟΔΗΓΟΥΝ ΣΤΙΣ ΟΙΚΟΓΕΝΕΙΕΣ ΛΥΣΕΩΝ ΤΗΣ ΕΞΙΣΩΣΗΣ (ΑΝΙΣΟΕΞΙΣΩΣΗΣ). ΑΠΟΔΕΙΚΝΥΟΝΤΑΙ ΤΡΙΑ ΘΕΩΡΗΜΑΤΑ ΠΟΥ ΘΕΜΕΛΙΩΝΟΥΝ ΤΗΝ ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ ΦΡΑΓΜΟΥ ΣΤΟΥΣ ΠΡΟΤΕΙΝΟΜΕΝΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ. ΤΕΛΟΣ, ΓΙΑ ΤΗΝ ΥΠΟΛΟΓΙΣΤΙΚΗ ΤΕΚΜΗΡΙΩΣΗΤΗΣ ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑΣ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ, ΕΧΕΙ ΕΠΙΛΥΘΕΙ ΜΕΓΑΛΟΣ ΑΡΙΘΜΟΣ ΠΡΟΒΛΗΜΑΤΩΝ, ΔΙΑΦΟΡΩΝ ΚΑΤΗΓΟΡΙΩΝ, ΠΟΥ ΤΟ ΜΕΓΕΘΟΣ ΤΟΥΣ ΦΘΑΝΕΙ ΤΙΣ 2000 ΜΕΤΑΒΛΗΤΕΣ ΜΕ ΠΟΛΥ ΙΚΑΝΟΠΟΙΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ.