Weekly outline

  • Γενικά

    Οι διαλέξεις για φέτος (2018-19) ξεκίνησαν Τετάρτη 20/2 και γίνονται στην αίθουσα 009 του Ν. Κτ. Ηλεκτρολόγων ώρα 4:30μμ-7:30μμ. 

    Ενδεικτικό πρόγραμμα διαλέξεων.


    Διδάσκοντες


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


    • Λουκάς Κάβουρας, Υ.Δ. ()
    • Νίκος Μελισσινός, Υ.Δ. ()
    • Γιάννης Παπαϊωάννου, Υ.Δ. ()


    Διαλέξεις

    • Τετάρτη 16:30 – 19:30, Αίθoυσα 009, Νέα Κτήρια ΗΜΜΥ


    Περιεχόμενα

    • Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, Vertex Cover, Set Cover, TSP σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, PTAS και FPTAS, Knapsack.
    • Βασικές έννοιες γραμμικού προγραμματισμού, η μέθοδος Simplex, δυϊκότητα στον γραμμικό προγραμματισμό, complementary slackness.
    • Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό, στρογγυλοποίηση, τυχαία στρογγυλοποίηση, η μέθοδος primal-dual.
    • Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία, ελάχιστη τομή, balls and bins και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές sparsification.
    • Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας.
    • Σχεδιασμός μηχανισμών, κοινωνική επιλογή, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, VCG.
    • Αλγόριθμοι μάθησης, no-regret, multiplicative updates, regression, kNN, SVMs.
    • Παραμετρικοί αλγόριθμοι και πολυπλοκότητα.
    • Κατανεμημένοι αλγόριθμοι, αξιόπιστη εκπομπή, Βυζαντινά πρωτόκολλα, consensus. Αλγόριθμοι κινητών οντοτήτων (mobile agents). 


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

    • V.V. Vazirani. Approximation Algorithms. Springer Verlag, Heidelberg, 2001.
    • D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge UP, 2010.
    • S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. MacGraw-Hill, 2006.
    • K. Steiglitz and C.H. Papadimitriou. Combinatorial Optimization: Algorithms and Complexity. 
    • V. Chvatal. Linear Programming. W.H. Freeman and Co., 1984. 
    • H. Karloff. Linear Programming. Birkhäuser, 1991. 
    • D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 2008. 
    • R. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications, 1993. 
    • N. Lynch, Distributed Algorithms. Morgan Kaufmann Publishers,1996. 
    • Roger Wattenhofer. Principles of Distributed Computing. ETH Zuerich course notes, 2011.
    • R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. 
    • M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. 
    • N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. 
    • Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
    • Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
    • M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.


    Σελίδα μαθήματος 2016-17      Σελίδα μαθήματος 2017-18

  • 20 February - 26 February

    20/2

    • Εισαγωγή-διαδικαστικά. 
    • Προσεγγιστικοί αλγόριθμοι: εισαγωγικές έννοιες, λόγος προσέγγισης, το πρόβλημα Vertex Cover. Το πρόβλημα Set Cover χωρίς βάρη, ανάλυση του Greedy αλγορίθμου (λογαριθμικός λόγος προσέγγισης)  (slides: 1-17)
    • Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.
    • Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.

    • 27 February - 5 March

      27/2
      • Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover με βάρη, H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Αναγωγές διατήρησης προσέγγισης.
      • Slides: 18-41
        Προτεινόμενη μελέτη: Vazirani 2.1 (δείτε και άσκηση 2.15, επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή) και 3, και DPV 5.4, 9.2.3

      • 6 March - 12 March

        6/3

        • 13 March - 19 March

          13/3: Γραμμικός Προγραμματισμός, Simplex

          • 20 March - 26 March

            20/3: Δυϊκότητα, Πιθανοτικοί Αλγόριθμοι

            • 27 March - 2 April

              27/3: Πιθανοτικοί Αλγόριθμοι
              • Πιθανοτικοί αλγόριθμοι: balls and bins, coupons collector, Chernoff-Hoeffding bounds, set balancing, πιθανοτική μέθοδος, πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT και 3-SAT (δείτε ακόμη και αυτές τις διαφάνειες για το 2-SAT και το 3-SAT), secretary problem, prophet inequalities (δείτε ακόμη εδώ για secretary problems και prophet inequalities). 


              • 3 April - 9 April

                3/4: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό
                • Διαφάνειες.
                  Προτεινόμενη μελέτη: D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 1.4-1.7, 5.1, 5.4, 5.5. Aξίζει ακόμη να δείτε τις ενότητες 7.1 - 7.6, αν και δεν τις καλύψαμε στο μάθημα.

                • 17 April - 23 April

                  17/4: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (συνέχεια),
                  Εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων.
                  • Primal-dual μέθοδος για το πρόβλημα set cover, αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT. 
                    Προτεινόμενη μελέτη: D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 7.1 - 7.6 (μέθοδος primal-dual για αλγόριθμους προσέγγισης), 6.1 - 6.3 (προσεγγιστικοί αλγόριθμοι βασισμένοι σε semidefinite programming relaxations), σημειώσεις για τον αλγόριθμο Goemans-Williamson, 1.6 (η μέθοδος dual fitting για set cover). 
                  • Σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων (διαφάνειες), παίγνια μηδενικού αθροίσματος, το θεώρημα Μinimax του von Neumann (διαφάνειες και διαφάνειες).
                    Προτεινόμενη μελέτη: σημειώσεις για παίγνια μηδενικού αθροίσματος και το θεώρημα του Nash. 
                    Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016. Κεφάλαια: 2, 4 και 5. 

                  • 8 May - 14 May

                    8/5: Κοινωνική Επιλογή και Σχεδιασμός Μηχανισμών.
                    • Κοινωνική επιλογή, κανόνες ψηφοφορίας, αξιωματική προσέγγιση και αποτελέσματα μη ύπαρξης, δημοπρασίες για μονοπαραμετρικά περιβάλλοντα, θεώρημα του Myerson, VCG. Διαφάνειες. 
                    • Προτεινόμενη μελέτη: 
                      Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016. Κεφάλαια: 13 (κοινωνική επιλογή), 14 και 15 (δημοπρασίες και σχεδιασμός μηχανισμών, περιέχουν και υλικό που δεν καλύψαμε στο μάθημα).
                      Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerome Lang, Ariel D. Procaccia (editors). Handbook of Computational Social Choice. Κεφάλαια 1 και 2 (ιστορικά στοιχεία για την περιοχή της Κοινωνικής Επιλογής και κανόνες ψηφοφορίας). 
                      Σημειώσεις από το μάθημα του Tim Roughgarden: Διάλεξη 2, διάλεξη 3 και διάλεξη 4. 

                    • 15 May - 21 May

                      15/5: Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (Ι)

                      • Θεωρία αριθμών. Διαιρετότητα. Κινέζικο Θεώρημα Υπολοίπων. 
                      • Θεωρία ομάδων. Σύμπλοκα, τάξη ομάδας, γεννήτορες. Θ. Lagrange και χρήση του στους πιθανοτικούς αλγορίθμους. 
                      • Οι έλεγχοι πρώτων αριθμών Fermat και Miller-Rabin.
                        Διαφάνειες (1-27)
                      • Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 2.1, 2.2, 2.3, 4.5

                      • 22 May - 28 May

                        22/5: Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙΙ)
                        Εισαγωγή στους παραμετρικούς αλγορίθμους

                        • Απόδειξη ορθότητας του ελέγχου Miller-Rabin.
                        • Αλγόριθμος παραγοντοποίησης Pollard-rho
                          Διαφάνειες (28-36)
                        • Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 4.5, 4.6. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).

                        • Εισαγωγή στους παραμετρικούς αλγορίθμους. Η κλάση FPT.
                        • FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization).
                          Διαφάνειες (1-13)
                        • Προτεινόμενη μελέτη: [M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.], κεφ. 1, 2.1, 2.2.1


                           

                        • 29 May - 4 June

                          29/5: Παραμετρικοί αλγόριθμοι δενδροπλάτους (treewidth) - παραμετρικές αναγωγές

                          • Παραμετρικοί αλγόριθμοι για Independet Set και 3-Coloring με παράμετρο το treewidth. Θεώρημα Courcelle.
                            Διαφάνειες (1-20)
                          • Προτεινόμενη μελέτη: [Cygan et al, Parameterized Algorithms], κεφ. 7.1-7.4

                          • Παραμετρικές αναγωγές. Παραμετρική δυσκολία του Independent Set με παράμετρο την πληθικότητα. 
                            Διαφάνειες (1-11)
                          • Προτεινόμενη μελέτη: [Cygan et al, Parameterized Algorithms], κεφ. 13.1-13.3 (συνοπτικά, ορισμούς μόνο).


                          • 5 June - 11 June

                            Διάλεξη 5/6: 

                            • Παίγνια Συμφόρησης: μοντέλο, εφαρμογές, συνάρτηση δυναμικού, σύγκλιση, τίμημα της αναρχίας, Braess paradox, τεχνικές βελτίωσης τιμήματος της αναρχίας. 
                              Προτεινόμενη μελέτη: Διαφάνειες και τα παρακάτω surveys: 1, 2, 3, 4, 5. 
                               
                            • Εισαγωγή σε Blockchain & Consensus
                              Διαφάνειες
                              Δείτε και: μια πιο τεχνική εισαγωγή στο Bitcoin (Διαφάνειες)