Η Μετάβαση Φάσης στο 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   Βιβλιογραφία