Section outline

  • Διάλεξη 27/5

    Αλγοριθμική Θεωρία Παιγνίων (συν.)

    • VCG μηχανισμός, φιλαλήθης μεγιστοποίηση του social welfare μέσω value queries και Maximal-in-Range μηχανισμών για subadditive συναρτήσεις και μέσω posted prices και demand queries για submodular συναρτήσεις. 
    • Προτεινόμενη μελέτη: βλ. υλικό προηγούμενης διάλεξης.  

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

    • Θεωρία αριθμών. Διαιρετότητα. Κινέζικο Θεώρημα Υπολοίπων. 
    • Θεωρία ομάδων. Σύμπλοκα, τάξη ομάδας, γεννήτορες. Θ. Lagrange και χρήση του στους πιθανοτικούς αλγορίθμους. 
    • Ο έλεγχος πρώτων αριθμών Fermat.
      Διαφάνειες (1-25)
    • Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 2.1, 2.2, 2.3, 4.5. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).

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

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