Θεωρία Υπολογισμού (Άρτιοι ΑΜ)

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

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

Τρίτη 9:00 – 11:00 (αίθουσα Α1)

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

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

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

Αναδρομικές γλώσσες - μηχανές 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. Μη Επιλυσιμότητα

Εργασίες

...

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

είτε στην Ιωάννα Συμεωνίδου (s.iwanna@gmail.com), είτε στον Αντώνη Τρουμπούκη (antru@di.uoa.gr) (στην εργασία σας θα

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

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

Εξετάσεις

Ύλη

Οι βαθμοί της (πτυχιακής) εξεταστικής περιόδου Φεβρουαρίου 2016, βρίσκονται εδώ.

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

και σε αυτόν που περιμένατε, μπορείτε να δείτε το γραπτό σας τη Δευτέρα 22/2/2016, 13:00 - 14:00. Τα γραπτά

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

---