Περιγραφή

Εισαγωγικές Έννοιες: Αυτόματα, Υπολογισιμότητα, Πολυπλοκότητα, Έννοιες, Ορισμοί, Θεωρήματα, Αποδείξεις και Είδη Αποδείξεων.

Αφηρημένες Μηχανές και Γλώσσες: Εισαγωγή, η Στοιχειώδης Μηχανή (ΣΜ), Μηχανές Πεπερασμένων Καταστάσεων (ΜΠΚ). Πεπερασμένο Αυτόματο (ΠΑ), Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΑΠΑ), Μη Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΜΑΠΑ), Δένδρα Αποδοχής (ΔΑ), Πεπερασμένα Αυτόματα με ε-Μεταβάσεις (ΜΑΠΑΕΜ), Ισοδυναμία ΜΑΠΑ και ΜΑΠΑΕΜ, Ελαχιστοποίηση ενός ΑΠΑ, Θεώρημα της Επαναληπτικότητας, Πεπερασμένα Αυτόματα και Γραμματικές, Γραμματικές της Ιεραρχίας Chomsky, Κανονικά Σύνολα (ΚΣ), Κανονικά Σύνολα και Πεπερασμένα Αυτόματα, Εύρεση της Κανονικής Έκφρασης ενός ΠΑ, Ικανότητες και Ανεπάρκειες των ΠΑ. Πεπερασμένα Αυτόματα με Στοιβάδα (ΠΑΣ), Μη Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΜΑΠΑΣ), Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΑΠΑΣ), Αποδοχή με Κενή Στοιβάδα, Ισοδυναμία ΠΑΣ και Γλωσσών Ανεξάρτητων Συμφραζομένων. Μηχανές Turing (ΜΤ), Εισαγωγή, Μαθηματική Περιγραφή, Χρήσιμα Τεχνάσματα για την Κατασκευή της ΜΤ, Τροποποιήσεις της ΜΤ, η ΜΤ ως Διαδικασία, Μη Επιλυσιμότητα, η Θέση των Church-Turing, η Καθολική ΜΤ, το Πρόβλημα του Τερματισμού.Υπολογιστική Πολυπλοκότητα, NP-πληρότητα. .

Διδάσκοντες

• Σ. Μπαλτζής

Περίγραμμα Μαθήματος