Ειδικά Θέματα Θεωρητικής Πληροφορικής: Υπολογιστική Πολυπλοκότητα

(Συνδιδασκαλία με το μάθημα Αλγόριθμοι και Πολυπλοκότητα ΙΙ του ΜΠΛΑ)

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

Ώρες διδασκαλίας: Δευτέρα 15:00-17:00 (αίθουσα E' Πληροφορικής), Τρίτη 12:00-14:00 (αίθουσα Ε' Πληροφορικής).
Διδάσκων: Σταύρος Κολλιόπουλος
Γραφείο: Β6, κτήριο Πληροφορικής
Email: id@host.uoa.gr όπου id sgk και host di
Ώρες επικοινωνίας: Τετάρτη, 15:00 - 16:00 στο γραφείο Β6 ή με ραντεβού.

Ανακοινώθηκε η τελική βαθμολογία περιόδου Σεπτεμβρίου.

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

Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/grad/CC-S11/
Περιέχει χρήσιμες πληροφορίες και καλό είναι να την επισκέπτεστε συχνά. Εδώ θα βρίσκετε πληροφορίες για το μάθημα, τυχόν σημειώσεις, ασκήσεις, ανακοινώσεις, κλπ.

Το βασικό βιβλίο που θα χρησιμοποιήσουμε στο μάθημα είναι το εξής:

Christos Papadimitriou. Computational Complexity (Addison-Wesley 1994, reprinted with corrections 1995).

Συμβουλευθείτε επίσης αυτή τη σελίδα. Υπάρχει τεράστιος πλούτος υλικού στο δίκτυο. ΄Αλλα προτεινόμενα βιβλία

M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Company, 1979).
D. Du and K. Ko. Theory of Computational Complexity (Wiley 2000).
S. Rudich, A. Wigderson (editors). Computational Complexity Theory (AMS/IAS, 2004).
Oded Goldreich. Computational Complexity: A Conceptual Perspective (Cambridge University Press 2008).

To μάθημα θα ξεκινήσει από μια σύντομη επισκόπηση βασικών εννοιών. Είναι επιθυμητό κάποιο βασικό υπόβαθρο σε Θεωρία Υπολογισμού. Το βιβλίο του Παπαδημητρίου καλύπτει τα βασικά. Μια πιο εκτεταμένη εισαγωγή είναι το

M. Sipser. Introduction to the theory of computation (PWS Publishing Company, 1997). Second edition published by Course Technology, 2005.

Κάποιες θεμελειώδεις εργασίες και άλλα βοηθήματα

Δείτε εδώ.

Ενδεικτική περιγραφή μαθήματος

Μηχανές Turing, υπολογισιμότητα, πολυπλοκότητα χρόνου, πολυπλοκότητα χώρου, κλάσεις πολυπλοκότητας, αναγωγές, NP-completeness, coNP, προσεγγιστικοί αλγόριθμοι, πιθανοκρατικοί αλγόριθμοι, πιθανοκρατικές κλάσεις πολυπλοκότητας. Ανάλογα με το χρόνο που απομένει άλλα θέματα όπως: η πολυωνυμική ιεραρχία, προβλήματα μέτρησης, #P, συστήματα αποδείξεων, ψευδοτυχαιότητα.

Εξετάσεις - Ασκήσεις - Βαθμολογία

Κατά τη διάρκεια του εξαμήνου θα δοθούν κάποια σετ ασκήσεων με βαρύτητα περίπου 20%, για όσους γράψουν τουλάχιστον 5 στην τελική εξέταση. 10% θα προσμετρηθεί η παρουσία και η συμμετοχή στην τάξη. Το υπόλοιπο του βαθμού θα προέλθει από την τελική εξέταση. Για τους προπτυχιακούς φοιτητές που παίρνουν το μάθημα, οι ασκήσεις θα μετρήσουν θετικά, εάν γράψουν τουλάχιστον 5 στην τελική εξέταση.

Πρώτη άσκηση (δημοσίευση Fri Mar 11 13:11:16 EET 2011, παράδοση 04.04.2011) | (Προσθήκη: Fri Mar 11 13:11:16 EET 2011) | Βαθμολογία (Προσθήκη: Tue May 3 12:08:43 EEST 2011)

Δεύτερη άσκηση (δημοσίευση Wed May 11 15:52:24 EEST 2011, παράδοση 31.05.2011) |Βαθμολογία (Προσθήκη: Tue Jun 14 15:11:48 EEST 2011)| Τα διορθωμένα γραπτά μπορείτε να τα παραλάβετε, εργάσιμες ώρες, από τη Γραμματεία Θεωρητικής Πληροφορικής (Γραφείο Α1, κυρία Κύρου).

Περυσινά διαγωνίσματα: Ιουνίου και Σεπτεμβρίου. Παρατίθενται ενδεικτικά, τα φετεινά διαγωνίσματα δεν θα είναι απαραίτητα ούτε της ίδιας φιλοσοφίας, ούτε της ίδιας δυσκολίας. (Προσθήκη: Fri Jun 3 13:52:21 EEST 2011)

ΤΕΛΙΚΗ ΒΑΘΜΟΛΟΓΙΑ ΙΟΥΝΙΟΥ 2011 (δημοσίευση Tue Jul 19 13:20:03 EEST 2011)

ΤΕΛΙΚΗ ΒΑΘΜΟΛΟΓΙΑ ΣΕΠΤΕΜΒΡΙΟΥ 2011 (δημοσίευση Wed Nov 2 17:24:50 EET 2011)

http://www.di.uoa.gr/~sgk/teaching/grad/CC-S11/index.html
Τελευταία ανανέωση: Wed Nov 2 17:24:50 EET 2011