Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF6123  Gr. 01
Titre : Structures de données avancées
Session : Automne 2017  Horaire et local
Professeur : Czyzowicz, Jurek
1. Description du cours paraissant à l'annuaire :

Objectifs

Permettre à l'étudiant de se familiariser avec les structures de données avancées et leur application pour la construction d'algorithmes efficaces. Approfondir ses connaissances en algorithmique à travers des problèmes à solutions complexes.

Contenu

Éléments de la théorie des graphes. Graphes planaires, leurs propriétés et applications. Algorithmes avancés sur les graphes. Types des tas. Files de priorité. Algorithmes géométriques. Algorithmes distribués pour robots mobiles, planification de trajectoires. Exploration des graphes et des environnements géométriques.
2. Objectifs spécifiques du cours :
Initier l'étudiant aux structures de données avancées et leur application pour la construction des algorithmes efficaces. Approfondir ses connaissances en algorithmique à travers des problèmes à solutions originales.
3. Stratégies pédagogiques :
  • Cours magistraux
  • Recherche dirigée dans des sujets spécialisés
  • Écriture et présentation d'un rapport
4. Heures de disponibilité ou modalités pour rendez-vous :
À déterminer.
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1    Éléments de la théorie de graphes. Problèmes NP-complets pour graphes. 05 sept. 2017 
2    Graphes planaires et leurs propriétés. Coloration. 12 sept. 2017 
3    Algorithme de couplage maximal pour les graphes bipartis. 19 sept. 2017 
4    Approfondissement et applications de la rechercher en profondeur. 26 sept. 2017 
5    Files de priorités avancées. 03 oct. 2017 
6    Semaine d'études. 10 oct. 2017 
7    Examen intra 17 oct. 2017 
8    Les plus courts chemins. 24 oct. 2017 
9    Les plus courts chemins (suite). 31 oct. 2017 
10    Algorithmes du postier chinois. 07 nov. 2017 
11    Algorithmes distribués pour robots mobiles. Exploration. 14 nov. 2017 
12    Flot maximum. 21 nov. 2017 
13    Présentations d'étudiants. 28 nov. 2017 
14    Révision. 05 déc. 2017 
15    Examen final. 12 déc. 2017 
6. Évaluation du cours :
  • Présentations d'étudiants : 20 %
  • Examen intra : 35 %
  • Examen final : 45 %
7. Politiques départementales et institutionnelles :
8. Principales références :
  1. Cormen, T., Leiserson, C.E., Rivest, R.L. et Stein, C., «Introduction à l'algorithmique», 2e cycle, 2e édition, Dunod, 2002.
  2. Christophides, N., «Graph Theory. An Algorithmic Approach», Academic Press, 1975.
  3. Sedgewick, R., «Algorithms in C++, Parts 1-4 : Fundamentals Data Structure, Sorting, Searching», 3e édition, Addison-Wesley, 1998.
  4. Sedgewick, R., «Algorithms in C++, Part 5 : Graph Algorithms», 3e édition, Addison-Wesley, 1998.
  5. Gibbons A., «Algorithmic Graph Theory», Cambridge University Press, 1985.
  6. Even. S., «Graph Algorithms», Computer Science Press, 1979.
9. Page Web du cours :
https://moodle.uqo.ca