Weekly outline

  • Γενικά

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



    Διδάσκοντες


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


    • Λουκάς Κάβουρας, Υ.Δ.
    • Αλβέρτος Καλαβάσης, Υ.Δ.
    • Γιάννης Παπαϊωάννου, Υ.Δ.


    Διαλέξεις

    • Τετάρτη 16:00 – 19:00, Αίθ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.

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

  • 26 February - 3 March

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



    • 4 March - 10 March

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


      • 11 March - 17 March

        Η διάλεξη της 11/3 δεν πραγματοποιήθηκε λόγω των έκτακτων μέτρων αντιμετώπισης της πανδημίας του SARS-CoV-2.

        • 18 March - 24 March

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

          • Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Προβλήματα Vertex Cover και Set Cover με και χωρίς βάρη. Ο λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).

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

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

          Το μάθημα πραγματοποιήθηκε διαδικτυακά. Σύνδεσμοι για τα βίντεο της διάλεξης:

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

          • 1 April - 7 April

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

            • Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. 

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

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

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

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


            • 8 April - 14 April

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

              • Προσεγγιστικοί αλγόριθμοι (slides 47-56): Το πρόβλημα Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
                Προτεινόμενη μελέτη                : Vazirani κεφ. 3.1 και 4.
              • Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34): ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack.
                Προτεινόμενη μελέτη: Vazirani κεφ. 8.
              • Προσεγγιστικοί αλγόριθμοι (3η ενότητα): το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS (σύντομη αναφορά).
                Προτεινόμενη μελέτη: Vazirani κεφ. 10.

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

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



              • 15 April - 21 April

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


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

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

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

                • 22 April - 28 April

                  Δεν έγινε διάλεξη, λόγω διακοπών του Πάσχα. 

                  • 29 April - 5 May

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


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

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

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


                    Δυστυχώς, για τεχνικούς λόγους, δεν κατέστη δυνατή η βιντεοσκόπηση της διάλεξης. 

                    • 6 May - 12 May

                      Διάλεξη 6/5: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό

                      • Η τεχνική Color Coding για τον υπολογισμό ενός μακρύτερου απλού μονοπατιού (δεν είχαμε προλάβει να την καλύψουμε στην προηγούμενη διάλεξη). 
                      • Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, Max-Cut και Max-SAT, ισχυρότερα relaxations, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT. 

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

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

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


                      • 13 May - 19 May

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

                         

                        • Primal-dual μέθοδος για το πρόβλημα set cover (συνέχεια από προηγούμενη διάλεξη). 
                        • Βασικές έννοιες Θεωρίας Παιγνίων και σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων (διαφάνειες), παραδείγματα παιγνίων, παίγνια 2 παικτών, κυρίαρχες στρατηγικές, αμιγείς και πεπλεγμένες στρατηγικές, ισορροπία Nash, παίγνια μηδενικού αθροίσματος, το θεώρημα Μinimax του von Neumann (διαφάνειες βασισμένες σε διαφάνειες Βαγγέλη Μαρκάκη από μεταπτυχιακό μάθημα Αλγοριθμικής Θεωρίας Παιγνίων).

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

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

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


                        • 20 May - 26 May

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

                          • Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. 
                          • Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης. 
                          • Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions. 
                          • Social welfare maximization, Walrasian equilibrium. 

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


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

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


                          • 27 May - 2 June

                            Διάλεξη 27/5

                            Αλγοριθμική Θεωρία Παιγνίων (συν.)

                            • VCG μηχανισμός, φιλαλήθης μεγιστοποίηση του social welfare μέσω value queries και Maximal-in-Range μηχανισμών για subadditive συναρτήσεις και μέσω posted prices και demand queries για submodular συναρτήσεις. 
                            • Προτεινόμενη μελέτη: βλ. υλικό προηγούμενης διάλεξης.  

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

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

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

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

                            • 3 June - 9 June

                              Διάλεξη 3/6 

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

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

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

                              Βίντεο της διάλεξης: θα σταλεί το link (ειδοποιήστε μας αν δεν το λάβετε).


                              • 10 June - 16 June

                                Διάλεξη 10/6

                                Παραμετρικοί αλγόριθμοι με παράμετρο το δενδροπλάτος (treewidth) 

                                Παραμετρικές αναγωγές

                                Βίντεο της διάλεξης: θα σταλεί το link (ειδοποιήστε μας αν δεν το λάβετε)