Weekly outline

  • Ακαδ. Έτος 2020-21

    Διδάσκοντες


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


    • Γιάννης Παπαϊωάννου, Υ.Δ.
    • Παναγιώτης Πατσιλινάκος, Υ.Δ. 


    Διαλέξεις


    Περιεχόμενα

    • Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, 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.

    Σελίδες παλαιότερων ετών:  2019-20   2018-19   2017-18   2016-17      

  • 22 February - 28 February

    Διάλεξη 24/2: Γραμμικός Προγραμματισμός, Simplex



    Βίντεο της διάλεξης 

    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).



    • 1 March - 7 March

      Διάλεξη 3/3: Γραμμικός Προγραμματισμός, η μέθοδος Simplex



      Προτεινόμενη μελέτη: σημειώσεις M. Goemans, μονογραφία H. Karloff, διαφάνειες Π. Σπυράκη. 

      Βίντεο της διάλεξης 

      (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


      • 8 March - 14 March

        Διάλεξη 10/3: Δυϊκότητα στον Γραμμικό Προγραμματισμό


        Προτεινόμενη Μελέτη:

        • Σημειώσεις (1ο set και 2o set) σχετικά με το Λήμμα του Farkas και τη γεωμετρική του ερμηνεία. 


        Βίντεο της διάλεξης 

        (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


        • 15 March - 21 March

          Διάλεξη 17/3: Προσεγγιστικοί αλγόριθμοι Ι

          • Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds). Το πρόβλημα Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).

          Διαφάνειες (προσωρινή έκδοση): 1-30.

          Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.

          Bίντεο της διάλεξης

          (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)

          • 22 March - 28 March

            Διάλεξη 24/3: Προσεγγιστικοί αλγόριθμοι ΙΙ

            • Weighted Set Cover: απόδειξη του λόγου Hn του άπληστου αλγόριθμου. Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος. 2-προσεγγιστικός αλγόριθμος για το Metric TSP.

            Διαφάνειες: 31-45.

            Προτεινόμενη μελέτη: Vazirani άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή) και 3.2, και DPV 5.4, 9.2.3

            Βίντεο της διάλεξης

            (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)



            • 29 March - 4 April

              Διάλεξη 31/3: Προσεγγιστικοί αλγόριθμοι ΙΙΙ

              • Αλγόριθμος Χριστοφίδη για το Metric TSP. Αλγόριθμος Hoogeveen για το πρόβλημα TSP(s-t path).
              • Το πρόβλημα Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης.
              • Τα προβλήματα Mutiway Cut και Minimum k-Cut.

                Διαφάνειες                : 46-58.

                Προτεινόμενη μελέτη: Vazirani κεφ. 3.1 και 4.

              Βίντεο της διάλεξης 

              (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό, και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)


              • 5 April - 11 April

                Διάλεξη 7/4: Προσεγγιστικοί αλγόριθμοι IV


                (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό, και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)

                • 12 April - 18 April

                  Διάλεξη 14/4: Πιθανοτικοί Αλγόριθμοι Ι


                  Προτεινόμενη μελέτη: 

                  Προτάσεις για περαιτέρω μελέτη: 



                  Βίντεο της διάλεξης 

                  (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


                  • 19 April - 25 April

                    Διάλεξη 21/4: Πιθανοτικοί Αλγόριθμοι ΙI

                    • Πιθανοτικοί αλγόριθμοι: πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problem, (δείτε ακόμη εδώ για secretary problems), Lovasz Local Lemma και εφαρμογή στην ικανοποιησιμότητα k-SAT, Chernoff-Hoeffding bounds, set balancing. 

                    Προτεινόμενη μελέτη: 
                    Προτάσεις για περαιτέρω μελέτη: 

                    Βίντεο της διάλεξης 

                    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


                    • 26 April - 2 May

                      Διάλεξη 28/4: Πιθανοτικοί Αλγόριθμοι ΙII - Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό


                      • Πιθανοτικοί αλγόριθμοι: Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία. 
                      • Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, Max-Cut. 

                      Προτεινόμενη μελέτη: 

                      Βίντεο της διάλεξης 

                      (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).



                      • 10 May - 16 May

                        Διάλεξη 12/5: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (συνέχεια), Βασικές Έννοιες (Αλγοριθμικής) Θεωρίας Παιγνίων 

                         

                        • Max-Cut και Max-SAT, ισχυρότερα relaxations, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT. 
                        • Primal-dual μέθοδος για το πρόβλημα set cover. 
                        • Βασικές έννοιες Θεωρίας Παιγνίων και σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων (διαφάνειες), παραδείγματα παιγνίων, παίγνια 2 παικτών.

                        Προτεινόμενη μελέτη: 

                        Βίντεο της διάλεξης 

                        (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


                        • 17 May - 23 May

                          Διάλεξη 19/5: Αλγοριθμική Θεωρία Παιγνίων - Βασικές έννοιες σχεδιασμού μηχανισμών

                          • Υπολογισμός ισορροπίας σε 2-player zero-sum games, von Neumann Minimax Theorem (διαφάνειες, καλύπτουν περισσότερη ύλη από αυτή που παρουσιάσαμε στο μάθημα). 
                          • Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. 
                          • Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης. 
                          • Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions. 
                          • Social welfare maximization, Walrasian equilibrium, VCG μηχανισμός. 

                          Προτεινόμενη μελέτη: 


                          Βίντεο της διάλεξης 

                          (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


                          • 24 May - 30 May

                            Διάλεξη 26/5

                            Α. Το Πρόβλημα της Ανάθεσης και της Μεταφοράς

                            Διαφάνειες (όπως παρουσιάστηκαν)
                            Διαφάνειες (πλήρης έκδοση) 

                            Προτεινόμενη μελέτη: Κεφάλαιο 5 από το βιβλίο του H. Taha ή κεφάλαιο 9 από το βιβλίο των F. Hillier and G. Lieberman (υπάρχουν και ελληνικές εκδόσεις) και σημειώσεις (i) για το primal-dual σχήμα και (ii) για ταιριάσματα, καλύμματα, Θεώρημα Konig, TU πίνακες.

                            Βίντεο Α' μέρους της διάλεξης

                            (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).

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

                            • Θεωρία αριθμών. Διαιρετότητα. Κινέζικο Θεώρημα Υπολοίπων. 
                            • Θεωρία ομάδων. Σύμπλοκα, τάξη ομάδας, γεννήτορες. Θ. Lagrange και χρήση του στους πιθανοτικούς αλγορίθμους. 
                            Διαφάνειες (1-24)

                            Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 2.1, 2.2, 2.3, 4.5. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).

                            Βίντεο Β' μέρους της διάλεξης

                            (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).

                            • 31 May - 6 June

                              Διάλεξη 2/6

                              Α. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙI)

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


                              Β. Εισαγωγή σε παραμετρικούς αλγορίθμους και πολυπλοκότητα

                              • Η κλάση FPT.  FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). 
                              • Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος). 
                              • Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά).
                              • Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά). 
                              • Διαφάνειες (1-29), Διαφάνειες (1-18) και Διαφάνειες (1-17 συνοπτικά). Δείτε και Διαφάνειες (συμπληρωματικές, 1-7)
                              • Προτεινόμενη μελέτη: [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, 3.1, 7.1-7.4, και 13.1-13.3 (συνοπτικά, ορισμούς μόνο).


                              Βίντεο της διάλεξης 

                              (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).