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

εαρινό εξάμηνο 2009-2010

● Γενικά ● Ανακοινώσεις ● Παρουσιάσεις ●

Γενικά

Διδάσκοντες

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

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

25/2/2010.

Διαλέξεις

  • Πέμπτη 16:00-20:00, αίθουσα 1.1.29 (παλαιό) Κτήριο Ηλεκτρολόγων (ΕΜΠ)

Προαπαιτούμενα

Μαθήματα σε Αλγόριθμους και Πολυπλοκότητα.

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

  1. R.Motwani, P. Raghavan: Randomized Algorithms
  2. Michael Mitzenmacher, Eli Upfal: Randomized Algorithms and Probabilistic Analysis
  3. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed: Probabilistic Methods for Algorithmic Discrete Mathematics

Πληροφορίες

  • Ε. Ζάχος, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.15. Τηλ. 210 7721646 - 44, fax: 210 7721645, email: .
  • Α. Παγουρτζής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.30. Τηλ. 210 7721644, fax: 210 7721645, email: .
  • Δ. Φωτάκης, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.10. Τηλ. 210 7724302, fax: 210 7722509, email: .

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

  • [25/02/2010] Τα μαθήματα ξεκίνησαν. Το πρόγραμμα παρουσιάσεων σας ενημερώνει για το περιεχόμενο κάθε διάλεξης και τον εκάστοτε ομιλητή.

Παρουσιάσεις

Ημ/νία Ομιλητής Θέμα παρουσίασης
25/2, 04/3 Δ. Φωτάκης Εισαγωγή: αντικείμενο, απλά παραδείγματα, βασικές τεχνικές και εφαρμογές (coupon’s collector, Chernoff bounds, balls-and-bins). Διαφάνειες.
11/3 Γ. Καούρη Βελτιστοποίηση γραφημάτων και δικτύων: All-Pairs Shortest Paths via Matrix Multiplication, Contraction Algorithm for Min-Cut and its extension / application to Network Reliability estimation, Minimum Spanning Tree ([MR, Κεφ. 10], [Karger’s PhD Thesis]). Διαφάνειες.
24/3 Π. Συμινελάκης Martingales ([MR, Ενοτ. 4.4], [MU, Κεφ. 12]). Διαφάνειες.
22/4 Π. Ποτίκας Markov Chains and Random Walks ([MR, Κεφ. 6], [MU, Κεφ. 7]). Διαφάνειες.
29/4 Θ. Λιανέας The Probabilistic Method: counting and expectation arguments, some (not-so-)simple examples, derandomization using conditional expectation, Lovasz Local Lemma, applications, explicit constructions using LLL ([MR, Κεφ. 5], [MU, Κεφ. 6], [Alon&Spencer], [Moser, STOC 2009]). Διαφάνειες.
06/5 Α. Γκόμπελ Approximate Counting: the Monte-Carlo method, the Markov-Chain-Monte-Carlo method, estimating the Permanent, coupling of Markov Chains ([MR, Κεφ. 11], [MU, Κεφ. 10], [MU, Κεφ. 11], [Sinclair’s PhD Thesis]). Διαφάνειες.
13/5 Α. Γαλάνης Simplification of Metric Spaces: low-distortion embeddings, Bourgain’s Theorem, Johnson-Lindenstrauss Lemma, volume respecting embeddings, probabilistic embeddings in (hierarchically separated) trees, algorithmic applications ([Matousek, Matousek&Indyk, papers by Bartal, [Kakcharoenphol, Rao Talwar, STOC 03], papers by Krauthgamer and Lee). Διαφάνειες.
27/5 Θ. Γουλεάκης Sublinear algorithms for MST weight, average degree, TSP, Steiner Tree, Facility Location (survey by Czumaj and Sohler, book by Muthu, papers, presentation, course by Indyk, papers by Czumaj and Sohler).Διαφάνειες.
03/6 Π. Πανταβός Streaming algorithms for frequency moments, heavy hitters, geometric problems (survey by Czumaj and Sohler, book by Muthu, papers, presentation, course by Indyk, papers by Czumaj and Sohler).
04/6 Γ. Παναγέας Randomized Load Balancing: The Power of 2 Choices ([MU, Κεφ. 14], survey by Mitzenmacher, [Vocking, FOCS 99], papers on randomized load balancing by Meyer auf der Heide and his group). Διαφάνειες.
10/6 Π. Κουτρής Randomization in Parallel and Distributed Computing: maximal Independent Sets, Perfect Matchings, Leader Election, Byzantine Agreement, broadcasting and gossiping, rumour spreading, fault-tolerance ([MR, Κεφ. 12], [Antonakopoulos], …) Διαφάνειες.
10/6 Μ. Θάνος Randomization in Approximation and Online Algorithms: randomized rounding, conditional expectation revisited, randomized algorithms for paging, k-server, metrical task systems, Yao’s lemma and lower bounds against the oblivious adversary (original papers by Raghavan, SDP rounding by Goemans & Williamson, [MR, Κεφ. 13], [Borodin, El-Yaniv]). Διαφάνειες.

Τελευταία ανανέωση: 06 Ιουνίου 2010