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

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

Ώρες διδασκαλίας: Τρίτη 09:00-11:00 Αίθουσα Ζ, Πέμπτη 09:00-11:00 Αίθουσα A2.
Διδάσκων: Σταύρος Κολλιόπουλος
Email: id@host.uoa.gr όπου id sgk και host di
Ώρες επικοινωνίας: Τρίτη, 13:00 - 14:00 στο γραφείο Β6 ή με ραντεβού.


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


Τελική βαθμολογία Φεβρουαρίου 2016. (Προσθήκη Fri Feb 19 21:11:50 EET 2016)
Τελική βαθμολογία Ιουνίου 2016. Εάν υπάρχει σημαντική απόκλιση ανάμεσα στο βαθμό σας και αυτό που περιμένατε, μπορείτε να δείτε το γραπτό σας τη Δευτέρα 27 Ιουνίου 2016, ώρα 13:00-14:00. Σε αυτή την περίπτωση το γραπτό θα αναβαθμολογηθεί από μηδενική βάση. (Προσθήκη Fri Jun 24 19:30:53 EEST 2016)

Τελική βαθμολογία Σεπτεμβρίου 2016. Εάν υπάρχει σημαντική απόκλιση ανάμεσα στο βαθμό σας και αυτό που περιμένατε, μπορείτε να δείτε το γραπτό σας την Τρίτη 18 Οκτωβρίου 2016, ώρα 15:00. Το γραπτό θα αναβαθμολογηθεί από μηδενική βάση. (Προσθήκη Mon Oct 17 15:23:44 EEST 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. Ομοίως, πρόκειται για μετάφραση της δεύτερης αγγλικής έκδοσης.

Το (1) υπερτερεί του (2) όσον αφορά την απόδοση βασικών όρων στα ελληνικά. Στην τάξη θα βασιζόμαστε κυρίως στο (1). Ένα βοήθημα για την ορολογία του (2) βρίσκεται εδώ.

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

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

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

Διαφάνειες

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

Ασκήσεις

Πρώτη άσκηση (Ανακοίνωση: Thu Mar 24 14:16:50 EET 2016, παράδοση μέχρι: 07.04.2016, ώρα 09:00). |
Δεύτερη άσκηση (Ανακοίνωση: Mon Apr 25 16:05:28 EEST 2016 παράδοση μέχρι: 12.05.2016, ώρα 09:00) |

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




http://www.di.uoa.gr/~sgk/teaching/TOC/index.html
Τελευταία ανανέωση: Mon Oct 17 15:23:44 EEST 2016