Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

Υπολογιστική Πολυπλοκότητα

Course Feature
Περιγραφή μαθήματος

Κωδικός Μαθήματος: Α3

Ειδίκευση - Ενότητα: Επιστήμη και Μηχανική Δεδομένων: Ενότητα Α - Τεχνολογίες Αλγορίθμων και Πληροφορίας

Τύπος: Μάθημα Επιλογής

Εβδομαδιαίες ώρες διδασκαλίας: 3

Μονάδες ECTS: 7

Ιστοσελίδα Μαθήματος:

Προσφερόμενο: ΟΧΙ

Περιεχόμενο:

  • Υπολογιστικά προβλήματα και τυπικές γλώσσες.
  • Μηχανές Turing.
  • Μέτρα πολυπλοκότητας: χρόνος εκτέλεσης και χώρος εργασίας.
  • Μη ντετερμινιστικές μηχανές Turing.
  • Κλάσεις πολυπλοκότητας.
  • Σχέσεις μεταξύ κλάσεων πολυπλοκότητας.
  • Θεωρήματα Ιεραρχίας. Θεώρημα Χάσματος.
  • Αναγωγή πολυωνυμικού χρόνου και πληρότητα.
  • Η κλάση NP.
  • Το Θεώρημα του Cook.
  • NP-πλήρη προβλήματα λογικής.
  • NP-πλήρη προβλήματα γραφημάτων
  • NP-πλήρη προβλήματα σε σύνολα.
  • NP-πλήρη προβλήματα σε αριθμούς και ψευδοπολυωνυμικοί αλγόριθμοι.
  • Η κλάση PSPACE.
  • PSPACE -πλήρη προβλήματα.
  • Το θεώρημα του Savitch.
  • Το θεώρημα των Immerman-Szelepscenyi.
  • Πιθανοτικές κλάσεις πολυπλοκότητας: RP, ZPP, PP, BPP.
  • Πολυωνυμική ιεραρχία.

Αντιστοιχία Μαθήματος με παλαιό ΠΜΣ: