Παρουσίαση/Προβολή

(Κ25) -  Ροντογιάννης Παναγιώτης

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

Κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα. Γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας. Αναδρομικές γλώσσες - μηχανές Turing. Αποφασισιμότητας (decidability). Ντετερμινισμός. Αναγωγή προβλημάτων (reduction). Σχέση των κλάσεων ντετερμινιστικού πολυωνυμικού χρόνου (P) και μη ντετερμινιστικού πολυωνυμικού χρόνου (NP). Θεωρία της NP-πληρότητας (NP-completeness). Όλες οι πληροφορίες για το μάθημα βρίσκονται στη σελίδα:

http://www.di.uoa.gr/~prondo/toc/toc.html

Ημερομηνία δημιουργίας

Τρίτη 2 Δεκεμβρίου 2