formations:masters:cours:resume_algorithmique_avancee_et_complexite [UFR Informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== Algorithmique avancée et complexité ======

==== Compétences visées : ====

Le cours vise à familiariser les étudiants aux techniques et méthodes avancées pour la conception et l'analyse des algorithmes selon plusieurs modèles et mesures de complexités (algorithmes randomizés, d'approximation, on-line, modèle parallèle, modèle distribué, ...).

==== Contenu : ====

Le cours commence par une introduction aux algorithmes randomizés. Cette partie présente différentes notions de convergence (Monte-Carlo, Las Vegas, "avec très forte probabilité", ...) pour les algorithmes. Le cours revient ensuite sur divers problèmes algorithmiques pour envisager plusieurs approches possibles comme l'analyse en moyenne,  les solutions approchées et les algorithmes d'approximation pour l'optimisation ou encore les mesures de compétitivité pour les algorithmes on-line.
Ces notions seront ensuite étendues dans le contexte distribué et parallèle. Le cours se termine par une introduction à la génération aléatoire uniforme de structures discrètes dans l'objectif de pouvoir alimenter à l'envie les entrées (ou des aléas vont intervenir) pour certains algorithmes. Chaque partie de ce cours est enrichie d'exercices liés aux notions que les étudiants devront assimiler.

Outils pour utilisateurs

Outils du site

Outils de la page