420KEE – Structures de données en informatique de gestion

Ceci est un petit site de support pour le cours 420-KEE-LG – Structures de données en informatique de gestion. Notez que plusieurs liens divers sont mis à votre disposition; parmi ceux-ci, soyez particulièrement attentives et attentifs à ceux portant sur :

Notez que tous les résultats aux tests ou aux travaux pratiques ne touchent que la classe de Patrice, pas celle de Pierre. Évidemment, pour le reste, vous êtes toutes et tous les bienvenus.

Détail des séances en classe

Index des séances théoriques
T00	T01	T02	T03	T04	T05	T06	T07	T08	T09	T10	T11	T12	T13	T14

Index des séances théoriques

T00

T01

T02

T03

T04

T05

T06

T07

T08

T09

T10

T11

T12

T13

T14

Date	Séance	Contenu
24 août	L00	Au menu : Survol du plan de cours Qu'est-ce qu'une structure de données? Choix de représentation et coûts (espace, temps) Tableaux tableaux unidimensionnels vecteurs unidimensionnels Présentation du laboratoire 1 Travail sur le laboratoire 1
26 août	T00	Au menu : Bref retour sur : la surcharge d'opérateurs les constructeurs Travail sur le laboratoire 1
31 août	L01	Au menu : Remise du laboratoire 1 Survol de l'idée d'un tableau dynamique Introduction aux vecteurs (voir http://en.cppreference.com/w/cpp/container/vector pour la documentation officielle) constructeurs méthodes size() et capacity() méthodes resize() et reserve() méthode push_back() méthode pop_back() méthode at() et opérateur [] (déclinaisons const et non-const) Tri avec std::sort() comportement par défaut variantes (intervalles, avec prédicat d'ordonnancement) Présentation du laboratoire 2 Travail sur le laboratoire 2
2 septembre	T01	Au menu : Réflexions sur le laboratoire 1 : attribut ou variable locale? Travail sur le laboratoire 2
7 septembre	s/o	Jour férié (Fête du travail)
9 septembre	T02	Au menu : Retour sur le laboratoire 1 : l'importance d'une programmatique (indentation, nomenclature, commentaires, etc.) homogène et cohérente distinguer attributs const et static const réinvestir le travail bien fait et appliquer le principe DRY (1^re partie) : utiliser ses propres fonctions! réinvestir le travail bien fait et appliquer le principe DRY (2^e partie) : lire la documentation des outils auxquels on a recours (et les utiliser!) quand lever une exception et quand retourner une « valeur d'erreur » Remise du laboratoire 2 Présentation du laboratoire 3 Travail sur le laboratoire 3
14 septembre	L02	Au menu : Exercices sur les matrices 2D Travail sur le laboratoire 3
16 septembre	T03	Au menu : Travail sur le laboratoire 3
21 septembre	L03	Au menu : mon ami et collègue Joan-Sébastien Morales prendra les rênes de notre classe pour cette semaine. Pour ma part, je serai à CppCon 2015. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/cppcon2015.html) si vous le souhaitez.
23 septembre	T04	Au menu : mon ami et collègue Joan-Sébastien Morales prendra les rênes de notre classe pour cette semaine. Pour ma part, je serai à CppCon 2015. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/cppcon2015.html) si vous le souhaitez.
28 septembre	L04	Au menu : Travail sur le TP1
30 septembre	T05	Au menu : Survol des matrices triangulaires Travail sur le TP1
5 octobre	L05	Au menu : Remise du TP1
7 octobre	T06	Au menu : Test 1
12 octobre	s/o	Jour férie (Action de Grâces)
13 octobre	L06	Au menu : Retour sur le test 1 Retour sur le TP1 Présentation plus formelle du type std::vector Présentation formelle du type std::deque Présentation formelle du type std::list Explication de techniques de mesure du temps écoulé Attention : mardi avec cours selon l'horaire du lundi
14 octobre	T07	Au menu : Présentation du labo 4 Présentation bref de la classe Chrono de Pierre Prud'homme (retouchée par votre humble serviteur), qui pallie quelques irritants d'un bogue de Visual Studio 2013 dans l'implémentation de l'horloge standard à haute résolution cette classe (le .h et le .cpp) a été déposée en tant que ressource mise à votre disposition sur Colnet Survol de l'idiome pImpl Survol de <random>
19 octobre	L07	Cette semaine, je serai à la rencontre de WG21. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/wg21-2015-Kona.html) si vous le souhaitez.
21 octobre	T08	Cette semaine, je serai à la rencontre de WG21. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/wg21-2015-Kona.html) si vous le souhaitez.
26 octobre	L08	Séance qui n'a pas lieu dû à une journée de grève. On verra bien ce qu'il adviendra... Je m'ennuie de vous!
28 octobre	T09	Au menu : On construit une liste doublement chaînée avec noeuds sentinelles (comme dans le schéma du document de Pierre Prud'homme) Pour aujourd'hui, vous devez implémenter les fonctions suivantes : Constructeur par défaut Sainte-Trinité : constructeur de copie affectation destruction Ajouter au début (push_front()) Retirer au début (pop_front()) Ajouter à la fin (push_back()) Retirer à la fin (pop_back()) Consulter l'élément au début (front()) Consulter l'élément à la fin (back()) Dire s'il est vide (empty()) Dire combien d'éléments il contient (size()) Nous transformerons sous peu cette classe en travail pratique sommatif, alors mettez-vous au boulot dès maintenant!
2 novembre	L09	Au menu : Remise des travaux corrigés, et discussion Labo 03 Labo 04 Binairo Survol de l'implémentation des services de base attendus pour Liste (voir T09 pour des détails) Choix d'implémentation pour le noeuds sentinelles Intérêt des noeuds sentinelles Construction par défaut Services de base (back(), empty(), size()) Insertion et suppression à l'une des extrémités Examen de l'implémentation correcte de la Sainte-Trinité pour un type tel que Liste En particulier, pour implémenter l'affectation, présentation de l'idiome d'affectation sécuritaire Considérations de documentation Survol de complexité algorithmique Invariants, préconditions et postconditions
4 novembre	s/o	Journée pédagogique (cours suspendus)
9 novembre	T10	Séance qui n'a pas lieu dû à une journée de grève. On verra bien ce qu'il adviendra... Je m'ennuie de vous!
11 novembre	L10	Au menu : Présentation du TP2 – SPA Travail sur le TP2 – SPA
16 novembre	T11	Au menu : Implémenter un itérateur Travail sur le TP2 – SPA
18 novembre	L11	Au menu : Travail sur le TP2 – SPA Remise du TP2 – SPA
23 novembre	T12	Au menu : Test 2
25 novembre	L12	Au menu : Retour sur le test 2 Récursivité : ce que c'est comment l'implémenter exemple d'application malsaine exemple d'application mitoyenne exemple de saine application
30 novembre	T13	Au menu : Algorithmes de recherche (introduction) Backtracking Présentation du TP3
2 décembre	L13	Au menu : Travail sur le TP3
7 décembre	s/o	Journée d'examen pour la formation générale (cours suspendus)
9 décembre	L14	Au menu : Travail sur le TP3
14 décembre	T14	Au menu : Remise du TP3 Test 3
16 décembre		Allez visiter EXPO INFO

Date

Séance

Contenu

24 août

L00

Au menu :

Survol du plan de cours
Qu'est-ce qu'une structure de données?
Choix de représentation et coûts (espace, temps)
Tableaux
- tableaux unidimensionnels
- vecteurs unidimensionnels
Présentation du laboratoire 1
Travail sur le laboratoire 1

26 août

T00

Au menu :

Bref retour sur :
- la surcharge d'opérateurs
- les constructeurs
Travail sur le laboratoire 1

31 août

L01

Au menu :

Remise du laboratoire 1
Survol de l'idée d'un tableau dynamique
Introduction aux vecteurs (voir http://en.cppreference.com/w/cpp/container/vector pour la documentation officielle)
- constructeurs
- méthodes size() et capacity()
- méthodes resize() et reserve()
- méthode push_back()
- méthode pop_back()
- méthode at() et opérateur [] (déclinaisons const et non-const)
Tri avec std::sort()
- comportement par défaut
- variantes (intervalles, avec prédicat d'ordonnancement)
Présentation du laboratoire 2
Travail sur le laboratoire 2

2 septembre

T01

Au menu :

Réflexions sur le laboratoire 1 :
- attribut ou variable locale?
Travail sur le laboratoire 2

7 septembre

s/o

Jour férié (Fête du travail)

9 septembre

T02

Au menu :

Retour sur le laboratoire 1 :
- l'importance d'une programmatique (indentation, nomenclature, commentaires, etc.) homogène et cohérente
- distinguer attributs const et static const
- réinvestir le travail bien fait et appliquer le principe DRY (1^re partie) : utiliser ses propres fonctions!
- réinvestir le travail bien fait et appliquer le principe DRY (2^e partie) : lire la documentation des outils auxquels on a recours (et les utiliser!)
- quand lever une exception et quand retourner une « valeur d'erreur »
Remise du laboratoire 2
Présentation du laboratoire 3
Travail sur le laboratoire 3

14 septembre

L02

Au menu :

Exercices sur les matrices 2D
Travail sur le laboratoire 3

16 septembre

T03

Au menu :

Travail sur le laboratoire 3

21 septembre

L03

Au menu : mon ami et collègue Joan-Sébastien Morales prendra les rênes de notre classe pour cette semaine.

Pour ma part, je serai à CppCon 2015. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/cppcon2015.html) si vous le souhaitez.

23 septembre

T04

Au menu : mon ami et collègue Joan-Sébastien Morales prendra les rênes de notre classe pour cette semaine.

Pour ma part, je serai à CppCon 2015. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/cppcon2015.html) si vous le souhaitez.

28 septembre

L04

Au menu :

Travail sur le TP1

30 septembre

T05

Au menu :

Survol des matrices triangulaires
Travail sur le TP1

5 octobre

L05

Au menu :

Remise du TP1

7 octobre

T06

Au menu :

Test 1

12 octobre

s/o

Jour férie (Action de Grâces)

13 octobre

L06

Au menu :

Retour sur le test 1
Retour sur le TP1
Présentation plus formelle du type std::vector
Présentation formelle du type std::deque
Présentation formelle du type std::list
Explication de techniques de mesure du temps écoulé

Attention : mardi avec cours selon l'horaire du lundi

14 octobre

T07

Au menu :

Présentation du labo 4
Présentation bref de la classe Chrono de Pierre Prud'homme (retouchée par votre humble serviteur), qui pallie quelques irritants d'un bogue de Visual Studio 2013 dans l'implémentation de l'horloge standard à haute résolution
- cette classe (le .h et le .cpp) a été déposée en tant que ressource mise à votre disposition sur Colnet
Survol de l'idiome pImpl
Survol de <random>

19 octobre

L07

Cette semaine, je serai à la rencontre de WG21. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/wg21-2015-Kona.html) si vous le souhaitez.

21 octobre

T08

Cette semaine, je serai à la rencontre de WG21. Vous pourrez me suivre (à travers ../../../Sujets/Orthogonal/wg21-2015-Kona.html) si vous le souhaitez.

26 octobre

L08

Séance qui n'a pas lieu dû à une journée de grève. On verra bien ce qu'il adviendra... Je m'ennuie de vous!

28 octobre

T09

Au menu :

On construit une liste doublement chaînée avec noeuds sentinelles (comme dans le schéma du document de Pierre Prud'homme)

Pour aujourd'hui, vous devez implémenter les fonctions suivantes :

Constructeur par défaut
Sainte-Trinité :
- constructeur de copie
- affectation
- destruction
Ajouter au début (push_front())
Retirer au début (pop_front())
Ajouter à la fin (push_back())
Retirer à la fin (pop_back())
Consulter l'élément au début (front())
Consulter l'élément à la fin (back())
Dire s'il est vide (empty())
Dire combien d'éléments il contient (size())

Nous transformerons sous peu cette classe en travail pratique sommatif, alors mettez-vous au boulot dès maintenant!

2 novembre

L09

Au menu :

Remise des travaux corrigés, et discussion
- Labo 03
- Labo 04
- Binairo
Survol de l'implémentation des services de base attendus pour Liste (voir T09 pour des détails)
- Choix d'implémentation pour le noeuds sentinelles
- Intérêt des noeuds sentinelles
- Construction par défaut
- Services de base (back(), empty(), size())
- Insertion et suppression à l'une des extrémités
- Examen de l'implémentation correcte de la Sainte-Trinité pour un type tel que Liste
  - En particulier, pour implémenter l'affectation, présentation de l'idiome d'affectation sécuritaire
Considérations de documentation
- Survol de complexité algorithmique
- Invariants, préconditions et postconditions

4 novembre

s/o

Journée pédagogique (cours suspendus)

9 novembre

T10

Séance qui n'a pas lieu dû à une journée de grève. On verra bien ce qu'il adviendra... Je m'ennuie de vous!

11 novembre

L10

Au menu :

Présentation du TP2 – SPA
Travail sur le TP2 – SPA

16 novembre

T11

Au menu :

Implémenter un itérateur
Travail sur le TP2 – SPA

18 novembre

L11

Au menu :

Travail sur le TP2 – SPA
Remise du TP2 – SPA

23 novembre

T12

Au menu :

Test 2

25 novembre

L12

Au menu :

Retour sur le test 2
Récursivité :
- ce que c'est
- comment l'implémenter
- exemple d'application malsaine
- exemple d'application mitoyenne
- exemple de saine application

30 novembre

T13

Au menu :

Algorithmes de recherche (introduction)
Backtracking
Présentation du TP3

2 décembre

L13

Au menu :

Travail sur le TP3

7 décembre

s/o

Journée d'examen pour la formation générale (cours suspendus)

9 décembre

L14

Au menu :

Travail sur le TP3

14 décembre

T14

Au menu :

Remise du TP3
Test 3

16 décembre

Allez visiter EXPO INFO

Documents sous forme électronique

Consignes des travaux pratiques

Consignes de l'activité synthèse

Pratiques de correction

Résultats des tests

Test	Séance	Poids	$\mu$	$\sigma^2$	$n$
Test 1	T06	$15\%$	$72,81\%$	$17,11\%$	$15$
Test 2	xxx	$15\%$	$??,??\%$	$??,??\%$	$??$
Test 3	xxx	$15\%$	$??,??\%$	$??,??\%$	$??$
$\mu$ :	$??,??\%$

Test

Séance

Poids

$\mu$

$\sigma^2$

$n$

Test 1

T06

$15\%$

$72,81\%$

$17,11\%$

$15$

Test 2

xxx

$15\%$

$??,??\%$

$??$

Test 3

xxx

$15\%$

$??,??\%$

$??$

$\mu$ :

$??,??\%$

Résultats des travaux pratiques

TP	Remise	Poids	$\mu$	$\sigma^2$	$n$	$N$
Labo 1	L01	$??\%$	$74,46\%$	$9,56\%$	$14$	$15$
Labo 2	T02	$??\%$	$75,82\%$	$8,21\%$	$11$	$15$
Labo 3	L03	$??\%$	$65,43\%$	$13,84\%$	$14$	$15$
Labo 4	T08	$??\%$	$75,19\%$	$11,57\%$	$15$	$15$
Travail pratique 1 (Binairo)	L05	$??\%$	$73,43\%$	$9,77\%$	$14$	$15$
??	xxx	$??\%$	$??,??\%$	$??,??\%$	$??$	$??$
Cumulatif	$\mu$ :	$??,??\%$
$\sigma^2$ :	$??,??\%$

Remise

Poids

$\mu$

$\sigma^2$

$n$

$N$

Labo 1

L01

$??\%$

$74,46\%$

$9,56\%$

$14$

$15$

Labo 2

T02

$??\%$

$75,82\%$

$8,21\%$

$11$

$15$

Labo 3

L03

$??\%$

$65,43\%$

$13,84\%$

$14$

$15$

Labo 4

T08

$??\%$

$75,19\%$

$11,57\%$

$15$

Travail pratique 1 (Binairo)

L05

$??\%$

$73,43\%$

$9,77\%$

$14$

$15$

xxx

$??\%$

$??,??\%$

$??$

Cumulatif

$\mu$ :

$??,??\%$

$\sigma^2$ :

$??,??\%$

Code de démonstration

Vous trouverez ci-après le code source de divers exemples de vos notes de cours. Il est possible que le code ne soit pas exactement le même que dans les notes de cours puisque j'ai retouché ces dernières récemment (le site Web est un peu en retard côté mises à jour), mais les différences sont cosmétiques.

	Je corrige les programmes en appliquant des codes de correction. Vous trouverez ici la liste des codes les plus fréquents
	Ma stratégie de correction en tant que telle (pour le code, à tout le moins) est résumée ici

	Consignes du TP00
	Consignes du TP01
	Consignes du TP02

	À déterminer
	À déterminer