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

 


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

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

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

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


ΑΝΑΚΟΙΝΩΣΗ: ΒΑΘΜΟΛΟΓΙΑ ΕΞΕΤΑΣΤΙΚΗΣ ΠΕΡΙΟΔΟΥ ΦΕΒΡΟΥΑΡΙΟΥ 2022

ΑΝΑΚΟΙΝΩΣΗ: Η τελική εξέταση του μαθήματος θα γίνει τη Δευτέρα 31/1/2022, ώρα 3:00 μμ. στην αίθουσα Ι5, με ανοιχτά βιβλία και σημειώσεις.

ΑΝΑΚΟΙΝΩΣΗ: Η προθεσμία παράδοσης των ασκήσεων παρατείνεται έως την Παρασκευή 14/1/2022.

ΑΝΑΚΟΙΝΩΣΗ: Η διάλεξη της Τετάρτης 22/12/2021 αναβάλλεται. Η αναπλήρωσή της θα γίνει την Παρασκευή  14/1/2022, ώρα 12:00.

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


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

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

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


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

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

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

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

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

5η σειρά ασκήσεων (δεν είναι για παράδοση) (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.