-
Partager cette page
INFO-F413
Randomized algorithms
Titulaire(s) du cours
Jean CARDINAL (Coordonnateur)Crédits ECTS
5
Langue(s) d'enseignement
anglais
Contenu du cours
The course focuses on Randomized Algorithms:
- Las Vegas and Monte-Carlo algorithms, examples : Minimum cut, binary space partitions
- Randomized complexity classes
- Game-theoretic techniques and Yao's Min-max principle
- Moments and deviations : Randomized selection, coupon collector
- Chernoff bounds
- Randomized data structures and hashing
Objectifs (et/ou acquis d'apprentissages spécifiques)
An understanding of the theoretical foundations of randomness and probabilities in the design of efficient algorithms, and a hands-on experience on the programming of randomized algorithms.
Pré-requis et Co-requis
Connaissances et compétences pré-requises ou co-requises
A good background in elementary probability theory and algorithm design.
Méthodes d'enseignement et activités d'apprentissages
Lectures, exercises, and individual programming assignments.
Références, bibliographie et lectures recommandées
Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995.
Support(s) de cours
- Université virtuelle
Autres renseignements
Contacts
Jean Cardinal email : jcardin@ulb.ac.be téléphone : (02 650) 56 08
Campus
Plaine
Evaluation
Méthode(s) d'évaluation
- Autre
Autre
Langue(s) d'évaluation
- anglais