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

 


Ακαδ. Έτος 2022-23

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

Ώρες Διαδασκαλίας:  Πέμπτη 9:00-12:00

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


ΑΝΑΚΟΙΝΩΣΗ: Οι διαλέξεις του μαθήματος θα ξεκινήσουν την Πέμπτη 6/10/2022.

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


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

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

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

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


ΑΣΚΗΣΕΙΣ

1η σειρά ασκήσεων (pdf)  (προθεσμία παράδοσης: 17/11/2022 10/11/2022)

2η σειρά ασκήσεων (pdf)  (προθεσμία παράδοσης: 8/12/2022 1/12/2022)

3η σειρά ασκήσεων (pdf)  (προθεσμία παράδοσης: 22/12/2022)


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

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