Θεωρία Υπολογισμού (7ΕΠ03)

Κωδικός: 
7ΕΠ03
Περιγραφή: 
Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing υπολογίσιμες συναρτήσεις. Θέση Church-Turing. Τα βασικά θεωρήματα: Κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμήσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία. Turing αναγωγισιμότητα και βαθμοί αναποκρισιμότητας. Υπολογιστική πολυπλοκότητα. Αιτιοκρατικές και μη - αιτιοκρατικές μηχανές Turing. Οι κλάσεις P και NP. Πολυωνυμικοί μετασχηματισμοί και NP - πληρότητα. Το θεώρημα του Cook. NP - πλήρη προβλήματα και αναγωγές.
Όνομα: 
Θεωρία Υπολογισμού
Είδος: 
Επιλογής (υποχρεωτικό)
Περίοδος: 
ΧΕ
Εξάμηνο: 
7
Ώρες Θεωρίας: 
4
ECTS: 
4
Συγγράμματα: 
- Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007. - Στοιχεία θεωρίας υπολογισμού, H. Lewis, Χ. Παπαδημητρίου, Εκδόσεις Κριτική, 2005.
Βιβλιογραφία: 
- Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007. - Στοιχεία θεωρίας υπολογισμού, H. Lewis, Χ. Παπαδημητρίου, Εκδόσεις Κριτική, 2005. - Αυτόματα και Τυπικές Γραμματικές, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2008. - Υπολογισιμότητα και Πολυπλοκότητα, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2004.
Μαθησιακοί Στόχοι: 
- Μοντέλα υπολογισμού και τυπικές γραμματικές - Μηχανές Turing - Ντετερμινισμός και μή-ντετερμινισμός - Μή-επιλυσιμότητα - Πολυωνυμική ιεραρχία - Κλάσεις P και NP
Τρόπος Εξέτασης: 
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό: 
Σημειώσεις