Έτος
2021-2022
Εξάμηνο
Εαρινό
Τύπος
Επιλογής
Διδάσκοντες
Aριστείδης Παγουρτζής
Ευστάθιος Ζάχος
Ημερομηνία έναρξης
3/3/2022
Περιγραφή
Εισαγωγή στα προβλήματα μέτρησης λύσεων και την κλάση #P. Μετρητικά προβλήματα επιλύσιμα σε πολυωνυμικό χρόνο (Μέτρηση τέλειων ταιριασμάτων σε επίπεδους γράφους, Ολογραφικοί αλγόριθμοι). Προβλήματα μέτρησης ομομορφισμών, #CSP, προβλήματα Holant. Θεωρήματα διχοτομίας για προβλήματα μέτρησης. Αποδοτικοί προσεγγιστικοί αλγόριθμοι (FPTAS, FPRAS) για μετρητικά προβλήματα. Στατιστική Φυσική και η συνάρτηση διαμέρισης (partition function). Περιγραφική πολυπλοκότητα για κλάσεις προβλημάτων μέτρησης.
Σημειώσεις
Είναι επιθυμητό οι φοιτητές/τριες να έχουν παρακολουθήσει επιτυχώς ένα μάθημα Υπολογιστικής Πολυπλοκότητας.