Γενικές Πληροφορίες
Ώρες Μαθήματος & Ασκήσεων:
Δευτέρα
Τετάρτη
Τετάρτη
13:00-16:00, Λ 206
9:00-11:00, Λ 206
9:00-11:00, Λ 206
Διδάσκων:
Μενέλαος Καραβέλας
Γραφείο:
Τηλέφωνο:
email:
Ώρες Γραφείου:
Γραφείο:
Τηλέφωνο:
email:
Ώρες Γραφείου:
Θ308Γ
2810 393 706
mkaravel at tem uoc gr
Δευτέρα 16:00-17:00, Τετάρτη 11:00-12:00
Διδακτικό Υλικό:
Michael Sipser, Εισαγωγή στη θεωρία υπολογισμού,
Πανεπιστημιακές Εκδόσεις Κρήτης, 2007. Απόδοση στα ελληνικά:
Χρήστος Καπούτσης.
Προαπαιτούμενα μαθήματα:
ΕΜ201 - Διακριτά Μαθηματικά
Περιεχόμενο Μαθήματος:
Πεπερασμένα αυτόματα και κανονικές γλώσσες, ισοδυναμία μεταξύ
αυτομάτων και κανονικών γλωσσών, ιδιότητες, λήμμα άντλησης για
κανονικές γλώσσες. Γλώσσες χωρίς συμφραζόμενα και αυτόματα
στοίβας, ισοδυναμία, ιδιότητες, λήμμα άντλησης για γλώσσες
χωρίς συμφραζόμενα. Μηχανές Turing. Μη-επιλύσιμα
προβλήματα. Πολυωνυμικά προβλήματα και προβλήματα στην κλάση
NP, NP-πλήρη προβλήματα. Αναγωγές προβλημάτων σε πολυωνυμικό
χρόνο/χώρο.
Βιβλιογραφία:
- Harry R. Lewis, Χρίστος Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική, 2005. Μετάφραση: Παναγιώτης Αντωνιάδης.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd edition. Addison-Wesley, 2001.
- Efim Kinber, Carl Smith. Theory of Computing: A Gentle Introduction, Prentice Hall, 2001.