Αυτόματα και Πολυπλοκότητα

ΑΥΤΟΜΑΤΑ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ

(Σε κάποιες σχολές αναφέρονται ως θεωρία υπολογισμού ή μεταγλωττιστές)

Περιγραφή

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

Λέξεις – Κλειδιά

NFA,DFA,Κανονικές Γλώσσες, Λήμμα άντλησης, Γλώσσες χωρίς συμφραζόμενα,αυτόματα στοίβας, μηχανές Turing

Ύλη

• Πεπερασμένα αυτόματα
• Αυτόματα στοίβας
• Μηχανές Turing
• Επιλύσιμα προβλήματα /  Μη επιλύσιμα προβλήματα

Σημειώσεις

ΟΧΙ

Ασκήσεις

ΝΑΙ