CONSERVATOIRE NATIONAL DES ARTS ET METIERS
PICARDIE

RCP104 - Optimisation en informatique  [ 6 crédits ]

Public Concerné
Elèves ingénieur, élèves en DEST, étudiants de master M1.
Pré requis : avoir des connaissances de base en algorithmique, réseaux informatiques, graphes et recherche opérationnelle.

Finalité de l'unité d'enseignement
Objectifs pédagogiques
A partir de problèmes concrets de l'informatique distribuée (Réseaux, Bases de données réparties, .. ), apprendre à traiter des problèmes difficiles de la recherche opérationnelle: savoir écrire un modèle mathématique et proposer des méthodes, non nécessairement optimales, mais efficaces, utilisant des outils pratiques pour résoudre ces problèmes (méthodes approchées, programmation linéaire et logiciels.).
Capacité et compétences acquises
L'étudiant ayant suivi cet enseignement sait reconnaître et modéliser un problème de recherche opérationnelle. Il sait le résoudre avec des outils simples. Il sait en particulier aborder certains problèmes d'optimisation combinatoire dans les réseaux informatiques.

Organisation
6 Crédits 

Contenu de la formation
1-Présentation de l'ensemble du cours à partir d'un problème d'optimisation en informatique distribuée ou en réseaux informatiques. Le problème est-il difficile (complexité)' Si oui, comment créer un modèle mathématique' Ce modèle permet-il d'obtenir une solution optimale à l'aide d'un logiciel' Si oui, l'étude est terminée. Sinon, comment obtenir une solution approchée et comment valider la solution trouvée'
2-Apprendre à écrire un programme mathématique: choisir les variables, déterminer leurs domaines, écrire l'objectif et les contraintes. Travail sur des "cas d'école": partition de graphes, coloration,..
Application à divers problèmes réels: dimensionnement de réseaux, localisation de concentrateurs dans les réseaux en étoile, placement de copies de fichiers, formation de grappes dans les réseaux SDH,...
3-Apprendre à transformer un programme non linéaire en un programme linéaire de façon à pouvoir utiliser les logiciels. Techniques de linéarisation, prise en compte de rapport ou de produit de variables,..
4-Résolution approchée de problèmes difficiles par des méthodes générales (Recuit simulé, Tabou, Algorithmes génétiques, ...) ou par des méthodes spécifiques. Validation des résultats obtenus par les heuristiques à l'aide de bornes obtenues par utilisation du logiciel.
5-Utilisation d'un logiciel (Cplex, XPRESS, PCX...) et des interfaces. (Travail sur ordinateur pendant les heures de cours). Rappel des principes de la programmation linéaire.
6-Étude d'un cas réel: réalisation d'un projet informatique.