Διδάσκων: Κων/νος Δ. Κούτρας
Γραφείο: Α6α
Ώρες Υποδοχής Φοιτητών:
Τρίτη 15:00-17:00, Tετάρτη 17:00-19:00, Πέμπτη 14:00-16:00
(Στην πραγματικότητα, είστε πάντα ευπρόσδεκτοι,
ιδίως γιά απορίες, αρκεί βέβαια να μπορώ εκείνη τη στιγμή)
Τηλέφωνο Γραφείου: 2710 372221
Ηλεκτρονική επικοινωνία: 
Ιστοσελίδα μαθήματος: http://www.uop.gr/cst/k03
Στόχος του μαθήματος είναι να καλύψει τα βασικά της Θεωρίας Αυτομάτων και Τυπικών Γλωσσών (Κανονικές Γλώσσες και Πεπερασμένα Αυτόματα, Γλώσσες χωρίς συμφραζόμενα και Αυτόματα Στοίβας), να δώσει στοιχεία από τη βασική Θεωρία Υπολογισιμότητας (μηχανές Turing, μη-επιλύσιμα προβλήματα, το αίτημα Church-Turing, κτλ.) και τη Θεωρία Πολυπλοκότητας (κλάσεις πολυπλοκότητας, NP-πληρότητα, αναγωγές). Η έμφαση είναι στη Θεωρία Υπολογισιμότητας, καθώς η Θεωρία Πολυπλοκότητας καλύπτεται σε ανεξάρτητο μάθημα του Τομέα Θεωρητικής Πληροφορικής, όμως θα προπαθήσουμε να καλύψουμε κάποια στοιχεία από τη Θεωρία ΝP-πληρότητας.
Διαλέξεις: Tετάρτη 15:00-17:00. Αίθουσα Υ5
Πέμπτη 12:00-14:00. Αίθουσα Ι4
Θα χρησιμοποιήσουμε υλικό από τα βιβλία (i) H. Lewis και Χρ. Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, [εκδόσεις ΚΡΙΤΙΚΗ] (ιι) Mike Sipser: Εισαγωγή στη Θεωρία Υπολογισμού, [ Πανεπιστημιακές Εκδόσεις Κρήτης]
Η περυσινή εξεταστέα ύλη του μαθήματος (σε .pdf) απο το βιβλίο Lewis-Παπαδημητρίου. Όποιος θέλει να μελετήσει από το βιβλίο του M. Sipser, ας συμβουλευτεί το παρόν.
Η βαθμολογία του μαθήματος εξαρτάται καθ' ολοκληρίαν από τη γραπτή
τελική εξέταση.
Εξετάζεστε με κλειστά βιβλία και σημειώσεις. Μπορείτε
να έχετε μαζί σας μόνο ένα φύλλο Α4, στο οποίο μπορείτε να έχετε σημειωμένο
ότι θέλετε. Θα πρότεινα δε, να το συμπληρώσετε προσωπικά, στη διάρκεια της
μελέτης σας. Θα διαπιστώσετε πως ακόμα και η διαδικασία να αποφασίσετε τι
θα γράψετε (και πως) στο προσωπικό σας "σημειωματάριο" γιά την εξέταση,
θα σας βοηθήσει πολύ.
Μερικές καταπληκτικές παρουσιάσεις σε Powerpoint από ένα μάθημα του S. Safra στο Tel Aviv University
Ένα άρθρο των L. Fortnow & S. Homer γιά την ιστορία της Υπολογιστικής Πολυπλοκότητας