Présentation

partie optimisation (10h CM, 12h TD, 10h TP)  :

Ce cours présente des approches par programmation linéaire, séparation & évaluation, programmation dynamique et heuristiques pour la résolution de problèmes d’optimisation combinatoire. Une introduction à la complexité et à la résolution de problèmes de satisfiabilité booléenne est également présentée.

Le cours aborde les points suivants :

• complexité algorithmique et théorie de la complexité
• modélisation et heuristique de résolution de problème de satisfiabilité booléenne (SAT)
• programmation linéaire : méthode du simplexe, modélisation MILP de problèmes d’optimisation 
• méthodes par séparation et évaluation, application à la programmation linéaire, problème de voyageur de commerce
• programmation dynamique : principe et applications (plus court chemin, gestion de stock)
• Approches diviser pour régner (et calcul parallèle)
• méthodes heuristiques approchées : introduction aux meta heuristiques, heuristiques gloutonnes. Applications d’heuristiques gloutonnes (sac à dos, couverture, voyageur de commerce)
• méthodologie de comparaison d’algorithmes

La mise en pratique se fait avec le logiciel CPLEX :

• utilisation directe
• langage de programmation OPL et modélisation
• génération de cas et automatisation de séries de test

partie Modélisation et programmation des réseaux sans fil (6h CM, 4h TD, 6h TP) :

Ce cours permet de présenter les notions de base de la modélisation et la programmation distribuée appliquée aux graphes et aux réseaux sans fil. Les simulations sont réalisées sur l'outil CupCarbon en utilisant le script SenScript. 

Le cours présente : 

1. Introduction au concept de la programmation distribuée et la présentation des algorithmes de base tels que le Local Minimum Finding (LMF) et le Global Minimum Findin (MinFinding) et les algorithmes de BFS/DFS distribués ainsi que le FLF (Flooding for Leaf Finding), pour trouver les feuilles d’un arbre couvrant.
   Ce cours permet aussi de faire la distinction entre la programmation classique, la programmation parallèle et la programmation distribuée.
2. Présentation de la plateforme CupCarbon et du script SenScripr pour la programmation des noeuds distribués ou capteurs
3. Présentation de plusieurs variantes de l’algorithme de l’élection du leader dans un graphe euclidien connecté ou dans un réseau sans fil : LOGO, BrOGO, DoTRO et WBS
4. Présentation des Pseudo-Polygones
5. Présentation d’algorithmes distribués pour trouver les noeuds bordures internes et externes d’un graphe euclidien connecté. Ce cours introduit en premier les algorithmes classiques pour trouver l’enveloppe convexe dans un graphe non connecté (Algorithme de Jarvis) et l’enveloppe polygonale dans un graphe connecté (LPCN). Ensuite, il présente 2 versions distribuées du LPCN : D-LPCN et D-RRLPCN