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

Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Εαρινό Εξάμηνο 2015-2016

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

Γενικές Πληροφορίες

Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/TOC/. (Επίσης μέσω http://eclass.uoa.gr/).
Περιέχει χρήσιμες πληροφορίες, συνιστάται να την επισκέπτεστε συχνά. Εκεί θα βρίσκετε πληροφορίες για το μάθημα, σημειώσεις, ασκήσεις, ανακοινώσεις, κλπ. Το τμήμα των περιττών ΑΜ καλύπτει συναφή ύλη όμως οι εξετάσεις δεν θα είναι κοινές.

Περιγραφή μαθήματος: Το μάθημα καλύπτει την βασική ιεραρχία αυτομάτων, γραμματικών, και γλωσσών: (α) κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα, (β) γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας και (γ) αναδρομικές γλώσσες - μηχανές Turing. Παράλληλα μελετώνται οι έννοιες της αποφασισιμότητας (decidability), του ντετερμινισμού, και της αναγωγής προβλημάτων (reduction). Αν το επιτρέπει ο χρόνος, εξετάζεται η σχέση των κλάσεων ντετερμινιστικού πολυωνυμικού χρόνου (P) και μη ντετερμινιστικού πολυωνυμικού χρόνου (NP), με έμφαση στη θεωρία της ΝP-πληρότητας (NP-completeness).

Συγγράμματα: 1) H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική, 2005. Πρόκειται για μετάφραση της δεύτερης αγγλικής έκδοσης.
2) M. Sipser. Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007. Ομοίως, πρόκειται για μετάφραση της δεύτερης αγγλικής έκδοσης.

'Aλλες πηγές είναι τα παρακάτω βιβλία:

• H. Lewis, C. Papadimitriou. Elements of the theory of computation (Prentice-Hall, second edition September 1997).
• M. Sipser. Introduction to the theory of computation (PWS Publishing Company, 1997; 2nd Edition: Course Technology, 2005).
• M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Company, 1979).
• J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 2000).

Διαδικαστικά

Εξετάσεις - Ασκήσεις - Βαθμολογία: Θα έχουμε κάποια σύνολα ασκήσεων (με συντελεστή περίπου 5% συνολικά), και ένα τελικό διαγώνισμα (95%). Για να περάσετε όμως το μάθημα πρέπει να έχετε τουλάχιστον 4 στο τελικό διαγώνισμα, ακόμα και αν ο βαθμός στις ασκήσεις είναι πολύ καλός. Ο ίδιος ακριβώς τρόπος βαθμολόγησης ισχύει και για την περίοδο Σεπτεμβρίου.

Διαφάνειες

Προειδοποίηση 1: Οι διαφάνειες δεν καλύπτουν πλήρως ούτε την ύλη του μαθήματος ούτε ό,τι λέγεται στην τάξη. Προειδοποίηση 2: οι διαφάνειες κωδικοποιούν ευσύνοπτα μέρος της παράδοσης. Η μελέτη τους είναι χρήσιμη.

• Πρώτο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα)
• Δεύτερο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα).
• Τρίτο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα). (ανανέωση Wed Mar 16 17:02:01 EET 2016)
• Τέταρτο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα)
• Πέμπτο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα)
• Έκτο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα).
• Έβδομο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα).
• Όγδοο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα)
• Ένατο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα).
• Δέκατο σύνολο | Σε συμπυκνωμένη μορφή (4 διαφάνειες ανά σελίδα).

Ασκήσεις

Για τεκμηριωμένες απορίες σχετικά με τη βαθμολόγηση παρακαλούμε απευθυνθείτε πρώτα στους διορθωτές Δημήτρη Καλημέρη (dkalimer At di uoa gr) και Ευγένιο Μαζαράκη (sdi0800110 at di uoa gr). Οι διορθωτές θα προτείνουν στο διδάσκοντα μείωση βαθμού αν διαπιστώσουν πως ο φοιτητής δεν κατανοεί σε βάθος τί έχει γράψει.