Ύλη του μαθήματος:

    Εισαγωγή

  1. Γενική εισαγωγή και λίγα ιστορικά πρόσωπα.
  2. Τρία κεντρικά παραδείγματα τρόπων υπολογισμού.
  3. Ο «συμβολικός» τρόπος υπολογισμού – σύνταξη και σημασία.
  4. Οι μηχανές Turing.
  5. (Το σχετικό περιεχόμενο τα 1ο – 4ο ευρίσκεται κυρίως στις διδόμενες σημειώσεις.)


    Α΄ Oμαλές γραμματικές και πεπερασμένα αυτόματα.

  6. Ομαλές γραμματικές και Πεπερασμένα αυτόματα.
    • Ορισμός ομαλών (ή «κανονικών») γραμματικών (regular grammars))
    • Ορισμός πεπερασμένων αυτομάτων (finite automata).
    • Ορισμός διαγραμμάτων μετάβασης (transition diagrams).
    • Γλώσσες και αναγνώριση λέξεων/γλωσσών.
    • Η ισοδυναμία των παραπάνω.
  7. Πεπ. αυτόματα: το «θεώρημα ισοδυναμίας» αιτιοκρατικών και μή.
    • Το ακριβές (deterministic vs non-deterministic automata).
  8. Πεπ. αυτόματα: τα θεωρήματα «κλειστότητας» (closure theorems).
    • Κλειστότητα ως προς συνολοθεωρητικές πράξεις (ένωση, τομή, διαφορά, συμπλήρωμα)
    • Κλειστότητα ως προς γραμματικές πράξεις (παράθεση, επανάληψη, κατοπτρισμός)
  9. Πεπ. αυτόματα: το «λήμμα άντλησης» και περιορισμοί (pumping lemma).
    • Διατύπωση και απόδειξη αντλητικού λήμματος.
    • Παραδείγματα εφαρμογής.
  10. Πεπ. αυτόματα: ο χαρακτηρισμός των Myhill-Nerode.
    • Το ακριβές: διατύπωση και απόδειξη του θεωρήματος.
    • Παραδειγματα.
  11. Πεπ. αυτόματα: τα θεωρήματα «διαγνωσιμότητας» (decision algorithms).
    • Αλγόριθμοι για τον χειρισμό ομαλών γλωσσών:
    • συμπερίληψη λέξης σε ομαλή γλώσσα.
    • Κενότητα ή πληρότητα ομαλής γλώσσας.
    • Συμπερίληψη ομαλής γλώσσας σε άλλη ομαλή.
    • Ισότητα ομαλών γλωσσών.
  12. Πεπ. αυτόματα και «ομαλές εκφράσεις» (regular expressions).
    • Ορισμός ομαλών περιγραφών.
    • Ισοδυναμία ομαλών περιγραφών και διαγραμμάτων μετάβασης.
  13. Πεπ. αυτόματα: υπάρχει «καθολικό» αυτόματο; (universal machines/automata).
    • Διευκρίνιση της έννοιας «καθολικό» αυτόματο.
    • Απόδειξη ανυπαρξίας καθολικού αυτομάτου.
    • (Το σχετικό περιεχόμενο για το 12ο ευρίσκεται κυρίως στις διδόμενες σημειώσεις.)

    Β΄ Ασυμφραστικές γραμματικές και στοιβακτικά αυτόματα.

  14. Ασυμφραστικές γραμματικές και συντακτικά δένδρα.
    • Ο ορισμός των ασυμφραστικών γραμματικών (context free grammars).
    • Τα συντακτικά δένδρα (parse trees).
  15. Ασυμφραστικές γραμματικές: ανάλυση και στοιβακτικά αυτόματα.
    • Συντακτική ανάλυση (syntax analysis)
    • Ορισμός στοιβακτικών αυτομάτων (pushdown automata).
  16. Ασυμφραστικές γραμματικές: αιτιοκρατικές εκδοχές.
    • Αιτιοκρατικές εκδοχές σ. Αυτομάτων (deterministic pushdown automata).
  17. Ασυμφραστικές γραμματικές: μορφή Chomsky και διαγνωσιμότητα.
    • Κανονική μορφή Chomsky (Chomsky normal form).
    • Η διαγνωσιμότητα των ασυμφραστικών γραμματικών.
  18. Ασυμφραστικές γραμματικές: κλειστότητα, «άντληση» και περιορισμοί.
    • Κλειστότητα ασ. γραμματικών ως προς ένωση (closure properties).
    • Κλειστότητα ασ. γραμματικών ως προς παράθεση, επανάληψη κατοπτρισμό.
    • Αντλητικό λήμμα για ασ. γραμματικές (pumping lemma).
    • Μή-κλειστότητα ασ. Γραμματικών ως προς τομή ή συμπλήρωμα.
  19. Στοιβακτικά αυτόματα: μια προσθήκη που δεν προσθέτει... «Μία κατάσταση + μία στοίβα = μία στοίβα».


  20. Γ΄ Μηχανές Turing & εναλλακτικοί τρόποι υπολογισμού: ισοδυναμία & περιορισμοί.

  21. Διάφορα είδη προγραμματισμού, και τα ισχυρότατα από αυτά.
  22. Θετικά νέα: Ισχύς(Μηχανές/Μνήμης)  Ισχύς(Αναδρομικές/Περιγραφές).
  23. Θετικά νέα: Ισχύς(Μηχανές/Τuring)  Ισχύς(Μηχανές/Μνήμης).
  24. Θετικά νέα: καθολικές μηχανές και η «αλγοριθμική ισοδυναμία».
  25. Τα άσχημα νέα: ανεπίλυτα προβλήματα.
  26. Η καταστροφή (θ. Rice) και η πανωλεθρία (θ. Gödel).
  27. (Το σχετικό περιεχόμενο για 19ο – 24ο όλα ευρίσκεται κυρίως στις διδόμενες σημειώσεις.)

Βιβλίο

Τα προτεινόμενα από το σύστημα «Εύδοξος». Εκτιμούμε ιδιαίτερα το βιβλίο του Sipser, από τις ΠΕΚ.