Algorithmique avancée (AA)

Description

Cette UE fait partie du M1 informatique mais peut être suivie en M2, dans le cas où l'étudiant-e ne l'aurait pas suivi en M1. Elle est indépendante de tout langage de programmation, mais vise à étudier les fondements avancés de l’algorithmique classique.

Mots-clés

Linear programming, NP-completeness, Backtracking

Contenu

La première partie est centrée sur la programmation mathématique, considérée comme le cœur de l'optimisation combinatoire et de la recherche opérationnelle. Les méthodes présentées ici sont basées sur la théorie de la programmation linéaire et de la dualité dans la programmation linéaire, ainsi que sur les techniques de résolution de programmes linéaires mixtes en nombre entiers (PLME) "Integer Programming". Ces méthodes, très développées aujourd’hui, permettent de concevoir des algorithmes efficaces (polynomiaux) pour la résolution des grands classiques du domaine tels que le problème du flot maximum, le problème de transport/affectation etc. Une analyse approfondie de la complexité de chacun des algorithmes est donnée. Un accent particulier est réservé aux techniques de modélisation avec une prise en compte de conditions logiques. Certains des problèmes considérés/étudiés seront résolues avec l'aide des solveurs les plus performants comme CPLEX, GUROBI, KNITRO.
La seconde partie présente les techniques de backtracking et de branch-and-bound comme première solution pour résoudre des problèmes NP-complets. Nous considérons les problèmes d'optimisation dits "NP-complets" tels que la répartition de charges de processeurs, la selection de centres, le problème du sac à dos, la couverture de sommets de poids minimal. Nous étudions ensuite la possibilité de déployer des algorithmes d'approximation, qui par nature s'exécutent en temps polynomial. Pour certains problèmes nous démontrons qu'il n'en existe pas, et pour d'autres nous établissons leurs ratios avec précision. Il est même parfois possible de concevoir des algorithmes dont l'approximation est aussi précise que l'on souhaite - on parle alors de "Polynomial Time Approximation Scheme". Enfin, toujours pour les problèmes d'optimisation, nous explorons, à titre culturel, la famille des algorithmes de recherche locale (local search), dont le "recuit simulé".

Compétences acquises

Enseignants

Sophie Pinchinat (responsable), Rumen Andonov