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