| Γνωστική Περιοχή: | Υπολογιστικών και Εφαρμοσμένων Μαθηματικών | ||
| Εξάμηνο: | 5ο | ||
| Κωδικός: | 52404 | ||
| Τύπος Μαθήματος: | Επιλογής | ||
| Ώρες Διδασκαλίας: | Θεωρία: 3 | Άσκηση: 0 | Εργαστήριο: 0 |
| ECTS : | 5 | ||
| Ιστοσελίδα Eclass: | |||
| Διδάσκοντες Μαθήματος: | |||
| Περίγραμμα μαθήματος: | Για να δείτε ή να αποθηκεύσετε το αρχείο πατήστε εδώ. | ||
Περιεχόμενο
Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing υπολογίσιμες συναρτήσεις. Θέση Church-Turing. Τα βασικά θεωρήματα: Κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμήσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία. Turing αναγωγισιμότητα και βαθμοί αναποκρισιμότητας. Υπολογιστική πολυπλοκότητα. Αιτιοκρατικές και μη – αιτιοκρατικές μηχανές Turing. Οι κλάσεις P και NP. Πολυωνυμικοί μετασχηματισμοί και NP – πληρότητα. Το θεώρημα του Cook. NP – πλήρη προβλήματα και αναγωγές.
Βιβλιογραφία
- Sipser M., Εισαγωγή στη Θεωρία Υπολογισμού, Παν. Εκδ. Κρήτης, 2009. Κωδικός βιβλίου στον Εύδοξο: 257
- Lewis H. R., Παπαδημητρίου Χ., Στοιχεία θεωρίας Υπολογισμού, Εκδ. Κριτική, 2005. Κωδικός βιβλίου στον Εύδοξο: 11776
Πρόσθετο Διδακτικό Υλικό
- Μάρκου Ε., Αλγοριθμική Θεωρία Κατανεμημένων Υπολογισμών, Ελληνικά Ακαδημαϊκά Ηλεκτρονικά Συγγράμματα και Βοηθήματα – Αποθετήριο Κάλλιπος, 2016.
