UE Advanced Algorithms

Code de l'ECUE : SMUFN317

Ce cours donne droit à 3.0 ECTS.

Structure

EUR DS4H

Domaine disciplinaire

Informatique

Lieu d'enseignement

Campus SophiaTech Les Lucioles

Niveau du cours

Master 1

Semestre

Semestre impair

Langue

Anglais , Français

PRESENTATION

Dans ce cours, nous mettrons en oeuvre des méthodes pour résoudre des problèmes difficiles pour la complexité des calculs (NP-difficiles) lorsqu'on a absolument besoin d'une réponse en un temps raisonnable. Pour cela, il faut nécessairement abandonner certaines exigences sur la réponse fournie par l'algorithme. Il existe cependant des techniques pour obtenir des réponses exploitables à ces problèmes difficiles, telles que les algorithmes probabilistes, les algorithmes d'approximation, le branching. Nous illustrerons ces techniques sur plusieurs grands problèmes d'optimisation combinatoires qui se rencontrent fréquemment en pratique dans des contextes variés: la coupe minimum, l'équilibrage de charges, le problème du sac a dos, le stable maximum dans les graphes, la sélection de k centres et d'autres encore. Dans votre vie professionnelle, vous aurez probablement à résoudre certains de ces problèmes dans la conception d'applications. Ce cours vous donnera à la fois une familiarité avec les problèmes les plus courants mais aussi des techniques que vous pourrez mettre en oeuvre pour résoudre d'autres problèmes d'optimisation que vous rencontrerez.

Responsable(s) du cours

Christophe Crespelle

Présentiel

12h de cours magistral
12h de travaux dirigés

PREREQUIS

Avant le début du cours, je dois ...

Faire le test de positionnement disponible sur l'espace Moodle.
Savoir calculer la complexité temporelle d'un algorithme.
Savoir utiliser les structures de données de base: tableaux, listes, arbres binaires, tas.
Connaître les algorithmes de base sur les graphes : parcours, plus courts chemins, etc.

OBJECTIFS

A la fin de ce cours, je devrais être capable de...

Formuler des problèmes d'optimisation combinatoire classiques et décrire des algorithmes pour les résoudre.
Modéliser un problème pratique par une question algorithmique.
Reconnaître des problèmes difficiles.
Utiliser un algorithme probabiliste pour résoudre un problème difficile.
Utiliser un algorithme d'approximation pour résoudre un problème difficile.

CONTENU

Algorithmes probabilistes

Aucune description
Algorithmes d'approximation

Aucune description
Schema polynomial d'approximation

Aucune description
Algorithmes de branching

Aucune description

Accéder au Syllabus complet (Authentification requise)

Important

Ce syllabus n’a aucune valeur contractuelle. Son contenu est susceptible d’évoluer en cours d’année : soyez attentifs aux dernières modifications.