Θεωρία Υπολογισμού: Γενικές πληροφορίες

Καθηγητής:	Σπύρος Σκιαδόπουλος
Γραφείο:	Δ3-4, 4ος Όροφος, Γκλαβάνη 37
Τηλέφωνο:	24210-74972
E-mail:	sskiad@uth.gr
URL μαθήματος	http://inf-server.inf.uth.gr/courses/CE302/
Λίστα μαθήματος	http://net-server.inf.uth.gr/mailman/listinfo/ce302/

Ώρες και αίθουσα διαλέξεων

Πέμπτη, 11-13 και 15-17, Αίθουσα 1, Γαμβέτα.

Περιεχόμενο μαθήματος

Το μάθημα αφορά την παρουσίαση (α) θεμελιωδών εννοιών θεωρίας υπολογισμού (όπως αλφάβητα και γλώσσες, πεπερασμένα αυτόματα και ιδιότητες, κανονικές εκφράσεις, γλώσσες και γραμματικές χωρίς συμφραζόμενα, αυτόματα στοίβας, μηχανές Τuring και την θέση των Church-Turing) και (β) θεμελιωδών εννοιών θεωρίας υπολογιστικής πολυπλοκότητας (όπως οι κλάσεις P και NP, και τα NP-πλήρη προβλήματα).

Βιβλία

Στοιχεία Θεωρίας Υπολογισμού, Harry R. Lewis και Χρίστος Χ. Παπαδημητρίου, Τεχνικό Επιμελητήριο Ελλάδας, 1992.
Θεωρία Υπολογισμού, Κωνσταντίνος Χαλάτσης, Ελληνικό ανοικτό πανεπιστήμιο, 2001.

Εργασίες

Κάθε σπουδαστής θα παραδώσει ασκήσεις που θα δοθούν στην διάρκεια του μαθήματος. Οι ημερομηνίες παράδοσης θα δίνονται με τα φυλλάδια των ασκήσεων. Επίσης θα δοθεί προαιρετικά θέμα (project) το οποίο θα παραδοθεί το στο διαγώνισμα του μαθήματος. Οι ημερομηνίες παράδοσης των ασκήσεων/θέματος είναι αυστηρές και δεν μπορούν να μεταφερθούν τον Σεπτέμβριο.

Διαγώνισμα

Το διαγώνισμα θα διεξαχθεί με ανοιχτά βιβλία.

Βαθμολογία

Ο τελικός βαθμός υπολογίζεται σαν το άθροισμα των βαθμών των γραπτών εξετάσεων, των ασκήσεων και του θέματος. Το άριστα στις γραπτές εξετάσεις είναι 7, στις ασκήσεις 3 (συνολικά), και στο θέμα 1 (bonus). Ειδικά για το διαγώνισμα του Σεπτεμβρίου μπορείτε να επιλέξετε αν (α) το άριστα του γραπτού θα είναι το 7 (οπότε θα προσμετρηθούν ασκήσεις και θέμα) ή (β) το άριστα θα είναι το 10 (οπότε ΔΕΝ θα προσμετρηθούν ασκήσεις και θέμα)

Διδακτέα ύλη

Εισαγωγή.
Αλφάβητα και γλώσσες.
Πεπερασμένα αυτόματα (ντετερμινιστικά και μη ντετερμινιστικά), κανονικές εκφράσεις και γλώσσες. Ισοδυναμία πεπερασμένων αυτομάτων και κανονικών εκφράσεων. Εφαρμογές και ιδιότητες των πεπερασμένων αυτομάτων και και κανονικών εκφράσεων.
Γλώσσες και γραμματικές χωρίς συμφραζόμενα. Αυτόματα στοίβας. Ισοδυναμία γραμματικών χωρίς συμφραζόμενα και αυτομάτων στοίβας. Εφαρμογές σε συντακτική ανάλυση (parsing) γλωσσών προγραμματισμού.
Διάφοροι τύποι μηχανών Turing. Υπολογισμός με μηχανές Τuring.
Η θέση των Church-Turing.
Προβλήματα που δεν είναι υπολογίσιμα (undecidable problems).
Υπολογιστική πολυπλοκότητα. Οι κλάσεις P και NP. NP-πλήρη προβλήματα.
Ενδιαφέροντα προβλήματα από την κλάση P (κυρίως από τη θεωρία γράφων).

Ευχαριστίες

Η δομή και οι διαφάνειες του μαθήματος έχουν βασιστεί στο μάθημα Θεωρία Υπολογισμού του καθ. Μανόλη Κουμπαράκη

Το πρότυπο των σελίδων αυτών σχεδιάστηκε από τους Πάνο Ξηρό και Σπύρο Σκιαδόπουλο για να καλύψει τις ανάγκες των μαθημάτων του Εργαστηρίου Βάσεων Γνώσεων και Δεδομένων και συγκεκριμένα τα μαθήματα: Δομές Δεδομένων, Βάσεις Δεδομένων, Θεωρία Υπολογισμού και Τεχνητή Νοημοσύνη.