Topic outline

  • Γενικά - Ανακοινώσεις - Forum

    • Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.

    • Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές. 

      Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.


  • Διδάσκοντες / Βοηθοί Διδασκαλίας

    • Άρης Παγουρτζής, Καθηγητής ()
    • Δημήτρης Φωτάκης, Καθηγητής ()
    • Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής ()
    • Ορέστης Πλευράκης, Μεταδιδακτορικός Ερευνητής ()


    Ώρες Γραφείου Διδασκόντων

    • Άρης Παγουρτζής: Τρίτη 14:00-15:00, γραφείο 1.1.6, (Παλαιό) Κτήριο Ηλεκτρολόγων.
    • Δημήτρης Φωτάκης: Τετάρτη 14:00 - 15:00, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
    • Θανάσης Λιανέας: θα ανακοινωθούν.
    • Ορέστης Πλευράκης: θα ανακοινωθούν.


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

    • Θάνος Τόλιας
    • Μαριάννα Σπυράκου
  • Γενικές Πληροφορίες

    Οι διαλέξεις του μαθήματος γίνονται κάθε Τετάρτη, ώρα 10:45-13:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 004. 

    Λόγω προγραμματισμένης εκδήλωσης της Σχολής την Τετάρτη 14 Φεβρουαρίου, η πρώτη διάλεξη για το εαρινό εξάμηνο 2024 θα γίνει την Τετάρτη 21 Φεβρουαρίου. 

    Οι online διαλέξεις θα γίνονται μέσω Webex στο παρακάτω link: 

    Meeting link: https://centralntua.webex.com/centralntua/j.php?MTID=mbd4ff61c85443168347069c9d8294506 
    Meeting number: 2792 126 0088
    Password:               i33iJM3UHPF
    Host key:                 747052


  • Περιεχόμενα

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

  • Βιβλιογραφία


  • Παλαιότερα Έτη


  • Εκπαιδευτικό Υλικό / Προτεινόμενη Μελέτη


  • Διαλέξεις

    • Διάλεξη 21/2/2024. Εισαγωγή - Διαδικαστικά. Εισαγωγή στους πιθανοτικούς αλγόριθμους, πιθανοτικός αλγόριθμος για το πρόβλημα Ελάχιστης Τομής (δείτε ακόμη wikipedia και σημειώσεις για τον αλγόριθμο Karger).
    • Διάλεξη 6/3/2024. Πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problems (δείτε ακόμη εδώ για secretary problems).
    • Διάλεξη 13/3/2024. Prophet inequalities. H πιθανοτική μέθοδος:  Lovasz Local Lemma (δείτε lecture notes για το LLL και εφαρμογές του), αλγοριθμική εκδοχή LLL - η μέθοδος της εντροπίας (δείτε lecture notes και lecture notes). Συγκέντρωση γύρω από τη μέση τιμή, Chernoff-Hoeffding bounds (δείτε lecture notes), εφαρμογές.
    • Διάλεξη 20/3/2024. Ανισότητες συγκέντρωσης γύρω από τη μέση τιμή, εφαρμογές, τυχαία δειγματοληψία. Online learning, learning from experts advice: αλγόριθμοι weighted majority και randomized weighted majority. 
    • Διάλεξη 27/3/2024. PAC learning, ERM, μάθηση με ομοιόμορφη και ανομοιόμορφη σύγκλιση, VC dimension, θεμελιώδες θεώρημα μηχανικής μάθησης. Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent
      Προσεγγιστικοί αλγόριθμοι: Βασικές Έννοιες. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. 
    • Διάλεξη 3/4/2024. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα (Weighted) Set Cover. Ανάλυση λόγου προσέγγισης του άπληστου αλγόριθμου (Greedy). Tight examples. Το πρόβλημα Maximum Coverage: (1-1/e)-προσεγγιστικός αλγόριθμος.
    • Διάλεξη 10/4/2024.  Προσεγγιστικοί αλγόριθμοι: το πρόβλημα TSP και Metric TSP. Το πρόβλημα Steiner Tree. Αναγωγές διατήρησης λόγου προσέγγισης. Προβλήματα τομών: multiway cut, minimum k-cut. Δένρα Gomory-Hu.
    • Διάλεξη 17/4/2024. Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. Διαφάνειες (25-34).  Το πρόβλημα Minimum Makespan Scheduling: 2-προσεγγιστικός και (4/3)-προσεγγιστικός αλγόριθμος. Διαφάνειες.
    • Διάλεξη 24/4/2024. I. Το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION). PTAS με αναγωγή στο Restricted Bin Backing. Διαφάνειες
      II. Υπολογιστική δυσκολία προσέγγισης (approximation hardness). Αναγωγές διατήρησης λόγου προσέγγισης. Αναγωγή από Set Cover σε Node Weighted Steiner Tree. Διαφάνειες (1-22). 
    • Διάλεξη 8/5/2024. I. Υπολογιστική δυσκολία προσέγγισης (approximation hardness). Αναγωγές εισαγωγής χάσματος, και αναγωγές διατήρησης χάσματος. Αναγωγές από MAX3SAT σε Clique, IS, Vertex Cover. Self-reducibility και hardness amplification (Clique). Διαφάνειες (23-43). 
      II. Εισαγωγή σε παραμετρικούς αλγορίθμους και παραμετρική πολυπλοκότητα
      • Η κλάση FPT.  FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). Διαφάνειες (6-20)
      • Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος). Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά). Διαφάνειες (1-18).
      • Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά). Διαφάνειες (1-17 συνοπτικά)
  • Γραπτές Ασκήσεις

    • Θα ανακοινωθούν δύο (2) σειρές γραπτών ασκήσεων
    • Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
    • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.

    Εκφωνήσεις Γραπτών Ασκήσεων