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 2018  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 (2 devoirs)
  • 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 au début de la session.

5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1   

COURS #1 :

  • Introduction aux algorithmes et données
  • Classifications des données
  • Complexité des algorithmes

À NOTER : Le cours se donne entre 8 h 30 et 11 h 30 durant la séance prévue pour les travaux dirigés (7 septembre 2018).

07 sept. 2018 
2   

COURS #2 :

  • Tableaux
  • Introduction à la programmation dynamique

Distribution du devoir #1.

Travail dirigé 1 (14 septembre 2018, 9 h - 11 h). Complexité des algorithmes. Tableaux.

10 sept. 2018 
3   

COURS #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

À NOTER : Le cours #4 se donnera entre 8 h 30 et 11 h 30 durant la séance prévue pour les travaux dirigés (21 septembre 2018).

17 sept. 2018 
4   

COURS #4 :

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

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

21 sept. 2018 
5   

PAS DE COURS LE 1ER OCTOBRE 2018.

Travail dirigé 3 : Les arbres d'appels récursifs. Algorithmes de tri.

Remise du devoir #1

Semaine d'études (08 octobre 2018)

05 oct. 2018 
6   

COURS #5 :

  • Algorithmes de tri (suite)
  • Tri rapide

Travail dirigé 4 (19 octobre 2018): Algorithmes de tri (suite). Tri rapide.

15 oct. 2018 
7   

COURS #6 :

  • Algorithmes à essais successifs
  • Révision avant l'examen intra

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

22 oct. 2018 
8   

Examen de mi-session

29 oct. 2018 
9   

COURS #7 :

  • Files; opérations, réalisations machine
  • Piles; opérations, réalisations machine
  • Applications

Distribution du devoir #2

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

05 nov. 2018 
10   

COURS #8 :

  • Notation polonaise
  • Arbres
  • Arbres de jeux
  • Algorithmes sur les arbres
  • Recherche dans les arbres binaires

Travail dirigé 7 (16 novembre 2018): Algorithmes de conversion de notation. Arbres de jeux.

12 nov. 2018 
11   

COURS #9 :

  • Arbres de recherche balancés. Arbre AVL.

Travail dirigé 8 (23 novembre 2018): Algorithmes pour les arbres de recherche.

19 nov. 2018 
12   

COURS #10 :

  • Algorithmes sur les graphes
  • Parcours d'un graphe en largeur et en profondeur

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

26 nov. 2018 
13   

COURS #11 :

  • Recherche du chemin le plus court dans un graphe

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

Remise du devoir #2 (7 décembre 2018).

03 déc. 2018 
14   

COURS #12 :

  • Adressage dispersé
  • Tables de hachage
  • Révision

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

10 déc. 2018 
15   

Examen final

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