Θεωρία Υπολογισμού
Κωδ.:
Κ25
Εξάμηνο:
6
Τύπος μαθήματος νέο ΠΠΣ
:
Κατ’ Επιλογή Υποχρεωτικά Μαθήματα (ΕΥΜ)
K (new pps):
A
E2:
Y
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
0
Συνιστώμενα Προαπαιτούμενα Μαθήματα :
Κατεύθυνση:
Κορμός Πληροφορικής και Τηλεπικοινωνιών
Κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα. Γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας. Αναδρομικές γλώσσες - μηχανές Turing. Αποφασισιμότητα (decidability). Ντετερμινισμός. Αναγωγή προβλημάτων (reduction). Σχέση των κλάσεων ντετερμινιστικού πολυωνυμικού χρόνου (P) και μη ντετερμινιστικού πολυωνυμικού χρόνου (NP). Θεωρία της NP-πληρότητας (NP-completeness).