Τυχαιοποιημένοι αλγόριθμοι

Τύπος
Επιλογής
Περιγραφή μαθήματος

Μοντέλα τυχαίου υπολογισμού (Las Vegas και Monte Carlo). Δομές δεδομένων. Συναρτήσεις κατάτμησης. Δειγματοληψία. Η εντροπική μέθοδος. Τυχαιοποιημένοι αλγόριθμοι σε γραφήματα. Τυχαιοποιημένοι γεωμετρικοί αλγόριθμοι. Τυχαιοποιημένοι αλγόριθμοι για κατά προσέγγιση μέτρηση. Τυχαιοποιημένοι παράλληλοι αλγόριθμοι. Τεχνικές αποτυχαιοπoίησης. Εργαλεία για την πιθανοτική ανάλυση αλγορίθμων.

Πιθανοτικές Μέθοδοι

Τύπος
Επιλογής
Περιγραφή μαθήματος

Εισαγωγή στην τυχαιότητα, Η πιθανοτική μέθοδος: η πρώτη ροπή, η μέθοδος της δεύτερης ροπής. Προβλήματα τοποθέτησης σφαιρών σε δοχεία. Φράγματα Chernoff. Το τοπικό λήμμα του Lovász, Martingales και εφαρμογές. Τυχαία γραφήματα. Οι ανισότητες Janson. Η ανισότητα του Azuma. Τυχαίοι περίπατοι. Αλυσίδες Markov. Τυχαίοι πίνακες, κατωφλικές συμπεριφορές, οριακά θεωρήματα.

Αλγοριθμική Θεωρία Παιγνίων

Τύπος
Επιλογής
Περιγραφή μαθήματος

Ισορροπία Nash σε παίγνια μηδενικού αθροίσματος και σε παίγνια μη-μηδενικού αθροίσματος, θεωρήματα σταθερού σημείου, υπολογισμός ισορροπίας Nash, η κλάση PPAD, προσεγγιστικοί αλγόριθμοι για τον υπολογισμό ισορροπίας Nash. Παίγνια συμφόρησης και ιδιοτελής δρομολόγηση, αμιγείς ισορροπίες Nash και συναρτήσεις δυναμικού, η κλάση PLS, τίμημα της αναρχίας και τίμημα της σταθερότητας, άνω και κάτω φράγματα, βελτίωση του τιμήματος της αναρχίας (διόδια, πολιτικές Stackelberg, μηχανισμοί συντονισμού, το παράδοξο του Braess). Σχεδιασμός μηχανισμών, κοινωνική επιλογή, θεωρήματα Arrow και Gibbard-Satterthwaite, φιλαλήθεις μηχανισμοί. Μηχανισμοί χωρίς χρηματικά ανταλλάγματα, παίγνια χωροθέτησης, ο χαρακτηρισμός Moulin, ευσταθή ταιριάσματα, top-trading-cycles. Δρομολόγηση σε ιδιοτελείς μηχανές. Δημοπρασίες, θεώρημα Myerson, μηχανισμός VCG, συνδυαστικές δημοπρασίες, multiplicative weight updates και μηχανισμοί με posted prices, άμεσοι μηχανισμοί και το πρόβλημα επιλογής γραμματέως. Φιλαλήθεια και πολυωνυμική προσεγγισιμότητα για προβλήματα μεγιστοποίησης κοινωνικής ωφέλειας. Μη φιλαλήθεις μηχανισμοί, smooth μηχανι- σμοί και το τίμημα της αναρχίας, επικοινωνιακή πολυπλοκότητηα συνδυαστικών δημοπρασιών, κάτω φράγματα στο τίμημα της αναρχίας από υπολογιστικά κάτω φράγματα στην προσεγγισιμότητα.

Επιχειρησιακή Έρευνα

Τύπος
Επιλογής
Περιγραφή μαθήματος

Εισαγωγή στο Γραμμικό Προγραμματισμό. Μέθοδος Simplex – Δυϊκότητα. Εισαγωγή στον Ακέραιο Προγραμ- ματισμό, Μοντελοποιήσεις. Εισαγωγή στο μη-Γραμμικό Προγραμματισμό. Συνθήκες βελτιστοποίησης. Εφαρμο- γές: Προβλήματα βελτιστοποίησης σε δίκτυα, θεωρία ελέγχου αποθεμάτων