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

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

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

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

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

Μονάδες ECTS: 7

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

Προσφερόμενο:

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

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

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