Κ25 Θεωρία Υπολογισμού
Εξάμηνο : 7ο
Ωρες Θεωρίας : 3
Ωρες Φροντιστηρίου : 1
Τομείς που προσφέρουν το μάθημα :
Συνιστώμενα Προαπαιτούμενα μαθήματα : - Κ09 - Διακριτά Μαθηματικά
Κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα. Γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας. Αναδρομικές γλώσσες - μηχανές Turing. Αποφασισιμότητα (decidability). Ντετερμινισμός. Αναγωγή προβλημάτων (reduction). Σχέση των κλάσεων ντετερμινιστικού πολυωνυμικού χρόνου (P) και μη ντετερμινιστικού πολυωνυμικού χρόνου (NP). Θεωρία της NP-πληρότητας (NP-completeness). Επιστροφή
|
![]](../images/rdcorner.gif){kind=small}