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

Objectifs

Au terme de cette activité, l'étudiant(e) sera en mesure : d'appliquer les principes de l'algorithmique et de la programmation structurée pour l'utilisation et l'implémentation de structures de données.

Contenu

Représentation en mémoire de structures de base. Pointeurs et allocation dynamique. Complexité des algorithmes. Structures de données abstraites : piles, files, listes, arbres et graphes. Techniques de tri et de recherche. Algorithmes de base sur les graphes.
2. Objectifs spécifiques du cours :
  • Présenter à l`étudiant les algorithmes fondamentaux en informatique.
  • Introduire l`étudiant aux structures de données, à leurs utilisations et à leurs implémentations.
  • Approfondir les principes d`algorithmique et de la programmation structurée.
  • Sensibiliser l`étudiant à l`importance de l`efficacité d`algorithmes et l`introduire à l`approche formel de l`évaluation de cette efficacité.
3. Stratégies pédagogiques :
  • Cours magistraux.
  • Travaux de programmation.
  • Exercises théoriques et pratiques durant les séances de laboratoires.
4. Heures de disponibilité ou modalités pour rendez-vous :
 
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1    Introduction aux algorithmes et données. Classifications des données. Complexité des algorithmes.

Les pointeurs : 15 septembre 2005 (pour les étudiants de génie seulement)

 12 sept. 2005 
2    Représentation des données en mémoire machine. Temps de compilation et temps d`exécution. Évolution d`un programme avec fonctions en temps d`exécution.

Listes chaînées : 22 septembre 2005 (pour les étudiants de génie seulement)

 19 sept. 2005 
3    Introduction à la récursivité. Fonctions récursives. Passage de contrôle dans le cas de fonctions récursives. Les arbres d`appels récursifs. 26 sept. 2005 
4    Introduction aux types abstraits. Algorithmes de tri et de recherche. 03 oct. 2005 
5    Semaine d'études. 10 oct. 2005 
6    Examen de mi-session. 17 oct. 2005 
7    Adresses comme données. Opérations sur les pointeurs. 24 oct. 2005 
8    Pointeurs (suite). Listes chaînées. 31 oct. 2005 
9    Files; opérations, réalisations machine. Piles; opérations, réalisations machine. Applications. 07 nov. 2005 
10    Notation polonaise. Tables de hachage. 14 nov. 2005 
11    Algorithmes sur les arbres. Recherche dans les arbres binaires. Arbres balancés. 21 nov. 2005 
12    Algorithmes sur les graphes. Parcours d`un graphe en largeur et en profondeur. Tri topologique. Calcul des composantes fortement connexes. 28 nov. 2005 
13    Recherche du chemin le plus court dans un graphe (algorithme de Dijkstra). Arbres couvrants du poids minimum. Algorithme de Kruskal. Algorithme de Prim. 05 déc. 2005 
14    Recherche de chaîne de caractères. 12 déc. 2005 
15    Examen final 19 déc. 2005 
6. Évaluation du cours :
  • Examen de mi-session : 35%
  • Examen final : 45%
  • Travaux de programmation : 20%
7. Politiques départementales et institutionnelles :
8. Principales références :
  1. T. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction à l`algorithmique, Dunod, 2002.
  2. R. Kruse, B. Leung, C. Tongo, Data Structures and Program Design in C, Prentice-Hall, 1991.
  3. R. Sedgewick, Algorithmes en langage C, InterEditions, 1991.
  4. M. A. Weiss, Data Structures and Algorithm Analysis in C, Benjamin Cummings, 1993.
  5. T. Standish, Data Structures, Algorithms & Software Principles in C, Addison-Wesley, 1992.
9. Page Web du cours :
http://w3.uqo.ca/jurek/inf4393/inf4393.html