ΜΥΕ-036 Υπολογιστική
Πολυπλοκότητα
Ακαδ.
Έτος 2023-24
Διδάσκων:
Χρήστος
Νομικός
Ώρες
Διαδασκαλίας:
Παρασκευή 16:00-19:00
Αίθουσα Διδασκαλίας: Ι1
ΑΝΑΚΟΙΝΩΣΕΙΣ
-
ΒΑΘΜΟΛΟΓΙΑ
ΕΞΕΤΑΣΤΙΚΗΣ ΠΕΡΙΟΔΟΥ
ΙΟΥΝΙΟΥ 2024
-
Η τελική
εξέταση του
μαθήματος θα
γίνει την Παρασκευή
28/6/2024, ώρα 3:00
μμ. Το τελικό
διαγώνισμα
χωρίζεται σε
δύο μέρη:
- Το πρώτο
μέρος (2 μονάδες) είναι με
κλειστές
σημειώσεις
περιλαμβάνει
γενικές
ερωτήσεις
θεωρίας (βασικούς
ορισμούς,
διατυπώσεις
θεωρημάτων
κλπ, όχι όμως
αποδείξεις
θεωρημάτων).
- Το δεύτερο
μέρος (9 μονάδες) είναι με
ανοιχτές
σημειώσεις
και
περιλαμβάνει
ασκήσεις.
- Η προθεσμία παράδοσης της
2ης και της
3ης σειράς ασκήσεων παρατείνεται έως τις
28 Ιουνίου 2024 (την ημέρα της τελικής εξέτασης).
Όσοι φοιτητές έχουν ήδη παραδώσει κάποια από τις σειρές αυτές, μπορούν αν
επιθυμούν να υποβάλουν ενημερωμένη έκδοση.
- Την
Πέμπτη 23 Μαΐου,
ώρα 11:00 - 14:00
θα γίνει αναπλήρωση της διάλεξης
που αναβλήθηκε την προηγούμενη εβδομάδα.
- Η διάλεξη της
επόμενης εβδομάδας θα γίνει εκτάκτως την
Πέμπτη 16 Μαΐου,
ώρα 11:00 - 14:00.
Δεν θα γίνει διάλεξη την Παρασκευή 17 Μαΐου.
- Η προθεσμία παράδοσης της
1ης και της 2ης σειράς ασκήσεων παρατείνεται έως τις 17 Μαΐου 2024.
Όσοι φοιτητές έχουν ήδη παραδώσει κάποια από τις σειρές αυτές, μπορούν αν
επιθυμούν να υποβάλουν ενημερωμένη έκδοση.
- Η διάλεξη της Παρασκευής
5/4/2024
αναβάλλεται.
- Το μάθημα
θα ξεκινήσει
εξ αποστάσεως
την Παρασκευή 23/2/2024.
Ο κωδικός εγγραφής
στην τάξη του μαθήματος
είναι
vsvu5ss.
ΑΣΚΗΣΕΙΣ
1η σειρά
ασκήσεων
(pdf)
2η σειρά
ασκήσεων
(pdf)
3η σειρά
ασκήσεων
(pdf)
4η σειρά
ασκήσεων
(pdf)
ΕΚΠΑΙΔΕΥΤΙΚΟ ΥΛΙΚΟ
Σημειώσεις
(pdf)
Υλοποιήσεις των μηχανών
Turing της ενότητας 2.1 (zip)
Πρόγραμμα προσομοίωσης
μηχανής
Turing με πολλές ταινίες από μηχανή με μία ταινία (zip)
ΠΡΟΤΕΙΝΟΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ:
"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.