ΜΥΕ-036 Υπολογιστική Πολυπλοκότητα

Ακαδ. Έτος 2023-24

Διδάσκων: Χρήστος Νομικός

Ώρες Διαδασκαλίας:  Παρασκευή 16:00-19:00

Αίθουσα Διδασκαλίας: Ι1

ΑΝΑΚΟΙΝΩΣΕΙΣ

• Η προθεσμία παράδοσης της 1ης και της 2ης σειράς ασκήσεων παρατείνεται έως τις 17 Μαΐου 2024. Όσοι φοιτητές έχουν ήδη παραδώσει κάποια από τις σειρές αυτές, μπορούν αν επιθυμούν να υποβάλουν ενημερωμένη έκδοση.
• Η διάλεξη της Παρασκευής 5/4/2024 αναβάλλεται.
• Το μάθημα θα ξεκινήσει εξ αποστάσεως την Παρασκευή 23/2/2024. Ο κωδικός εγγραφής στην τάξη του μαθήματος είναι vsvu5ss.

ΑΣΚΗΣΕΙΣ

1η σειρά ασκήσεων (pdf)

2η σειρά ασκήσεων (pdf)

ΕΚΠΑΙΔΕΥΤΙΚΟ ΥΛΙΚΟ

Σημειώσεις (pdf)

Υλοποιήσεις των μηχανών Turing της ενότητας 2.1 (zip)

Πρόγραμμα προσομοίωσης μηχανής Turing με πολλές ταινίες από μηχανή με μία ταινία (zip)

ΠΡΟΤΕΙΝΟΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ:

"Computational Complexity", C. Papadimitriou.

"Computers and Intractability: A Guide to the Theory of NP-Completenes", M. R. Garey and D. S. Johnson.

"Computability, Complexity, and Languages", M. Davis, R. Sigal and E. Weyuker.

"Εισαγωγή στη Θεωρία Υπολογισμού", M. Sipser.

"Στοιχεία Θεωρίας Υπολογισμού" H. Lewis and C. Papadimitriou.