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

Εξάμηνο:
7ο
Τύπος Μαθήματος:
Προαιρετικό (ΠΜ)
Κατεύθυνση:
CS (Computer Science), CΕT (Computer Engineering and Telecoms)
Κωδικός:
ΘΠ20
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
B Βασικό
Διαχείριση Δεδομένων και Γνώσης (S2):
-
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
-
Σχετικά Μαθήματα
Υποχρεωτικά Προαπαιτούμενα:
Συνιστώμενα Προαπαιτούμενα:
-
Αναλυτική Περιγραφή
DIT_PPS_ΘΠ20-Υπολογιστική Πολυπλοκότητα.pdf
Σύντομη περιγραφή Μαθήματος

Μηχανές Turing (Μ.Τ.) (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.). Η θέση Church-Turing.  Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.). Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T.. Η κλάση P. Η κλάση NP. Συντακτικός ορισμός της κλάσης NP. Η κλάση CO-NP. Η κλάση EXP. Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας. Το θεώρημα Cook-Levin. NP-πλήρεις γλώσσες. Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες. Το θεώρημα του Savitch. H κλάση PSPACE. PSPACE πληρότητα. Οι κλάσεις L, NL και EXPSPACE. NL πληρότητα. Το θεώρημα χωρικής Ιεραρχίας. Το θεώρημα χρονικής Ιεραρχίας.

Βιβλιογραφία
  • Michael Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης 2007
  • Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική 2005
  • Christos H. Papadimitriou: Computational Complexity, Pearson publications 1993
  • Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company 1979
  • Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press 2007
  • John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley 1979
e-Class link
Υπολογιστική Πολυπλοκότητα - ECLASS

Διδάσκων