Θεωρία Υπολογισμού

Εισαγωγή: Η ενότητα αυτή εισάγει τον αναγνώστη στο αντικείμενο της Θεωρίας Γλωσσών και Αυτομάτων. Παρουσιάζει επίσης τις σημαντικότερες εφαρμογές της. Ακόμη, παρατίθενται τα οργανωτικά θέματα διδασκαλίας του μαθήματος, όπως η προτεινόμενη βιβλιογραφία και η διαδικασία αξιολόγησης.

Λέξεις Κλειδιά: Εισαγωγή, οργανωτικά θέματα, βιβλιογραφία

Σύνολα και Σχέσεις: Παρουσιάζονται βασικά στοιχεία για τα σύνολα και τις σχέσεις. Τι ορίζεται ως σύνολο. Ποιες είναι οι ιδιότητες και οι πράξεις επί των συνόλων. Τι είναι το δυναμοσύνολο και η διαμεριση. Τα διατεταγμένα ζεύγη, οι δυαδικές σχέσεις και οι διατεταγμένες πλειάδες. Παράλληλα με τους ορισμούς παραθέτονται παραδείγματα και ασκήσεις κατανόησης.

Λέξεις Κλειδιά: Σύνολα, σχέσεις, δυναμοσύνολο, διαμεριση, διατεταγμένα ζεύγη,  δυαδικές σχέσεις, διατεταγμένες πλειάδες

Συναρτήσεις – σχέσεις: Στην ενότητα αυτή γίνεται κατανοητή η έννοια της συνάρτησης, τα είδη συναρτήσεων και η σύνθεση δυαδικών σχέσεων. Επίσης, παρουσιάζεται η αναπαράσταση με το μοντέλο του κατευθυνόμενου γράφου. Επίσης, ορίζονται οι ανακλαστικές, συμμετρικές και μεταβατικές σχέσεις και οι κλάσεις ισοδυναμίας.

Λέξεις Κλειδιά: Συνάρτηση, σύνθεση δυαδικών σχέσεων, κατευθυνόμενος γράφος, ανακλαστική/ συμμετρική/ μεταβατική σχέση, κλάσεις ισοδυναμίας

Ισοδυναμία, διάταξη, άπειρα σύνολα: Εξετάζονται οι σχέσεις και κλάσεις ισοδυναμίας. Πότε οι σχέσεις αποτελούν μερικές ή ολικές διατάξεις. Ορισμοί για πεπερασμένα και άπειρα σύνολα. Πώς αποδεικνύεται ότι ένα σύνολο είναι μετρήσιμα άπειρο.

Λέξεις Κλειδιά: Σχέσεις ισοδυναμίας, κλάσεις ισοδυναμίας, μερικές διατάξεις,  ολικές διατάξεις, πεπερασμένα / άπειρα / μετρήσιμα άπειρα σύνολα

Τεχνικές απόδειξης & Κλειστότητα: Η ενότητα αυτή παρουσιάζει τα βήματα και οι εφαρμογή τριών θεμελιωδών τεχνικών απόδειξης: η Αρχή της Μαθηματικής Επαγωγής, η Αρχή του “περιστερώνα” και η Αρχή της διαγωνιοποίησης. Επίσης, παρουσιάζεται η κλειστότητα και πώς αυτή υπολογίζεται.

Λέξεις Κλειδιά: Τεχνικές απόδειξης, Αρχή της Μαθηματικής Επαγωγής, Αρχή του “περιστερώνα”, Αρχή της διαγωνιοποίησης, κλειστότητα

Συμβολοσειρές & γλώσσες: Τι είναι το αλφάβητο και οι συμβολοσειρές ενός αλφαβήτου. Παρουσιάζονται οι πράξεις συμβολοσειρών όπως η παράθεση και η αντιστροφή. Ορίζεται η γλώσσα, οι ιδιότητες γλωσσών και οι πράξει της παράθεσης και  Kleene star.

Λέξεις Κλειδιά: Αλφάβητο, συμβολοσειρές, πράξεις συμβολοσειρών, παράθεση συμβολοσειρών, αντιστροφή συμβολοσειρών, γλώσσα, ιδιότητες γλωσσών, παράθεση γλωσσών, Kleene star γλωσσών

Πεπερασμένη αναπαράσταση γλωσσών: Η ενότητα αυτή παρουσιάζει τις κανονικές εκφράσεις, που αποτελούν έναν τρόπο  αναπαράστασης γλωσσών, και τα χαρακτηριστικά τους. Ακόμη παρουσιάζονται οι κλάσεις γλωσσών και οι ιδιότητές τους και δίνεται έμφαση στην κλάση των κανονικών γλωσσών, οι οποίες περιγράφονται από κανονικές εκφράσεις. Τέλος, ορίζεται η μηχανή αναγνώρισης γλώσσας και η παραγωγή γλωσσών.

Λέξεις Κλειδιά: κανονικές εκφράσεις, κλάσεις γλωσσών, ιδιότητές κανονικών γλωσσών, κανονικές εκφράσεις, μηχανή αναγνώρισης γλώσσας,  παραγωγή γλωσσών

Πεπερασμένα Αυτόματα (ΠΑ): Παρουσιάζεται η δομή και λειτουργία του πεπερασμένου αυτομάτου (ΠΑ), το οποίο είναι μια μηχανή που αναγνωρίζει μία γλώσσα. Εξετάζεται, για αρχή, το ντετερμινιστικό ΠΑ

Λέξεις Κλειδιά: Πεπερασμένο αυτόματο, αναγνώριση γλώσσας, ντετερμινιστικό πεπερασμένο αυτόματο

Μη ντετερμινιστικά αυτόματα (ΜΝΠΑ): Εισαγωγή στο μη ντετερμινισμό και τα μη ντετερμινιστικά πεπερασμένα αυτόματα με παραδείγματα. Αντιπαραβάλλονται τα ΜΝΠΑ με τα ντετερμινιστικά πεπερασμένα αυτόματα (ΝΠΑ) που διδάχθηκαν ήδη.

Λέξεις Κλειδιά: Μη ντετερμινισμός, μη ντετερμινιστικά πεπερασμένα αυτόματα

Ισοδυναμία ντετερμινιστικών και μη ντετερμινιστικών αυτομάτων: Τα θέματα της ενότητας είναι η αναγνώριση της ισοδυναμίας ανάμεσα σε ένα ΝΠΑ και ένα ΜΝΠΑ και η κατασκευή ένός ΝΠΑ που είναι ισοδύναμο με ένα ΜΝΠΑ.

Λέξεις Κλειδιά: Ισοδυναμία ΝΠΑ και ΜΝΠΑ, μετατροπή ΜΝΠΑ σε ΝΠΑ

Κλειστότητα, ΠΑ & καν. Εκφράσεις: Το θεώρημα της κλειστότηταςκαι η κλειστότητα των κανονικών γλωσσών. Πώς αποδεικνύεται η κανονικότητα μιας γλώσσας; Περιγραφή γλωσσών με κανονικές εκφράσεις.

Λέξεις Κλειδιά: Θεώρημα κλειστότητας, κλειστότητα κανονικών γλωσσών, αναπαράσταση γλωσσών, κανονικές εκφράσεις

Κανονικότητα ή μη των γλωσσών: Αποδεικνύοντας την κανονικότητα των γλωσσών. Η απόδειξη και εφαρμογή του θεωρήματος της “άντλησης”.

Λέξεις Κλειδιά: Κανονικότητα γλωσσών, θεωρήματος “άντλησης”.

Ελαχιστοποίηση πεπερασμένων αυτομάτων: Ισοδυναμία συμβολοσειρών. Διαίρεση των καταστάσεων ενός ΝΠΑ σε κλάσεις και περιγραφή της ελαχιστοποίησης ΝΠΑ.

Λέξεις Κλειδιά:  Ισοδυναμία συμβολοσειρών, ελαχιστοποίηση ΝΠΑ

Γραμματικές Χωρίς Συμφραζόμενα (ΓΧΣ): Αναγνωριστές & παραγωγοί γλωσσών και οι  ΓΧΣ ως παραγωγοί γλωσσών: (τυπικός ορισμός, παραδείγματα παραγωγής)

Λέξεις Κλειδιά: Αναγνωριστές γλωσσών, παραγωγοί γλωσσών, Γλώσσες Χωρίς Συμφραζόμενα

Συντακτικά δέντρα (ΣΔ): Τι περιγράφει ένα Συντακτικό Δέντρο (Δομή, τυπικός ορισμός) ΣΔ και παραγωγές. Όμοιες παραγωγές. Αριστερότερες και δεξιότερες παραγωγές. Το Θεώρημα του Συντακτικού Δέντρου. Διφορούμενες γραμματικές.

Λέξεις Κλειδιά: Συντακτικά Δέντρα, όμοιες παραγωγές, αριστερότερες παραγωγές, δεξιότερες παραγωγές, θεώρημα του Συντακτικού Δέντρου,  διφορούμενες γραμματικές

Αυτόματα Στοίβας (ΑΣ): Λειτουργία ΑΣ. Τυπικός ορισμός και παραδείγματα ΑΣ.

Λέξεις Κλειδιά: Αυτόματα Στοίβας

Αυτόματα Στοίβας και Γραμματικές Χωρίς Συμφραζόμενα: Θεώρημα ισοδύναμης αναπαράστασης. Παραγωγή ΑΣ από ΓΧΣ και το αντίστροφο.

Λέξεις Κλειδιά: Θεώρημα ισοδύναμης αναπαράστασης, παραγωγή ΑΣ, παραγωγή ΓΧΣ

Λήμμα Άντλησης για Γραμματικές Χωρίς Συμφραζόμενα: Ορισμός Λήμματος Άντλησης γι ΓΧΣ. Συντακτικά Δέντρα και παραγόμενες συμβολοσειρές. Μη κλειστότητα των ΓΧΣ.

Λέξεις Κλειδιά: Λήμμα “Άντλησης” γι ΓΧΣ. Συντακτικά Δέντρα,  μη κλειστότητα των ΓΧΣ

Ντεντερμινιστικές Γλώσσες Χωρίς Συμφραζόμενα - Μηχανές Turing: Ντετερμινιστικές ΓΧΣ. Εισαγωγή στις Μηχανές Turing. Τυπικός ορισμός ΜΤ.

Λέξεις Κλειδιά: Ντετερμινιστικές ΓΧΣ, Εισαγωγή Μηχανές Turing

Μηχανές Turing: Σύνθεση και Υπολογισμοί: Ορισμός και λειτουργία των μηχανών Turing. Ένας συμβολισμός για μηχανές Turing. Αναδρομικές συναρτήσεις.

Λέξεις Κλειδιά: Μηχανές Turing, αναδρομικές συναρτήσεις

Υπολογισμοί Μηχανών Turing - Αναδρομικές Γλώσσες: Υπολογισμοί με Μηχανές Turing. Γλώσσες που αποφασίζονται και αναδρομικές). Αναδρομικές συναρτήσεις. Αναδρομικά απαριθμήσιμες γλώσσες.

Λέξεις Κλειδιά: Μηχανές Turing, αναδρομικές γλώσσες, αναδρομικά απαριθμήσιμες γλώσσες

Μηχανές Turing Πολλαπλών Ταινιών: Ορισμός, χρήση, υπολογισμός και συμβολισμός των ΜΤ Πολλαπλών ταινιών. Θεώρημα προσομοίωσης.

Λέξεις Κλειδιά: ΜΤ Πολλαπλών ταινιών, Θεώρημα προσομοίωσης

Μηχανές Turing Τυχαίας Προσπέλασης: ΜΤ Τυχαίας Προσπέλασης. Αρχιτεκτονική, εντολές, λειτουργία, ορισμός ΜΤ Τυχαίας Προσπέλασης. Απόφαση-ημιαπόφαση και υπολογισμός.

Λέξεις Κλειδιά:  ΜΤ Τυχαίας Προσπέλασης, απόφαση-ημιαπόφαση

Μη Ντεντερμινιστικές Μηχανές Turing:  Ορισμός, σημασία,και προσομοίωση μη ντετερμινιστικών ΜΤ.

Λέξεις Κλειδιά: Μη ντετερμινισμός, Μηχανές Turing

Γραμματικές Χωρίς Περιορισμούς: Ορισμός και παράδειγμα ΓΧΠ. ΓΧΠ και αναδρομικά απαριθμήσιμες γλώσσες.

Λέξεις Κλειδιά:Γραμματικές Χωρίς Περιορισμούς, αναδρομικά απαριθμήσιμες γλώσσες

Καθολική Μηχανή Turing: Ποια είναι η θέση των Church-Turing για τις υπολογιστικές μηχανές. Η «προγραμματιζόμενη» Μηχανή Turing. Αναπαράσταση Μηχανής Turing.

Λέξεις Κλειδιά: Church-Turing, υπολογιστικές μηχανές, «προγραμματιζόμενη» Μηχανή Turing, καθολική Μηχανή Turing

Μη Επιλυσιμότητα: Το πρόβλημα του Τερματισμού. Το πρόβλημα του Τερματισμού με ΜΤ. Αναγωγή.

Λέξεις Κλειδιά: Mη επιλυσιμότητα, τερματισμός, αναγωγή