Génie Mathématique & Modélisation

Recherche opérationnelle et Algorithmique
Génie Mathématique & ModélisationAnnée 1, Semestre S6
Cycle ingénieur		6 crédits ECTS1GMS6ROA
Objectifs
  • Processus complet de résolution de problèmes simples du « monde réel », depuis la modélisation jusqu'à l'implémentation sur machine, en passant par les techniques de l'optimisation linéaire et de l'algorithmique appuyées sur les structures de données de base.
Liste des ECAlgorithmique
Recherche opérationnelle
Horaire encadré96 h
Travail personnel46 h
Évaluation50% Algorithmique
50% Recherche opérationnelle
Pré-requisAlgorithmique du tronc commun.
Bases d'algèbre linéaire et de calcul matriciel.
ResponsableGaelle LOOSLI
17/06/2009
Génie Mathématique & ModélisationAlgorithmique
Objectifs
  • Utilisation des structures de données appropriées pour l'élaboration d'algorithme efficace en terme de complexité ; validation des algorithmes.
Compétences
  • Analyse de complexité. Structures de donnée. Validation des algorithmes.
Description
  • Complexité des algorithmes (itératifs et récursifs)
  • Analyse amortie (fonctions potentielles)
  • Structures de donnée (de base, tas, arbre de recherche)
  • Parcours de graphes (connexité, tri topologique)
  • Algorithme de Prim, de Dijkstra, de Bellman-Ford, de Ford-Fulkerson
Horaire encadré50h (20h CM + 20h TD + 10h TP)
Évaluation33% Contrôle continu, Travail pratique
67% Examen final, Écrit
Bibliographie

Introduction to algorithms, 2 nd edition, Cormen TH, Leiserson CE, Rivest RL, Stein Clifford, McGraw-Hill Book Company (2001)

EnseignantsGaelle LOOSLI
17/06/2009
Génie Mathématique & ModélisationRecherche opérationnelle
Objectifs
  • Modélisation et résolution des problèmes issus du « monde réel »
  • admettant une formulation par la programmation linéaire ; utilisation de cet outil pour la démonstration et la compréhension de résultats théoriques.
Compétences
  • Programmation linéaire, théorie des graphes, théories des jeux.
Description
  • Modélisation en
  • programmation linéaire
    • Algorithme du simplexe
    • Dualité linéaire
    • Application en théorie des jeux à deux joueurs et à somme nulle.
    • Méthode réseau du simplexe
    • Preuves simples par la programmation linéaire du théorème de König, du théorème de Birckhoff-von Neumann, du théorème de König-Egervary et du théorème de Hall.
Horaire encadré46h (18h CM + 18h TD + 10h TP)
Évaluation33% Contrôle continu, Travail pratique
67% Examen final, Écrit
Bibliographie

Linear programming, Chvatal V, Freeman, 1983

Graphes et programmation linéaire, Sakarovitch M, Hermann, Paris, 1984

Support
  • Logiciel CPLEX LP, ILOG CPLEX
EnseignantsGaelle LOOSLI
17/06/2009