Διαλέξεις

• Διάλεξη 2/3/2022. Εισαγωγή - Διαδικαστικά. Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent. Γραμμικός προγραμματισμός, βασικές έννοιες και γεωμετρία. 
• Διάλεξη 9/3/2022. Γραμμικός προγραμματισμός, κορυφές και βασικές εφικτές λύσεις, η μέθοδος Simplex.
• Διάλεξη 16/3/2022. Δυϊκότητα στον γραμμικό προγραμματισμό. Εισαγωγή στους πιθανοτικούς αλγόριθμους, πιθανοτικός αλγόριθμος για το πρόβλημα Ελάχιστης Τομής, balls and bins. 
• Διάλεξη 23/3/2022. Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds).
  Διαφάνειες (1-28). Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.
• Διάλεξη 30/3/2022. Το πρόβλημα (Weighted) Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).  Το πρόβλημα Maximum Coverage. 
  Διαφάνειες (29-41). Προτεινόμενη μελέτη: Vazirani 2.1, και άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή). Επίσης: DPV 5.4 και 9.2.3.
• Διάλεξη 6/4/2022. Επανάληψη σε Set Cover και Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem, TSP), μη-προσεγγισιμότητα, αλγόριθμος Χριστοφίδη. Προβλήματα TSP(s-t path), Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης. Τα προβλήματα Mutiway Cut και Minimum k-Cut. 
  Διαφάνειες (42-59). Προτεινόμενη μελέτη: Vazirani, κεφ. 3 και 4.
• Διάλεξη 13/4/2022. Επανάληψη σε Mutiway Cut και Minimum k-Cut. Δένδρα Gomory-Hu.
  Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. 
  Διαφάνειες (25-34). Προτεινόμενη μελέτη: Vazirani κεφ. 8.
• Διάλεξη 4/5/2022. 
  • Το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS.
    Διαφάνειες. Προτεινόμενη μελέτη: Vazirani κεφ. 10.

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

• Διάλεξη 11/5/2022. Πιθανοτικοί Αλγόριθμοι: η πιθανοτική μέθοδος (απλά παραδείγματα εφαρμογής σε max-cut και maximum independent set), πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problem, (δείτε ακόμη εδώ για secretary problems).  
• Διάλεξη 25/5/2022. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙI): Αντίστροφος modulo n, επαναλαμβανόμενος τετραγωνισμός, Κινέζικο Θεώρημα Υπολοίπων (CRT). Ο έλεγχος πρώτων αριθμών Miller-Rabin. Απόδειξη ορθότητας βάσει Θ. Lagrange.
  Διαφάνειες (1-30). Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 4.4, 4.5, 4.6. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).
• Διάλεξη 1/6/2022: Πιθανοτικοί αλγόριθμοι: Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, deterministic rounding για το πρόβλημα της ανάθεσης εργασιών σε μη συσχετιζόμενες παράλληλες μηχανές (δείτε lecture notes), Max-Cut, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT (δείτε lecture notes).
• Διάλεξη 8/6/2022: Εισαγωγή σε παραμετρικούς αλγορίθμους και παραμετρική πολυπλοκότητα
  • Η κλάση FPT.  FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). Διαφάνειες (1-20). Δείτε και Διαφάνειες (συμπληρωματικές, 1-7).
  • Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος). Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά). Διαφάνειες (1-18).
  • Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά). Διαφάνειες (1-17 συνοπτικά). 
  • Προτεινόμενη μελέτη: [M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.], κεφ. 1, 2.1, 2.2.1, 3.1, 7.1-7.4, και 13.1-13.3 (συνοπτικά, ορισμούς μόνο).
    

   
  

Πρόσθετες διαλέξεις για μεταπτυχιακούς φοιτητές