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

Περίληψη

ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΜΕΛΕΤΩΝΤΑΙ ΘΕΜΑΤΑ ΤΗΣ ΨΕΥΔΟ-BOOLE ΑΛΓΕΒΡΑΣ ΠΟΥ ΑΝΑΦΕΡΟΝΤΑΙ ΣΤΗ ΜΗ ΓΡΑΜΜΙΚΗ ΨΕΥΔΟ-BOOLE ΕΞΙΣΩΣΗ ΚΑΙ ΑΝΙΣΟΕΞΙΣΩΣΗ ΚΑΙ ΠΡΟΤΕΙΝΟΝΤΑΙ ΤΡΕΙΣ ΑΛΓΟΡΙΘΜΟΙ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ ΠΟΥ ΔΙΝΟΥΝ ΤΙΣ ΟΙΚΟΓΕΝΕΙΕΣ ΛΥΣΕΩΝ ΤΩΝ ΠΡΟΒΛΗΜΑΤΩΝ ΑΥΤΩΝ. ΤΑ ΠΡΟΒΛΗΜΑΤΑ ΑΥΤΑ ΕΙΝΑΙ ΕΚΘΕΤΙΚΗΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ ΧΡΟΝΟΥ ΚΑΙ ΓΙΑ ΤΗΝ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΕΠΙΛΥΣΗ ΤΟΥΣ ΑΠΑΙΤΕΙΤΑΙ Η ΑΝΑΠΤΥΞΗ ΙΣΧΥΡΩΝ ΣΥΝΘΗΚΩΝ ΦΡΑΓΜΟΥ ΣΤΙΣ ΚΟΡΥΦΕΣ ΤΟΥ ΔΕΝΔΡΟΥ ΑΝΙΧΝΕΥΣΗΣ ΛΥΣΕΩΝ. ΓΙΑ ΤΗΝ ΕΠΙΛΥΣΗ ΤΗΣ ΓΡΑΜΜΙΚΗΣ ΨΕΥΔΟ-BOOLE ΕΞΙΣΩΣΗΣ (ΑΝΙΣΟΕΞΙΣΩΣΗΣ) ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ Η ΑΝΤΙΣΤΟΙΧΗ ΓΡΑΜΜΙΚΗ ΕΞΙΣΩΣΗ (ΑΝΙΣΟΕΞΙΣΩΣΗ). ΜΕ ΒΟΗΘΕΙΑ ΚΑΤΑΛΛΗΛΟΥ ΥΠΟΣΥΝΟΛΟΥ ΛΥΣΕΩΝ ΤΗΣ ΤΕΛΕΥΤΑΙΑΣ ΔΗΜΙΟΥΡΓΟΥΝΤΑΙ ΣΥΣΤΗΜΑΤΑ ΕΞΙΣΩΣΕΩΝ BOOLE ΠΟΥ ΟΔΗΓΟΥΝ ΣΤΙΣ ΟΙΚΟΓΕΝΕΙΕΣ ΛΥΣΕΩΝ ΤΗΣ ΕΞΙΣΩΣΗΣ (ΑΝΙΣΟΕΞΙΣΩΣΗΣ). ΑΠΟΔΕΙΚΝΥΟΝΤΑΙ ΤΡΙΑ ΘΕΩΡΗΜΑΤΑ ΠΟΥ ΘΕΜΕΛΙΩΝΟΥΝ ΤΗΝ ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ ΦΡΑΓΜΟΥ ΣΤΟΥΣ ΠΡΟΤΕΙΝΟΜΕΝΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ. ΤΕΛΟΣ, ΓΙΑ ΤΗΝ ΥΠΟΛΟΓΙΣΤΙΚΗ ΤΕΚΜΗΡΙΩΣΗΤΗΣ ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑΣ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ, ΕΧΕΙ ΕΠΙΛΥΘΕΙ ΜΕΓΑΛΟΣ ΑΡΙΘΜΟΣ ΠΡΟΒΛΗΜΑΤΩΝ, ΔΙΑΦΟΡΩΝ ΚΑΤΗΓΟΡΙΩΝ, ΠΟΥ ΤΟ ΜΕΓΕΘΟΣ ΤΟΥΣ ΦΘΑΝΕΙ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

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 RESUL ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/2064
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/2064
Εναλλακτικός τίτλος
A STUDY OF PSEUDO-BOOLEAN EQUATIONS INEQUALITIES AND SYSTEMS
Συγγραφέας
ΣΥΝΕΦΑΚΗ-ΑΡΑΜΠΑΤΖΗ, ΑΣΠΑΣΙΑ
Ημερομηνία
1992
Ίδρυμα
Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Σχολή Πολυτεχνική. Τμήμα Γενικό
Εξεταστική επιτροπή
ΤΣΟΥΡΟΣ ΚΩΝΣΤΑΝΤΙΝΟΣ
ΚΑΜΑΡΙΝΟΠΟΥΛΟΣ ΛΕΩΝΙΔΑΣ
ΣΕΡΑΦΕΙΜΙΔΟΥ-ΚΩΝΣΤΑΝΤΙΝΙΔΟΥ ΜΑΡΙΑ
ΦΡΑΓΚΑΚΙΣ ΧΑΡΑΛΑΜΠΟΣ
ΛΟΥΚΑΚΗΣ ΜΑΝΩΛΗΣ
Επιστημονικό πεδίο
Μηχανική & Τεχνολογία
Λέξεις-κλειδιά
ΑΛΓΟΡΙΘΜΟΙ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ; Διμερή γραφήματα; ΜΕΘΟΔΟΣ ΔΙΑΚΛΑΔΩΣΗΣ ΚΑΙ ΦΡΑΓΜΟΥ; ΨΕΥΔΟ-BOOLE ΕΞΙΣΩΣΕΙΣ, ΑΝΙΣΩΣΕΙΣ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά