Αρχική σελίδα | Επικοινωνία | Πίνακας πλοήγησης |

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

χειμερινό εξάμηνο 2011-2012

● Γενικά ● Ανακοινώσεις ● Διαλέξεις ● Ασκήσεις ●

Γενικά

Διδάσκοντες

• Στάθης Ζάχος, Καθηγητής ()
• Άρης Παγουρτζής, Επίκ. Καθηγητής ()

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

• Αντώνης Αντωνόπουλος ()

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

• κάθε Δευτέρα 16:15-18:00 (Παλαιό Κτίριο Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
• κάθε Πέμπτη 15:30-17:15 (Παλαιό Κτίριο Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31 ή Αμφιθέατρο Ηλεκτρολόγων)

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

• κάθε Δευτέρα 15:00-16:00 στο εργαστήριο 1.1.3 (CoReLab)
• κάθε Πέμπτη 14:00-15:00 στο εργαστήριο 1.1.3 (CoReLab)

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

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

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

• Η επαναληπτική εξέταση του μαθήματος θα γίνει την Δευτέρα 24 Σεπτεμβρίου, ώρα 12:00, στην αίθουσα 1.1.29, στα Παλαιά Κτίρια Ηλεκτρολόγων.
  
  
• NEW! Βαθμοί Εξεταστικής Περιόδου Φεβρουαρίου 2012
• [ΑΛΛΑΓΗ ΩΡΑΣ] Η εξέταση θα γίνει στην αίθουσα 005 του Νέου Κτιρίου Ηλεκτρολόγων, την Δευτέρα 19 Μαρτίου στις 5:00.
  
  
• Η εξεταστέα ύλη του μαθήματος είναι η εξής:

  1) Από το βιβλίο του Παπαδημητρίου [1] :
  Chapter 1: Problems and Algorithms Chapter 2: Turing Machines Chapter 3: Computability Section 5.7: Second-Order Logic Chapter 7: Relation between Complexity Classes Chapter 8: Reductions and Completeness Chapter 9: NP-Complete Problems Section 10.1: NP and coNP & Section 10.3: Function Problems Section 14.3: Oracles Section 15.2: Parallel Models of Computation & Section 15.3: The class NC Section 17.2: The Polynomial Hierarchy (χωρίς την απόδειξη των Θ. 17.12 και Θ.17.13)
  2) Από το βιβλίο των Arora-Barak [2] :
  Chapter 7 (Randomized Computation): Sections 7.1, 7.3, 7.4, 7.5 Chapter 17 (Complexity of Counting): 17.1, 17.2, 17.3, και από το 17.4 μόνο την εκφώνηση (χωρίς την απόδειξη) του Θ. Toda (Θ.17.14).
  3) Από τις σημειώσεις του κ. Ζάχου:
  Εισαγωγή στην Υπολογισιμότητα Θεώρημα Cook (με απόδειξη) Μετασχηματισμοί Προβλημάτων Μετασχηματισμοί Προβλημάτων 2
  4) Από τις Διαφάνειες Παρουσιάσεων (που υπάρχουν στην σελίδα):
  Γ. Κοκκίνης: Σύντομα βιογραφικά Α. Ψωμάς: Subclasses of TFNP and stuff Χ. Αγγελιδάκης: Probabilistically Checkable Proofs (εκτός από την απόδειξη στις διαφάνειες 17-18) Χρ. Γαλανάκη: Short Interactive Proofs

  Υπενθυμίζουμε ότι η εξέταση του μαθήματος θα γίνει την Δευτέρα 19 Μαρτίου, 3:00-6:00, στην αίθουσα 005 του Νέου Κτιρίου Ηλεκτρολόγων.
  
  Καλό διάβασμα & Καλή επιτυχία!
  
  
  
  
• [25/1/12]
  Η εξέταση του μαθήματος θα γίνει την Δευτέρα, 19 Μαρτίου 2012.
• [10/1/12]
  Το Quiz θα γίνει (τελικά) την Δευτέρα 16/1/12. Η ύλη παραμένει η:
  • Theorem 9.7
  • Pages 203-206
• [12/12/11]
  Ανακοινώθηκε νέα σειρά ασκήσεων (Προστέθηκε και η 10.4.6). Παράδοση την Πέμπτη 12/1/2012.
• [5/12/11]

  Διαβάστε:	μέχρι:
  4.3, 8.1, 8.2	Πέμπτη 8/12
  5.7, 8.3	Δευτέρα 12/12
  9.1, 9.2	Πέμπτη 15/12
  9.3, 9.4, 9.5	Δευτέρα 19/12
  10.1, 10.3, 10.4	Πέμπτη 22/12

  Επίσης, θα διδαχθούν:
  • Ύλη κεφ.11 από αλλού (ίσως Seffi Naor's Notes)
  • Κεφ.12 όχι
  • Κεφ.13 από αλλού
  • Κεφ.14 από αλλού
  • Κεφ.15
  • Κεφ.16+πολλά καινούρια
  • Κεφ.17
  • Κεφ.18 από αλλού
  • Κεφ.19 κάποια αποτελέσματα
  • Κεφ.20
  • +κάποια extra θέματα
• [24/11/11]: Ανακοινώθηκαν προθεσμίες παράδοσης για τις δύο πρώτες σειρές ασκήσεων.
• [21/11/11]: Την Δευτέρα 28/11 θα γίνει δεκάλεπτο quiz στην Ενότητα 3.3: More Undecidability.

Διαλέξεις - Παρουσιάσεις

Η/Μ	Ομιλητής	Θέμα - Περιεχόμενο
7/11/11		Brief Introduction, Chapter 1
10/11/11		Chapter 1: Problems and Algorithms Chapter 2: Turing Machines
14/11/11		Chapter 2 (cont.) Chapter 3: Undecidability
21/11/11	Γ. Κοκκίνης	Chapter 3 (cont.) Σύντομη βιογραφική ομιλία (slides) Chapter 7:Complexity classes (προετοιμάστε τα 7.1, 7.2)
24/11/11	Α. Κουτλή	Chapter 7 (cont.): 7.3 Regular Languages
28/11/11	Π. Θεοφιλόπουλος	Chapter 8: Reductions and Completeness (Εισαγωγή) Turing Machines and Chomsky Hierarchy (slides)
1/12/11		Δεν έγινε μάθημα
5/12/11		Quiz στο Section 3.3 Chapter 8: Reductions and Completeness (Θ. Cook)
8/12/11	Β. Βλάχος	Arithmetical Hierarchy (slides) Reductions and Completeness (από Σημειώσεις*) *Βρίσκονται στο "Συμπληρωματικό Υλικό"
12/12/11	Π. Γροντάς	Problem Reductions (από Σημειώσεις*) Blum Complexity (slides)
15/12/11		P-Completeness and NP-Completeness
22/12/11		Chapter 10: coNP and function problems
9/1/12		Chapter 7 (από [2]): Randomized Computation
12/1/12		Chapter 7 (από [2]) (cont'd)
16/1/12		Chapter 7 (από [2]) (cont'd)
19/1/12		Hierarchies of Complexity Classes
23/1/12	Α. Αντωνόπουλος	Oracles and the Polynomial-Time Hierarchy (slides)
26/1/12	Χ. Λίτσας Α. Ψωμάς	Integer Linear Programming (slides) Subclasses of TFNP and stuff (slides)
2/2/12		Chapter 15: Parallel and Log-Space Computation Chapter 16: Logarithmic Space (both briefly)
6/2/12	Α. Αντωνόπουλος	Non-Uniform Complexity (slides)
9/2/12	Α. Αντωνόπουλος	The Polynomial-Time Hierarchy (cont'd) Quantifier Characterizations (*δείτε και το κείμενο στο Συμπληρωματικό Υλικό)
13/2/12		Δεν έγινε μάθημα
16/2/12	Χ. Αγγελιδάκης	Probabilistically Checkable Proofs (slides)
20/2/12	Α. Göbel Γ. Κούρτης	Counting Complexity Algebraic Computation (slides)
23/2/12	Χρ. Γαλανάκη Γ. Τσελεκούνης	Short Interactive Proofs (slides) Zero-Knowledge Proofs(slides)

Συμπληρωματικό Υλικό

• Παράδειγμα Yλοποίησης Μηχανής Turing
• Σύντομη Εισαγωγή στην Θεωρία Υπολογιστικής Πολυπλοκότητας (Σ. Ζάχος, Ά. Παγουρτζής, Δ. Φωτάκης)
• Εισαγωγή στην Υπολογισιμότητα
• Θεώρημα Cook (με απόδειξη)
• Μετασχηματισμοί Προβλημάτων
• Μετασχηματισμοί Προβλημάτων 2
• A survey of Probabilistically Checkable Proofs (S. Arora)
• Inapproximability of Combinatorial Optimization Problems (L. Trevisan)
• What is a Natural Proof? (Timothy Y. Chow) Published in AMS Notices
• A Landscape of Computational Complexity (M. Faramawi, K. Regan)
• Quantifier Characterization of Complexity Classes (Διαθέσιμο σύντομα)

Ασκήσεις

• 1η Σειρά Ασκήσεων (Η/Μ Παράδοσης: 1/12/11)
• Κεφ. 1: 1.4.5, 1.4.12, 1.4.15
• Από το παράδειγμα Μηχανής Turing 2.3 στην σελίδα 23, να μετατρέψετε τον συμβολισμό του βιβλίου σε αυτόν που χρησιμοποιείται στο μάθημα.
• Να περιγράψετε, χρησιμοποιώντας την διαδικασία του Θεωρήματος 2.1 (σελ.30), Μηχανή Turing με μία ταινία που προσομοιώνει Μηχανή Turing με τρεις ταινίες.
  
  
• 2η Σειρά Ασκήσεων (Η/Μ Παράδοσης: 5/12/11)
  • Να εφαρμόσετε την διαδικασία απόδειξης του Θεωρήματος 2.2 (σελ.32-Linear Speedup Theorem) για ε=1/2.
  • Κεφ. 7: 7.4.5, 7.4.6, 7.4.7
  • Χρησιμοποιώντας ως "black box" τον αλγόριθμο της απόδειξης του Θ. Immerman-Szelepscenyi (Θ. 7.6), σχεδιάστε αλγόριθμο για το πρόβλημα nonREACHABILITY, που να δείχνει ότι το πρόβλημα είναι στην κλάση NL.
    (Ορίζουμε το nonREACHABILITY ως εξής: "δίνεται γράφος G, και κόμβοι u,v. Ισχύει ότι δεν υπάρχει path από τον κόμβο u στον v;")
  
  
• 3η Σειρά Ασκήσεων (Η/Μ Παράδοσης: 16/1/12)
  • 9.5.12, 9.5.13, 9.5.14, 9.5.15, 10.4.6

Τελευταία ανανέωση: 12/3/2012