Université Lille1

| Licences | Licence Info | Master Informatique | Master Miage | Alternance | Masters |
: L2S3 : L2S3H : L2S4 : L3S5 Info : L3S5 Miage : L3S6 Info : L3S6 Miage :
: Algo : BD : COMEIT : COMPIL : COO : DPP : PDC :
Vous êtes ici : FIL > Portail > Licence Info > L3S5 Info > Algo

ALGO

Responsable

François Lemaire. Bâtiment M3. Bureau 330bis.
Site web : http://www.lifl.fr/~lemaire
Courrier électronique : Francois.Lemaire à lifl.fr

Volume horaire

Sur 12 semaines :
  • une heure trente de cours magistral (support de cours en ligne)
  • une heure trente de TD en salle banalisée (feuilles de TD en ligne).
  • une heure trente de TP en salles équipées d'ordinateurs (Linux, AMPL, ...)

Crédits

5 ECTS

Modifié le Thu 24 November 2011, à 03:48:39 PM

Objectifs

Savoir que certains problèmes algorithmiques sont des problèmes d'optimisation et peuvent se formaliser et se résoudre comme tels. Savoir modéliser certains problèmes posés en Français sous la forme de programmes linéaires ou sous la forme de problèmes de théorie des graphes (chemins de valeur minimale, flot maximal, flot maximal à coût minimal, arbre couvrant minimal). Savoir utiliser un logiciel de résolution de programmes linéaires. Logiciel AMPL. Connaître quelques algorithmes importants de résolution de programmes linéaires (simplexe) et de la théorie des graphes (Bellman, Dijkstra, Ford-Fulkerson, Kruskal).

Contenu

  • Rappels d'algèbre linéaire. Pivot de Gauss.
  • Programmation linéaire. Modélisation en AMPL.
  • Le simplexe. Version graphique. L'algorithme du tableau simplicial. Problèmes de démarrage. La dualité.
  • Théorie des graphes. Algorithmes de parcours. Arbres couvrants. Plus court chemin (Bellman, Dijkstra).
  • Applications de la théorie des graphes. Méthode MPM. Flot maximal (Ford-Fulkerson). Arbres couvrants optimaux (Kruskal).

Bibliographie

  • Le polycopié donné dans l'onglet « documents » suffit.
  • Introduction à l'algorithmique. 2ème édition. Dunod. Cormen, Leiserson, Rivest et Stein. Un livre de référence pour tout informaticien.
  • Précis de recherche opérationnelle. 5ème édition. Dunod. Faure, Lemaire et Picouleau. Un livre davantage tourné vers les exemples et moins vers l'algorithmique que le précédent.
  • AMPL A modelling language for mathematical programming. International Thomson Publishing. Fourer, Gay and Kernighan. Le manuel de référence du logiciel AMPL, avec de nombreux exemples. En Anglais.
  • Model building in mathematical programming. 3rd edition. John Wiley and Sons Ltd. Williams. Un livre dédié principalement à la modélisation par programmes linéaires, riche d'une douzaine de problèmes. En Anglais.

Modifié le Thu 24 November 2011, à 03:48:39 PM

Gpe Nature Horaire Salle Enseignant e-mail
Cours Vendredi 13h30-15h SUP 14 François Lemaire
1 TD Vendredi 10h15-11h45 M5 A5 Léopold Weinberg Leopold.Weinberg@lifl.fr
TP Mardi 15h15-16h45 M5 A12 Léopold Weinberg
2 TD Mercredi 15h30-17h M5 A9 Arnaud Liefooghe Arnaud.Liefooghe@lifl.fr
TP Mardi 10h15-11h45 M5 A13 Arnaud Liefooghe
3 TD Mercredi 10h15-11h45 M5 A9 François Lemaire Francois.Lemaire@lifl.fr
TP Jeudi 13h30-15h M5 A12 François Lemaire
4 TD Jeudi 13h30-15h M5 A3 Benoît Groz benoit.groz@inria.fr
TP Mardi 8h30-10h M5 A12 Benoît Groz

Modifié le Thu 24 November 2011, à 03:48:39 PM

Séance COURS TD TP Remarque
1 36 du 05/09 au 10/09 Introduction à la modélisation et à AMPL.

Résolution graphique de programmes linéaires. Vocabulaire. Définitions. 		Pas de TD Pas de TP Horaire spécial.
Le physicien britannique Patrick Blackett est considéré comme un des fondateurs de la recherche opérationnelle. Un article sur le personnage.
2 37 du 12/09 au 17/09 L'algorithme du tableau simplicial dans un cas favorable. Définitions préliminaires et énoncé de l'algorithme. Résolution graphique. Modélisation en AMPL d'une campagne de publicité. TD 2 TP 1. Prise en main d'AMPL :
  • tester les variantes des modèles d'acierie (jusqu'à la gestion du stock)
  • utiliser les commandes model et reset
  • réfléchir à l'exercice 3 de la feuille de TD2
3 38 du 19/09 au 24/09 Justification de l'algorithme dans un cas favorable. Terminaison et complexité. Introduction aux problèmes de démarrage : la méthode des deux phases. L'algorithme du tableau simplicial. Quelques exos de modélisation. TD 3 Modélisation en AMPL d'une campagne de publicité.
4 39 du 26/09 au 01/10 Présentation du DM repartition_marche.pdfet son fichier de données repartition_marche.data

Un problème d'emploi du temps résolu en AMPL emploitemps.pdf

Introduction à la dualité.

Suite de la feuille 3. Exécution manuelle de l'algorithme du tableau simplicial dans le cas favorable et exercices de modélisation Modélisation en AMPL du problème de production de papier. Gestion de stocks.
5 40 du 03/10 au 08/10 La dualité en programmation linéaire. Les problèmes de démarrage. TD 4 Fin de la modélisation en AMPL du problème de production de papier avec gestion de stocks.
6 41 du 10/10 au 15/10 Fin de la dualité. Introduction à la théorie des graphes. La dualité. TD 5. Travail sur le DM (séance 1/2).
7 42 du 17/10 au 22/10 Parcours en largeur (+ court chemin). Fin du TD5 sur la dualité. Travail sur le DM (séance 2/2).
8 43-44 du 24/10 au 5/11 Parcours en profondeur (tri topologique). Chemins de valeur minimale entre un sommet distingué et tous les sommets : algorithmes de Bellman et de Dijkstra. Problèmes introductifs de théorie des graphes. TD 6 TP d'introduction sur les graphes. TP graphe 1 interruption pédagogique du 26 octobre soir au 3 novembre matin
9 45 du 07/11 au 12/11 Pas de cours (jour férié) Rappels de notions de complexité. TD 7 TP de parcours de graphes. TP graphe 2 vendredi 11 novembre férié
10 46 du 14/11 au 19/11 Algorithmes de Bellman et Dijkstra. Calculs de chemins minimaux en AMPL. Méthode MPM. Parcours et tri topologique. TD 8 Chemins de plus courte distance. TP graphe 3

Rendu du DM à votre enseignant de TD lors du TD
11 47 du 21/11 au 26/11 Flots maximaux. Algorithmes de Bellman et Dijkstra. TD 9 Parcours en profondeur et labyrinthe. TP graphe 4Fichiers de labyrinthe : labyrinthe1.grp, labyrinthe2.grp.
12 48 du 28/11 au 03/12 Arbres, arbres couvrants, algorithme de Kruskal. Flots maximaux. TD 10 Fin des TPs précédents. Algorithme de Dijkstra pour ceux qui n'ont pas pris de retard.
13 49 du 05/12 au 10/12 Pas de Cours Arbres couvrants de valeur minimale TD 11

Contrôle-TP

14 50 du 12/12 au 17/12 Pas de cours Pas de TD Pas de TP Semaine de DS.

Modifié le Thu 24 November 2011, à 03:48:39 PM

L'évaluation s'effectue suivant une procédure de contrôle continu, et un examen en fin de semestre.

Trois notes seront attribuées à chaque étudiant durant le semestre :

  • NOTE : une note sur 20 de Travaux Dirigés obtenue en additionnant les 4 meilleures de 5/6 mini interros notées sur 5 en TD
  • TP : calculée sur un mini-projet d'AMPL (à rendre à mi semestre) et un contrôle TP en fin de semestre
  • DS : une note sur 20 pour l'examen de fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne pondérée de ces trois notes, avec un SUP :

N = (TP + sup(NOTE + 2*DS, 3*DS)) /4

Pour la seconde session d'examen, la notes de TP est conservée. Le calcul se fait par

N=(TP + 3*DS)/4

L'unité acquise apporte 5 ECTS.

Modifié le Thu 24 November 2011, à 03:48:39 PM

Espace étudiants

L'URL du logiciel AMPL. Installation de la version étudiant du logiciel sur une machine Unix ou Linux (l'installation sous Windows est possible aussi) :
  1. Télécharger le fichier « ampl.gz ». Le décompresser par « gunzip ampl.gz ». Le rendre exécutable par « chmod a+x ampl ».
  2. Télécharger le fichier « cplex.tgz ». Le décompresser par « gunzip cplex.tgz ». Extraire le contenu de l'archive décompressée par « tar xf cplex.tar ».
  3. Télécharger le fichier « minos.gz ». Le décompresser par « gunzip minos.gz ». Le rendre exécutable par « chmod a+x minos ».
  4. S'assurer que le répertoire dans lequel se trouvent les trois exécutables « ampl », « minos » et « cplex » est bien listé dans la variable d'environnement « PATH ».
Le support de cours au format PDF.

La bibiothèque en C pour les TP sur les graphes est ici.

Documentation pour installer le mode AMPL pour emacs : ici

Modifié le Thu 24 November 2011, à 03:48:39 PM