0. Introduction - Les conteneurs

Après cette quête, tu sauras utiliser un conteneur de base.

Objectifs

• Comprendre la notion de conteneur du point de vue algorithmique
• Savoir représenter un conteneur en pseudo-code

Vérifiez-moi ces conteneurs, apprenti docker.

Jeune docker, te voilà sur le marché du travail. J'ai quelques trucs à t'expliquer avant que tu te lances dans ta carrière.

Le métier de docker est physique. Tu te dois d'être en bonne condition et d'être prêt à porter des charges lourdes. Tu sélectionnes et positionnes de gigantesques conteneurs dans lesquels il y a du matériel.

De temps en temps, tu as pour mission de vérifier la nature des conteneurs, leur provenance et ce qu'il y a à l'intérieur. Bien souvent ces conteneurs sont chargés de matériel d'un type précis: des voitures, du caoutchouc, des pièces électroniques. Ces conteneurs viennent de partout dans le monde et tu dois être capable de t'assurer de leur fiabilité.

Eh bien allez, on attaque ! C'est l'heure de t'apprendre comment gérer tes conteneurs !

Un ensemble typé

Un conteneur contient bien souvent des objets d'un seul et même type et il en est de même pour les conteneurs en algorithmique.

Les conteneurs, comme leur nom l'indique, contiennent des choses. Par exemple, un coffre de pirate contient des trésors, un cartable contient des affaires de classe. Ces deux objets de la réalité journalière sont des conteneurs.

D'un point de vue purement algorithmique, les objets contenus dans les conteneurs sont plus abstraits qu'un cartable. Un conteneur contient des valeurs, les unes à la suite des autres. Par conséquent, un conteneur n'est rien d'autre qu'une suite de valeurs organisée de manière contiguë.

Ça veut dire que les chaînes de caractères sont des conteneurs ?

Exactement ! Au niveau conceptuel, une variable de type chaîne de caractères est un conteneur puisqu'elle contient plusieurs caractères. Une chaîne de caractères est un conteneur contenant des caractères.

Il est possible de déclarer des conteneurs de tous types : un conteneur d'entiers, un conteneur de flottants, un conteneur de dates ... Il est même possible de déclarer un conteneur contenant des types différents ! Ceci est assez rare en algorithmique, mais ça peut arriver en programmation, car les langages à typage dynamique le permettent, ce que ne permettra jamais explicitement un langage statique.

Alors les conteneurs contiennent des valeurs d'un certain type : mais qu'en est-il de la taille des conteneurs ? Est-elle finie, infinie ?

Un ensemble de taille n

Les conteneurs avec lesquels tu vas travailler ont une charge maximum. Tu dois t'assurer que la charge qu'ils comportent est optimale, ni supérieure à sa capacité, ni trop peu sinon l'espace est gâché. Cependant, l'algorithmique laisse le choix en terme de comportement des conteneurs. On peut déclarer un conteneur de taille fixe ou dynamique, ça ne changera pas grand-chose au concept ni à l'utilité d'un conteneur. Cependant, en programmation, la quantité de mémoire qu'occupe un conteneur de taille dynamique est supérieure à un de ses homologues de taille finie à nombre de valeurs contenues égal. On préfère donc bien choisir son type de conteneur pour ne pas surcharger la mémoire vive inutilement.

Afin de préciser le comportement des conteneurs, des conventions ont été mises à disposition par des experts du sujet. Le conteneur étant une notion générique, représentant tout type de suite de valeurs, on doit décliner le conteneur dans un type plus précis qui permet de préciser son comportement. Voici quelques types de conteneurs aux comportements différents :

• Le tableau : stocke des données de manière contiguë auxquelles on accède via un index.

• La pile : le premier paramètre empilé sera le dernier dépilé. Le dernier paramètre empilé sera le premier dépilé. On appelle aussi ces conteneurs des conteneurs de type FILO (First-in Last-out)

• La file : l'inverse de la pile - de type FIFO (First-in First-out). Le premier paramètre enfilé sera le premier défilé. Le dernier paramètre enfilé sera le dernier défilé.

Un ensemble peut être d'une certaine taille - c'est une grande découverte - mais comment je fais pour en déclarer un ?

Déclaration d'un tableau en pseudo-code

Eh bien on en arrive à la fin. Il ne te reste plus qu'à apprendre comment présenter les spécificités des conteneurs avec lesquels tu travailles : leurs dimensions, le matériau dans lequel ils sont faits et ce qu'ils contiennent.

Pour ce faire, intéressons-nous un peu à la syntaxe de la déclaration d'un tableau en pseudo-code. Le pseudo-code est censé être du code lisible, dont la syntaxe est indépendante de celle d'un langage de programmation. Tu es assez libre en terme de syntaxe, tant que ton pseudo-code est compréhensible par quelqu'un d'autre. Mais je te propose quand même une syntaxe compréhensible :

x est un tableau d'entiers

Si je désire spécifier la taille maximale de mon conteneur, je peux écrire comme suit :

x est un tableau d'entiers de taille 4

Si je veux accéder à un des éléments du tableau x, j'utilise son index entouré decrochets:

x est un tableau d'entiers de taille 4
x[0] = 0 -- Premier élément du tableau
x[1] = 1 -- Deuxième élément du tableau

Rien ne te choque dans le bloc de pseudo-code ci-dessus ?

Le premier élément du tableau est zéro ?!

Effectivement, le premier élément d'un tableau en algorithmique et en programmation est 0. Je sais que ceci peut sembler bizarre, mais ça paraît normal après y avoir fait face suffisamment de fois.

Mais du coup, dans la réalité, à quoi un tableau peut-il bien servir ?

Un cas concret

Après avoir vu ce qu’est un tableau, tu dois sûrement te demander à quoi peut bien servir un tableau. Je vais te montrer un exemple d’utilisation d’un tableau dans un contexte professionnel.

Un professeur enseigne à un groupe d’élèves. Chaque élève du groupe, pour chacune des matières qu’il suit, a une moyenne. La moyenne d’une matière est déterminée par la somme de toutes ses notes divisée par le nombre de notes. Vois-tu comment on pourrait tirer avantage des tableaux ?

En mettant toutes les notes dans le même tableau ?

Eh bien, oui ! Comme un tableau représente une suite de valeurs qui, mises ensemble, fournissent une seule et même information, eh bien on devrait regrouper toutes les notes d’un élève dans un tableau pour créer un modèle le plus proche de la réalité.

Ensuite, on pourra se servir dudit tableau pour réaliser toutes les opérations possibles ; les valeurs seront organisées et on comprendra très vite qu’il s’agit des notes d’un élève.

notesDeRobert est un tableau de nombres décimaux de taille 3
notesDeRobert[0] = 19.5 # Bravo Robert !
notesDeRobert[1] = 7.25 # Robert, tu t’es relâché
notesDeRobert[2] = 12.5 # Assez bien
moyenneDeRobert = (notesDeRobert[0] + notesDeRobert[1] + notesDeRobert[2])

Challenge

Du pseudo-code

Ecris un pseudo-code qui crée un tableau d'entiers de taille 10, puis associe un entier à chaque case.

Critères de validation

• Soumets un lien vers ta solution sur pastebin

• La solution est rédigée en pseudo-code

• A chaque case du tableau un entier est assigné