3 Ιουνίου - 9 Ιουνίου

Διάλεξη 3/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). 
• Διαφάνειες (1-25). Δείτε και Διαφάνειες (συμπληρωματικές, 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

Βίντεο της διάλεξης: θα σταλεί το link (ειδοποιήστε μας αν δεν το λάβετε).