Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα (ΣΗΜΜΥ, ΣΕΜΦΕ, ΜΠΛΑ)
χειμερινό εξάμηνο 2008-2009

● Γενικά ● Ανακοινώσεις ● Υλικό ● Ασκήσεις ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Λέκτορας ()

Βοηθοί διδασκαλίας

  • Ανδρέας-Νικόλαος Γκόμπελ, Υ.Δ. ()

Διαλέξεις (θεωρία)

  • κάθε Δευτέρα 17:00-18:00 (Αμφιθέατρο Ηλεκτρολόγων)
  • κάθε Πέμπτη 16:00-17:00 (Αμφιθέατρο Ηλεκτρολόγων)

Ώρες γραφείου

  • κάθε Τρίτη 14:00-16:00 στο εργαστήριο 1.1.30 (CoReLab) του κτηρίου Ηλεκτρολόγων
  • κάθε Πέμπτη 14:00-16:00 στο εργαστήριο 1.1.30 (CoReLab) του κτηρίου Ηλεκτρολόγων

Βιβλιογραφία

  1. Christos Papadimitriou: Computational Complexity, Addison Wesley, 1994
  2. Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 2nd edition, MIT Press, 2001.
  3. J. Kleinberg, E. Tardos: "Algorithm Design", Addison-Wesley, 2005.
  4. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (Μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
  5. Sara Baase, Allen Van Gelder, "Computer Algorithms: Introduction to Design and Analysis", 3rd edition, Addison Wesley Longman, 2000.
  6. Alfred V. Aho, John E. Hopcroft, "The Design and Analysis of Computer Algorithms", Addison-Wesley Series in Computer Science and Information Processing, 1974.
  7. Dexter C. Kozen, "The Design and Analysis of Algorithms", Springer, 1991.

Ανακοινώσεις

  • [08/12/2008] Την Δευτέρα 8 Δεκεμβρίου δεν θα γίνει το μάθημα, έπειτα από απόφαση της συγκλήτου.
  • [04/11/2008] Την Πέμπτη 6 Νοεμβρίου δεν θα γίνει μάθημα.

Υλικό

Διαφάνειες/Σημειώσεις μαθήματος

  • Ενότητα 1: Εισαγωγή
  • Ενότητα 2: Turing Machines
  • Ενότητα 3: Undecidability (Συργκάνης Βασίλειος, 23/10/2008) [PDF]
  • Ενότητα 4: Boolean Logic (Παναγέας Ιωάννης, 30/10/2008) [PDF]
  • Ενότητα 5: First-order Logic (Κορφιάτης Γεώργιος, Αγγελής Γεώργιος) (03/11/2008 - 10/11/2008) [PDF1] [PDF2]
  • Ενότητα 6: Undecidability in Logic (Μπακάλη Ελένη) (13/11/2008)
  • Ενότητα 7: Relations between complexity classes (Πετούση Μαργαρίτα) (20/11/2008 - 24/11/2008) [PDF]
  • Ενότητα 8: Reductions and completeness (Κοσμίδης Παύλος)
  • Ενότητα 9: NP-complete problems (Κοσμίδης Πάυλος, Γκόμπελ Ανδρέας)(19/01/2009) [PDF 2]
  • Ενότητα 10: coNP and function problems (Γκόμπελ Ανδρέας-Νικόλαος) (23/01/2009) [PDF]
  • Ενότητα 11 Randomized computation (Γαλάνης Ανδρέας, Παναγέας Ιωάννης)
  • Ενότητα 12: Cryptography (Αγγελάκης Αθανάσιος)
  • Ενότητα 13: Approximability (Κουτρής Παράσχος)
  • Ενότητα 14: On P vs. NP (Μπουραντάνη Ελισάβετ-Ευαγγελία)
  • Ενότητα 15: Parallel computation (Βακαλόπουλος Γεώργιος, Συργκάνης Βασίλειος)
  • Ενότητα 16: Logarithmic space (Γκούμας Αλέξανδρος)
  • Ενότητα 17: The polynomial hierarchy (Ζαχαρίας Πιτουράς)
  • Ενότητα 18: Computation that counts (Γκόμπελ Ανδρέας-Νικόλαος)
  • Ενότητα 19: Polynomial space (-)

Ασκήσεις

Από βιβλίο Computational Complexity, C. Papadimitriou :

  • Κεφ. 1: 1.4.4, 1.4.5, 1.4.11, 1.4.15, * μία απο 1.4.12-1.4.14
  • Κεφ. 2: 2.8.4, (2.8.5), 2.8.17
  • Κεφ. 3: 3.4.1, 3.4.8, 3.4.9

Τελευταία ανανέωση: 31 Ιανουαρίου 2009