Plan de cours

De
Publié par

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 ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 106
Nombre de pages : 12
Voir plus Voir moins

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 par le professeur et serviront de préparation aux travaux pratiques et aux examens. La
participation des élèves aux dits ateliers est donc obligatoire.

Mini-tests Des mini-tests périodiques sont administrés pour faire le suivi de votre acquisition des
connaissances. Cela permet aux enseignants de remédier au plus tôt à certaines difficultés
Les travaux pratiques doivent êtres réalisés individuellement.


Page 5 Jeannine Malo Structures de données
Modalités d’évaluation
Évaluation formative
L’évaluation formative consiste à des activités dont le but est de vous aider, pendant l'apprentissage, à
distinguer ce qui est acquis de ce qui ne l'est pas, de découvrir où et en quoi vous éprouvez des difficultés
d'apprentissage et à proposer les correctifs appropriés.
Les ateliers formatifs (voir section précédente) sont la principale forme d’évaluation formative dans ce cours.
Le professeur vérifiera la qualité des travaux exécutés en classe et à la maison par les moyens suivants :
– correction par l’étudiant de ses travaux, selon les solutions présentées en classe par l’enseignant
ou par d’autres étudiants ;
– correction par le professeur, qui annote les solutions avec ses commentaires ;
– supervision des ateliers par le professeur, qui formule alors des recommandations ponctuelles.


Page 6 Jeannine Malo Structures de données
Évaluation sommative
L’évaluation sommative consiste à mesurer l’apprentissage portant uniquement sur l’atteinte des objectifs
terminaux du cours, pour vous donner une note au bulletin. Le minimum requis pour réussir le cours est de
60 % et la réussite du cours est obligatoire pour obtenir le diplôme.

Le jugement de l’enseignant doit se faire par des activités évaluées à partir de critères connus par vous. Ces
activités ont une pondération substantielle et leur réussite est déterminante sur le cheminement futur de vos
apprentissages. La décision finale demeure le jugement de l’enseignant ; c’est sa responsabilité de déterminer si
vous avez atteint le seuil minimal de réussite, en tenant compte de différents facteurs lui permettant de prendre
une décision.

Vous trouverez, ci-dessous, la forme des différentes activités d’évaluation ainsi que leurs critères qui
permettront de juger du degré de maîtrise de la compétence. Pour chacun, la pondération et le moment de
passation sont indiqués.

Forme Critères d’évaluation Pondération Échéancier
Mini-tests  Choix des structures de données Périodes numéro 5, 8,
(7 mini-tests, dont on appropriées au contexte 11, 15, 24, 26 et 28
garde les 6 meilleures  Création correcte de piles, files, listes
notes) et arbres
 Choix approprié du mode d’allocation
des structures de données en mémoire
 Mise à jour correcte des structures de
données en fonction des opérations 15%
 Utilisation appropriée de la mémoire
en fonction du mode d’allocation
retenu
 Application correcte des techniques
de manipulation des données en
mémoire

Examen intra  Choix des structures de données Vers la période 19
appropriées au contexte
 Création correcte de piles, files et
listes
 Choix approprié du mode d’allocation
des structures de données en mémoire
 Mise à jour correcte des structures de
données en fonction des opérations 25%
 Utilisation appropriée de la mémoire
en fonction du mode d’allocation
retenu
 Application correcte des techniques
de manipulation des données en
mémoire

Page 7 Jeannine Malo Structures de données
Examen final  Choix des structures de données Durant la semaine
appropriées au contexte d’examens
e
 Création correcte de piles, files, listes (15 semaine)
arbres et tableaux dans un langage de
programmation
 Choix approprié du mode d’allocation 30%
des structures de données en mémoire
 Application correcte des techniques
de manipulation des données en
mémoire

Travail pratique  Choix des structures de données À réaliser de la période
numéro 1 appropriées au contexte 11 à la période 18
 Création correcte de piles, files et
listes
 Choix approprié du mode d’allocation
des structures de données en mémoire
 Mise à jour correcte des structures de
données en fonction des opérations 15%
 Utilisation appropriée de la mémoire
en fonction du mode d’allocation
retenu
 Application correcte des techniques
de manipulation des données en
mémoire

Travail pratique  Création correcte d’arbres À réaliser de la période
numéro 2  Mise à jour correcte des structures de 22 à la période 28
données en fonction des opérations
 Utilisation appropriée de la mémoire
en fonction du mode d’allocation
15%
retenu
 Application correcte des techniques
de manipulation des données en
mémoire


Page 8 Jeannine Malo Structures de données
Objectifs relatifs à la langue française
La Politique de valorisation de la langue française précise des modalités pour vous assurer la maîtrise du
français. Pour améliorer la qualité de la langue, dans ce cours, le professeur s’assurera que les communications
écrites respectent les règles de la langue française. Il contrôlera l’application de ces règles lors des différentes
évaluations. Dans le cas des travaux de programmation, les identificateurs devront être des termes français, les
commentaires ainsi que les textes apparaissant à l’écran lors de l’exécution des programmes devront être dans
un français convenable. Jusqu’à 10 % de la note de l’épreuve pourra être enlevé à ce titre.
Un travail peut être refusé par le professeur s’il est jugé illisible ou incompréhensible.

Page 9 Jeannine Malo Structures de données
Règles particulières
Ces règles sont des exigences particulières que vous devez respecter pour assurer votre réussite et l’atteinte de
la ou des compétences visées par ce cours.
Présence aux cours et aux La présence au cours et aux activités d’apprentissage est obligatoire. Vous ne
activités d’apprentissage pouvez pas décider selon votre bon vouloir d'assister ou non aux cours. Votre
participation active aux différentes activités d'apprentissage réalisées en classe est
un des facteurs importants permettant l'acquisition progressive de la compétence
visée et d'augmenter vos chances de réussite : les exposés du professeur, les
discussions en groupe, les explications et les exemples donnés oralement, les
échanges sur les productions des autres élèves, les évaluations formatives, etc.,
font partie intégrante de la démarche d'apprentissage prévue pour être menée en
classe et non selon un modèle de formation à distance. L’élève qui, sans
justification valable, n’aurait pas participé à au moins 80% des activités
d’apprentissage prévues en classe peut se voir refuser le droit de se présenter aux
épreuves d’évaluation sommatives ultérieures. (PIEA, 2003, p. 12)
Le professeur n’est pas tenu, dans ses heures de disponibilité, d’aider l’élève à
compenser le retard engendré par des absences injustifiées à ses cours.
Dans le cas d'une absence à une épreuve d'évaluation sommative, l'étudiant devra
en donner la justification écrite au professeur qui, selon la pertinence de la
justification pourra faire subir à l’étudiant à une épreuve équivalente. Si l'absence
n'est pas justifiée ou si la justification donnée n’est pas jugée recevable, l'étudiant
se verra attribuer la note zéro pour l'épreuve.

Respect des échéances Tout travail non remis à l’enseignant dans un délai de trois jours ouvrables après
l’échéance n’est pas considéré et la note zéro est attribuée. L’enseignant refuse
votre travail si les autres membres de la classe possèdent déjà les résultats de
l’évaluation de ce même travail : la note zéro est alors octroyée. (PIEA, 2003,
p. 13)

Tout travail remis en retard sera pénalisé d’un maximum de 10 % de l’épreuve.

Précisions relatives à la Toute fraude, tentative de fraude ou collaboration à une fraude ainsi que tout
fraude et au plagiat plagiat, toute tentative de plagiat ou toute collaboration à un plagiat avant ou lors
d’une épreuve d'évaluation sommative entraîne automatiquement pour l'étudiant
reconnu coupable la note zéro (PIEA, 2003, p. 12).
Page 10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.