• Αρχικη
• Υλη
• Συμβουλες μελετης
• Ασκησεις
• Επικοινωνια

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

Εισαγωγή

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




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

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



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

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




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

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

Βιβλίο

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