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

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

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

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

Τελική βαθμολογία Ιουνίου. (Προσθήκη Mon Jul 13 18:03:34 EEST 2009)
Τελική βαθμολογία Σεπτεμβρίου. (Προσθήκη Mon Sep 28 13:11:59 EEST 2009)

Εξετάσεις

Η πρόοδος θα γίνει τη Δευτέρα 18 Μαίου 2009, 14:00-16:00. Μπορείτε να έχετε μαζί σας το paper του Karp ("Reducibility among combinatorial problems"), μόνο. Δεν θα κρατήσουμε ακαδημαϊκό τέταρτο, θα ξεκινήσουμε να γράφουμε στις 14:00. Αποτελέσματα προόδου. (Προσθήκη Fri May 29 18:56:01 EEST 2009)

Το επίσημο πρόγραμμα των εξετάσεων Ιουνίου βρίσκεται εδώ και υπερισχύει αυτής εδώ της σελίδας. Το μάθημα μας αναφέρεται ως Υπολ. Πολυπλοκότητα. Η αίθουσα θα είναι μία απο τις αίθουσες του ισογείου του κτηρίου Πληροφορικής, θα συγκεντρωθούμε στην Ε'.

Στις εξετάσεις μπορείτε να έχετε μαζί σας μόνο το paper του Karp ("Reducibility among combinatorial problems"), ολόκληρο.

Τελική βαθμολογία. (Προσθήκη Mon Jul 13 18:03:34 EEST 2009)

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

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

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

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).

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, συστήματα αποδείξεων, ψευδοτυχαιότητα.

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

Κατά τη διάρκεια του εξαμήνου θα δοθούν κάποια σετ ασκήσεων. Θα υπάρξει υποχρεωτική προοδος με βαρύτητα 35% και τελικό διαγώνισμα με βαρύτητα 65%. Θετικό ρόλο (μέχρι +10%) θα παίξουν οι ασκήσεις για όσους (i) στα διαγωνίσματα γράψουν συνολικά τουλάχιστον 5 και (ii) παρακολουθήσουν τουλάχιστον το 60% των παραδόσεων. Για τους προπτυχιακούς φοιτητές που παρακολουθούν το μάθημα, η πρόοδος θα μετρήσει με βαρύτητα 50% εάν αυτό βελτιώνει το συνολικό τους βαθμό.

Πρώτη άσκηση (δημοσίευση 03.04.2009, παράδοση 13.04.2009) | Βαθμολογία (Προσθήκη: Thu Apr 30 13:33:14 EEST 2009).

Δεύτερη άσκηση (δημοσίευση 03.06.2009, παράδοση 17.06.2009)

Διορθωτής των ασκήσεων είναι ο κ. Θανάσης Κουτσώνας ( akoutson at math uoa gr).

Περυσινά διαγωνίσματα: πρόοδος και Ιούνιος. Παρατίθενται ενδεικτικά, τα φετεινά διαγωνίσματα δεν θα είναι απαραίτητα ούτε της ίδιας φιλοσοφίας, ούτε της ίδιας δυσκολίας. (Προσθήκη: Tue May 12 13:10:42 EEST 2009)

http://www.di.uoa.gr/~sgk/teaching/grad/CC-S09/index.html
Τελευταία ανανέωση: Mon Sep 28 13:11:59 EEST 2009