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

 


Ακαδ. Έτος 2021-22

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

Ώρες Διαδασκαλίας:  Τετάρτη 17:00-20:00

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


ΑΝΑΚΟΙΝΩΣΗ: Το μάθημα θα ξεκινήσει τη Τετάρτη 6/10/2021.


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

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

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


ΑΣΚΗΣΕΙΣ (Προθεσμία παράδοσης για όλες τις σειρές ασκήσεων: 11/1/2022. Οι ασκήσεις συνεισφέρουν 2 μονάδες bonus στην τελική βαθμολογία).

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


Προτεινόμενη Βιβλιογραφία:

"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.