Τίτλος Μαθήματος Θεωρία Υπολογισμού
Κωδικός Μαθήματος 321-6702
Εξάμηνο 5
ECTS 5
Ώρες (Θεωρία) 3
Ώρες (Εργαστηρίο)
Διδάσκοντας 321-6702

Ύλη μαθήματος

Τυπικές γλώσσες. Κανονικές γλώσσες, πεπερασμένα αυτόματα, λήμμα άντλησης για κανονικές γλώσσες. Γραμματικές και γλώσσες χωρίς συμφραζόμενα, αυτόματα στοίβας, λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα. Μηχανές Turing, υπολογισιμότητα, η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού. Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp. Αναγωγή και πληρότητα. Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ, αλγοριθμικές συνέπειες NP-πληρότητας. Πολυπλοκότητα χώρου, η κλάση PSPACE, το θεώρημα του Savitch, PSPACE-πλήρη προβλήματα. Πιθανοτικός υπολογισμός. Πιθανοτικά ελέγξιμες αποδείξεις.

Επιδιωκόμενα μαθησιακά αποτελέσματα

Η κατανόηση των ορίων του υπολογισμού μέσα από την μελέτη απλών και σύνθετων υπολογιστικών μηχανών.

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

Δεν απαιτούνται.

Εγχειρίδια του μαθήματος

1. Sipser Michael, Εισαγωγή στη Θεωρία Υπολογισμού.
2. Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Στοιχεία θεωρίας υπολογισμού.

Συμπληρωματική βιβλιογραφία

Information and Computation

Διδακτικές και μαθησιακές μέθοδοι

 

Δραστηριότητα Φόρτος Εργασίας Εξαμήνου
Διαλέξεις 39 ώρες

 
Προσωπική μελέτη 83 ώρες
 
Τελική εξέταση 3 ώρες
Σύνολο Μαθήματος 125 ώρες (5 ECTS)

 

Μέθοδοι αξιολόγησης / βαθμολόγησης

Διαλέξεις με προβολή διαφανειών. Χρήση υλικού από διαδίκτυο, όπως υπερκειμένου και webcasts. Καταγραφή διαλέξεων σε βίντεο για επαναλητπικούς λόγους και καλύτερη εμπέδωση. Ασκήσεις θεωρητικές και εργαστηριακές ανά εβδομάδα. Παρουσίαση από φοιτητές ερευνητικών εργασιών. Τελική γραπτή εξέταση.

Γλώσσα διδασκαλίας

Ελληνικά (Αγγλικά αν υπάρχουν φοιτητές/φοιτήτριες ERASMUS)

Τρόπος παράδοσης μαθήματος

Φυσική Παρουσία.