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

Ακαδημαϊκό Έτος 2011-2012

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

Τρίτη 09:00 – 11:00 (αίθουσα Ζ)

Πέμπτη 09:00 – 11:00 (αίθουσα Ζ)

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

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

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

Συγγράμματα

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

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

Βαθμολογία

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

να έχετε τουλάχιστον 4 στο τελικό διαγώνισμα, ακόμα και αν ο βαθμός στις ασκήσεις είναι πολύ καλός. Ο ίδιος ακριβώς τρόπος βαθμολόγησης

ισχύει και για την περίοδο Σεπτεμβρίου.

Διαλέξεις

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

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

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

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

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

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

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

7. Μηχανές Turing

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

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

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

Εργασίες

Η πρώτη εργασία. Οι βαθμοί της πρώτης εργασίας.

Η δεύτερη εργασία.

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

Αντώνη Τρουμπούκη (grad1050@di.uoa.gr) είτε στον Κώστα Χαντζόπουλο (khandj@gmail.com),

ανάλογα με το ποιος από τους δύο έχει διορθώσει την εργασία σας (πάνω στην εργασία σας υπάρχουν

τα αρχικά του διορθωτή).

Εξετάσεις

…

---