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

 


Ακαδ. Έτος 2020-21

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

Ώρες Διαδασκαλίας:


ΑΝΑΚΟΙΝΩΣΗ: Το μάθημα θα ξεκινήσει τη Δευτέρα 5/10/2020. Οι διαλέξεις του μαθήματος θα γίνονται εξ αποστάσεως, με χρήση της πλατφόρμας Microsoft Teams (κωδικός εγγραφής στην ομάδα του μαθήματος: szjt4ve). 


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

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

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


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

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

Αναλυτικές διαφάνειες για τις μηχανές Turing της ενότητας 2.1 (zip)

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

Παραδειγμα αναγωγής 3SAT σε VERTEX-COVER (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.