Programme d’études 2019-2020English
Graphes et optimisation combinatoire
Unité d’enseignement du programme de Master en sciences informatiques à la Faculté des Sciences
CodeTypeResponsable Coordonnées
du service
Enseignant(s)
US-MC-SCINFO-044-MUE 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çais361200055.001er quadrimestre

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

Unité d'enseignement

Objectifs par rapport aux acquis d'apprentissage du programme

  • Gérer des projets de développement informatique d'envergure
    • -Etre capable d'appliquer, de mobiliser, d'articuler et de valoriser les connaissances et les compétences acquises en vue de contribuer à la conduite et à la réalisation d'un projet
  • Gérer des travaux de recherche, de développement ou d'innovation
    • -Etre capable d'appréhender une problématique inédite relevant des sciences informatiques et de ses applications
    • -Rechercher de façon méthodique des informations scientifiquement valides, mener une analyse critique, proposer et argumenter des solutions éventuellement innovantes à des problématiques ciblées
  • Maîtriser les techniques de communication
    • -Pouvoir communiquer de façon claire, structurée et argumentée, tant à l'oral qu'à l'écrit, ses conclusions, ses propositions originales ainsi que les connaissances et principes sous-jacents
  • Développer et intégrer un fort degré d'autonomie
    • -Etre capable d'acquérir seul de nouveaux savoirs

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 Q1 pour l'UE

  • Présentation et/ou travaux
  • Examen écrit

Commentaire sur les évaluations Q1 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

  • Présentation et/ou travaux
  • Examen écrit

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'évaluation rattrapage BAB1 (Q1) pour l'UE

  • Néant

Commentaire sur les évaluations rattr. Q1 de l'UE

Sans objet

Types d'activités

AATypes d'activités
I-MARO-011
  • Cours magistraux
  • Travaux pratiques

Mode d'enseignement

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

Supports principaux

AASupports principaux
I-MARO-011

Supports principaux non reproductibles

AASupports principaux non reproductibles
I-MARO-011Sans objet

Supports complémentaires

AASupports complémentaires
I-MARO-011Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
,Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
,Copie de présentation - Partie 3 - Métaheuristiques - M. Mezmaz

Supports complémentaires non reproductibles

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

Autres références conseillées

AAAutres références conseillées
I-MARO-011P. 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-011Autorisé
(*) 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 : 14/09/2019
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111
Courriel: info.mons@umons.ac.be