Weekly outline

  • Γενικά

    Ακαδ. έτος

    • 2017-18

    Διδάσκων

    Βοηθοί διδασκαλίας
    Έναρξη μαθήματος
    • Το πρώτο μάθημα θα γίνει στις 20/2/2018.
    Διαλέξεις
    • Παρασκευή 15:00-19:00 Παλιό Κτήριο Ηλεκτρολόγων ΕΜΠ, αίθουσα 1.1.31. (Προσοχή: αλλαγή ημέρας και ώρας!)
    Περιεχόμενο μαθήματος (ενδεικτικό)

    Το αντικείμενο του μαθήματος είναι η μελέτη αλγοριθμικών μεθόδων και η ανάλυση πολυπλοκότητας για υπολογιστικά προβλήματα και θεμελιώδεις διαδικασίες που σχετίζονται με δίκτυα, κυρίως υπολογιστών και επικοινωνιών. Ορισμένα από τα θέματα που θα καλυφθούν:

    • Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling.
    • Κατανεμημένα πρωτόκολλα: εκλογή αρχηγού, broadcasting, gossiping, byzantine agreement, secret sharing. Ασύρματα ad hoc δίκτυα. Συγχρονισμένοι και ασύγχρονοι αλγόριθμοι. Fault tolerance.
    • Προβλήματα αυτόνομων οντοτήτων, εξερεύνηση δικτύων, προβλήματα συνάντησης (rendezvous), εντοπισμός βλαβών σε δίκτυα. Πρωτόκολλα δρομολόγησης, compact routing, geometric routing.
    • Ειδικά θέματα: χρονοδρομολόγηση (scheduling), δρομολόγηση και ανάθεση συχνοτήτων σε οπτικά δίκτυα, αλγόριθμοι πλοήγησης, προγραμματισμός δρομολογίων οχημάτων.
    • Στοιχεία θεωρίας παιγνίων: σημεία ισορροπίας Nash, "κόστος της αναρχίας". Εγωιστική δρομολόγηση σε κλασικά, ασύρματα και οπτικά δίκτυα. Παίγνια συμφόρησης. Σύγκλιση σε ισορροπίες Nash και σχεδίαση μηχανισμών.
    Βιβλιογραφία
    • 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.
    • H. Karloff. Linear Programming. Birkhäuser, 1991. 
    • 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. 
    • Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
    • Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.

  • 19 February - 25 February

    20/2

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

    • 26 February - 4 March

      27/2
      • Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover, χωρίς και με βάρη, f-προσεγγιστικός και H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα μεγιστοποίησης Maximum Coverage (slides: 16-26).
        Προτεινόμενη μελέτη: Vazirani 2.1 (δείτε και άσκηση 2.15, επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή), και DPV 5.4.
        Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.

      • 5 March - 11 March

        9/3
        • Προσεγγιστικοί αλγόριθμοι (slides 27-41): το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
          Προτεινόμενη μελέτη          : Vazirani 3 και 4, και DPV 9.2.3.
          Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.

        • 12 March - 18 March

          16/3

          • 19 March - 25 March

            23/3
            • Προσεγγιστικοί αλγόριθμοι (3η ενότητα): προσεγγιστικό σχήμα (PTAS) για το πρόβλημα Minimum Makespan Scheduling με αναγωγή στο Restricted Bin Packing. Ακριβής αλγόριθμος δυναμικού προγραμματισμού για το Restricted Bin Packing.
              Προτεινόμενη μελέτη: Vazirani κεφ. 10.
            • Γραμμικός προγραμματισμός: εισαγωγή, τυπική και κανονική μορφή, πολύεδρο εφικτών λύσεων, βασικές εφικτές λύσεις (διαφ. 1-12).
              (ανέβηκε νέα έκδοση).
              Προτεινόμενη μελέτη: DPV 7.1 (δείτε και Karloff κεφ. 1 για μια πιο αναλυτική παρουσίαση, καθώς και τις πολύ καλές διαφάνειες/σημειώσεις του μαθήματος LP του Henry Wolkowicz, U Waterloo, ενότητες 1-4 και 11-13).

            • 26 March - 1 April

              30/3

              • Γραμμικός προγραμματισμός: ο αλγόριθμος Simplex (διαφ. 13-26).
                Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.
                Προτεινόμενη μελέτη: Karloff κεφ. 2, δείτε και τις πολύ καλές διαφάνειες/σημειώσειςτου μαθήματος LP του Henry Wolkowicz, U Waterloo, (ενότητες 14-16, αλλά και 17-20 για πιο προχωρημένα θέματα). Δείτε ακόμη DPV 7.6 για έναν διαφορετικό, αλλά αρκετά ενδιαφέροντα τρόπο παρουσίασης του Simplex.
              • Χρήση γραμμικού προγραμματισμού για προσεγγιστικούς αλγορίθμους, f-προσεγγιστικός αλγόριθμος για το Set Cover με στρογγυλοποίηση (rounding). 
                Προτεινόμενη μελέτη: Vazirani κεφ. 14.1.

              • 2 April - 15 April

                Διακοπές Πάσχα

                • 16 April - 22 April

                  20/4

                  • Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
                    Προτεινόμενη μελέτη: Vazirani κεφ. 12.


                  • 23 April - 29 April

                    27/4


                    • 30 April - 6 May

                      4/5

                      Δεν έγινε μάθημα.

                      • 7 May - 13 May

                        11/5

                        Πιθανοτικοί αλγόριθμοι:

                        • Πρόβλημα ελάχιστης τομής (mincut - αλγόριθμος του Karger) [MU, 1.5].
                        • Πρόβλημα μέγιστης τομής (maxcut - πιθανοτική μέθοδος και derandomization) [MU, 6.2 & 6.3].
                        • Αλγόριθμοι Las Vegas και Monte Carlo (MU, σελ. 62).
                        • Πιθανοτικό πρωτόκολλο για έλεγχο ισότητας συμβολοσειρών. [R. Karp: Introduction to Randomized Algorithms, Section 5]


                        MU: Mitzenmacher-Upfal, 2nd edition

                        Δείτε και: https://www.cs.ox.ac.uk/people/elias.koutsoupias/pc2016-17/lectures.pdf (2.2, 3.2)



                        • 14 May - 20 May

                          18/5

                          Κατανεμημένοι αλγόριθμοι:


                          • 21 May - 27 May

                            25/5

                            Παραμετρικοί αλγόριθμοι. Αλγόριθμοι FPT για το Vertex Cover. Πυρηνοποίηση (kernelization). Δενδροπλάτος (treewidth). FPT reductions και W[1]-hardness.

                            [Προσοχή: οι διαφάνειες είναι προσωρινές, θα γίνουν αλλαγές]

                            Προτεινόμενη μελέτη: Fundamentals of Parameterized Complexity, Rodney G. Downey , Michael R. Fellows. (κεφ. 2, 3.1-3.3, 4.2, 10.2, 20, προαιρετικά: 21, 22.2, 22.3)


                            • 28 May - 3 June

                              • 4 June - 10 June