Recherche opérationnelle (06POGROP)
- Coefficient : 1.5
- Volume Horaire: 33h estimées de travail (dont 21h EdT)
- CTD : 9h encadrées (et 1.5h de séances d'études dirigées)
- Labo : 9h encadrées (et 1.5h de séances d'études dirigées)
- Travail personnel hors EdT : 12h
Liste des AATs
Description
- Parcours de graphes
- parcours en profondeur
- parcours en largeur
- liens avec FIFO/LIFO
- Chemins dans les graphes
- avec les parcours
- algorithme de Roy-Warshall
- algorithme de Dijkstra
- Voyageur de commerce
- énoncé du problème, réductions
- résolution par ”brute force”
- notions de complexité algorithmique
- Optimisation
- notion d’heuristique
- algorithmes backtracking
- algorithmes branch and bound
Acquis d'Apprentissage visés (AAv)
AAv1 [heures: 15, B2,B3] : À l'issue de l'enseignement, chaque élève est capable de mettre en œuvre correctement les outils mathématiques pertinents pour résoudre des problèmes de calculs de chemins optimaux (profondeur, largeur, plus court via Ford ou Dijkstra) dans des graphes orientés ou non, valués ou non. Correctement signifie ici :
- L'élève est capable d'implémenter des algorithmes de parcours de graphe simples.
- L'élève peut reconnaître, éventuellement corriger, choisir et utiliser des algorithmes déjà fournis, pour résoudre un problème spécifique.
AAv2 [heures: 15, B2,B3] : À l'issue de l'enseignement, chaque élève est capable de mettre en oeuvre correctement les outils mathématiques pertinents pour résoudre des problèmes de maximisation de flot dans un réseau de transport, en tenant compte d'un éventuel coût. Correctement signifie ici :
- L'élève sait reconnaître, éventuellement corriger, choisir et utiliser des algorithmes déjà fournis, pour résoudre un problème spécifique de maximisation de flot (éventuellement à coût minimal)..
- L'élève sait représenter graphiquement le problème pour expliquer et justifier la méthode proposée.
Modalités d'évaluation
moyenne de plusieurs évaluations courtes de contrôle continu de CTD (coefficient 1) et de Labo (coefficient 1)
Mots clés
Recherche opérationnelle, optimisation, voyageur de commerce, parcours d’arbre, parcours de graphe, parcours en largeur, parcours en profondeur, algorithme de Dijkstra, algorithme de Roy-Warshall, backtracking, branch and bound.
Pré-requis
Il est pré-requis une connaissance dans un ou des langages de programmation ainsi qu’une compréhension minimale d’outils basiques tels que les tableaux, les listes, les fonctions récursives...
Ressources
Le cours s’appuie sur une forte interaction avec un projet de travaux pratiques. Tous les outils utilisés sont gratuits et open-source.