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

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

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

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

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

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

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

        Το τελικό διαγώνισμα χωρίζεται σε δύο μέρη:

• - Το πρώτο μέρος (2 μονάδες) είναι με κλειστές σημειώσεις περιλαμβάνει γενικές ερωτήσεις θεωρίας (βασικούς ορισμούς, διατυπώσεις θεωρημάτων κλπ, όχι όμως αποδείξεις θεωρημάτων).
• - Το δεύτερο μέρος (8 μονάδες) είναι με ανοιχτές σημειώσεις και περιλαμβάνει ασκήσεις.

ΑΝΑΚΟΙΝΩΣΗ: Το φροντιστηριακό μάθημα της Παρασκευής 13/1/2023 θα γίνει 18:30-20:00.

ΑΝΑΚΟΙΝΩΣΗ: Την εβδομάδα 9-13/1/2023 θα γίνουν δύο έκτακτα φροντιστηριακά μαθήματα, στα οποία θα συζητηθούν οι λύσεις των ασκήσεων που δόθηκαν κατά τη διάρκεια του εξαμήνου, σύμφωνα με το παρακάτω πρόγραμμα:

• Δευτέρα  9/1/2023, 12:00-13:30: 1η και 2η σειρά ασκήσεων
• Παρασκευή  13/1/2023, 18:30-20:00 12:00-13:30: 3η και 4η σειρά ασκήσεων

ΑΝΑΚΟΙΝΩΣΗ: Οι διαλέξεις του μαθήματος θα ξεκινήσουν την Πέμπτη 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)  (προθεσμία παράδοσης: 9/1/2023 22/12/2022)

4η σειρά ασκήσεων (pdf)  (προθεσμία παράδοσης: 13/1/2023)

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

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