Programme d’études 2023-2024 | English | ||
Graphes et optimisation combinatoire | |||
Unité d’enseignement du programme de Master : ingénieur civil en informatique et gestion (CHARLEROI) (Horaire décalé) à la Faculté Polytechnique |
Code | Type | Responsable | Coordonnées du service | Enseignant(s) |
---|---|---|---|---|
UI-M1-IRIGIG-101-C | UE Obligatoire | TUYTTENS Daniel | F151 - Mathématique et Recherche opérationnelle |
|
Langue d’enseignement | Langue d’évaluation | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Crédits | Pondération | Période d’enseignement |
---|---|---|---|---|---|---|---|---|---|
| Français | 36 | 4 | 0 | 0 | 0 | 4 | 4.00 | 2e quadrimestre |
Code(s) d’AA | Activité(s) d’apprentissage (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Période d’enseignement | Pondération |
---|---|---|---|---|---|---|---|---|
I-MARO-153 | Graphes et optimisation combinatoire | 36 | 4 | 0 | 0 | 0 | Q2 | 100.00% |
Unité d'enseignement |
---|
Objectifs par rapport aux acquis d'apprentissage du programme
Acquis d'apprentissage de l'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 : descriptif et cohérence pédagogique
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.
Un projet/challenge est organisé et il fait partie du contenu de l'AA.
Les modalités d'enseignement sont susceptibles d'être ajustées en fonction
du contexte d'enseignement imposé par les mesures sanitaires.
Compétences préalables
Programmation linéaire; dualité, notion d'algorithme
Types d'activités
AA | Types d'activités |
---|---|
I-MARO-153 |
|
Mode d'enseignement
AA | Mode d'enseignement |
---|---|
I-MARO-153 |
|
Supports principaux non reproductibles
AA | Supports principaux non reproductibles |
---|---|
I-MARO-153 | Sans objet |
Supports complémentaires non reproductibles
AA | Support complémentaires non reproductibles |
---|---|
I-MARO-153 | Sans objet |
Autres références conseillées
AA | Autres références conseillées |
---|---|
I-MARO-153 | P. 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
AA | Reports des notes d'AA d'une année à l'autre |
---|---|
I-MARO-153 | Autorisé |
Evaluation du quadrimestre 2 (Q2) - type
AA | Type(s) et mode(s) d'évaluation Q2 |
---|---|
I-MARO-153 |
|
Evaluation du quadrimestre 2 (Q2) - commentaire
AA | Commentaire sur l'évaluation Q2 |
---|---|
I-MARO-153 | Le rapport et la présentation du projet/challenge (partie de l'AA) intervient pour 20%.de la note. L'absence à la présentation du projet/challenge (et/ou non remise du rapport) implique une absence sur la totalité de l'UE. Examen écrit en présentiel 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 % Les modalités d'évaluation sont susceptibles d'être ajustées en fonction du contexte d'enseignement/évaluation imposé par les mesures sanitaires. |
Evaluation du quadrimestre 3 (Q3) - type
AA | Type(s) et mode(s) d'évaluation du Q3 |
---|---|
I-MARO-153 |
|
Evaluation du quadrimestre 3 (Q3) - commentaire
AA | Commentaire sur l'évaluation Q3 |
---|---|
I-MARO-153 | Le rapport et la présentation du projet/challenge (partie de l'AA) intervient pour 20%.de la note. L'absence à la présentation du projet/challenge (et/ou non remise du rapport) implique une absence sur la totalité de l'UE. Examen écrit en présentiel 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 % Les modalités d'évaluation sont susceptibles d'être ajustées en fonction du contexte d'enseignement/évaluation imposé par les mesures sanitaires. |