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 ή μέσο).

          • This week

            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 ή μέσο).