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

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

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

Δευτέρα 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.  Εισαγωγή στην Υπολογιστική Πολυπλοκότητα

 

Εργασίες

Πρώτη εργασία.

Δεύτερη εργασία.

 

Για ερωτήσεις σχετικά με τις εργασίες σας, μπορείτε να απευθύνεστε είτε στους ... ΤΒΑ... . (στην εργασία σας θα είναι

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

μόνο αν υπάρχει σοβαρό θέμα σχετικά με την εργασία σας.

 

Εξετάσεις

Ύλη

 

Οι βαθμοί της εξεταστικής περιόδου Ιουνίου 2018, βρίσκονται εδώ. (ανακοίνωση βαθμών: 25/6/2018)

 

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

που περιμένατε, μπορείτε να δείτε το γραπτό σας την Τρίτη 3/07/2018, 10.00-11.00 (προσοχή: την επόμενη βδομάδα). Στην

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

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

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