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 2017  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 :
À déterminer
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
08 sept. 2017 
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 (11 septembre 2017).

Travail dirigé 1 (15 septembre 2017, 9 h - 11 h). Il se donne durant la séance prévue pour le cours: Complexité des algorithmes. Tableaux.

15 sept. 2017 
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
  • Approfondissement de la récursivité
  • Fonctions récursives

Travail dirigé 2 (25 septembre 2017): Tableaux (suite). Programmation dynamique. Passage de contrôle dans le cas de fonctions récursives.

22 sept. 2017 
4   
  • Passage de contrôle dans le cas de fonctions récursives
  • Les arbres d'appels récursifs
  • Algorithmes de tri

Travail dirigé 3 (2 octobre 2017): Les arbres d'appels récursifs. Algorithmes de tri

29 sept. 2017 
5   
  • Algorithmes de tri (suite)
  • Tri rapide

Travail dirigé 4 (16 octobre 2017): Algorithmes de tri (suite). Tri rapide.

06 oct. 2017 
6    Semaine d'études 13 oct. 2017 
7   
  • Algorithmes à essais successifs
  • Révision avant l'examen intra

Travail dirigé 5 (23 octobre 2017): Algorithmes à essais successifs. Révision avant l'examen intra.

20 oct. 2017 
8    Examen de mi-session 27 oct. 2017 
9   
  • Files; opérations, réalisations machine
  • Piles; opérations, réalisations machine
  • Applications

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

Remise du devoir #1 (30 novembre 2017).

Distribution du devoir #2

03 nov. 2017 
10   
  • Notation polonaise
  • Arbres
  • Arbres de jeux
  • Algorithmes sur les arbres
  • Recherche dans les arbres binaires

Travail dirigé 7 (13 novembre 2017): Algorithmes de conversion de notation. Arbres de jeux.

10 nov. 2017 
11   
  • Arbres de recherche balancés. Arbre AVL.

Travail dirigé 8 (20 novembre 2017): Algorithmes pour les arbres de recherche.

17 nov. 2017 
12   
  • Algorithmes sur les graphes
  • Parcours d'un graphe en largeur et en profondeur

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

24 nov. 2017 
13   
  • Recherche du chemin le plus court dans un graphe

Travail dirigé 10 (4 décembre 2017): Algorithmes du chemin le plus court.

Remise du devoir #2 (4 décembre 2017).

01 déc. 2017 
14   
  • Tables de hachage

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

08 déc. 2017 
15    Examen final 15 déc. 2017 
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