Darstellung / Vorschau

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

Beschreibung des Kurses

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

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

Creation Date

Dienstag, 2. Dezember 2