Υπολογιστική Πολυπλοκότητα (ΘΠ20)

Αρχοντία Γιαννοπούλου

Περιγραφή

Στόχος του μαθήματος είναι ο αυστηρός ορισμός της χρονικής και χωρικής πολυπλοκότητας των αλγορίθμων, ο ορισμός των βασικών κλάσεων πολυπλοκότητας και η παρουσίαση αντιπροσωπευτικών προβλημάτων για κάθε μία από αυτές.

Μεγάλη έμφαση δίνεται στην περιγραφή του μη-ντετερμινιστικού υπολογισμού και στην παρουσίαση του ερωτήματος αν οι κλάσεις P και NP ταυτίζονται.

Τέλος, επιδιώκεται η εξοικείωση των φοιτητών με τις τεχνικές κατάταξης προβλημάτων στις κλάσεις πολυπλοκότητα.

(Περισσότερες πληροφορίες εδώ.)

Ώρες διδασκαλίας: Τετάρτη 13:00 - 15:00 και Παρασκευή 11:00 - 13:00 μέσω zoom.
Ημερομηνία έναρξης μαθημάτων: Τετάρτη 30/09/2020 

Περιεχόμενο μαθήματος

Υπολογισιμότητα:

  • Μηχανές Turing (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.)
  • Η θέση Church-Turing.

Χρονική πολυπλοκότητα:

  • Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.).
  • Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T..
  • Η κλάση P.
  • Η κλάση NP.
  • Το θεώρημα προβολής.
  • Η κλάση coNP.
  • Η κλάση EXP.
  • Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας.
  • Το θεώρημα Cook-Levin.
  • NP-πλήρεις γλώσσες.
  • Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες.

Χωρική πολυπλοκότητα:

  • Το θεώρημα του Savitch.
  • H κλάση PSPACE.
  • PSPACE πληρότητα.
  • Οι κλάσεις L, NL και EXPSPACE.
  • NL πληρότητα.

Θεωρήματα Ιεραρχίας:

  • Το Θεώρημα Χωρικής Ιεραρχίας.
  • Το Θεώρημα Χρονικής Ιεραρχίας.

Ημερολόγιο

Ανακοινώσεις