Section outline

  • Προσφέρεται σε αυτό το εξάμηνο στο διδακτορικό πρόγραμμα της ΣΗΜΜΥ αντί του μαθήματος "Προχωρημένα Θέματα Θεωρητικής Πληροφορικής: Θεωρία Αριθμών και Κρυπτογραφία". 

    Προσφέρεται επίσης στα ΔΠΜΣ ΑΛΜΑ, ΕΜΕ, Μαθηματική Προτυποποίηση.

    Διδάσκοντες:

    Βοηθός Διδασκαλίας:

    Διαλέξεις:
    • Πέμπτη 16:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31) & διαδικτυακά (Webex link)

    Έναρξη μαθημάτων: 03/03/22


    Περιεχόμενο Μαθήματος:
    Εισαγωγή στα προβήματα μέτρησης λύσεων και την κλάση #P. Μετρητικά προβλήματα επιλύσιμα σε πολυωνυμικό χρόνο (Μέτρηση τέλειων ταιριασμάτων σε επίπεδους γράφους, Ολογραφικοί αλγόριθμοι). Προβλήματα μέτρησης ομομορφισμών, #CSP, προβλήματα Holant. Θεωρήματα διχοτομίας για προβλήματα μέτρησης. Αποδοτικοί προσεγγιστικοί αλγόριθμοι (FPTAS, FPRAS) για μετρητικά προβλήματα. Στατιστική Φυσική και η συνάρτηση διαμέρισης (partition function). Περιγραφική πολυπλοκότητα για κλάσεις προβλημάτων μέτρησης.