Περιγραφή
Το μάθημα πραγματεύεται τις έννοιες της υπολογισιμότητας (τι είναι υπολογίσιμο και τι όχι) και της υπολογιστικής πολυπλοκότητας (τι μπορεί να υπολογισθεί αποδοτικά και τι όχι). Τα θέματα που θα καλύψουμε είναι θεωρία αυτομάτων και τυπικών γλωσσών, υπολογισιμότητα από μηχανές Turing, μη-υπολογισιμότητα, και υπολογιστική πολυπλοκότητα. Σε όλη την πορεία του μαθήματος, ένα κεντρικό ζήτημα θα είναι η σχέση ντετερμινιστικών και μη-ντετερμινιστικών υπολογιστικών μηχανών. Συνοπτικά, θα μπορούσαμε να περιγράψουμε την πορεία του μαθήματος ως εξής:
Αρχικά, θα ορίσουμε την κλάση των κανονικών γλωσσών και το υπολογιστικό μοντέλο των πεπερασμένων αυτομάτων. Θα αποδείξουμε ότι τα πεπερασμένα αυτόματα αναγνωρίζουν τις κανονικές γλώσσες και μόνο αυτές. Θα δούμε επίσης ότι μερικές σχετικά απλές γλώσσες δεν είναι κανονικές και άρα δεν αναγνωρίζονται από πεπερασμένα αυτόματα. Αυτό υποδεικνύει ότι το υπολογιστικό μας μοντέλο χρήζει ενίσχυσης.
Έτσι θα ορίσουμε μια μεγαλύτερη κλάση γλωσσών, τις γλώσσες χωρίς συμφραζόμενα, και ένα ισχυρότερο υπολογιστικό μοντέλο, τα (μη-ντετερμινιστικά) αυτόματα στοίβας, και θα αποδείξουμε ότι τα αυτόματα στοίβας αναγνωρίζουν τις γλώσσες χωρίς συμφραζόμενα και μόνο αυτές. Και πάλι όμως μερικές σχετικά απλές γλώσσες δεν είναι χωρίς συμφραζόμενα και άρα δεν αναγνωρίζονται από αυτόματα στοίβας. Πρέπει λοιπόν να ενισχύσουμε κι άλλο το υπολογιστικό μας μοντέλο.
Εν τέλει, θα ορίσουμε ένα πραγματικά ισχυρό υπολογιστικό μοντέλο, αυτό των μηχανών Turing, και θα διερευνήσουμε τις υπολογιστικές του δυνατότητες. Θα δούμε ότι κάθε προσπάθεια περαιτέρω ενίσχυσης αυτού του μοντέλου αποτυγχάνει (Church-Turing thesis). Και πάλι όμως υπάρχουν προβλήματα (αντίστοιχα γλώσσες) που δεν λύνονται (αντίστοιχα αναγνωρίζονται) από μηχανές Turing (μη-υπολογισιμότητα).
Έπειτα, θα εστιάσουμε σε υπολογίσιμα προβλήματα και θα διερευνήσουμε πότε ένα πρόβλημα είναι αποδοτικά επιλύσιμο από έναν υπολογιστή και πότε όχι (Cook-Karp thesis). Η συναρπαστική θεωρία υπολογιστικής πολυπλοκότητας θα αποτελέσει το βασικό μας εργαλείο σε αυτή την προσπάθεια. Θα ξεκινήσουμε με τις θεμελιώδεις έννοιες της αναγωγής και της πληρότητας. Θα ορίσουμε τις κλάσεις P και NP και την έννοια της NP-πληρότητας. Θα δούμε μερικά σημαντικά NP-πλήρη προβλήματα και θα μάθουμε τεχνικές για να αποδεικνύουμε ότι ένα πρόβλημα είναι NP-πλήρες. Τέλος θα παρουσιάσουμε μερικές σημαντικές κλάσεις υπολογιστικής πολυπλοκότητας, όπως οι PSPACE, #P, RP, BPP, και ZPP.
Διδάσκων
Δημήτρης Φωτάκης, Επίκουρος Καθηγητής
Ύλη
Το μάθημα θα βασιστεί στο βιβλίο των Harry Lewis και Χρίστου Παπαδημητρίου Στοιχεία Θεωρίας Υπολογισμού (εκδ. Κριτική 2005). Στην ύλη για τις εξετάσεις περιλαμβάνεται ότι καλύψαμε στις διαλέξεις. Από το βιβλίο, περιλαμβάνονται όλες οι ενότητες που αναγράφονται δίπλα στις διαλέξεις. Υπάρχουν ακόμη θέματα που καλύψαμε αλλά δεν καλύπτονται (στον ίδιο βαθμό) στο βιβλίο.
Επικοινωνία
Προσπαθήστε να παρακολουθείτε τις παραδόσεις συστηματικά. Σε μαθήματα σαν και αυτό, η περιστασιακή μελέτη δεν μπορεί να υποκαταστήσει την παρακολούθηση. Αν έχετε απορίες ή αντιμετωπίζετε δυσκολίες στη μελέτη σας, μη διστάσετε να τις συζητήσετε με το διδάσκοντα.
Δ. Φωτάκης. Ώρες γραφείου: Τετάρτη 12-14
Δομή Μαθήματος - Σημειώσεις - Οδηγός Μελέτης
Εισαγωγικά. (ενότητες 1.1, 1.2, 1.3, και 1.6).
Γλώσσες - (Μη)-μετρήσιμα σύνολα - Διαγωνιοποίηση. (ενότητες 1.4, 1.5, και 1.7).
Κανονικές Γλώσσες. (ενότητα 1.8).
Πεπερασμένα Αυτόματα. (ενότητα 2.1).
Αυτόματα και Κανονικές Γλώσσες, Μη-Κανονικές Γλώσσες, Λήμμα Άντλησης. (ενότητες 2.3 και 2.4).
Γλώσσες χωρίς Συμφραζόμενα. (ενότητα 3.1).
Αυτόματα Στοίβας. (ενότητες 3.3 και 3.4 - εξαιρείται η απόδειξη του Θεωρήματος 3.4.1).
Γλώσσες που δεν είναι χωρίς Συμφραζόμενα - Λήμμα Άντλησης. (ενότητες 3.2 και 3.5).
(Ντετερμινιστικές) Μηχανές Turing. Κάποια απλά παραδείγματα Μηχανών Turing (ενότητα 4.1).
Υπολογισμοί με Μηχανές Turing. (ενότητα 4.2).
Επεκτάσεις Μηχανής Turing. Μη ντετερμινιστικές Μηχανές Turing. (ενότητες 4.3 και 4.5).
Η Θέση των Church-Turing. Καθολικές Μηχανές Turing. (ενότητες 5.1 και 5.2).
Το πρόβλημα του Τερματισμού. Μη επιλύσιμα προβλήματα σχετικά με Μηχανές Turing. (ενότητες 5.3, 5.4, και 5.7).
Εξετάσεις
- ΒαθμολογίαΟ βαθμός των εργασιών (ΒΕ) συνεισφέρει το 30% του τελικού βαθμού. Επίσης, θα υπάρξει μια υποχρεωτική ενδιάμεση εξέταση (πρόοδος) την εβδομάδα μετά τις διακοπές του Πάσχα, ο βαθμός της οποίας (ΒΠ) συνεισφέρει το 20% του τελικού βαθμού. Ο βαθμός της τελικής εξέτασης (ΒΤΕ) θα συνεισφέρει το 50% του τελικού βαθμού και πρέπει κάποιος να επιτύχει ΒΤΕ >= 5.0 για να περάσει το μάθημα. Ο τελικός βαθμός του μαθήματος (ΤΒ) θα είναι:
TB = 0.3* BE + 0.2*BΠ + 0.5*BTE
και φυσικά πρέπει ΤΒ >= 5.0 ώστε το μάθημα να θεωρηθεί ότι εξετάστηκε με επιτυχία.
Εργασίες
Θα ανακοινωθούν τρεις ατομικές υποχρεωτικές εργασίες. Σε κάθε εργασία θα πρέπει να λύσετε κάποιες ασκήσεις σχετικές με την ύλη που καλύφθηκε στις αμέσως προηγούμενες διαλέξεις. Η παράδοση κάθε εργασίας θα γίνεται ΜΟΝΟ κατά την διάρκεια του μαθήματος της ημέρας που λήγει η προθεσμία. Μετά τη λήξη του συγκεκριμένου μαθήματος ΔΕΝ θα γίνονται δεκτές άλλες εργασίες.
Εκφώνηση 1ης εργασίας. Ημερομηνία παράδοσης: Πέμπτη 27/3/2008.
Εκφώνηση 2ης εργασίας. Ημερομηνία παράδοσης: Τετάρτη 14/5/2008.
Εκφώνηση 3ης εργασίας. Ημερομηνία παράδοσης: Παρασκευή 6/6/2008.
Βιβλιογραφία
H. Lewis και Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού. Κριτική, 2005.
Μ. Sipser. Introduction to the Theory of Computation. PWS, 1997.
J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2000.
C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
S. Arora. Computational Complexity: A Modern Approach. 2006.
M.R. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
Μερικές Σχετικές Ιστοσελίδες
MIT, 18.404J / 6.840J, Theory of Computation, Fall 2002 (M. Sipser).
Princeton, CS487, Theory of Computation, Fall 2000 (S. Arora).
Warwick, CS203, Automata and Formal Languages, (P. Goldberg).
UCSD, CSE105, Introduction to the Theory of Computation, Winter 2002, (D. Micciancio).
Αν σας αρέσουν τα μαθηματικά και θέλετε να γίνετε πλούσιοι, κοιτάξτε τη σελίδα του Clay Mathematics Institute.
Ένα πολύ ενδιαφέρον άρθρο του Bernard Chazelle για την εξέλιξη της Επιστήμης των Υπολογιστών.