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

Κωδικός μαθήματος: ΜΥΕ036

Εβδομαδιαίες ώρες διδασκαλίας: 3,2,0

Εξάμηνο σπουδών: >=6ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος: http://www.cse.uoi.gr/~cnomikos/courses/cc/cc-main.htm

Προσφερόμενο:

Προαπαιτούμενα:

Περιεχόμενο:

Υπολογιστικά προβλήματα και τυπικές γλώσσες. Πρωταρχικές αναδρομικές συναρτήσεις. Αναδρομικές συναρτήσεις. Μηχανές Turing και ισοδύναμα υπολογιστικά μοντέλα. Η θέση του Church. Κανονική μορφή Kleene.

Μη επιλυσιμότητα. Αναδρομικά και αναδρομικά αριθμήσιμα σύνολα. Η αριθμητική ιεραρχία. Μη ντετερμινιστικές μηχανές Turing. Κλάσεις πολυπλοκότητας. Οι κλάσεις P, NP και PSPACE. Αναγωγές και πληρότητα. NP-πλήρη προβλήματα. Γραμματικές και η Ιεραρχία Chomsky.

Παρατηρήσεις: