Programme d’études 2018-2019English
Graphes et optimisation combinatoire
Unité d’enseignement du programme de Master ingénieur civil en informatique et gestion (Charleroi (Hor. décalé)) à la Faculté Polytechnique
CodeTypeResponsable Coordonnées
du service
Enseignant(s)
UI-M1-IRIGIG-808-CUE ObligatoireTUYTTENS DanielF151 - Mathématique et Recherche opérationnelle
  • TUYTTENS Daniel

Langue
d’enseignement
Langue
d’évaluation
HT(*) HTPE(*) HTPS(*) HR(*) HD(*) CréditsPondération Période
d’enseignement
  • Français
Français36400044.002e quadrimestre

Code(s) d’AAActivité(s) d’apprentissage (AA) HT(*) HTPE(*) HTPS(*) HR(*) HD(*) Période
d’enseignement
Pondération
I-MARO-153Graphes et optimisation combinatoire364000Q2100.00%

Unité d'enseignement

Objectifs par rapport aux acquis d'apprentissage du programme

  • Imaginer, concevoir, réaliser et mettre en oeuvre des modèles conceptuels et des solutions informatiques pour répondre à des problèmes complexes notamment de décision, d'optimisation, de gestion et de production dans le cadre d'une démarche d'innovation en entreprise en intégrant l'évolution des besoins, contextes et enjeux (techniques, économiques, sociétaux, éthiques et environnementaux).
    • Concrétiser une solution choisie sous la forme de diagrammes, de graphes, de prototypes, de logiciels et/ou de modèles numériques.
    • Evaluer la démarche et les résultats en vue de leur adaptation (modularité, optimisation, qualité, robustesse, fiabilité, évolutivité,...).
  • Mobiliser un ensemble structuré de connaissances et compétences scientifiques et techniques spécialisées permettant de répondre, avec expertise et adaptabilité, aux missions de l'ingénieur civil en Informatique et Gestion
    • Maîtriser et mobiliser de façon pertinente des connaissances, des modèles, des méthodes et des techniques relatifs au domaine de l'Informatique et Gestion
    • Identifier et étudier les applications possibles des technologies nouvelles et émergentes dans le domaine des sciences et technologies de l'information et du management quantitatif et qualitatif de l'entreprise.
    • Evaluer la validité des modèles et des résultats compte tenu de l'état de la science et des caractéristiques du problème.
  • Communiquer et échanger des informations de manière structurée - oralement, graphiquement et par écrit, en français et dans une ou plusieurs autres langues - sur les plans scientifique, culturel, technique et interpersonnel en s'adaptant au but poursuivi et au public concerné.
    • Argumenter et convaincre, tant à l'oral qu'à l'écrit, vis-à-vis de clients, des enseignants et des jurys.
    • Utiliser et produire des documents scientifiques et techniques (modélisation mathématique, architecture des données et du logiciel, rapport, cahier des charges, analyse financière, documentation et manuels, ...) adaptés au but poursuivi et au public concerné.
  • Agir en professionnel responsable, faisant preuve d'ouverture et d'esprit critique, inscrit dans une démarche de développement professionnel autonome.
    • Exploiter les différents moyens mis à disposition pour se documenter et se former de manière autonome.

Acquis d'apprentissage UE

Faire comprendre et connaître les notions et problèmes fondamentaux de la théorie des graphes;Etudier les algorithmes correspondants; approfondir les notions d'algorithmique acquises par ailleurs en s'intéressant à l'efficacité des algorithmes (familiarisation avec les calculs de complexité algorithmique);Faire comprendre et connaîre les problèmes fondamentaux et les méthodes de base de l'optimisation combinatoire;Illustrer quelques méthodes sur quelques problèmes;Montrer l'utilité des notions et algorithmes pour la résolution de problèmes pratiques de gestion de production, logistique, etc.

Contenu de l'UE

Notions de base de la théorie des graphes et structures de données; étude de problèmes de la théorie des graphes: arbres, plus court chemin, connexité, flots;introduction à la complexité : classes P et NP; étude de problèmes classiquesde l'optimisation combinatoire : sac-à-dos, couverture, voyageur de commerce; introduction aux méta-heuristiques

Compétences préalables

Programmation linéaire; dualité, notion d'algorithme

Types d'évaluations Q2 pour l'UE

  • Examen écrit
  • Epreuves pratiques

Commentaire sur les évaluations Q2 de l'UE

Rapports de travaux pratiques: 20%.  Examen écrit sans notes portant sur les deux parties du cours.  Partie 1 : Théorie des graphes  (théorie et exercices)  40 %. Partie 2 : Optimisation combinatoire (théorie et exercices)  40 %  

Types d'évaluation Q3 pour l'UE

  • Examen écrit
  • Epreuves pratiques

Commentaire sur les évaluations Q3 de l'UE

Rapports de travaux pratiques: 20%.  Examen écrit sans notes portant sur les deux parties du cours.  Partie 1 : Théorie des graphes  (théorie et exercices)  40 %. Partie 2 : Optimisation combinatoire (théorie et exercices)  40 %  

Types d'activités

AATypes d'activités
I-MARO-153
  • Cours magistraux
  • Ateliers et projets encadrés au sein de l'établissement

Mode d'enseignement

AAMode d'enseignement
I-MARO-153
  • Face à face

Supports principaux

AASupports principaux
I-MARO-153Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
Copie de présentation - Partie 3 - Métaheuristiques - D. Tuyttens

Supports principaux non reproductibles

AASupports principaux non reproductibles
I-MARO-153Sans objet

Supports complémentaires

AASupports complémentaires
I-MARO-153

Supports complémentaires non reproductibles

AASupport complémentaires non reproductibles
I-MARO-153Sans objet

Autres références conseillées

AAAutres références conseillées
I-MARO-153P. Lacomme, C. Prins & M. Sevaux Algorithmes de graphes, Editions Eyrolles, 2003. J. Dréo, A. Pétrowski, P. Siarry & E. taillard Métaheuristiques pour l'optimisation difficile, Editions Eyrolles, 2003.

Reports des notes d'AA d'une année à l'autre

AAReports des notes d'AA d'une année à l'autre
I-MARO-153Autorisé
(*) HT : Heures théoriques - HTPE : Heures de travaux pratiques encadrés - HTPS : Heures de travaux pratiques supervisés - HD : Heures diverses - HR : Heures de remédiation - Dans la colonne Pér. (Période), A=Année, Q1=1er quadrimestre et Q2=2e quadrimestre
Date de génération : 02/05/2019
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111
Courriel: info.mons@umons.ac.be