Plan de cours

Titre du cours : Structures de données
Code officiel : 420-C33-BB
Programme d’études : Techniques de l’Informatique
Session visée par le cours : Automne 2010
Discipline : Informatique
Préalables : 420-C22-BB 420-C23-BB
420-P42-BB, 420-P43-BB, 420-PP1-BB Préparatoire à

Pondération
Nombre d’heures par semaine
Heures de travail à la
Heures/contact Heures de laboratoire
maison ou au laboratoire de
en classe ou de travail dirigé
pratique libre
3 3 3

Nom du ou des Coordonnées :
enseignants téléphone, courriel, bureau
de ce cours
Jeannine Malo (514) 332-3000, p. 7809, jeannine.malo@bdeb.qc.ca, H-024
Plan de cours Jeannine Malo Structures de données
Ce plan de cours est un guide mis à votre disposition pour organiser vos activités d’études et de travail liées à ce
cours. Il est donc important que vous en preniez connaissance, de façon attentive, puisqu’il vous renseigne sur
les apprentissages à réaliser, les exigences du cours et les éléments essentiels de son déroulement. Après que
l’enseignant vous l’a remis et expliqué, le contenu de ce plan de cours ne peut pas être modifié sans vous
avoir consulté.
Place du cours dans le programme d’études
Ce cours fait partie du tronc commun aux deux voies de spécialisation offertes : « Informatique de gestion » et
« Gestion des réseaux informatiques ».

Il est situé à la troisième session du programme et complète la séquence des cours de programmation de base :
420-C13-BB Programmation I et 420-C23-BB Programmation II. Il constitue un préalable à trois des quatre
cours de la quatrième session de la voie de sortie « Informatique de gestion » : 420-PP1-BB Projet de design et
programmation Windows, 420-P42-BB Programmation des bases de données et 420-P43-BB Design et
conception. Il n’est cependant préalable à aucun cours de la voie de spécialisation « Gestion des réseaux
informatiques ».

Ce cours vise principalement à vous amener à comprendre les structures de données abstraites, leurs différents
modes de représentation en mémoire vive, ainsi que leur utilisation. Vous aurez à vous prononcer sur le choix
de structures de données dans des contextes différents et à donner les justifications de ces choix. Le langage
utilisé est le C++ sans utiliser l’approche orientée objet.

Tout cours vise l’atteinte de plusieurs compétences prescrites par le Ministère. Une compétence fait appel à des
connaissances que vous possédez déjà et vous amène à acquérir de nouveaux savoirs et à développer de
nouvelles habiletés. L’atteinte de la compétence est importante pour votre développement professionnel ou pour
répondre à des exigences universitaires.
Éléments de compétence Compétence(s) à atteindre dans ce cours
(principales étapes de réalisation)
 Procéder à l’organisation logique des données en
Organiser et exploiter des données mémoire
 Exploiter des données en mémoire
 Adapter l’algorithme aux contraintes du langage
Exploiter un langage de programmation structurée
de programmation

Page 2 Jeannine Malo Structures de données
Planification du cours
Voici les différentes activités qui vous amèneront à atteindre la ou les compétences visées par le cours. Comme
vous le verrez ci-dessous, le cours est découpé en objectifs terminaux qui traduisent le résultat attendu au terme
d’une séquence d’apprentissage. Pour chacun, des objectifs spécifiques viennent spécifier ce à quoi vous devez
parvenir pour atteindre l’objectif terminal. Le contenu détaillé précise les sujets amenés dans ce cours et le
calendrier indique le moment où ce contenu sera traité.
Connaître les différentes structures de données abstraites et leurs caractéristiques. Objectif terminal :
Objectifs spécifiques Contenu détaillé Calendrier
Connaître les structures de données Structures de données linéaires 9 heures
linéaires et leurs caractéristiques  Liste triée
 File
 Pile
 Liste circulaire
 Liste doublement chaînée
 «Double Ended Queue (Deque)»

Connaître les structures de données Structures de données non-linéaires 9 heures
non-linéaires et leurs  Arbres
caractéristiques  Graphes



Connaître les différents modes de représentation des structures de données en mémoire Objectif terminal :
et leurs caractéristiques.
Objectifs spécifiques Contenu détaillé Calendrier
Représenter des structures de Pointeurs 3 heures
données de façon dynamique Structures
Chaînage des éléments

Représenter des structures de Chaînage des éléments dans un tableau 3 heures
données de façon statique


Page 3 Jeannine Malo Structures de données

Utiliser différentes structures de données dans des programmes en utilisant le langage
Objectif terminal : C++.
Objectifs spécifiques Contenu détaillé Calendrier
Choisir des structures de données 6 heures
abstraites appropriées au contexte

Déclarer et initialiser des structures Chaînage des éléments à l’aide de pointeurs 12 heures
de données abstraites dynamiques et  Pointeurs
statiques  Opérateurs
 Arithmétique des pointeurs
 Pointeurs et tableaux
 Principe d’allocation dynamique
 Instructions d’allocation et de libération de mémoire
 Allocation dynamique de tableaux
 Tableaux de pointeurs
 Pointeurs de pointeurs

Chaînage des éléments dans un tableau à l’aide
d’indices

Organiser des données à l’aide des Chaînage des éléments à l’aide des pointeurs 9 heures
structures de données abstraites
dynamiques et statiques Chaînage des éléments dans des tableaux à l’aide
d’indices

Créer et manipuler des données à Opérations sur les structures de données : 27 heures
l’aide des structures de données  Insérer un élément
abstraites dynamiques et statiques  Accéder à un élément
 Modifier un élément
 Éliminer un élément
 Fusionner deux structures de données
 Scinder une structure de données
 Faire une copie d’une structure de données
 Déterminer le nombre d’éléments contenus dans
une structure de données
 Ordonner les éléments d’une structure de données
 Trouver une occurrence d’une valeur
 Copier les éléments d’une structure sur un fichier
de telle sorte qu’il soit possible de reconstituer un
objet ayant les mêmes propriétés

La récursivité
 Récursivité directe et indirecte
 Applications de la récursivité



Page 4 Jeannine Malo Structures de données
Utiliser des techniques de programmation avancées. Objectif terminal :
Objectifs spécifiques Contenu détaillé Calendrier
Connaître et utiliser des méthodes  Tri utilisant un arbre binaire 3 heures
de tri utilisant des structures de  «Shellsort»
données abstraites  «Quicksort»
 «Heapsort»

Concept de complexité d’un algorithme

Connaître et utiliser des techniques Techniques de recherche dans un arbre 3 heures
de recherche utilisant des structures Tables de hachage
de données abstraites


Notes

1. L’échéancier détaillé du cours se trouve sur la page du cours
(http://www.colvir.net/prof/jeannine.malo/CoursC33/Echeancier.htm).
2. Cette planification demeure une projection du déroulement du cours. Celle-ci peut subir des
changements, avec préavis.


Méthodes d’enseignement et d’apprentissage
Voici les différentes méthodes d’enseignement et d’apprentissage que l’enseignant utilisera pour vous amener à
atteindre les objectifs terminaux visés par ce cours.

Exposés magistraux Les notions théoriques du cours seront présentées sous forme d’exposés magistraux, qui
feront ensuite l’objet d’ateliers formatifs.

Ateliers formatifs En règle générale, le cours sera amené sous forme d’ateliers formatifs portant chacun sur un
thème. Ces ateliers, réalisés en classe, permettront d’expérimenter les nouvelles notions qui auront été
présentées préalablement p