Η Μετάβαση Φάσης στο Random - SAT ('νω φράγματα στο κατώφλι μη - ικανοποιησιμότητας)

Η Μετάβαση Φάσης στο Random - SAT ('νω φράγματα στο κατώφλι μη - ικανοποιησιμότητας) Διπλωματική εργασία. Πανεπιστήμιο Πατρών. [Πολυτεχνική Σχολή] Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής Ιωάννης Γραμματικόπουλος; Ε. Κυρούσης επιβλέπων καθ. - Πάτρα Πανεπιστήμιο Πατρών. Τμήμα ΤΜΗΥΠ 2003 - iii,60σ. σχημ.

Βιβλιογραφία : σσ. 57 - 60

1. Εισαγωγή 1.1 Η μετάβαση φάσης στο πρόβλημα SAT 1.2 Μετάβαση φάσης και αλγοριθμική πολυπλοκότητα 2. Η Μέθοδος των τοπικών μεγίστων 2.1 Ορολογία και μοντέλα για τυχαίους λογικούς τύπους και γραφήματα 2.2 Η Μέθοδος της πρώτης ροπής 2.3 Η μέθοδος των local - maxima 2.4 Η Γενίκευση της μεθόδου 3. Η μέθοδος των single -flips 3.1 Η περιγραφή της μεθόδου sihgle - flips 3.2 Βελτιστοποίηση στη μέθοδο των single - flips 4. Η μέθοδος των double - flips 4.1 Εισαγωγή στη μέθοδο των double - flips 4.2 Συσχετισμοί γεγονότων μπλοκαρίσματος των double - flips 4.3 Υπολογισμός του φράγματος με τη μέθοδο των double - flips 5. Προοπτικές εξέλιξης της μεθόδου Local Maxima 5.1 Βέλτιστη εκμετάλευση των double - flips 5.2 Η μέθοδος Local Maxima στο 3 - coloring 5.3 Απόπειρες μέτρησης των double - flips στο 3 -coloring 5.4 Απόπειρες μέτρησης των double - flips στο 3 -SAT 5.5 Καλύτερη τιμή άνω φράγματος στο 3 - SAT 5.6 τα k - flips το 3 - coloring Βιβλιογραφία


Πτυχιακή Εργασία
ΠΤΥΧΙΑΚΗ ΕΡΓΑΣΙΑ 2003
Υπολογιστική πολυπλοκότητα
ΠΡΟΒΛΗΜΑ SAT
ΠΙΘΑΝΟΤΙΚΗ ΜΕΘΟΔΟΣ
Πιθανότητες
Πανεπιστήμιο Πατρών, Βιβλιοθήκη & Κέντρο Πληροφόρησης, 265 04, Πάτρα
Τηλ: 2610969621, Φόρμα επικοινωνίας
Εικονίδιο Facebook Εικονίδιο Twitter Εικονίδιο Soundcloud