Κατάλογος Μαθημάτων

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

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα:

• Έχει την γνώση των ορίων που έχουν τα σημερινά μοντέλα του υπολογισμού.
• Έχει την δεξιότητα να εφαρμόζει την θεωρία του υπολογισμού σε όλα τα γνωστά μοντέλα του υπολογισμού.
• Έχει την ικανότητα να μελετάει θεωρητικά την υπολογιστική ικανότητα των γνωστών μοντέλων υπολογισμού.

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

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

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