Ce cours de programmation linéaire est un cours participatif, ouvert et partagé.
L'objectif de ce cours est de présenter la programmation linéaire. Des activités permettent de s'entraîner à la modélisation
de problèmes pratiques en programmation linéaire. Différents tests permettent de comprendre comment résoudre un programme linéaire, en présentant les éléments de l'algorithme du Simplex. Ensuite, la section sur la dualité permet de comprendre en profondeur
une solution d'un programme linéaire et de son dual. La section analyse de sensibilité explique comment la solution optimale est modifiée lorsque l'on change les paramètres du programme linéaire.
Ce cours de programmation dynamique pour la RO est un cours participatif, ouvert et partagé.
- Décrire le Modèle de chemin
- Ecrire la formule de récurrence
- Proposer un algorithme de résolution (itératif)
- Reconstruire la solution optimale obtenue par backtrack
- Programmer l'algorithme et le backtrack
- Connaitre les principaux modèles de résolution pour les problèmes classiques : plus court chemin, Sac-à-dos et extension...
- Connaitre les grands problèmes de RO qui se résolvent avec de la DP : maintenance, ordonnancement sur machine parallèle, gestion de couts fixes...
-
un cours rédigé qui s'appuie sur des vidéo youtube courtes;
-
des exercices avec corrections détaillées;
-
des activités de programmation auto-évaluées (l'étudiant peut lancer les tests prédéfinis) avec estimation expérimentale de la complexité de la fonction proposée par l'étudiant. Cette fonctionnalité permet de différentier non seulement un algorithme pseudo polynomial d'une énumération complète mais aussi d'identifier des heuristiques, par exemple à base de boucles for imbriquées qui permettent juste de passer les tests sans résoudre le problème en général.
-
Modèle de chemin et application au problème du sac-à-dos
-
Exercices résolus de DP en RO
-
Autour du sac-à-dos : sac-à-dos entier, subset sum, rendu de monnaie, équilibrage de charge
-
ordonnancement d'intervalles
-
Maintenance
-
Investissement
-
Exercices résolus de DP en Informatique pour acquérir de l'aisance de modélisation
-
multiplication de matrices
-
Alignement de séquences
-
Activités du programmation
-
Autour du sac-à-dos
-
Découpe
-
Keeping water
-
Hotels
-
Production systems
- Jeu
- Auteur : Nadia Brauner, Université Grenoble-Alpes
- Public : étudiants à partir du niveau L3 Math ou Info
- Prérequis : Algorithmique de base, Théorie des graphes
- Type de contenu : Banque de question
- Objectif : Modélisation, résolution de problème de graphe, gamification
Vous allez pénétrer en Graphistan. Vos connaissances en graphe, en modélisation, en optimisation seront mises à rude épreuve. Sauron, Voldemort et Palpatine guettent le moindre faux pas. Qu’Euler soit avec vous !
Ce cours propose des énigmes liées au graphes. La résolution d’une énigme ouvre des portes vers de nouvelles énigmes. Dans une ambiance moyenâgeuse, vous rencontrerez des chevaliers, des sorciers, des Gobelins, des Simurgh… Le jeu a été illustré par des étudiants et certains d’entre eux ont même créé les énigmes pour votre plaisir. Arriverez-vous à visiter le Graphistan et à en sortir un peu mieux armé sur les graphes ?