| ΑΥΤΟΜΑΤΑ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ | |
|---|---|
| (Σε κάποιες σχολές αναφέρονται ως θεωρία υπολογισμού ή μεταγλωττιστές) | |
| Περιγραφή | Το μάθημα πραγματεύεται τις έννοιες της υπολογισιμότητας (τι είναι υπολογίσιμο και τι όχι) και της υπολογιστικής πολυπλοκότητας (τι μπορεί να υπολογισθεί αποδοτικά και τι όχι). Τα θέματα που καλύπτονται είναι θεωρία αυτομάτων και τυπικών γλωσσών, υπολογισιμότητα από μηχανές Turing, μη-υπολογισιμότητα, και υπολογιστική πολυπλοκότητα. Σε όλη την πορεία του μαθήματος, ένα κεντρικό ζήτημα θα είναι η σχέση ντετερμινιστικών και μη-ντετερμινιστικών υπολογιστικών μηχανών. |
| Λέξεις – Κλειδιά | NFA, DFA, Κανονικές Γλώσσες, Λήμμα άντλησης, Γλώσσες χωρίς συμφραζόμενα, αυτόματα στοίβας, μηχανές Turing |
| Ύλη |
|
| Σημειώσεις | ΟΧΙ |
| Ασκήσεις | ΝΑΙ |
