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


χειμερινό εξάμηνο 2013-2014

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

Γενικά

Διδάσκοντες

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

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

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

Έναρξη Μαθήματος

  • Πέμπτη, 12 Δεκεμβρίου 2013

Διαλέξεις

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

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

  • Δευτέρα/Πέμπτη μετά το μάθημα
  • Παρασκευή 12:00-16:00
    στο Eργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.

Διοικητικά

  • Περιεχόμενο Μαθήματος-Syllabus (pdf)
  • Βαθμολόγηση:
    • Γραπτή Εξέταση: 6 μονάδες
    • Ασκήσεις: 2 μονάδες
    • Ομιλία: 2 μονάδες
    • Quizes: 1 μονάδα

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

  1. Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994
  2. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
  3. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008

  4. L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
  5. E. Allender, M. Loui, and K. Regan, Three chapters for the CRC Handbook on Algorithms and Theory of Computation (M.J. Atallah, ed.), (Boca Raton: CRC Press, 1998).
  6. Johan Håstad, Lecture Notes on Complexity Theory, 2009

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

  • Η επαναληπτική εξέταση του μαθήματος θα γίνει την Τετάρτη, 22 Οκτωβρίου, στις 15:00.
  • [NEW!] Αποτελέσματα Κανονικής Εξέτασης Απριλίου 2014
  • [31/3/2014] Ανακοινώθηκε η εξεταστέα ύλη του μαθήματος εδώ.
  • [26/3/2014] Η κανονική εξέταση του μαθήματος θα γίνει την Δευτέρα, 28 Απριλίου 2014, στις 15:00, στην Αίθουσα 002, στα Νέα Κτίρια ΗΜΜΥ, ΕΜΠ.
  • Αποτελέσματα Επαναληπτικής Εξέτασης Φεβρουαρίου 2014
  • [10/1/2014] H επαναληπτική εξέταση του μαθήματος θα γίνει την Τετάρτη, 5 Φεβρουαρίου 2014 στις 15:00, στο Αμφ. 1 στα Νέα Κτίρια Ηλεκτρολόγων, ΕΜΠ.
  • [12/12/13] Τα μαθήματα ξεκίνησαν. Όποιος δεν έχει γραφτεί στην λίστα του μαθήματος, μπορεί να το κάνει στα επόμενα μαθήματα.

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

Η/Μ Ομιλητής Θέμα - Περιεχόμενο
12/12/2013
Εισαγωγή - Διαδικαστικά
Hierarchies of Complexity Classes
(Overview of the field)
16/12/2013
Hierarchies of Complexity Classes
(Overview of the field) - cont'd
19/12/2013 Introduction to Complexity Theory.
Problems, Algorithms and Languages. Decision and optimization problems.
Equivalence of Computational Models, Turing Machines, Representation as strings and simulation.
♦ Δείτε τις ενότητες 1-4 εδώ, και το παράδειγμα Μηχανής Turing που περιγράψαμε εδώ. Επίσης, εδώ θα βρείτε τις διαφάνειες που χρησιμοποιήσαμε στο μάθημα.
23/12/2013 Turing machines with multiple strings, linear speedup, nondeterminism.
Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
9/1/2014 Computability & Undecidability: The Halting Problem, Recursive and Rec. Enumerable sets. Rice's Theorem.
13/1/2014 Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.
16/1/2014 Space Computation: The classes L and NL, Savitch's Theorem.
20/1/2014

Θ. Λιανέας		 Space Computation: Immerman-Szelepscényi Theorem, NL-completeness
Reingold's Theorem: Undirected Reachability in Logspace.
23/1/2014 A. Χάλκη Reductions & NP-Completeness: Different types of reductions, (Karp, Cook, Cook[1], tt), and relations among them, NP-completeness
27/1/2014 1o Quiz (Computability & Basic Complexity Classes)
3/2/2014
Ε. Παρταλίδου

Π. Καλογερόπουλος
[slides]		 NP-complete Problems:
-Cook's Theorem, SAT and Satisfiability
variants
-IS, CLIQUE, MAX-CUT
6/2/2014
A. Αγγελόπουλος
[slides] 		NP-complete Problems:
-HP, TSP, 3COL, 0/1IP
10/2/2014 Ι. Τζιώτης
 Ladner's Theorem, Density, Sparse Sets
13/2/2014 Δ. Μπογιόκας

Ν. Κωτσάνη		 The "Berman-Hartmanis" Conjecture, NP-isomorphism, padding
Second-Order Logic, Undecidability-Incompleteness, Fagin’s Theorem.
17/2/2014 Π. Μπαρμπαγιάννης
[Slides]		 Function Problems: The classes coNP and ΔNP, Function classes and reductions, the classes PLS and PPAD.
Oracles & Optimization Problems
20/2/2014 Oracles & Optimization Problems
The Polynomial Hierarchy
24/2/2014 The Polynomial Hierarchy (cont'd)
Randomized Computation: The classes BPP, RP, coRP, ZPP, Quantifier Notation ane related results, syntactic and semantic classes, The BPP-Theorem, the "P vs BPP Question".
27/2/2014 Randomized Computation: Error Reduction, The Class PP, Relativized Results
6/3/2014


Μ. Γαλενιανού
[slides]		 Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs.
Parallel Computation (classes NC, RNC, AC, TC, the PRAM model and the Isolating Lemma)
10/3/2014 2o Quiz (Reductions & Randomization)
13/3/2014



Δ. Μυρισιώτης
[slides]		 Interactive Proofs: IPs, Arthur-Merlin Games, Quantifier Notation and related results, Shamir's Theorem, Probabilistically Checkable Proofs and the PCP Theorem.
3DM, Knapsack, Pseudopolynomial Algorithms and Strong NP-completeness
17/3/2014 Ζ. Αβαρικιώτη
[slides]
Σ. Πατμανίδης
[slides]		 Alternation

Quantum Computation
20/3/2014
(2:30-5:30)		 Λ. Κάβουρας
[Slides]
Μ. Ζαμπετάκης
A. Στούκα
[slides]
N. Λάμπρου
[slides]
 Hardness of Approximations

Dinur's Proof of the PCP Theorem
One-way functions, The class UP

Pseudorandom Generators, Hardcore Predicates, Zero-knowledge
24/3/2014 Δεν θα γίνει μάθημα
27/3/2014 Δεν θα γίνει μάθημα
31/3/2014
(3:00-7:00)		 Ι. Ψαρρός
[Slides]
Β. Αναγνωστόπουλος
[Slides]


Μ. Ζαμπετάκης		 Inapproximability, Approximation Schemes

Pseudorandomness & Derandomization
Counting Complexity: #P, #P-completeness, Toda's Theorem, Gaps and related results, TotP
Smoothed Analysis of Algorithms
28/4/2014
(3:00-6:00)		 Τελική Εξέταση

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

Ασκήσεις

Ασκήσεις Η/Μ Ανάρτησης Η/Μ Παράδοσης Link
1η Σειρά 4/2/2014 6/3/2014 pdf
2η Σειρά 2/3/2014 7/4/2014 pdf
3η Σειρά 11/4/2014 2/5/2014 pdf

Σύνδεσμοι: Complexity around the World (Wide Web)


Μπορείτε να δείτε τα εξής πολύ ενδιαφέροντα papers σχετικά με την Υπολογιστική Πολυπλοκότητα:

Complexity Blogs

Electronic Journals

Complexity Courses

Other Links