Section outline

  • Διάλεξη 2/6

    Α. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙI)

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


    Β. Εισαγωγή σε παραμετρικούς αλγορίθμους και πολυπλοκότητα

    • Η κλάση FPT.  FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). 
    • Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος). 
    • Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά).
    • Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά). 
    • Διαφάνειες (1-29), Διαφάνειες (1-18) και Διαφάνειες (1-17 συνοπτικά). Δείτε και Διαφάνειες (συμπληρωματικές, 1-7)
    • Προτεινόμενη μελέτη: [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 (συνοπτικά, ορισμούς μόνο).


    Βίντεο της διάλεξης 

    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).