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 2018  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.

 04 sept. 2018 
2   

Graphes planaires et leurs propriétés. Coloration.

 11 sept. 2018 
3   

Approfondissement et applications de la recherche en profondeur.

 18 sept. 2018 
4   

Algorithme de couplage maximal pour les graphes bipartis.

 25 sept. 2018 
5   

Algorithmes du postier chinois.

 02 oct. 2018 
6   

Semaine d'études

 09 oct. 2018 
7   

Files de priorités avancées.

 16 oct. 2018 
8   

Examen intra

 23 oct. 2018 
9   

Les plus courts chemins.

 30 oct. 2018 
10   

Les plus courts chemins (suite).

 06 nov. 2018 
11   

Algorithmes distribués pour robots mobiles. Exploration.

 13 nov. 2018 
12   

Flot maximum.

 20 nov. 2018 
13   

Présentations d'étudiants.

 27 nov. 2018 
14   

Révision.

 04 déc. 2018 
15   

Examen final

 11 déc. 2018 
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