Informatique 3


Pré-requis :

Informatique 1, Informatique 2

 

Objectifs: 

–        Modéliser un problème en termes de graphes.

–        Comprendre pourquoi la modélisation aide à trouver une solution générale et non se concentrer sur les détails.

–        Développer une compréhension des points communs dans les problèmes et comment la théorie graphique aide à se concentrer sur les aspects essentiels de problèmes.

–        Modéliser et résoudre un problème sous forme d’un programme linéaire.

 

Contenu de l’enseignement :  

       

Chap. 1 : Introduction à la théorie des graphes. (Cours : 13h30, TD : 13h30)

1.      Le concept de graphes.

2.      Algorithmes de base en théorie des graphes :

–        le plus court chemin

–        les flots

3.      Les notions de base des arbres.

Chap. 2 : Introduction à la programmation linéaire. (Cours : 09h00, TD : 09h00)

1.      Le concept de programmation linéaire (variables, contraintes et fonction objectif)

2.      Résolution graphique des problèmes de programmation linéaire à deux variables.

3.      Résolution des problèmes linéaires par la méthode du simplexe.

4.      Dualité : définitions et notions de base.

 

Travaux Pratiques :

–          Néant

 

Références bibliographiques :

–        Gondran, M., Minoux, M., and Vajda, S. (1984). Graphs and Algorithms. John Wiley & Sons, Inc., New York, NY, USA.

–        Prins, C. (1994). Algorithmes de graphes avec programmes en PASCAL. Eyrolles.

–        Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network

–        Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle

–        River, NJ, USA.

–        Winston, W. L. (2003). Introduction to Mathematical Programming: Applications and Algorithms. Duxbury Resource Center.

–        Winston, W. L. (2004). Operations Research. Applications and Algorithms. Brooks/Cole, 4th edition.

–        Charon, I., Germa, A., and Hudry, O. (1996). Méthodes d’optimisation combinatoire. Collection pédagogique de télécommunication. Masson.

 

Modalités d’évaluation :

Interrogation, Devoir surveillé, Travaux pratiques, Examen final