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

Objectifs

Permettre à l'étudiant de s'initier à la conception, à la description et au choix des structures d'information indépendamment d'un langage de programmation. Lui permettre de développer l'habileté à les implanter à l'aide de certains langages typiques.

Contenu

Introduction aux types abstraits, à leur formalisation axiomatique et à leur implantation. Critères d'évaluation des structures de l'information et de leurs implantations: tableau, enregistrement, chaîne de caractères, ensemble, pile, file, liste, arbres simples et équilibrés, graphe, adressage dispersé. Étude de la complexité de différents algorithmes de tri et de recherche avec l'accent mis sur le choix de la structure de données. Compromis espace versus temps.
2. Objectifs spécifiques du cours :
  • Introduire les étudiants à l`évaluation des algorithmes basée sur leur complexités
  • Introduire l`étudiant aux structures de données, à leurs utilisations et à leurs implémentations. Discuter le choix des structures de données en fonction de l'efficacité d'algorithme
  • Approfondir les principes d`algorithmique et de la programmation structurée
3. Stratégies pédagogiques :
  • Cours magistraux
  • Travaux de programmation
  • Exercices théoriques et pratiques durant les séances d'exercices
  • Examen de mi-session
  • Examen final
4. Heures de disponibilité ou modalités pour rendez-vous :
Jeudi 13 h-15 h
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
09 sept. 2016 
2   
  • Tableaux
  • Introduction à la programmation dynamique

Distribution du devoir #1.

Le cours se donne entre 12 h 30 et 15 h 30, durant la séance prévue pour les travaux dirigés.

14 sept. 2016 
3   
  • 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

Travail dirigé 1 (21 septembre 2016): Complexité des algorithmes. Tableaux.

16 sept. 2016 
4   
  • Approfondissement de la récursivité
  • Fonctions récursives
  • Passage de contrôle dans le cas de fonctions récursives
  • Les arbres d`appels récursifs

Travail dirigé 2 (28 septembre 2016): Tableaux (suite). Programme dynamique.

23 sept. 2016 
5   
  • Algorithmes de tri

Travaux dirigés 3-4 (5 octobre 2016): Passage de contrôle dans le cas de fonctions récursives. Les arbres d`appels récursifs. Algorithmes de tri. Tri rapide.

30 sept. 2016 
6   
  • Algorithmes à essais successifs

Travail dirigé 5 (19 octobre 2016): Algorithmes à essais successifs. Révision avant l'examen INTRA.

07 oct. 2016 
7    Semaine d'études 14 oct. 2016 
8    Examen de mi-session 21 oct. 2016 
9   
  • Files; opérations, réalisations machine
  • Piles; opérations, réalisations machine
  • Applications

Travail dirigé 6 (2 novembre 2016): Files et piles.

Remise du devoir #1 (2 novembre 2016).

Distribution du devoir #2

28 oct. 2016 
10   
  • Notation polonaise
  • Arbres
  • Arbres de jeux
  • Algorithmes sur les arbres
  • Recherche dans les arbres binaires

Travail dirigé 7 (9 novembre 2016): Algorithmes de conversion de notation. Arbres de jeux.

04 nov. 2016 
11   
  • Arbres de recherche balancés

Travail dirigé 8 (16 novembre 2016):(Algorithmes pour les arbres de recherche.

11 nov. 2016 
12   
  • Algorithmes sur les graphes
  • Parcours d`un graphe en largeur et en profondeur
  • Tri topologique.

Travail dirigé 9 (23 novembre 2016): Parcours de graphes en largeur et en profondeur.

18 nov. 2016 
13   
  • Recherche du chemin le plus court dans un graphe

Travail dirigé 10 (30 novembre 2016): Algorithmes du chemin le plus court.

Remise du devoir #2 (30 novembre 2016).

25 nov. 2016 
14   
  • Tables de hachage

Travail dirigé 11 (7 décembre 2016): Tables de hachage. Révision avant l'examen final.

02 déc. 2016 
15    Examen final 09 déc. 2016 
6. Évaluation du cours :
  • Examen de mi-session : 40%
  • Examen final : 45%
  • Devoirs : 15%
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, 2009.
  2. Michael T. Goodrich, Roberto Tamassia Data Structures and Algorithms in Java, Wiley, %th Ed., 2010.
  3. R. Kruse, B. Leung, C. Tongo, Data Structures and Program Design in C, Prentice-Hall, 1998.
  4. R. Sedgewick, K. Wayne, Algorithmes, Addison-Wesley, 2011.
  5. P. J. Cabrini, Structures de données avancées avec la STL, Loze-Dion, 2005.
9. Page Web du cours :
https://moodle.uqo.ca