Programme d’études 2017-2018 | English | ||
Graphes et optimisation combinatoire | |||
Unité d’enseignement du programme de Master en sciences informatiques à la Faculté des Sciences |
Code | Type | Responsable | Coordonnées du service | Enseignant(s) |
---|---|---|---|---|
US-M1-INFO60-016-M | 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 | 0 | 0 | 0 | 0 | 0 | 5 | 5 | 1er quadrimestre |
Code(s) d’AA | Activité(s) d’apprentissage (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Période d’enseignement | Pondération |
---|---|---|---|---|---|---|---|---|
I-MARO-011 | 100.00% |
Unité d'enseignement |
---|
Objectifs par rapport aux acquis d'apprentissage du programme
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
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
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
Commentaire sur les évaluations rattr. Q1 de l'UE
Sans objet
Types d'activités
AA | |
---|---|
I-MARO-011 |
Mode d'enseignement
AA | |
---|---|
I-MARO-011 |
Supports principaux
AA | |
---|---|
I-MARO-011 |
Supports principaux non reproductibles
AA | |
---|---|
I-MARO-011 |
Supports complémentaires
AA | |
---|---|
I-MARO-011 |
Supports complémentaires non reproductibles
AA | |
---|---|
I-MARO-011 |
Autres références conseillées
AA | |
---|---|
I-MARO-011 |
Reports des notes d'AA d'une année à l'autre
AA | |
---|---|
I-MARO-011 |