Θεωρία Υπολογισμού

Ακαδημαϊκό Έτος 2016-2017

Ώρες διδασκαλίας του μαθήματος

Δευτέρα 9:00 – 11:00 (αίθουσα Α2)

Πέμπτη 9:00 – 11:00 (αίθουσα Α2)

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

Κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα. Γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας.

Αναδρομικές γλώσσες - μηχανές Turing. Αποφασισιμότητα (decidability). Ντετερμινισμός. Αναγωγές προβλημάτων (reductions).

Συγγράμματα

·         H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική, 2005.

·         M. Sipser, Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.

Βαθμολογία

Θα υπάρχουν ασκήσεις (με συντελεστή περίπου 5% συνολικά), και ένα τελικό διαγώνισμα (95%).

Διαλέξεις

1.      Εισαγωγή - Γλώσσες

2.      Κανονικές Γλώσσες

3.      Πεπερασμένα Αυτόματα

4.      Ιδιότητες Κανονικών Γλωσσών – Pumping Lemma

5.      Γραμματικές χωρίς Συμφραζόμενα – Αυτόματα Στοίβας

6.      Ιδιότητες Γραμματικών χωρίς Συμφραζόμενα – Pumping Lemma

7.      Μηχανές Turing

8.      Υπολογισμοί με μηχανές Turing

9.      Επεκτάσεις της Μηχανής Turing

10.  Μη Επιλυσιμότητα

11.  Εισαγωγή στην Υπολογιστική Πολυπλοκότητα

 

Εργασίες

Πρώτη εργασία. Παράδοση: 6/4/2017 (στο διάλειμμα του μαθήματος). Βαθμοί πρώτης εργασίας.

Δεύτερη εργασία. Παράδοση: 22/5/2017 (στο διάλειμμα του μαθήματος). Βαθμοί δεύτερης εργασίας.

 

Για ερωτήσεις σχετικά με τις εργασίες σας, μπορείτε να απευθύνεστε είτε στον Γιώργο Παπαδημητρίου (gspapajim@di.uoa.gr),

είτε στον Δημήτριο Σπυρόπουλο (sdi1200170@di.uoa.gr), είτε στην Ιωάννα Συμεωνίδου (s.iwanna@gmail.com), είτε στον

Αντώνη Τρουμπούκη (antru@di.uoa.gr) (στην εργασία σας θα είναι σημειωμένα τα αρχικά του διορθωτή με τον οποίο μπορείτε

να επικοινωνήσετε). Θα σας παρακαλούσα να επικοινωνείτε μόνο αν υπάρχει σοβαρό θέμα σχετικά με την εργασία σας.

 

Εξετάσεις

Ύλη

 

Οι βαθμοί της εξεταστικής περιόδου Ιουνίου 2017, βρίσκονται εδώ.

 

Μόνο στην περίπτωση που θεωρείτε ότι υπάρχει σημαντική απόκλιση ανάμεσα στο βαθμό που ανακοινώθηκε

και σε αυτόν που περιμένατε, μπορείτε να δείτε το γραπτό σας την Τρίτη 11/7/2017, 10:00 - 12:00. Στην περίπτωση

αυτή το γραπτό σας θα βαθμολογηθεί εξαρχής. Δεν θα συζητηθούν καθόλου αιτήματα επανεξέτασης του γραπτού

για λόγους όπως "ξεκινάω μεταπτυχιακά το Σεπτέμβρη" ή "είναι ένα από τα τελευταία μαθήματα που μου έχουν

μείνει", κλπ. Τα γραπτά θα δειχτούν μόνο τη συγκεκριμένη μέρα και ώρα.