Η Μετάβαση Φάσης στο Random - SAT ('νω φράγματα στο κατώφλι μη - ικανοποιησιμότητας) Διπλωματική εργασία. Πανεπιστήμιο Πατρών. [Πολυτεχνική Σχολή] Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

• Κύριος συγγραφέας: Γραμματικόπουλος, Ιωάννης (Συγγραφέας)
• Άλλοι συγγραφείς: Κυρούσης, Λευτέρης Μ.
• Μορφή: Βιβλίο
• Γλώσσα: Greek
• Έκδοση: Πάτρα Πανεπιστήμιο Πατρών. Τμήμα ΤΜΗΥΠ 2003
• Θέματα: Πτυχιακή Εργασία; ΠΤΥΧΙΑΚΗ ΕΡΓΑΣΙΑ 2003; Υπολογιστική πολυπλοκότητα; ΠΡΟΒΛΗΜΑ SAT; ΠΙΘΑΝΟΤΙΚΗ ΜΕΘΟΔΟΣ; Πιθανότητες

Πίνακας περιεχομένων:

• 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 Βιβλιογραφία