Section outline

  • 22/5: Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙΙ)
    Εισαγωγή στους παραμετρικούς αλγορίθμους

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

    • Εισαγωγή στους παραμετρικούς αλγορίθμους. Η κλάση FPT.
    • FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization).
      Διαφάνειες (1-13)
    • Προτεινόμενη μελέτη: [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