École normale supérieure Éducation en ligne gratuite

Algorithmes d'approximation, partie I

Description

Algorithmes d'approximation, partie I

Avec quelle efficacité pouvez-vous emballer des objets dans un nombre minimum de boîtes? Dans quelle mesure pouvez-vous regrouper les nœuds afin de séparer à moindre coût un réseau en composants autour de quelques centres? Ce sont des exemples de problèmes d'optimisation combinatoire NP-dur. Il est très probablement impossible de résoudre efficacement ces problèmes, notre objectif est donc de donner une solution approximative qui peut être calculée en temps polynomial et qui offre en même temps des garanties prouvables sur son coût par rapport à l'optimum.

Ce cours suppose la connaissance d'un cours d'algorithmes de premier cycle standard, et met particulièrement l'accent sur les algorithmes qui peuvent être conçus en utilisant la programmation linéaire, une technique préférée et incroyablement réussie dans ce domaine. En suivant ce cours, vous serez exposé à un éventail de problèmes aux fondements de l'informatique théorique et à de puissantes techniques de conception et d'analyse. À la fin, vous serez en mesure de reconnaître, face à un nouveau problème d'optimisation combinatoire, s'il est proche de l'un des quelques problèmes de base connus, et pourrez concevoir des relaxations de programmation linéaire et utiliser l'arrondi aléatoire pour tenter de résoudre votre propre problème. Le contenu du cours et en particulier les devoirs sont de nature théorique sans aucune affectation de programmation.

Ceci est le premier d'un cours en deux parties sur les algorithmes d'approximation.

Prix: inscrivez-vous gratuitement!

Langue : Anglais

Sous-titres: Anglais

Algorithmes d'approximation, partie I - École normale supérieure