Πανεπιστήμιο Πελοποννήσου

Τμήμα Πληροφορικής & Τηλεπικοινωνιών

Υπολογισιμότητα & Πολυπλοκότητα
Εαρινό Εξάμηνο

Διδάσκων: Κων/νος Δ. Κούτρας
Γραφείο: Α6α
Ώρες Υποδοχής Φοιτητών: Δευτέρα 11:00-13:00, Τετάρτη 13:00-14:00, Πέμπτη 15:00-17:00
(Οι ώρες υποδοχής είναι τελείως τυπικές. Είστε πάντα ευπρόσδεκτοι για
να συζητήσουμε σχετικά με το μάθημα.)
Τηλέφωνο Γραφείου: 2710 372221
Ηλεκτρονική επικοινωνία:

Ιστοσελίδα μαθήματος: http://www.uop.gr/~ckoutras/ComCompl.html

Περιεχόμενα

• Περιγραφή Μαθήματος
• Διαλέξεις-Διαφάνειες
• Διδακτικό Υλικό-Εξετάσεις
• Βιβλιογραφία
• Χρήσιμοι σύνδεσμοι

  ---

  ΠΕΡΙΓΡΑΦΗ ΜΑΘΗΜΑΤΟΣ

  H Θεωρία Υπολογισιμότητας ασχολείται με τα μαθηματικά μοντέλα της έννοιας του αλγορίθμου και υπήρξε ο προπομπός της Θεωρητικής Πληροφορικής. Υιοθετώντας τις μηχανές Turing ως υπολογιστικό μοντέλο, θα ασχοληθούμε με το βασικό ερώτημα των ορίων της αλγοριθμικής επιλυσιμότητα, αποδεικνύοντας πως υπάρχουν αλγοριθμικώς ανεπίλυτα προβλήματα. Το κυριότερο μέρος του μαθήματος είναι η Θεωρία Υπολογιστικής Πολυπλοκότητας, το κομμάτι της Θεωρητικής Πληροφορικής που διερευνά τι είναι υπολογίσιμο αν περιορίσουμε τους διατιθέμενους υπολογιστικούς πόρους (χρόνο, μνήμη, αριθμό επεξεργαστών, κτλ.). Στόχο έχει να διερευνήσει γιατί μερικά προβλήματα φαίνεται να είναι πολύ δυσκολότερα από κάποια άλλα, και τελικά, ποιά είναι τα όρια των υπολογιστών στην πράξη (όπου φυσικά δεν έχουμε απεριόριστο χρόνο και μνήμη).Στο μάθημα θα δούμε τις βασικές κλάσεις πολυπλοκότητας χρόνου και χώρου και τις γνωστές μεταξύ τους σχέσεις. Θα εξετάσουμε σχετικά αναλυτικά την κλάση ΝΡ και τα πλήρη της προβλήματα, εμβαθύνοντας στην έννοια της αναγωγής. Θα δούμε μερικά από τα αποτελέσματα που αναδεικνύουν τη δυσκολία διαχωρισμού κλάσεων πολυπλοκότητας, με αναφορά ιδίως στο περίφημο πρόβλημα P vs NP. Aν ο χρόνος επιτρέψει, θα εξετάσουμε - έστω και επιφανειακά - κάποιο από τα πιό "προχωρημένα" θέματα στη Θεωρία Πολυπλοκότητας (πιθανοτική πολυπλοκότητα, προσεγγισιμότητα, δομικές ιδιότητες του ΝΡ).
  

  ---

  ΔΙΑΛΕΞΕΙΣ-Διαφάνειες

  Τετάρτη 11:00-13:00 (Ι8), Πέμπτη 13:00-15:00 (Ι8)

  Tα slides των πρώτων διαλέξεων παρακάτω, έχουν βασιστεί σε μεγάλο μέρος στις παραδόσεις του συναδέλφου Δημ. Καββαδία από το Πανεπιστήμιο Πατρών, ό οποίος πολύ ευγενικά, έθεσε στη διάθεσή μου όλο το πρωτογενές υλικό.

  Εισαγωγή-Λίγα Ιστορικά ( 2in1 )

  Αλγόριθμοι και Προβλήματα ( 2in1 )

  ---

  ΔΙΔΑΚΤΙΚΟ ΥΛΙΚΟ - ΕΞΕΤΑΣΗ
  

  Θα επιλέξετε ένα από τα προτεινόμενα συγγράμματα. Αντλούμε υλικό τόσο από το βιβλίο των Lewis-Παπαδημητρίου (Elements of the Theory of Computation, ελληνική έκδοση από τις εκδόσεις Κριτική) όσο και από το βιβλίο του M. Sipser (Introduction to the Theory of Computation, ελληνική έκδοση από ΠΕΚ).

• Επίσης, υπάρχουν κάποιες δικές μου, συμπληρωματικές σημειώσεις. Σχετικά συχνά όμως, θα σας παραπέμπω στο βιβλίο του Χρ. Παπαδημητρίου:

  Christos Papadimitriou: Computational Complexity, Addison-Wesley, 1994

  του οποίου υπάρχουν αντίτυπα στη βιβλιοθήκη.

  ΄H εξέταση του μαθήματος θα γίνει με κλειστά βιβλία και σημειώσεις. Επιτρέπεται να έχετε μαζί σας μόνο ένα φύλλο Α4, στο οποίο θα έχετε σημειώσει κατά τη μελέτη σας, ότι εσείς κρίνετε σκόπιμο.

  ---

  Προτεινόμενα βιβλία

  Γιά όποιον ενδιαφερθεί κάπως παραπάνω γιά το αντικείμενο, υπάρχουν τα εξής βιβλία. Ας έλθει να μιλήσουμε για τα πιο προχωρημένα κεφάλαια της Πολυπλοκότητας. Προσωπικά, έχω μία ελαφρά προτίμηση στο πρώτο απο τα παρακάτω βιβλία. Είναι ένα εκτεταμένο (περίπου 1000 σελίδες) βιβλίο, το οποίο καλύπτει τα πάντα στην Υπολογιστική Πολυπλοκότητα, ενώ η παρουσίαση σε κάποια κεφάλαια είναι απλά εκπληκτική. Το συνιστώ ανεπιφύλακτα.
Cristopher Moore, Stephan Mertens: The Nature of Computation.

Sanjeev Arora, Βoaz Barak: Computational Complexity: a modern approach.

Οded Goldreich: P, NP, and NP-Completeness: The Basics of Complexity Theory.

 

---

• Χρήσιμοι σύνδεσμοι

  Μερικές καταπληκτικές παρουσιάσεις σε Powerpoint από ένα μάθημα του S. Safra στο Tel Aviv University

  Ένα άρθρο των L. Fortnow & S. Homer γιά την ιστορία της Υπολογιστικής Πολυπλοκότητας

   

  ---