Section outline

  • Collapse Expand

    Γενικά

    Collapse all Expand all

    Ακαδ. έτος

    • 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.

  • Collapse Expand

    19 February - 25 February

    20/2

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

  • Collapse Expand

    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.
      Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.

  • Collapse Expand

    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.
      Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.

  • Collapse Expand

    12 March - 18 March

    16/3

  • Collapse Expand

    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).

  • Collapse Expand

    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.

  • Collapse Expand

    2 April - 15 April

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

  • Collapse Expand

    16 April - 22 April

    20/4

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


  • Collapse Expand

    23 April - 29 April

    27/4


  • Collapse Expand

    30 April - 6 May

    4/5

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

  • Collapse Expand

    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)



  • Collapse Expand

    14 May - 20 May

    18/5

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


  • Collapse Expand

    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)


  • Collapse Expand

    28 May - 3 June

  • Collapse Expand

    4 June - 10 June