Actualité

[[{"title":"S.D. : Listes chaînées","posi":0},{"text":"

La structure de tableau permet de stocker des séquences d'éléments mais n'est pas adaptée à toutes les opérations que l'on pourrait vouloir effectuer

sur des séquences. Les tableaux de Python permettent par exemple d'insérer ou de supprimer efficacement des éléments à la fin d'un tableau, avec les opérations append et pop, mais se prêtent mal à l'insertion ou la suppression d'un élément à une autre position.

En effet, les éléments d'un tableau étant contigus et ordonnés en mémoire, insérer un élément dans une séquence demande de déplacer tous les éléments qui le suivent pour lui laisser une

place.

Si par exemple on veut insérer une valeur v à la première position d'un tableau

il faut d'une façon où d'une autre construire le nouveau tableau

dans lequel la case d'indice 0 contient maintenant la valeur v.

On peut le faire en utilisant l'opération insert des tableaux de Python.

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.insert(v,0)

print(\"t =\",t)

Cette opération est cependant très coûteuse, car elle déplace tous les éléments du tableau d'une case vers la droite après avoir agrandi le tableau.

C'est exactement comme si nous avions écrit les lignes suivantes :

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.append(None)

for i in range(len(t) - 1, 0, -1):

t[i] = t[i - 1]

t[0] = v

print(\"t =\",t)

Avec une telle opération on commence donc par agrandir le tableau, en ajoutant un nouvel élément à la fin avec append.

None

Puis on décale tous les éléments d'une case vers la droite, en prenant soin de commencer par le dernier et de terminer par le premier.

Enfin, on écrit la valeur v dans la première case du tableau.

Au total, on a réalisé un nombre d'opérations proportionnel à la taille du tableau. Si par exemple le tableau contient un million d'éléments, on fera un

million d'opérations pour ajouter un premier élément.

En outre, supprimer le premier élément serait tout aussi coûteux, pour les mêmes raisons.

Dans cette séquence nous étudions une structure de données, la liste chaînée, qui d'une part apporte une meilleure solution au problème de l'insertion et de la suppression au début d'une séquence d'éléments, et d'autre part servira de brique de base à plusieurs autres structures dans les prochaines séquences.

"},{"text":""}],[{"text":"Une liste chaînée permet avant tout de représenter une liste, c'est-à-dire une séquence finie de valeurs, par exemple des entiers.

Comme le nom le suggère sa structure est en outre caractérisée par le fait que les éléments sont chaînés entre eux, permettant le passage d'un élément à l'élément suivant.

Ainsi, chaque élément est stocké dans un petit bloc alloué quelque part dans la mémoire, que l'on pourra appeler maillon ou cellule, et y est accompagné d'une deuxième information : l'adresse mémoire où se trouve la cellule contenant l'élément suivant de la liste.

$\"\"$

Ici, on illustré une liste contenant trois éléments, respectivement 1, 2 et 3.

Chaque élément de la liste est matérialisée par l'emplacement en mémoire

contenant d'une part sa valeur (dans la case de gauche} et d'autre part l'adresse mémoire de la valeur suivante (dans la case de droite).

Programme — Cellule d'une liste chaînée

class Cellule:

\"\"\"une cellule d'une Liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

Dans le cas

du dernier élément, qui ne possède pas de valeur suivante, on utilise une valeur spéciale désignée ici par le symbole ⊥ et marquant la fin de la liste.

Une façon traditionnelle de représenter une liste chaînée en Python consiste à utiliser une classe décrivant les cellules de la liste, de sorte que chaque élément de la liste est matérialisé par un objet de cette classe.

Cette classe est appelée ici Cellule et est donnée dans le programme ci-dessus.

Tout objet de cette classe contient deux attributs : :

- un attribut valeur pour la valeur

de l'élément (l'entier, dans notre exemple)

- et un attribut suivante pour la cellule suivante de la liste.

Lorsqu'il n'y à pas de cellule suivante, c'est-à-dire lorsque l'on considère la dernière cellule de la liste, on donne à l'attribut suivante la valeur None.

Dit autrement, None est notre représentation du symbole ⊥.

Pour construire une liste, il suffit d'appliquer le constructeur de la classe Cellule autant de fois qu'il y a d'éléments dans la liste.

lst = Cellule(1, Cellule(2, Cellule(3, None)))

Ainsi, l'instruction construit la liste 1,2,3 donnée en exemple plus haut et la stocke dans une variable lst.

Plus précisément, on a ici créé trois objets de la classe Cellule, que l'on peut visualiser comme suit

#affiche le contenu de lst

print(lst)

c = lst

espace = \" \"

while c is not None :

print(espace,\"|-->\",c.valeur,\" , \",c.suivante)

c = c.suivante

espace += \" \"

Tester le code ci-dessous et conclure.

$\"liste11.png$

La valeur contenue dans la variable lst est l'adresse mémoire de l'objet contenant la valeur 1, qui lui-même contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 2, qui enfin contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 3.

Ce dernier contient la valeur None dans son attribut suivante, marquant ainsi la fin de la liste.

Par la suite, on s'autorisera un dessin simplifié, de la manière suivante.

Dans ce dessin, il faut interpréter chaque élément de la liste comme un objet de la classe Cellule.

","title":"Structure de liste chaînée"},{"edit":"

Mettre ici les résultats.

"}],[{"text":"

$\"liste11.png$

Comme on le voit, une liste est soit la

valeur None, soit un objet de la classe Cellule dout l'attribut suivante contient une liste. C'est là une définition récursive de la notion de liste.

","title":"Définition récursive des listes chaînées"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Représentations alternatives. D'autres représentations des listes chaînées sont possibles. Plutôt qu'un objet de la classe Cellule, on pourrait

utiliser un couple, et dans ce cas écrire (1, (2, (3,None))), ou encore un tableau à deux éléments, et dans ce cas écrire [1, [2, [3,None]]]. Cependant, l'utilisation d'une valeur structurée avec des champs nominés

(ici les attributs valeur et suivante) est idiomatique, y compris dans un langage comme Python.

Variantes des listes chaînées. Il existe de nombreuses variantes de la structure de liste chaînée, dont la liste cyclique, où le dernier élément est lié au premier,

ou la liste doublement chaînée, où chaque élément est lié à l'élément suivant et à l'élément précédent dans la liste,

ou encore la liste cyclique doublement chaînée qui combine ces deux variantes.

Dans tout cette séquence, on ne manipule que des listes simplement chaînées et ne contenant pas de cycles.

Homogénéité. Bien que nous illustrions cette séquence avec des listes d'entiers, les listes chaînées, au même titre que les tableaux Python, peuvent

contenir des valeurs de n'importe quel type.

Ainsi, on peut imaginer des listes de chaînes de caractères, de couples, etc. Comme pour les tableaux, nous recommandons une utilisation homogène des listes chaînées, où tous les éléments de la liste sont du même type.

","title":""},{"edit":"

"}],[{"text":"

$\"liste11.png$

Dans cette section, nous allons programmer quelques opérations fondamentales sur les listes.

D'autres opérations sont proposées en exercices.

","title":"Opérations sur les listes"},{"edit":""}],[{"text":"

La première opération que nous allons programmer consiste à calculer la longueur d'une liste chaînée, c'est-à-dire le nombre de cellules qu'elle contient.

Il s'agit donc de parcourir la liste, de la première cellule jusqu'à la dernière, en suivant les liens qui relient les cellules entre elles.

On peut réaliser ce parcours, au choix, avec une fonction récursive ou avec une boucle.

Nous allons faire les deux. Dans les deux cas, on écrit une fonction longueur qui reçoit une liste lst en argument et renvoie sa longueur.

def longueur (lst):

\"\"\"renvoie La longueur de la Liste lst\"\"\"

Commençons par la version récursive. Elle consiste à distinguer le cas de base, c'est-à-dire une liste vide ne contenant aucune cellule, du cas général, c'est-à-dire une liste contenant au moins une cellule.

Dans le premier cas, il suffit de renvoyer 0 :

if lst is None:

return 0

Ici, on a testé si la liste lst est égale à None avec l'opération is de Python mais on aurait tout aussi bien pu utiliser ==, c'est-à-dire écrire lst == None.

Dans le second cas, il faut renvoyer 1, pour la première cellule, plus la longueur du reste de la liste, c'est-à-dire la longueur de la liste lst suivante, que l'on peut calculer récursivement :

else:

return 1 + longueur (lst.suivante)

On se persuade facilement que cette fonction termine, car le nombre de cellules de Ia liste passée en argument à la fonction longueur décroît strictement à chaque appel.

Écrivons maintenant la fonction longueur différemment, cette fois avec une boucle. On commence par se donner deux variables : une variable n contenant la longueur que l'on calcule et une variable c contenant la cellule courante du parcours de la liste.

def longueur (lst) :

\"\"\"renvoie la longueur de la liste lst\"\"\"

n = 0

c = lst

Initialement, n vaut 0 et c prend la valeur de lst, c'est-à-dire None si la liste est vide et la première cellule sinon.

Le parcours est ensuite réalisé avec une boucle while, qui exécute autant d'itérations qu'il y a de cellules dans

la liste.

while c is not None:

L'opération is not est, comme on le devine, la négation de l'opération is.

On exécuter donc cette boucic tant que c n'est pas égale à None.

À chaque étape, c'est-à-dire pour chaque cellule de la liste, on incrémente le compteur n et on passe à la cellule suivante en donnant à c la valeur de c.suivante.

n += 1

c = c.suivante

Une fois que l'on sort de la boucle, il suffit de renvoyer la valeur de n.

return n

Il est important de comprendre que, dans cette version itérative, seule la variable c est modifiée, pour désigner successivement les différentes cellules de la liste :

L'affectation c = c.suivante ne modifie pas le contenu ou la structure de la liste, seulement le contenu de la variable c, qui est l'adresse d'une cellule de ta liste.

Le code complet de ces deux fonctions Longueur est donné ci-dessous.

Programme — Calcul de la longueur d'une liste

class Cellule:

\"\"\"une cellule d'une Liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

lst = Cellule(1, Cellule(2, Cellule(3, None)))

# avec une fonction récursive

def longueurR(lst):

\"\"\"renvoie la Longueur de La liste lst\"\"\"

if lst is None :

return 0

else:

return 1 + longueurR(lst.suivante)

# avec une boucle

def longueurB(lst):

\"\"\"renvoie la longueur de la Liste lst\"\"\"

n = 0

c = lst

while c is not None:

n += 1

c = c.suivante

return n

print(longueurB(lst))

print(longueurR(lst))

Complexité. Il est clair que la complexité du calcul de la longueur est directement proportionnelle à la longueur elle-même, puisqu'on réalise un nombreux constant d'opération pour chaque cellule de la liste. Ainsi, pour une liste lst de mille cellules, longueur(lst) va effectuer mille tests, mille appels récursifs et mille additions dans sa version récursive, et mille tests, mille additions et deux mille affectations dans sa version itérative.

","title":"Longueur d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comparaison avec None.

c.suivante == None ou c.suivante is None?

À priori, il n'y à pas de différence entre écrire lst is None et lst == None.

Les deux opérations ne sont pas exactement les mêmes : l'opération is est une égalité physique {être identiquement le même objet, au même endroit dans la mémoire) et l'opération == est une égalité structurelle (être la même valeur, après une comparaison

en profondeur).

Mais dans le cas particulier de la valeur None, ces deux

égalités coïncident, car l'objet qui représente None est unique.

On teste donc bien si la valeur de lst est None dans les deux cas.

Cependant, une classe peut redéfinir l'égalité représentée par l'opération == et, dans ce cas, potentiellement modifier le résultat d'une comparaison avec None. Pour cette raison, il est d'usage de tester l'égalité à None avec is plutôt qu'avec ==. Bien évidemment, dans le cas précis de notre propre classe Cellule, nous savons qu'elle ne redéfinit pas l'opération ==, Néanmoins, nous choisissons de nous conformer à cette bonne pratique.

"}],[{"text":"

Comme deuxième opération sur les listes, écrivons une fonction qui renvoie le n-ième élément d'une liste chaînée.

On prend la convention que le premier élément est désigné par n = 0, comme pour les tableaux.

On cherche donc à écrire une fonction de la forme suivante.

def nieme_element(n, lst):

\"\"\"renvoie Le n-ième élément de la liste lst

Les éléments sont numérotés à partir de 9\"\"\"

Comme pour la fonction Longueur, nous avons le choix entre écrire la fonction nieme_element comme une fonction récursive ou avec une boucle.

Nous faisons ici le choix d'une fonction récursive.

Comme pour le calcul de la longueur, nous commençons par traiter le cas d'une liste qui ne contient aucun élément. Dans ce cas, on choisit de lever une exception, en l'occurrence la même exception IndexError que celle levée par Python lorsque l'on tente d'accéder à un indice invalide d'un tableau.

if lst is None:

raise IndexError (\"indice invalide\")

La chaîne de caractères passée en argument de l'exception est arbitraire.

Si en revanche la liste lst n'est pas vide, il y à deux cas de figure à considérer. Si n = 0, c'est que l'on demande le premier élément de la liste et il est alors renvoyé.

if n == 0:

return Ist.vaieur

Sinon, il faut continuer la recherche dans le reste de la liste. Pour cela, on fait un appel récursif à nieme_element en diminuant de un la valeur de n.

else:

return nieme_element(n - 1, lst.suivante)

Attention à ne pas oublier ici l'instruction return, car il faut renvoyer le résultat de l'appel récursif et non pas se contenter de faire un appel récursif.

Ceci achève le code de la fonction nieme_element. Le code complet est

Programme — N-ième élément d'une liste

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

Complexité. La complexité de la fonction nieme_element est un peu plus subtile que celle de la fonction longueur. Dans certains cas, on effectue exactement n appels récursifs pour trouver le n-ième élément, et donc un nombre d'opérations proportionnel à n.

Dans d'autres cas, en revanche, on parcourt toute la liste. Cela se produit clairement lorsque n > longueur (lst). Il pourrait être tentant de commencer par comparer n avec la longueur de la liste, pour ne pas parcourir la liste inutilement, mais c'est inutile car le calcul de la longueur parcourt déjà toute la liste. Pire encore, calculer la longueur de la liste à chaque appel récursif résulterait en un programme de complexité quadratique (proportionnelle au carré de la longueur de la liste).

On peut remarquer que la liste est également intégralement parcourue lorsque n < 0. En effet, la valeur de n va rester strictement négative, puisqu'on la décrémente à chaque appel, et on finira par atteindre la liste vide.

Pour y remédier, ii suffit de modifier légèrement le premier test de la fonction, de la manière suivante :

if n < 0 or lst is None:

raise IndexError(\"indice invalide\")

On obtient exactement le même comportement qu'auparavant (la levée de l'exception IndexError) mais cela se fait maintenant en temps constant, car la liste n'est plus parcourue.

","title":"N-ième élément d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Considérons maintenant l'opération consistant à mettre bout à bout les éléments de deux listes données.

On appelle cela la concaténation de deux

listes.

Ainsi, si la première liste contient 1,2,3 et la seconde 4,5 alors le résultat de la concaténation est 1,2,3,4,5. Nous choisissons d'écrire la concaténation sous la forme d'une fonction concatener qui reçoit deux listes en arguments et renvoie une troisième liste contenant la concaténation.

def concatener{(l1, l2):

\"\"\"concatène les listes l1 et l2, sous la forme d'une nouvelle liste\"\"\"

Il est ici aisé de procéder récursivement sur la structure de la liste 11. Si elle est vide, la concaténation est identique à la liste l2, qu'on se contente donc de renvoyer.

if l1 is None:

return l2

Sinon, le premier élément de la concaténation est le premier élément de l1 et le reste de la concaténation est obtenu récursivement en concaténant le reste de 11 avec l2.

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

Le programme ci-dessus contient l'intégralité du code.

Il est important de comprendre ici que les listes passées en argument à la fonction concatener ne sont pas modifiées.

Plus précisément, les éléments de la liste l1 sont copiés et ceux de l2 sont partagés.

Illustrons-le avec la concaténation des listes 1,2,3 et 4,5.

Après les trois instructions

l1 = Cellule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

on à la situation suivante, avec huit cellules au total :

On voit que les trois cellules de l1 ont été dupliquées, pour former le début de la liste 1,2, 3 ,4, 5, et que les deux cellules de l2 sont partagées pour former à la fois la liste l2 et la fin de la liste l3.

Il n'y a pas de danger à réaliser ainsi un tel partage de cellules, tant qu'on ne cherche pas à modifier les listes, Une alternative consisterait à copier également tous les éléments de l2, ce qui pourrait se faire en écrivant une fonction copie et en remplaçant return l2 par

return copie(l2).

Mais c'est inutile dès lors qu'on choisit de ne jamais modifier les listes une fois construites.

Dans la section suivante, nous discuterons d'une autre façon de réaliser la concaténation de deux listes l1 et l2, consistant à modifier la dernière cellule de la liste 11 pour la faire pointer vers la première cellule de la liste l2.

Mais nous mettrons également en garde contre les dangers que comporte une telle modification.

Programme - Concaténation de deux listes

def concatener(l1, l2):

\"\"\"concatène les listes l1 et l2, sous La forme d'une nouvelle liste\"\"\"

if l1 is None:

return l2

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

l1 = Cellule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

print(\"lg l3=\", longueurB(l3))

Complexité. Il est clair que le coût de la fonction concatener est directement proportionnel à la longueur de la liste 11. En revanche, il ne dépend

pas de la longueur de la liste l2.

","title":"Concaténation de deux listes"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme quatrième et dernière opération sur les listes, considérons le renversement d'une liste, c'est-à-dire une fonction renverser qui, recevant en argument une liste comme 1,2, 3, renvoie la liste renversée 3, 2,1.

Vu que la récursivité a été utilisée avec succès pour écrire les trois opérations précédentes, il semble naturel de chercher une écriture récursive de la fonction renverser.

Le cas de base est celui d'une liste vide, pour laquelle

il suffit de renvoyer la liste vide. Pour le cas récursif, en revanche, c'est plus délicat, car le premier élément doit devenir le dernier élément de la liste renversée. Aussi, il faut renverser la queue de la liste puis concaténer à la fin le tout premier élément.

Vu que nous venons justement d'écrire une fonction

concatener, il n'y a qu'à s'en servir. Cela nous donne un code relativement simple pour la fonction renverser.

def renverser1(lst):

if lst is None:

return None

else:

return concatener(renverser(lst.suivante), Cellule(lst.valeur, None))

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

r1 = renverser1(l1)

Un tel code, cependant, est particulièrement inefficace. Si on en mesure le temps d'exécution, on s'aperçoit qu'il est proportionnel au carré du nombre d'éléments.

Pour renverser une liste de 1000 éléments, il faut près d'un demimillion d'opérations.

En effet, il faut commencer par renverser une liste de 999 éléments, puis concaténer le résultat avec une liste d'un élément. Comme on l'a vu, cette concaténation coûte 999 opérations. Et pour renverser la liste de 999 éléments, il faut renverser une liste de 998 éléments puis concaténer le résultat avec une liste d'un élément. Et ainsi de suite.

Au total, on a donc au moins 999 + 998 + .. + 1 = 499500 opérations.

Une fois n'est pas coutume, la récursivité nous à mis sur la piste d'une mauvaise solution, du moins en termes de performance.

Il se trouve que dans le cas de la fonction renverser, une boucle while est plus adaptée.

En effet, il suffit de parcourir les éléments de la liste lst avec une simple boucle, et d'ajouter ses éléments au fur et à mesure en tête d'une seconde liste, appelons-la r.

Ainsi, le premier élément de la liste lst se retrouve en dernière position dans la liste r, le deuxième élément de lst en avant-dernière position dans r, etc., jusqu'au dernier élément de lst qui se retrouve en première position dans r.

Une bonne image est celle d'une pile de feuilles de papier sur notre bureau : si on prend successivement chaque feuille au sommet de la pile pour former à côté une seconde pile, alors on aura inversé l'ordre des feuilles au final.

Ici, la liste lst joue le rôle de la première pile et la liste r celle de la seconde.

Pour mettre en œuvre le code, on commence par se donner deux variables : une variable r pour le résultat et une variable c pour parcourir la liste lst.

def renverser(lst):

r = None

c = lst

On parcourt ensuite la liste avec une boucle while, en ajoutant à chaque étape le premier élément de c en tête de la liste r, avant de passer à l'élément suivant.

while c is not None:

Cellule(c.valeur, r)

c = c.suivante

Enfin, il ne reste plus qu'à renvoyer la liste r une fois sorti de la boucle.

return r

Le programme ci-dessous contient l'intégralité du code.

def renverser(lst):

\"\"\"renvoie une liste contenant les éléments de lst dans l'ordre inverse\"\"\"

r = None

c = lst

while c is not None:

r = Cellule(c.valeur, r)

c = c.suivante

return r

def afficher(lst) :

\"\"\"affiche les éléments d'une liste\"\"\"

c = lst

while c is not None:

print(c.valeur,c.suivante)

c = c.suivante

print(\"l1 = \")

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

afficher(l1)

print(\"r1 = \")

r1 = renverser(l1)

afficher(r1)

Complexité. Il est clair que cette nouvelle fonction

directement proportionnel à la longueur de la liste lst, car le code fait un simple parcours de la liste, avec deux opérations élémentaires à chaque étape.

Ainsi, renverser une liste de 1000 éléments devient presque instantané, avec un millier d'opérations, là où notre fonction basée sur la concaténation utilisait un demi-million d'opérations.

","title":"Renverser une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Jusqu'à présent, nous avons délibérément choisi de ne jamais modifier les deux attributs valeur et suivante d'un objet de la classe Cellule. Une fois qu'un tel objet est construit, il n'est plus jamais modifié.

Cependant, rien ne nous empêcherait de le faire, intentionnellement ou accidentellement, car il reste toujours possible de modifier la valeur de ces attributs a posteriori avec des affectations.

Reprenons l'exemple de la liste 1,2,3 du début de cette séquence, construite avec

lst = Cellule(1, Cellule(2, Cellule(3, None)))

et que nous représentons ainsi :

Nous pouvons modifier la valeur du deuxième élément de la liste avec l'affectation suivante

lst.suivante.valeu = 4

On n alors la situation suivante :

C'est-à-dire avec la liste 1,3,8.

Ici, on vient de modifie le contenu de la liste,

en modifiant un attribut valeur.

Mais on peut également modifier la structure de la liste, en modifiant un attribut suivante.

Si par exemple on réalise maintenant l'affectation

lst.suivante.suivante =Cellule(5,None)

alors on se retrouve avec la situation suivante :

Ici, on a représenté que l'attribut suivante du deuxième élément pointait anciennement vers l'élément 3 (en pointillés) et qu'il pointe désormais vers un nouvel élément 5. La variable lst contient maintenant la liste 1,4,3.

","title":"Modification d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Puisque les listes peuvent être modifiées à posteriori, comme nous venons de l'expliquer, il peut être tentant d'en tirer profit pour écrire autrement certaines de nos opérations sur les listes.

Ainsi, pour réaliser la concaténation de deux listes, par exemple, il suffit de modifier l'attribut suivante du

dernier élément de la première liste pour lui donner la valeur de la seconde liste.

Cela semble une bonne idée. Mais il y a un risque.

Supposons que l'on construise deux listes 1,2,3

et 4,5 de la manière suivante :

l2 = Cellule(2, Cellule(3, None))

l1 = Cellule(1, l2)

l3 = Cellule(4, Cellule(5, None))

On note en particulier que la variable l2 contient toujours la liste 2,3, même si elle a servi depuis à construire la liste 1,2,3 stockée dans la variable l1.

S'il nous prend maintenant l'envie de concaténer les listes l1 et l3 en reliant le dernier élément de l1 au premier élément de l3, par exemple en appelant

une fonction concatener_en_place(l1, l3) qui ferait cela, alors on se retrouverait dans cette situation :

La variable l1 contient maintenant la liste 1,2,3,4,5, ce qui était recherché, mais la variable l2 ne contient plus la liste 2,3 mais la liste 2,3,4,5.

C'est là un effet de bord qui n'était peut-être pas du tout souhaité.

D'une manière générale, pouvoir accéder à une même donnée par deux chemins différents n'est pas un problème en soi, mais modifier ensuite la donnée par l'intermédiaire de l'un de ces chemins (ici l1) peut résulter en une modification non souhaitée de la valeur accessible par un autre chemin (ici l2).

Par ailleurs, que feraient deux appels supplémentaires à concatener_en_place(l1, l3)?

C'est pourquoi nous avons privilégié une approche où la concaténation, et plus généralement les opérations qui construisent des listes, renvoient de nouvelles listes plutôt que de modifier leurs arguments.

On peut remarquer que c'est là une approche également suivie par certaines constructions de Python. L'opération + de Python, par exemple, ne modifie pas ses arguments mais renvoie une nouvelle valeur, qu'il s'agisse d'entiers, de chaînes de caractères ou encore de tableaux.

Ainsi, si t est le tableau [1, 2], alors t + [3]

construit un nouveau tableau [1, 2, 3].

En ce sens, l'opération + se distingue d'autres opérations, comme .append, qui modifient leur argument.

Comme nous allons le voir dans la section suivante, cela ne nous empêche pas pour autant d'utiliser nos listes dans un style de programmation impératif.

","title":"Du danger des listes mutables"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Pour terminer cette séquence sur les listes chaînées, nous allons maintenant montrer comment encapsuler une liste chaînée dans un objet.

L'idée consiste à définir une nouvelle classe, Liste, qui possède un unique attribut, tete, qui contient une liste chaînée. On l'appelle tete car il désigne la tête de la liste, lorsque celle-ci n'est pas vide (et None sinon).

Le constructeur initialise l\"attribut tete avec la valeur None.

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

Autrement dit, un objet construit avec Liste() représente une liste vide.

On peut également introduire une méthode est_vide qui renvoie un booléen indiquant si la liste est vide.

def est_vide(self):

return self.tete is None

En effet, notre intention est d'encapsuler, c'est-à-dire de cacher, la représentation de la liste derrière cet objet. Pour cette raison, on ne souhaite pas que l'utilisateur de la classe Liste teste explicitement si l'attribut tete vaut None, mais qu'il utilise cette méthode est_vide.

On poursuit la construction de la classe Liste avec une méthode pour ajouter un élément en tête de la liste.

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

Cette méthode modifie l'attribut tete et ne renvoie rien. Si par exemple on exécute les quatre instructions ci-dessous :

lst = Liste()

lst.ajoute(3)

lst.ajoute(2)

lst.ajoute(1)

on obtient la situation suivante :

On a donc construit ainsi la liste 1,2,3, dans cet ordre.

On peut maintenant reformuler nos opérations, à savoir longueur, nieme_element, concatener ou encore renverser, comme autant de méthodes de la classe Liste.

Ainsi, on peut écrire par exemple

def longueur(self):

return longueur(self.tete)

qui ajoute à la classe Liste une méthode longueur, qui nous permet d'écrire lst.longueur(} pour obtenir la longueur de la liste lst.

Il est important de noter qu'il n'y a pas confusion ici entre la fonction longueur définie précédemment et la méthode longueur.

En particulier, la seconde est définie en appelant la première. Le langage Python est ainsi fait que, lorsqu'on écrit longueur (self.tete), il ne s'agit pas d'un appel récursif à la méthode longueur. (Un appel récursif s'écrirait self. longueur().) Si l'on trouve que donner le même nom à la fonction et à la méthode est source de confusion, on peut tout à fait choisir un nom différent pour la méthode, comme par exemple

def taille(self):

return longueur(self.tete)

Mieux encore, on peut donner à cette méthode le nom __len__ et Python nous permet alors d'écrire len(lst} comme pour un tableau.

En eflet, lorsque l'on écrit len en Python, ce n'est qu'un synonyme pour l'appel de méthode __len__().

De même, on peut ajouter à la classe Liste une méthode pour accéder au n-ième élément de la liste, c'est-à-dire une méthode qui va appeler notre fonction nieme_element sur self.tete.

Le nom de la méthode est arbitraire et nous pourrions choisir de conserver le nom nieme_element. Mais

là encore nous pouvons faire le choix d'un nom idiomatique en Python, à savoir __getitem__

def __getitem_ _(self, n):

return nieme_element(n, self.tete)

Ceci nous permet alors d'écrire lst{[i] pour accéder au i-ème élément de notre liste, exactement comme pour les tableaux.

Pour la fonction renverser, on fait le choix de nommer la méthode reverse car là encore OuiCar là encore c'est un nom qui existe déjà pour les tableaux de Python.

Programme - Encapsulation d'une liste dans un objet

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

def est_vide(self):

return self.tete is None

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

def __len__(self):

return longueurB(self.tete)

def __getitem__(self, n):

return nieme_element(n, self.tete)

def reverse(self) :

self.tete = renverser(self.tete)

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

lst = Liste()

print(lst.est_vide())

lst.ajoute(3)

print(lst.est_vide())

lst.ajoute(2)

lst.ajoute(1)

print(len(lst))

print(lst[1])

Enfin, le cas de la concaténation est plus subtil, car il s'agit de renvoyer une nouvelle liste, c'est-à-dire un nouvel objet. On choisit d'appeler la méthode __add__ qui correspond à la syntaxe + de Python.

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

Ainsi, on peut écrire lst+lst pour obtenir la liste 1,2,3,1,2,3.

","title":"Encapsulation dans un objet"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Intérêt d'une telle encapsulation. Il est multiple. D'une part, il cache la représentation de la structure à l'utilisateur.

Ainsi, celui qui utilise notre classe Liste n'a plus à manipuler explicitement la classe Cellule.

Mieux encore, il peut complètement ignorer l'existence de la classe Cellule.

De même, il ignore que la liste vide est représentée par la valeur None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le

code qui l'utilise n'ait besoin d'être modifié à son tour.

D'autre part, l'utilisation de classes et de méthodes nous permet de donner le même nom à toutes les méthodes qui sont de même nature.

Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide, ajoute, etc. Si nous avions utilisé de simples fonctions, il faudrait distinguer

liste _est_vide, pile est vide, ensemble _est_vide, etc.

","title":""},{"edit":"

"}],[{"text":"

Écrire une fonction listeN(n) qui reçoit en argument un entier n, supposé positif ou nul, et renvoie la liste des entiers 1,2,...,n, dans cet ordre. Si n = 0, la liste renvoyée est vide.

Tester avec :

l2 = listeN(5)

afficher(l2)

Résultat :

1 <__main__.Cellule object at 0x103540a20>

2 <__main__.Cellule object at 0x103540a58>

3 <__main__.Cellule object at 0x103540da0>

4 <__main__.Cellule object at 0x103540a90>

5 None

Attention les adresses mémoires ne seront pas les mêmes.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def listeN(n):

lst = None

while n > 0:

lst = Cellule(n, lst)

n -= 1

return lst

l2 = listeN(5)

afficher(l2)

"}],[{"text":"

Écrire une fonction affiche liste(lst) qui affiche, en utilisant la fonction print, tous les éléments de la liste lst, séparés par des espaces, suivis d'un retour chariot.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

affiche_liste(l2)

Le résultat est :

a b c d

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour éviter que print n’insère un retour chariot après chaque élément, on utilise print(..., end= \" \"), puis un unique print() à la fin de la liste.

Avec une récursivité :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

if lst is None:

print()

else :

print(lst.valeur, end=\" \")

affiche_liste(lst.suivante)

affiche_liste(l2)

Avec une itération :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

c = lst

while c is not None:

print(c.valeur, end=\" \")

c = c.suivante

print()

affiche_liste(l2)

"}],[{"text":"

Ecrire une procédure insertion_en_tete(lst,x) qui prend comme paramètres une liste lst et une valeur x et qui insère un nouvel élément en tête de la liste chaînée lst.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, None)))

affiche_liste(lst1)

insertion_en_tete(lst1,0)

affiche_liste(lst1)

Résultat :

1 2 3

0 1 2 3

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def insertion_en_tete(lst,x):

lst.suivante = Cellule(lst.valeur,lst.suivante)

lst.valeur = x

"}],[{"text":"

Ecrire une procédure insertion_en_queue(lst,x) qui prend comme paramètres une liste lst et une valeur x et qui insère un nouvel élément en queue de la liste chaînée lst.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, None)))

affiche_liste(lst1)

insertion_en_queue(lst1,4)

affiche_liste(lst1)

Résultat :

1 2 3

1 2 3 4

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def insertion_en_queue(lst,x):

if lst.suivante is None :

lst.suivante = Cellule(x,None)

else :

insertion_en_queue(lst.suivante,x)

"}],[{"text":"

Ecrire une procédure inserer_dans_liste(lst,x,posi) qui a comme paramètres :

- la liste lst;

- la valeur de l'élément;

- la position posi

et qui insère un nouvel élément de sorte qu'il se trouve à une position donnée dans la liste. La position est un entier et correspond au numéro du futur élément dans la liste. Le

premier élément porte le numéro 0.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, None)))

affiche_liste(lst1)

inserer_dans_liste(lst1,4,0)#posi en tete

affiche_liste(lst1)

inserer_dans_liste(lst1,8,2)#posi au milieu

affiche_liste(lst1)

inserer_dans_liste(lst1,7,4)#posi en queue

affiche_liste(lst1)

inserer_dans_liste(lst1,10,6)# indice trop grand

Résultat :

1 2 3

4 1 2 3

4 1 8 2 3

4 1 8 2 3 7

Traceback (most

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def inserer_dans_liste(lst,x,posi):

if posi == 0 :

if lst.suivante is not None:

lst.suivante = Cellule(lst.valeur,lst.suivante)

lst.valeur = x

else :

lst.suivante = Cellule(x,None)

elif lst.suivante is None :

raise IndexError(\"Problème d'indice\")

else :

inserer_dans_liste(lst.suivante,x,posi-1)

"}],[{"text":"

Ecrire une procédure sup_tete(lst) qui prend comme paramètres une liste lst et qui supprime le premier élément de la liste chaînée lst.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, None)))

affiche_liste(lst1)

sup_tete(lst1)

affiche_liste(lst1)

Résultat :

1 2 3

2 3

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def sup_tete(lst) :

lst.valeur = lst.suivante.valeur

lst.suivante = lst.suivante.suivante

"}],[{"text":"

Ecrire une procédure sup_queue(lst) qui prend comme paramètres une liste lst et qui supprime le dernier élément de la liste chaînée lst.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, None)))

affiche_liste(lst1)

sup_queue(lst1)

affiche_liste(lst1)

Résultat :

1 2 3

1 2

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def sup_queue(lst) :

if lst.suivante.suivante is None :

lst.suivante = None

else :

sup_queue(lst.suivante)

"}],[{"text":"

Ecrire une procédure sup_element(lst,posi) qui prend comme paramètres une liste lst, un entier pour la position et qui supprime l'élément en position posi dans la liste chaînée lst.

Attention, la numérotation dans la liste commence à 0.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, None))))

affiche_liste(lst1)

sup_element(lst1,1)

affiche_liste(lst1)

Résultat :

1 2 3 4

1 3 4

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def sup_element(lst,posi) :

if posi == 0 :

lst.valeur = lst.suivante.valeur

lst.suivante = lst.suivante.suivante

else :

sup_element(lst.suivante,posi-1)

"}],[{"text":"

Réécrire la fonction nieme_element

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Résultat :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme pour la fonction longueur, on se sert d’une

variable c pour parcourir la liste. On se sert également d’une variable i pour

mesurer notre avancement dans la liste. Il y a donc une double condition

d’arrêt à la boucle.

def nieme_element(n, lst):

i = 0

c = lst

while i < n and c is not None:

i += 1

c = c.suivante

if n < 0 or c is None:

raise IndexError(\"indice invalide\")

return c.valeur

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Note : la condition n < 0 nous préserve d’une valeur négative qui aurait été passée à la fonction nieme_element. Bien entendu, on aurait pu effectuer ce

test dès l’entrée de la fonction, avant même de parcourir la liste, ou encore supposer que n est positif ou nul.

"}],[{"text":"

Écrire une fonction occurrences(x, lst) qui renvoie le nombre d'occurrences de la valeur x dans la liste lst.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Résultat :

nb b : 3

nb a : 1

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Avec une fonction récursive :

def occurrences(x, lst):

if lst is None:

return 0

elif x == lst.valeur:

return 1 + occurrences(x, lst.suivante)

else:

return occurrences(x, lst.suivante)

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Avec une itération (boucle) :

def occurrences(x, lst):

n=0

c = lst

while c.suivante is not None :

if x == c.valeur:

n += 1

c = c.suivante

if x == c.valeur:

n += 1

return n

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

"}],[{"text":"

Écrire une fonction trouve(x, lst} qui renvoie le rang de la première occurrence de x dans lst, le cas échéant, et None sinon.

L'écrire comme une fonction récursive, puis avec une boucle while.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec ;

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

Résultat :

posi c : 2

posi a : 0

posi e : None

"},{"solution":"

Ici la version récursive est assez pénible à écrire, car

il faut tester si l’appel récursif a renvoyé None :

ef trouve(x, lst):

if lst is None:

return None

elif lst.valeur == x :

return 0

else:

r = trouve(x, lst.suivante)

if r == None:

return None

else:

return 1 + r

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

La boucle, en revanche, est plus simple à écrire :

def trouve(x, lst):

i=0

c = lst

while c is not None:

if c.valeur == x:

return i

c = c.suivante

i += 1

return None

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

"}],[{"text":"

Écrire une fonction récursive concatener_inverse(l1, l2)

qui renvoie le même résultat que concatener(renverser(l1), l2), mais sans appeler ces deux fonctions.

En déduire une fonction renverser qui a la même complexité que le programme renverser de la séquence.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

Résultat :

6 5 4 3 2 1 1 2 3 4 5 6

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On procède récursivement sur la structure de la

liste l1 :

def concatener_inverse(l1, l2):

if l1 is None:

return l2

else:

return concatener_inverse(l1.suivante, \\

Cellule(l1.valeur, l2))

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

La fonction renverser s’en déduit trivialement, en prenant une liste videdef renverser (1st):

return concatener_inverse(lst, None)

"}],[{"text":"

Écrire une fonction identiques(l1, l2) qui renvoie un booléen indiquant si les listes l1 et l2 sont identiques, c'est-à-dire contiennent exactement les mêmes éléments, dans le même ordre.

On suppose que l'on peut comparer les éléments de l1 et l2 avec l'égalité == de Python.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

Résultat :

True

False

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On le fait ici avec une fonction récursive. Il faut

prendre soin de bien traiter le cas où l’une ou l’autre des listes est vide :

def identiques(l1, l2):

if l1 is None:

return l2 is None

if l2 is None:

return l1 is None

return l1.valeur == l2.valeur \\

and identiques(l1.suivante, l2.suivante)

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

"}],[{"text":"

Écrire une fonction inserer(x, lst) qui prend en arguments un entier x et une liste d'entiers lst, supposée triée par ordre croissant, et qui renvoie une nouvelle liste dans laquelle x a été inséré à sa place

Ainsi, insérer la valeur 3 dans la liste 1,2, 5,8 renvoie la liste 1,2,3,5,8.

On suggère d'écrire inserer comme une fonction récursive.

Tester avec :

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

Résultat :

2 4 7 8 9 12

1 2 4 4 7 8 9 12 14

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas d'arrêt est double : soit la liste est vide,

soit x n’est pas plus grand que la valeur en tête de liste. Dans les deux cas, on ajoute x au début de lst. Sinon, on conserve le premier élément et on

insère x récursivement dans la liste lst.suivante.

def inserer(x, lst):

if lst is None or x <= lst.valeur:

return Cellule(x, lst)

else:

return Cellule(lst.valeur, inserer(x, lst.suivante))

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

"}],[{"text":"

En se servant de l'exercice précédent, écrire une fonction tri_par_insertion(lst) qui prend en argument une liste d'entiers lst et renvoie une nouvelle liste, contenant les mêmes éléments et triée par ordre croissant.

On suggère de l'écrire comme une fonction récursive.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Résultat :

5 8 7 1 3 6

1 3 5 6 7 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas de base correspond à une liste de longueur

au plus 1, pour laquelle il suffit de la renvoyer.

def tri_par_insertion(lst):

if lst is None or lst.suivante is None:

return lst

else:

return inserer(lst.valeur, \\

tri_par_insertion(lst.suivante))

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Note : on pourrait également écrire if longueur(ist) <= 1 mais ce serait calculer inutilement la longueur de la liste (calculer la longueur oblige à parcourir toute la liste), ce qui dégraderait les performances de ce programme.

"}],[{"text":"

Écrire une fonction liste_de_tableau(t} qui renvoie une liste qui contient les éléments du tableau t, dans le même ordre.

On suggère de l'écrire avec une boucle for.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec :

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

Résultat ;

[2, 4, 5, 7, 9, 10, 12]

2 4 5 7 9 10 12

"},{"solution":"

Pour préserver l’ordre des éléments, il faut prendre

soin de parcourir le tableau de la droite vers la gauche :

def liste_de_tableau(t):

lst = None

for i in range(len(t) - 1, -1, -1):

lst = Cellule(t[i], lst)

return lst

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

"}],[{"text":"

Écrire une fonction derniere_cellule(lst) qui renvoie l'adresse mémoire de la dernière cellule de la liste lst. On suppose la liste lst non vide.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

print(derniere_cellule(lst2))

Résultat :

<__main__.Cellule object at 0x10405f898>

<__main__.Cellule object at 0x10405fe48>

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def derniere_cellule(lst):

c = lst

while c.suivante is not None:

c = c.suivante

return c

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

"}],[{"text":"

En utilisant la fonction de l'exercice précédent, écrire une seconde fonction, concatener_en_place(l1, l2), qui réalise une concaténation en place des listes l1 et l2, c'est-à-dire qui relie la dernière cellule de l1 à la première cellule de l2. Cette fonction doit renvoyer la toute première cellule de la concaténation.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

Résultat :

5 8 7 1 3 6

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def concatener_en_place(l1, l2):

if l1 is None:

return l2

c = derniere_cellule(l1)

c.suivante = l2

return l1

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

"}],[{"text":"

Fonction de vérification d’une liste chaînée triée

Ecrire une fonction qui vérifie si une liste chaînée est triée par valeurs croissantes du champ Info.

04-**-Procédure d’insertion en tête de liste chaînée

Ecrire une procédure qui insère un nouvel élément en tête d’une liste chaînée.

05-**-Procédure d’insertion en queue de liste chaînée

Ecrire une procédure qui insère un nouvel élément en queue d’une liste chaînée.

06-**- Procédure d’insertion à une position donnée

Ecrire une procédure qui insère un nouvel élément de sorte qu'il se trouve à une position donnée

dans la liste. La position est un entier et correspond au numéro du futur élément dans la liste. Le

premier élément porte le numéro 1.

07-**- Procédure de suppression d’un élément d’une liste chaînée à

une position donnée

Ecrire une procédure qui supprime un élément d’une liste chaînée à une position donnée.

DVD-MIAGE Exercices Algorithmique

Exercices ch. 9, 10 et 11 Page 3/20

08-**- Fonction de calcul de moyenne des étudiants

Le département dans lequel vous êtes inscrit souhaite gérer les notes de ses étudiants. Les étudiants

ont pour identifiant leur numéro d’étudiant. Ils ont un nom et un prénom. Ces informations sont

stockées dans une liste chaînée dont chaque élément comporte aussi un champ moy pour la

moyenne de l'étudiant et un champ eval qui est un pointeur sur sa liste de notes. La liste de notes de

chaque étudiant est aussi une liste chaînée dont la tête est le champ eval de la cellule de l'étudiant.

On dispose des déclarations suivantes :

Types :

Ch10 = Chaine de 10 caractères

Ch30 = Chaine de 30 caractères

Ent

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 18 Octobre 2020; Clics : 1560

[[{"title":"SQL - Systèmes de Gestion de Bases de Données","posi":0},{"text":"

Après l’étape de modélisation des données, utilisant le modèle relationnel, vient l'étape de la mise en pratique.

Le système d'information repose sur un programme essentiel, le système de gestion de buses de données relationnel.

Ce dernier est un logiciel permettant :

- de créer des bases de données, c’est-à-dire des ensembles de tables ;

- de créer des tables en spécifiant leurs schémas ;

- de spécifier des contraintes d'intégrité, telles que les clés primaires et étrangères ou encore des contraintes de domaine ou des contraintes utilisateur ;

- d'ajouter des données à des tables, mais uniquement si ces entités

respectent les contraintes ;

- de mettre à jour ou de supprimer des données dans des tables et de supprimer des tables ;

- d'interroger les données grâce à des programmes écrits dans un langage de requêtes ;

- d'assurer la sûreté des données, par exemple en garantissant que même en cas de problème matériel (coupure de courant, défaut sur un disque les données sont récupérables.

De plus, le SGBD devant permettre des accès simultanés aux données de la part de plusieurs utilisateurs, il est souvent architecturé sur un modèle client-serveur.

Le serveur est le programme qui à effectivement accès aux données et les clients sont des programmes émettant des ordres (requête, mise à jour, etc.) et affichant les résultats de ces derniers.

Dans ce contexte multi-utilisateur, le SGBD permet de plus de définir des droits d'accès différents aux données selon les utilisateurs.

Ainsi, un SBGD possède des utilisateurs munis d’identifiants et de mots de passes (comme un système d’exploitation).

Les utilisateurs ont des droits différents (consultation simple de tables, mise

à jour de leurs tables ou droits d'administration permettant de configurer

le SGBD).

Un aspect fondamental des SGBD modernes et du langage SQL est que le programmeur de bases de données ne spécifie jamais comment récupérer les données. Il ne programme aucun algorithme, ne spécifie jamais de structure de données.

Certaines structures de données fixées sont connues

des SGBD : arbres, table de hachage.

Le programmeur avancé peut guider le SGBD dans le choix initial de représentation, mais il est la plupart du

temps fait automatiquement.

Au moment d'écrire sa requête, le programmeur n'indiquera jamais qu’il souhaite utiliser un tri fusion par exemple, mais simplement qu'il souhaite obtenir les données dans un certain ordre.

Le système fera alors le meilleur choix possible d'algorithme en fonction des informations à sa disposition (statistiques sur les données des tables, tailles de ces dernières, caractéristiques du système d’exploitation et du matériel sur lequel il s'exécute).

Dans ce contexte, SQL est parfois qualifié de langage déclaratif, c'est-à-dire un langage dans lequel on indique (on « déclare ») les résultats qu’on souhaite obtenir, pas la manière dont on souhaite les calculer.

"},{"text":""}],[{"text":"

Avant les années 1960, le principal moyen de stockage pour les ordinateurs était la bande magnétique.

Le traitement de données était donc réalisé en lots (batch en anglais), c'est-à-dire qu'une partie des données était rapatriée depuis la bande magnétique jusqu’en mémoire principale, traitée, puis les résultats affichés ou restockés sur bande. Puis le lot suivant de données était lu, traité et affiché, et ainsi de suite.

L'arrivée des systèmes à accès direct (comme les disquettes et disques durs) a changé la façon d’accéder aux données et les traitements que l’on pouvait espérer en faire.

En premier lieu, le modèle « hiérarchique » est proposé. Il reproduit, sur disque, les structures de données en mémoire.

Dans ce modèle, les données sont organisées en structures ou enregistrements (qui associent des clés à des données, comme les dictionnaires de Python).

Une particularité est que les enregistrements sont liés entre eux au moyen de pointeur, de manière à former

des listes chaînées ou des arbres (d’où le nom de système hiérarchique).

Les «requêtes» de l’époque sont donc semblables aux algorithmes de recherche dans ces structures de données.

Comme nous l'avons vu, Edgar F. Codd introduit en 1970 le modèle relationnel. Apparaissent à partir de cette époque des SGBD relationnels, comme System

R d'IBM, le premier à proposer une implémentation du langage SQL.

System R n'est cependant qu’un projet de recherche utilisé chez quelques industriels comme cas d'étude. Le premier SGBD commercial est Oracle, commercialisé par la société Relational Software en 1979 (devenue

depuis Oracle Corporation).

Les logiciels propriétaires tels qu'Oracle, mais aussi DB/2 d'IBM ou Sybase (maintenant SAP ASE), sont pendant des années la seule alternative viable pour les entreprises.

Avec le développement du Web au milieu des années 1990, le besoin de solutions logicielles moins onéreuses et plus ouvertes augmente.

En effet, les SGBD propriétaires étaient non seulement coûteux, mais aussi conçus pour fonctionner sur des serveurs aux architectures spécifiques, hors de portée des particuliers, des associations et des petites entreprises.

C’est dans ce contexte que naissent des alternatives telles que MySQL (maintenant MariaDB) en

1995 puis PostgreSQL en 1996. Ces dernières sont devenues au cours des 25 dernières années des logiciels robustes, capables de concurrencer dans de

nombreux cas les alternatives propriétaires.

En parallèle de l'évolution des systèmes, le langage SQL a lui aussi évolué. Cette évolution s'est faite de manière anarchique, de nombreux éditeurs de logiciels rajoutant leur propres extensions non standardisées.

Ce phénomène d’«enfermement» (vendor lock-in en anglais) est toujours d’actualité et rend difficile la présentation du langage SQL. Certaines opérations basiques doivent êtres déclinées selon tous les dialectes de SQL utilisés par les différents systèmes.

Une des raisons est le peu d'intérêt qu'ont les éditeurs

de systèmes commerciaux à faciliter la migration de leurs clients chez des systèmes concurrents.

","title":"Historique"},{"edit":"

Mettre ici les résultats.

"}],[{"text":"

Comme expliqué aux séquences précédentes, une action du monde réel (on parle parfois de processus métier) peut être modélisée par des ordres SQL donnés à un SGBD.

Si Alice (dont la carte a le code barre '19833284474405') emprunte le livre Ravage (dont l'ISBN est '978-2072534911') le 1er février 2020, la borne d'emprunt (qui exécute un programme graphique permettant de scanner les cartes et livres) eflectuera

l’ordre SQL suivant :

INSERT INTO emprunt VALUES

('19833284474405', '978-2072534911', '2020-02-15') ;

On voit ici que l’action d'emprunter se traduit par un seul ordre SQL.

Nous avons déjà vu qu'il est inutile de vérifier avant l'emprunt que le livre a effectivement été rendu (et pas juste redéposé en rayon sans passer par la borne).

En effet, si l'ISBN du livre est toujours dans la table emprunt, alors la contrainte d’intégrité faisant de l’attribut isbn une clé primaire sera violée et le SGBD renverra une erreur.

Le programme s’exécutant sur la borne pourra alors afficher un message d'erreur à l'usager.

","title":"Transactions"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Considérons maintenant une action plus complexe, consistant à sortir un livre de l'inventaire, par exemple s'il est en trop mauvais état pour être emprunté.

Ce processus d'apparence simple cache de nombreuses subtilités.

En effet, retirer une entrée de la table livre viole la contrainte de clé étrangère sur l’attribut isbn dans la table auteur_de.

Il faut donc d’abord retirer les lignes correspondantes dans cette table. Il peut y en avoir plusieurs si un livre à plusieurs auteurs. De plus, il peut être souhaitable, si

on à supprimé le dernier livre d’un auteur, de supprimer aussi cet auteur de la base.

Ce processus peut s'exprimer par plusieurs ordres SQL.

Supposons que l’on veuille supprimer le livre Les Aventures de Huckieberry Finn

d'ISBN ’978-2081509511?.

DELETE FROM auteur_de WHERE isbn = '7978-2081509511';

DELETE FROM auteur

WHERE NOT (a_id IN (SELECT a_id FROM auteur_de));

DELETE FROM livre WHERE isbn = '978-2081509511' ;

Le premier ordre supprime la référence au livre dans la table auteur_de.

Le deuxième ordre supprime de la table auteur tous les auteurs dont l’identifant (attribut a_id) n'apparaît pas dans la table auteur_de grâce à une requête imbriquée dans la clause WHERE.

Enfin, le livre est supprimé de la table livre par le troisième ordre.

Ces trois ordres forment un tout qu’on ne doit pas dissocier. En effet, considérons maintenant la situation suivante :

un usager a reposé le livre en rayon sans passer par une borne pour le rendre. Il reste donc dans la table

emprunt une référence vers l’ISBN de ce livre (contrainte de clé étrangère) et le dernier ordre et seulement celui-ci va échouer.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Ajoutons une telle entrée dans la table emprunt et regardons ce qui se produit :

INSERT INTO emprunt VALUES ('934701281931682','978-2081509511','2020-02-01');

DELETE FROM auteur_de WHERE isbn = '978-2081509511';

DELETE FROM auteur

WHERE NOT (a_id IN (SELECT a_id FROM auteur_de));

DELETE FROM livre WHERE isbn = '978-2081509511';

ERROR: update or delete on table \"livre\" violates foreignDETAIL: Key (isbn)=(978-2081509511) is still referenced

from table \"emprunt\"

SELECT * FROM auteur WHERE nom = 'Twain';

Nos données sont dans un état incohérent, car les deux premiers ordres DELETE sont exécutés sans problème, retirant de la base l’auteur du livre et la relation entre ce dernier et le livre, alors que livre est toujours présent dans la base (la dernière requête SELECT ne renvoie aucun résultat). On souhaite donc que, si l’un des trois ordres échoue, les trois ordres soient annulés.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Cette notion fondamentale des SGBD s’appelle une transaction. Une transaction est une séquence d'instructions SQL (requêtes, mises à jour) qui

forment un tout et doivent soit toutes réussir, soit toutes être annulées, afin de laisser la base dans un état cohérent.

Le langage SQL supporte bien évidemment les transactions. Pour déclarer qu’une suite d'ordres est une transaction, il suffit de la faire précéder de START TRANSACTION. On pourra alors la conclure par l'instruction COMMIT afin de valider la transaction.

L'instruction ROLLBACK permet de manuellement annuler la transaction. Il est à noter que si une erreur se produit lors d’une transaction, alors toutes les tables

sont remises dans leur état d'avant la transaction au moment du COMMIT ou du ROLLBACK (qui ont alors le même effet).

INSERT INTO emprunt VALUES ('934701281931582', '978-2081509511', '2020-02-01');

START TRANSACTION;

DELETE FROM auteur_de WHERE isbn = '978-2081509511';

DELETE FROM auteur

WHERE NOT (a_id IN (SELECT a_id FROM auteur_de));

DELETE FROM livre WHERE isbn = '978-2081509511';

COMMIT;

ERROR: update or delete on table “Livre” violates foreign

key constraint \"emprunt_isbn_fkey\" on table \"emprunt\"

DETAIL: Key (isbn)=(978-2081509511) is still referenced

from table \"emprunt\"

SELECT * FROM auteur WHERE nom = ’Twain”’;

ERROR: current transaction is aborted, commands ignored

until end of transaction block

ROLLBACK;

SELECT * FROM auteur WHERE nom = ‘Twain’;0 Twain | Mark

Comme on le voit, à l'issue de la transaction, c’est-à-dire après l'exécution de l’ordre ROLLBACK, la table auteur à été restaurée dans son état d'avant la

transaction.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On peut noter qu'une syntaxe populaire, ne faisant pas partie du standard, mais supportée par tous les SGBD modernes, est celle utilisant le mot clé BEGIN pour START TRANSACTION et END pour ROLLBACK/COMMIT :

BEGIN;

DELETE FROM auteur_de WHERE isbn = '978-2081509511';

DELETE FROM auteur

WHERE NOT (a_id IN (SELECT a_id FROM auteur_de));

DELETE FROM livre WHERE isbn = '978-2081509511';

END;

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Mettons en œuvre une transaction plus complexe maintenant, permettant d'ajouter l'auteur Mark Twain s’il n’est pas déjà dans la table auteur !.

START TRANSACTION;

SELECT * INTO mark_present

FROM auteur

WHERE nom = 'Twain' AND prenom = 'Mark';

SELECT MAX(a_id) AS m INTO max_a_id

FROM auteur

WHERE (SELECT COUNT(*) FROM mark_present) = 0;

INSERT INTO auteur

(SELECT m+1, 'Twain', 'Mark'’

FROM max_a_id WHERE m IS NOT NULL);

DROP TABLE mark_present;

DROP TABLE max_a_id;

COMMIT ;

La première requête sélectionne toutes les lignes de la table auteur pour lesquelles le nom et le prénom sont ceux de Mark Twain et sauve ce résultat dans la table mark_present.

Si Mark Twain est bien présent, alors (au moins) une ligne sera copiée dans cette table.

Si Mark Twain n’est pas présent, alors la table mark_present sera vide.

La deuxième requête est plus subtile. Elle sélectionne les plus grands a_id de la table auteur pour lesquels la table temporaire mark_present est vide (son « COUNT » vaut 0). On peut remarquer que cette condition est indépendante de la ligne que l’on considère.

Ainsi, si la table mark_present est vide, alors la condition est toujours vraie.

La requête va donc renvoyer le maximum de fois les a_id de la table, car toutes les lignes sont sélectionnées.

À l'inverse, si mark_present est non vide, alors la condition est toujours fausse et aucun a_id n’est sélectionné. Dans ce cas, la fonction

d’agrégation renvoie la valeur spéciale NULL.

Pour résumer, les deux premiers ordres SELECT ensemble ont pour effet de mettre dans une colonne m

d’une table temporaire max_a_id le plus grand identifiant présent dans la table auteur si Mark Twain en est absent et NULL s’il est présent.

Le dernier ordre utilise enfin un « INSERT avec SELECT ». Le SELECT imbriqué renvoie le triplet (m+1, ‘Twain’, Mark’) si la colonne m de la table max_a_id est non NULL. Comme dans ce cas-ci m contient le plus grand

a_id de la table auteur, m+1 est un nouvel identifiant et est donc bien une clé primaire valide.

Si m est NULL, aucune insertion n'est faite (car Mark

Twain est déjà présent).

Les deux derniers ordres DROP détruisent les tables temporaires créées dans cette transaction.

Notons que si un problème survient durant la transaction, l'ordre ROLLBACK aura aussi pour effet de supprimer les tables temporaires créées pendant la transaction.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les propriétés ACID sont quatre garanties offertes par les SGBD relationnels concernant les transactions.

L'acronyme ACID est constitué des initiales des quatre propriétés : Atomicité, Isolation, Cohérence, Durabilité.

Atomicité : Par ce terme, on désigne le fait qu’une transaction est «tout ou rien».

Soit la transaction est arrivée à son terme, et les données sont alors modifiées, soit elle a échoué, et toutes les modifications sont annulées pour restaurer la base de données dans l’état où elle était avant la transaction.

Cohérence : Les transactions doivent faire passer la base d’un état cohérent à un autre état cohérent.

À l'issue d’une transaction, en particulier, toutes les contraintes d'intégrité doivent être vérifiées.

Isolation : Si deux transactions s’exécutent simultanément, alors leur exécution doit produire le même effet que si on les avait exécutées l’une

après l'autre (une transaction ne peut en particulier pas observer un état intermédiaire où certaines modifications n’ont pas été validées par un COMMIT).

Durabilité : Une transaction validée par un COMMIT est valide « pour de bon ».

Le système s’assure donc que, quels que soient les problèmes logiciels ou matériels qui pourraient survenir (défaillance de disque dur, panne de courant, etc.), les mises à jour d’une transaction validée ne sont jamais perdu.

","title":"Propriétés ACID"},{"edit":"

"}],[{"text":"

Nous illustrons la propriété d'isolation avec l'exemple suivant. Supposons que l’on tente d'exécuter de manière simultanée deux copies de la transaction

«ajout de Mark Twain si absent» décrite plus haut.

Une manière simple de procéder consiste à ouvrir deux connexions à la base de données et de rentrer les deux séries d’ordres dans chacune de ces connexions.

START TRANSACTION;

SELECT * INTO mark_present

FROM auteur

WHERE nom = 'Twain'

AND prenom = 'Mark’;

SELECT MAX(a.id) AS m

INTO max_a_id

FROM auteur

WHERE (SELECT COUNT (*)

FROM mark_present) = 0;

INSERT INTO auteur (SELECT m+1, 'Twain', 'Mark'

FROM max_a_id

WHERE m IS NOT NULL);

DROP TABLE mark_present;

DROP TABLE max_a_id;

COMMIT ;

START TRANSACTION;

SELECT * INTO mark_present

FROM auteur

WHERE nom = 'Twain'

AND prenom = 'Mark’;

SELECT MAX(a.id) AS m

INTO max_a_id

FROM auteur

WHERE (SELECT COUNT (*)

FROM mark_present) = 0;

INSERT INTO auteur (SELECT m+1, 'Twain', 'Mark'

FROM max_a_id

WHERE m IS NOT NULL);

DROP TABLE mark_present;

DROP TABLE max_a_id;

COMMIT

Supposons que ces deux transactions soient envoyées au même moment au SGBD (par exemple parce que deux documentalistes souhaitent ajouter Mark Twain). Si ces deux transactions sont exécutées l’une après l'autre :

- la première ajoute Mark Twain dans la base;

- la seconde, trouvant Mark Twain dans la base, ne fait rien.

Si ces deux transactions étaient exécutées en parallèle de façon naïve, leurs ordres pourraient s’entremêler de la façon suivante :

- la transaction de gauche recherche Mark Twain et ne le trouve pas;

--la transaction de droite recherche Mark Twain et ne le trouve pas non plus ;

- la transaction de gauche détermine un certain identifiant et ajoute Mark Twain ;

- la transaction de gauche est validée par son COMMIT;

- la transaction de droite détermine le même identifiant (car elle travaille sur la version de la table telle qu’elle était en début de transaction) et tente d'ajouter Mark Twain, mais viole alors la contrainte de clé

Le modèle ACID interdit un tel comportement, car le résultat de l'exécution séquentielle {tout se passe bien car la deuxième transaction ne fait rien) est différent de l'exécution en parallèle des deux transactions.

Un système dans lequel cela serait possible ne posséderait pas la propriété d'isolation.

En pratique, les SGBD modernes évitent cette situation en bloquant la deuxième transaction dès qu'elle accède à une table en cours d'utilisation par une autre transaction.

Dans notre scénario, la transaction de droite serait «bloquée» sur son premier SELECT (qui détermine si Mark Twain est présent), tant que la transaction de gauche n’a pas exécuté son COMMIT. Elle sera alors

débloquée et ne fera rien, car le SELECT trouvera Mark Twain dans la table.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Nous terminons ce tour d'horizon des SGBDSs par une courte introduction à l’utilisation d’un SGBD depuis un langage de programmation.

Nous utilisons Python, mais les concepts présentés ici sont facilement transposables dans d’autres langages (tels que PHP pour la création d’un site web

riche).

L'une des difficultés d'une telle présentation repose sur le fait que, pour chaque SGBD existant, certaines lignes spécifiques propres à ce SGBD sont nécessaires.

Ainsi, ces lignes seront différentes selon que l’on se connecte à PostgreSQL, MariaDB ou encore Oracle.

Un programme (simple) interagissant avec un SGBD effectue généralement les actions suivantes :

1. Connexion au SGBD. C’est lors de cette phase que l’on spécifie où se trouve le SGBD (par exemple en donnant son adresse IP), le nom d'utilisateur et le mot de passe, ainsi que d’autres paramètres système.

2. Envoi d'ordres au SGDB. On crée (le plus souvent dans des chaînes de caractères) des ordres SQL.

3. On récupère les données correspondant aux résultats dans des structures de données du langage (par exemple dans des tableaux Python).

4. On peut ensuite exécuter du code Python sur les données récupérées.

","title":"interaction entre un SGBD et un programme"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le programme ci-dessus importe en premier lieu le module mariadb, qui permet de se connecter au SGBD MariaDB (mysql). Si l’on souhaite se connecter à un autre SGBD), il faudra changer cette ligne pour charger le bon module.

Attention, si le module mariadb n\"est pas présent sur votre ordinateur. Il faut l'importer avec le terminale de commande (cmd) avec la commande :

pip3 install mariadb

Un aspect important du langage Python est que ces concepteurs ont défini une interface unifiée d'accès aux bases de données.

Ainsi, même si les SGBD visés sont différents, les méthodes Python utilisées seront toujours les mêmes, ce qui rend le code facilement portable d'un SGBD à un autre.

Programme — SELECT depuis Python

import mariadb as sdbd

#Entrer l'adresse IP du serveur ou le nom de domaine

HOST = \"217.182.207.90\" # ou \"domaine.com\"

#Le nom de la base de données

DATABASE = \"DBuser1\" #changer le ? par le numero donnée par le professeur

#Le nom de l'utilisateur de la DB

USER = \"user?\"

# Le mot de passe de l'utilisateur

PASSWORD = \"lemotdepasse\"

#connexion à la SGDB

cnx = sdbd.connect(host=HOST, database=DATABASE, user=USER, password=PASSWORD)

print(\"Connecté à:\", cnx.get_server_info())

c = cnx.cursor()

c.execute (\"SELECT * FROM livre WHERE annee < 1990\")

for l in c.fetchall():

print(l[0], l[2])

cnx.close()

Tester le code et mettre les résultats ci-dessous.

Nous avons choisi d'importer le module mariadb sous le nom générique sgbd ce qui évitera de devoir changer de nom dans la suite du programme si on change

de SGBD.

Le programme établit ensuite une connexion vers le SGBD. Il utilise pour cela la fonction connect du module. Cette dernière prend en argument des paramètres nommés.

Nous en donnons trois ici :

le paramètre host permet de spécifier le nom ou l'adresse du serveur et les paramètres user

et password permettent de donner le nom d'utilisateur et le mot de passe à utiliser pour se connecter au SGBD.

Le résultat de cet appel est un objet représentant la connexion au serveur (une exception est levée si jamais la connexion échoue).

L'objet cnx est celui qui est utilisé dans toute la suite

pour communiquer avec le SGBD.

La première chose à faire est la création

d'un curseur (variable c) au moyen de la méthode .cursor() de l’objet de connexion.

Un curseur représente essentiellement un ordre SQL.

Les deux principales méthodes que nous présentons sur les curseurs sont les suivantes :

- execute(s, p) permet d'exécuter un ordre SQL s, Ce dernier est simplement représenté par une chaîne de caractères Python, pouvant contenir une succession d'ordres séparés par des « ; ». Le paramètre p est

optionnel et est un tableau de valeurs Python dont l’utilisation sera détaillée dans la suite.

Notons que cette méthode ne renvoie aucun résultat.

Elle transmet juste l’ordre SQL au SGBD, qui va calculer un résultat.

- fetchall() renvoie tous les résultats du dernier ordre passé, sous la forme d’un tableau de n-uplets de valeurs Python. Chaque n-uplet représente une ligne de résultat de la requête.

Les valeurs sont ordonnées comme pour le résultat d’un SELECT. Un appel à fetchall() « réinitialise » le curseur. Si on appelle fetchall() deux fois, le deuxième appel renverra un tableau vide. Il faut ré-exécuter une requête pour obtenir de nouveau un résultat.

Dans le programme ci-dessus, on a donc exécuté une requête renvoyant tous les livres dont l’année est inférieure à 1990.

Comme on le voit, les valeurs ont été automatiquement traduites : les chaînes de caractères SQL (type VARCHAR) sont représentées par des chaînes

de caractères Python. Les entiers (type INTEGER) sont devenus des entiers Python.

Le programme parcourt cette liste de n-uplets au moyen d’une boucle for et affiche que le titre et l’année. Pour cela, il accède aux éléments d’indices 0 et 2 de chaque n-uplet.

Enfin, le programme se termine en fermant la connexion vers le SGBD. La méthode .close() est similaire à celle utilisée sur les descripteurs de fichiers et permet de libérer les ressources associées à la connexion (côté Python et côté SGBD).

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Une fonctionnalité importante est la possibilité de pouvoir insérer dans des ordres SQL des valeurs venant du monde Python, par exemple saisies par

l'utilisateur.

Nous illustrons cela avec le programme ci-dessous. Dans ce dernier, on demande à l'utilisateur de saisir une chaîne de caractères.

On veut ensuite exécuter la requête SELECT * FROM livre WHERE titre LIKE ’%s%' où s est la chaîne saisie par l'utilisateur. Nous utilisons ici la facilité fournie par la méthode .execute().

Programme — Recherche paramétrée

import mariadb as sdbd

#Entrer l'adresse IP du serveur ou le nom de domaine

HOST = \"217.182.207.90\" # ou \"domaine.com\"

#Le nom de la base de données

DATABASE = \"DBuser1\" #changer le ? par le numero donnée par le professeur

#Le nom de l'utilisateur de la DB

USER = \"user?\"

# Le mot de passe de l'utilisateur

PASSWORD = \"motdepasse\"

#connexion à la SGDB

cnx = sdbd.connect(host=HOST, database=DATABASE, user=USER, password=PASSWORD)

print(\"Connected to:\", cnx.get_server_info())

c = cnx.cursor()

texte = input (\"Texte à rechercher dans le titre :\")

c = cnx.cursor()

motif = '%' + texte + '%';

c.execute(\"SELECT * FROM livre WHERE titre LIKE %s\", \\

[ motif ])

for l in c.fetchall():

print(l[0], l[2])

cnx.close()

Il est possible de laisser dans la requête des «trous» dénotés par les caractères « %s ». Ces trous sont ensuite remplacés par les valeurs se trouvant dans le tableau passé en second paramètre à .execute() (le premier trou est remplacé par la première valeur du tableau et ainsi de suite).

Ainsi, si l'utilisateur saisit la chaîne Ast, alors la variable

motif contiendra la chaîne '%Ast%’.

La requête envoyée au SGBD sera alors

la suivante :

SELECT * FROM livre WHERE titre LIKE '%Ast%'

Il serait tentant de créer ia requête directement en Python au moyen de concaténations. On pourrait ainsi écrire directement

c.execute(\"SELECT * FROM livre WHERE titre LIKE '\" + motif + \"'\")

Cette approche est à proscrire et ne doit en aucun cas être utilisée?. En effet, le code ci-dessus est particulièrement fragile et peut être modifié par un utilisateur mal intentionné.

Ce dernier pourraît par exemple saisir comme texte :

'; DROP TABLE emprunt; SELECT * FROM livre WHERE titre = '

La requête formée et envoyée au SGBD serait alors :

SELECT * FROM livre WHERE titre LIKE '%';

DROP TABLE emprunt ;

SELECT * FROM livre WHERE titre = '%';

Le SGBD exécutera alors les ordres en séquence et en particulier le deuxième lui indiquant de supprimer la table emprunt.

Une telle subversion s'appelle une injection de code SQL. De nombreuses failles de sécurité » des sites

web sont en fait basées sur des injections de code SQL. Une telle faille n’est pas présente dans le programme ci-dessus. En effet, ce dernier laisse le soin à la méthode execute d'insérer le texte. Cette dernière va donc correctement échapper la chaîne de caractères et le programme effectuera la requête inoffensive

SELECT * FROM livre WHERE titre LIKE '%';DROP TABLE emprunt;SELECT * FROM livre WHERE titre = '%';

où toute la partie soulignée fait partie de la chaîne de caractères recherchée.

Cette requête essaye de trouver un livre dont le titre est littéralement

'; DROP TABLE emprunt; SELECT * FROM livre WHERE titre = '

","title":"Ordres paramétrés"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Pour chacun des scénarios suivant dire laquelle des quatre propriétés ACID est mise en jeu.

1. Une transaction tente d'insérer 20 lignes dans une table. L'insertion

de la 19° ligne échoue, à cause d’une contrainte de clé primaire. La

transaction est annulée et ancune des lignes ne se retrouve dans la

table.

2. Une table T2 contient des clés étrangères, référençant les clés d’une

table T,. On exécute une transaction arbitraire qui modifie T2. Après

la transaction 72 contient toujours des clés étrangères.

3. On exécute intégralement une transaction, validée par un « COMMIT ».

La machine exécutant le SGBD subit une panne de courant. Au redé-

marrage, l'effet de la transaction à bien été pris en compte.

4. Sur une table T contenant une colonne n de type INTEGER, on exécute

deux transaction, « en même temps ». La première ajoute 1 à toutes

les cases de la colonne n et la seconde retire 1 à ces même cases. Le

contenu de la table T après exécution (sans erreur) est le même.

Solution page 495 0

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

1. Atomicité.

2. Cohérence.

3. Durabilité.

4. Isolation.

"}],[{"text":"

On considère la base de données de la médiathèque. On suppose qu'un utilisateur à perdu sa carte, dont le code barre est '11111111111111'. Un employé lui crée une nouvelle carte, dont le code barre est '222222222222222'.

Donner une transaction permettant de réaliser le processus de « remplacement de carte ».

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On doit modifier deux tables au sein de la même

transaction. Attention, on ne peut pas brutalement mettre à jour la table emprunt pour changer le code barre, ni la table usager, car il y a une contrainte de clé étrangère sur le code_barre. On procède donc de la façon suivante :

START TRANSACTION;

SELECT * INTO tmp FROM emprunt

WHERE code_barre = '111111111111111';

DELETE FROM emprunt WHERE code_barre = '111111111111111';

UPDATE usager SET code_barre = '222222222222222'

WHERE code_barre = '111111111111111';

INSERT INTO emprunt

(SELECT '222222222222222', isbn, retour FROM tmp);

DROP TABLE tmp;

COMMIT;

Le premier ordre sauvegarde dans une table temporaire tous les emprunts.

Ensuite, on modifie la table usager. Comme il n’y a plus d'emprunt correspondant à cet usager,la mise à jour ne viole pas de contrainte.

On peut ensuite réinsérer les lignes sauvegardées en utilisant la valeur fixe '222222222222222'. On n'oublie pas de détruire la table temporaire en fin de transaction.

"}],[{"text":"

Sur un site web de réservation de billets de trains, un usager peut consulter la liste des billets qui répondent à certains critères (destination, date, prix, etc.).

Lorsqu'il trouve un billet à sa convenance, il peut le

sélectionner puis l’acheter.

On suppose que la base de données du site stocke tous les billets disponibles dans une unique table billet_a_vendre où les billets possèdent

un attribut « id INTEGER PRIMARY KEY » et d’autres attributs que l’on ne précise pas.

Les billets vendus sont stockés dans une table « billet_vendu », ayant le même schéma que «billet_a_vendre».

On suppose enfin que la recherche se fait par un simple

SELECT id FROM BILLET_A_ VENDRE WHERE ...;

où les critères sont ceux cochés sur le site.

1. Étant donné un identifiant de billet, donner le code SQL de la transaction.

2 Expliquer pourquoi il est possible que quelqu'un trouve un billet à sa convenance, mais qu’au moment de l'achat le billet ne soit plus disponible.

3. Pour « corriger » le problème précédant, on décide de mettre la recherche et l'achat dans la même transaction. Quel nouveau problème (bien plus grave) est causé par cette approche ?

Solution page 496 D

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

1. Voici la transaction :

START TRANSACTION;

INSERT INTO billet_vendu

(SELECT *

FROM billet_a_vendre

WHERE id = 1);

DELETE FROM billet_a_vendre WHERE id = i;

COMMIT ;

2. Le « SELECT ... » permettant de rechercher un billet peut s'exécuter en parallèle avec un achat. Supposons qu’il reste un billet disponible et deux acheteurs. Le premier acheteur trouve ce billet avec un « SELECT ». Le second acheteur trouve aussi ce billet. Les deux entament une transaction d'achat (celle trouvée à la question 1). Si la transaction réussit pour le premier acheteur, alors elle va échouer pour le second acheteur (le « SELECT » imbriqué ne va rien renvoyer).

3. Si on met tout le processus de recherche et d'achat dans une même transaction, alors cela veut dire que deux utilisateurs ne peuvent pas chercher en même temps, car le SGBD va bloquer toutes les transactions, sauf une, pour garantir la propriété d'isolation.

"}],[{"text":"

Considérons une table :

CREATE TABLE T (id INTEGER PRIMARY KEY, jour DATE, heure TIME, tmp DECIMAL(5,2));

Cette table permet d'enregistrer des relevés de température faits par une sonde. Chaque relevé possède un identifiant unique, le jour du relevé, l'heure

du relevé et la température relevée.

Supposons données trois valeurs j (un

jour),h (une heure) et t une température.

Écrire une transaction qui ajoute la nouvelle entrée en choisissant automatiquement un nouvel identifiant.

On pourra, dans un premier temps, considérer qu’il y a des données dans la table T, puis complexifier la transaction pour gérer le cas de la table vide.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

START TRANSACTION;

CREATE TABLE id_max_tmp (id INTEGER) ;

INSERT INTO id_max_tmp VALUES (-1);

INSERT INTO id_max_ tmp (SELECT MAX(id) FROM T);

INSERT INTO T (SELECT 1+MAX(id), j, h, t

FROM id_max_tmp

WHERE NOT (id IS NULL));

DROP TABLE id_max_tmp;

COMMIT;

La transaction crée une table temporaire id_max_tmp. On y insère une valeur par défaut valant -1. On y insère ensuite le plus grand identifiant trouvé dans la table T. Si la table T est vide, cette requête insère NULL dans la table id_max_tmp. Si la table est non vide, elle insère le plus grand identifiant. table id_max_tmp et on lui ajoute 1.

On l'utilise comme valeur d'insertion avec les constantes j, h et t.

On détruit ensuite la table temporaire.

"}],[{"text":"

Considérons la table T des relevés de température de l’exercice précédent. On considère deux ordres exécutés en parallèle :

SELECT MIN(jour) FROM T WHERE tmp >= 40;

qui renvoie le jour la plus ancien pour lequel la température a dépassé 40°.

UPDATE T SET tmp = tmp * 1.8 + 32;

qui convertit toutes les températures en degrés Farenheit.

Est-ce que la propriété ACID d'isolation garantit que la requête SELECT MIN... , renvoie toujours le même résultat quel que soit l’ordre d'exécution

des deux requêtes ?

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Exercice 164, page 343 Non, la propriété d'isolation n'offre pas cette ga-

rantie. Elle permet juste de s’assurer que la requête « SELECT MIN... »

donnera un résultat qui correspond soit à une exécution où elle précède en-

tièrement la mise à jour, soit à une exécution où elle suit entièrement la mise

à jour. En d’autres termes, la requête ne peut pas observer une table T où

seulement une partie des lignes ont été mises à jour.

"}],[{"text":"

En s'inspirant du programme python de connexion à une SGBD, écrire un programme Python qui sauvegarde l’intégralité de la table usager dans un fichier CSV nommé usager.csv.

On pourra utiliser le module Python csv

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

import mariadb

import csv

with open(\"usager.csv\", \"w\") as fichier:

csvf = csv.writer(fichier)

#on écrit l'en-tête

csvf.writerow([\"nom\", \"prenom\", “adresse\" ,\\

“cp\", \"ville\", \"email\", \"code _barre\"])

#on se connecte à la base

cnx = mariadb.connect(host=\"localhost\", \\

user=\"moi\", password=\"secret\")

c = cnx.cursor()

#on exécute la requête renvoyant tous les livres

c.execute(\"SELECT * FROM livre\")

#on écrit chaque ligne dans Le fichier

for l in c.fetchall(0):

csvf.writerow(l)

cnx.close()

"}],[{"text":"

En s'inspirant du programme python sur les SGBD, écrire un programme Python qui demande à l'utilisateur de saisir deux années, recherche tous les livres publiés entre ces deux années et crée un fichier HTML contenant une table présentant les résultats

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

import mariadb

a1 = int(input(\"Saisir la première année : \"))

a2 = int(input(\"Saisir la deuxième année : \"))

with open(\"res.html\", \"w\") as fichier:

fichier.write(\"\"\"</DOCTYPE html>

<html>

<body><table>\"\"\")

cnx = mariadb.connect(host=\"localhost\", \\

user=\"moi\", password=\"secret\")

c = cnx.cursor()

#on exécute la requête renvoyant tous les livres

c.execute(\"\"\"SELECT * FROM livre

WHERE annee >= %s AND annee <= %s\"\"\", \\

[a1, a2])

for lig in in c.fetchall():

fichier.write(\"<tr>\")

for col in lig:

fichier.write(\"<td>\")

fichier.write(str(col)

fichier.write(\"</td>\")

fichier.write(\"</tr>\\n\")

fichier.write(\"</table></body></html>\")

cnx.close()

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 7 Octobre 2020; Mis à jour : 7 Octobre 2020; Clics : 1338

[[{"title":"Représentation approximative des nombres réels","posi":0},{"text":"

Dans les séquences précédentes, nous avons vu que le langage Python permet de calculer avec des nombres déchmaux particuliers appelés nombres flottants.

Nous allons voir dans cette séquence que ces nombres ont un encodage très compact, sur 32 ou 64 bits, qui permet de représenter des nombres très grands, bien au-delà de ce qu'il est possible de représenter avec un codage des entiers sur le même nombre de bits, mais également de très petits nombres.

"},{"text":""}],[{"text":"

L'encodage des nombres flottants est inspiré de

l'écriture scientifique des nombres décimaux qui se compose d'un signe (+ ou - }, d’un nombre décimal m, appelé mantis ompris dans l'intervalle [ 1 , 10 [ (1 inclus et 10 exclu) et d'un entier relatif n appelé exposant.

Par exemple, avec cette notation,

2156 s'écrit +2,156 x 10³

","title":"Écriture scientifique"},{"edit":"

Mettre le résultat ici de la requête sql.

"},{"text":"

Ainsi, de manière générale, l'écriture scientifique d’un nombre décimal est de la forine :

avec m la mantis et n l'exposant.

On note en toute rigueur que le nombre 0 ne peut pas être représenté avec cette écriture.

"}],[{"text":"

La représentation des nombres flottants ct les opérations arithmétiques qui les accompagnent ont été définies dans la norme internationale IEEE 754.

C'est la norme la plus couramment utilisée dans les ordinateurs.

Selon la précision ou l'intervalle de représentation souhaité, la norme définit un format de données sur 32 bits, appelé single précision où binary32, ct un autre sur 64 bits, appelé double précision où binary64.

Il existe également des versions étendues de ces formats dont nous ne parlerons pas ici.

Dans les deux cas, la représentation d'un nombre fottant est similaire à l'écriture scientifique d’un nombre décimal, À savoir une décomposition en trois parties : un signe s. une mantisse m el un exposant n.

De manière générale, un nombre flottant à la forme suivante.

(-1)S x m x 2( n - d )

Les différences entre la norme IREE 754 ot l'écriture scientifique sont premièremont que la base choisie est maintenant la base 2, ensuite que la mantisse est donc dans l'intervalle [ 1 , 2 [, et enfin que l'exposant n'est décalé (ou biaisé) d'une valcur d qui dépend du format choisi (32 ou 64 bits).

Dans le format 32 bits, représenté par ie schéma ci-dessous, le bit de poids fort est utilisé pour représenter le signe s (avec 0 pour le signe +), les 8 bits suivants sont réservés pour stocker la valeur de l'exposant n et les 23 servent à décrire la mantisse.

1bit | 8bits | 23bits

signe|exposant| mantisse

1 |01010111|01010101 01110111 1101011

Afin de représenter des exposants positifs et négatifs, la norme IEEE 754 n'utilise pas l'encodage par complément à 2 des entiers relatifs, mais une technique qui consiste à stocker l'exposant de manière décalée sous la forme d'un nombre non signé.

Ainsi, l'exposant décalé n est entre 0 et 255. Pour le format un entier sur 8 bits qui représente des entiers

32 bits, l'exposant n est décalé avec d = 127, ce qui permet de représenter des 127,128. Néanmoins, les valeurs 0 et 255 exposants signés dans l'intervalle

étant réservées pour représenter des nombres particuliers (voir ci-dessous), les exposants signés sont donc ceux de l'intervalle [-126, 127].

La mantisse m étant toujours comprise dans l'intervalle [1 , 2 [, elle représente un nombre de la forme 1 xx xx c'est-à-dire un nombre commeparaZU.1. Norme IEEE /b4 253$

de précision, les 23 bits dédiés à la mantisse sont uniquement utilisés pour

représenter les chiffres après la virgule, qu'on appelle la fraction. Ainsi, si

les 23 bits dédiés à la mantisse sont b1 bo... b23, alors la mantisse représente

le nombre

1+bhx2 4h x 224... bg x 2729

Par exemple, le mot de 32 bits suivant

signe exposant fraction

RSS PRE ——————

T 10000110 10101101100000000000000

représente le nombre décimal calculé ainsi :

signe = 1!

exposant = (2749522) 197

= (128+4+2)—127

= 131-127

imantisse =

Soit, au final, le nombre décimal suivant :

—1,677734875 x 27 = 214,75

Coucernant les deux formats, la différence entre les encodages 32 et 64

bits est simplement la valeur d du décalage pour l'exposant et le nombre de

bits alloués pour la fraction f de la mantisse m et l’exposant n. Le tableau

ci-dessous résume les deux encodages.

! Bbits [| 23b#s |(-1x1/xate nn |

1lbits | S2bits [(-1) x1,f x 21671029)

Aïnsi, en simple précision (32 bits), les nombres flottants positifs peuvent

représenter les nombres décimaux compris (approximativement) dans l'in-

tervalle 107%, 105$], tandis qu'en double précision, l'intervalle des nombres254 Chapitre 20. Représentation approximative des nombres réels

Valeurs spéciales. Tel que nous l'avons défini jusqu'ici, le format des

nombres Aottants ne permet pas de représenter le nombre 0. En effet, puisque

un nombre flottant sur 32 bits correspond à la formule (—1}° x 1, / x gte—127), la forme L, f de la mantisse interdit la représentation du 0. Pour remédier

à ce problème, la norme IEEE 754 utilise les valeurs de l'exposant restées

jusqu’à présent inutilisées, à savoir 0 et 235, pour représenter le nombre 0

mais aussi d’autres valeurs spéciales.

Ainsi, le nombre 0 est représenté par le signe 0, un exposant 0 et une

mantisse 0. En fait, la norme reconnaît deux nombres 0 : le Q positif, noté

+6, qui est celui que nous venons de décrire, et le O négatif, noté —0, qui est

celui avec un bé de signe à 1.

La norme permet également de représenter deux infinis, notés —:x et

+oo, en utilisant la valeur 255 de l’exposant el nne mautisse à Ô (le bit de

signe étant utilisé pour représenter le signe de ces infinis). Ces deux infinis

sont utilisés pour indiquer des dépassements de capacité.

Eufin, une valeur spéciale, notée NaN (pour Mot a Number), permet de

représenter les résultats d'opérations invalides comme 0/0, 4/-T où encore

O0 x +50. Cette valeur est encodée avec nn signe à 0, un exposant à 255 et

importe quelle mantisse diflérente de 0.

Les encodages de ces valeurs spéciales sont résumés dans le tableau ci-

dessous.

où 0 0 | +0

1 0 0 —0

0 255 0 | +0

1 255 0 x

0 | 255 £20 NaN

Nombres dénormalisés. Comme nous l'avons vu plus haut, si l'exposant

d’un nombre flottant (sur 32 bits) est compris entre 1 ct 254, alors la valeur

représentée par l'encodage est (—1)$ x 1, f x 2127), Les nombres représen-

. Avec cet encodage, le plus

tés ainsi sont les nombres flottants normal.

petit nombre décimal positif représentable est done 27126 (soit + 107%).

Maintenant, puisque la mantisse est. implicitement de la forme 1. f, il n’y à

pas de nombres représentables dans l'intervalle {0,271%[, alors qu'il y en à

2% dans l'intervalle [1 x 27126,9 x 27167 2 [2-16 97128],

Afin de rééquilibrer la représentation des nombres autour de 0, là norme

IEEE 754 permet d'encoder des nombres de la forme

(—1)° x 0, f x 27126

aver nine mantieer N f enmmeneant imnlicitement nar nn Î Cec nombhrne£U.1. INOFTME IELE 194 299

tants avec un exposant à 0 et une mantisse différente de 0. De cette ma-

s est

nière, la plus petite valeur représentable avec des nombres dénormali

2-23 4 2126 — 9149

Dénormalisés et test d'égalité. Saus les nombres cdénormalisés. les

deux tests 7 — y = Üetr = y ne seraient pas systématiquement équiva-

lents

Arrondis. Ii est important de noter que la représentation des nombres dé-

cimaux par des flottants est une représentation approximative. Par exemple, le nombre décimal 1,6 ne peut pas être représenté exactement avec cet en-

codage. Pour cela, il faut arrondir cette valeur en choisissant le meilleur

nombre flottant pour la représenter.

La norme IEEE 754 définit quatre modes d'arrondi pour choisir le

meilleur flottant :

e au plus près : le Aottant le plus proche de Ja valeur exacte (en cas

d'égalité, on privilégie le flottant pair, c’est-à-dire avec une mantisse

se terminant par 0);

e vers zéro : Le flottant Le plus proche de 0:

e vers plus l'infini : le plus petit flottant supérieur ou égal à la valeur

exacte ;

e vers moins l'infini : le plus grand flottant inférieur où égal à la valeur

exacte,

Le mode d'arrondi par défaut de la norme est au plus près. Par exemple, le

nombre flottant le plus proche de 1,6 est

001111111 10011001100110011001101

qui correspond au nombre décimal

(271497149849 849949 +2 8e

216 + 9 ir + 220 + 2-21 + 273)

2(127—127)

= 1, 60000002384185791015625

Cette opération d'arrondi se propage également aux opérateurs arithrmé-

tiques, En effet, même si deux nombres décimaux sont exactement repré-

sentables avec des flottants, il n'en est pas nécessairement de même pour

le résultat d'une opération entre ces deux nombres. Ainsi, la norme IEEE

754 exige, pour les opérations usuelles (addition, multiplication, soustrac-256 Chapitre 20. Keprésentation approximative des nombres réels

résultat obtenu en appliquant un opérateur sur deux nombres flottants est

le même que celui que l'on obtiendrait en effectuant l'opération en précision

infinie sur ces deux nombres puis en arrondissant.

","title":"Norme IEEE 754"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Ils sont représentés selon la norme IEEE 754 double précision (format 64 bits). On peut utiliser la notation décimale ou scientifique pour les définir :

x = 1.6

y = 1.2e-4

print(\"x= \",x)

print(\"y= \",y)

La fonction float() permet de convertir un entier en un flottant.

Inversement, la fonction int() transforme un flottant en un entier simplement en ignorant la partie après la virgule.

x = float(-4)

y = int(5.9)

print(\"x= \",x)

print(\"y= \",y)

Les opérations arithmétiques usuelles s'appliquent également aux flottants.

x = 3.4 + 0.012

y = 1.2 / 2.0

print(\"x= \",x)

print(\"y= \",y)

Il convient également de préciser que l'opérateur de division / produit toujours un résultat flottant, quelque soit le type de ses arguments.

x = 1 / 2

y = 4 / 2

z = 2 / 3.2

print(\"x= \",x)

print(\"y= \",y)

print(\"z= \",z)

Certaines expressions peuvent générer des valeurs spéciales, comme inf ou nan, pour représenter respectivement des dépassements de capacité ou des

opérations non valides.

x = 1e200

print( x * x )

print(x * x * 0)

Des conversions d’entiers vers flottants peuvent être réalisées de manière implicite dans les expressions arithmétiques où un opérateur s'applique à la fois à un entier et un flottant, comme par exemple dans le caleul ci-dessous.

x = 5 * 2.7

print(\"x = \",x)

Ces conversions peuvent provoquer des erreurs qu’il est important de bien différencier des débordements de capacité sur les flottants.

Par exemple, dans le code ci-dessous

y = 10 ** 400

y = y + 0.5

Lève l'erreur suivante :

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

OverflowError: int too large to convert to float

La variable y contient un entier après son initialisation à 10 ** 400. Cot entier doit être converti (de manière implicite) en un flottant afin que l’addition y + 0.5 puisse être exécutée, mais cette conversion provoque une erreur.

","title":"Les flottants en Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La bibliothèque standard de Python fournit également de nombreuses fonctions mathématiques rassemblées dans un module math.

Pour utiliser les fonctions de cette bibliothèque, il faut tout d'abord charger le module math à l'aide d'une directive d'import.

import math

Les fonctions ou constantes mathématiques de ce module sont ensuite aecessibles on utilisant la notation pointée math.f, où f est le nom de la fonction

{ou constante).

x = math.sqrt(9)

y = math.sin(1.6 * math.pi)

print(\"math.sqrt(9) =\",x)

print(\"math.sin(1.6 * math.pi) =\",y)

Enfin, la fonction print perinet d'afficher des nombres flottants en précisant le nombre de chiffres après la virgule à l'aide d’une chaîne de formatage :

\"%. [precision]f\",

où [precision] est une constante entière (positive).

Pour afficher une valeur v selon un certain formatage, il faut faire suivre la chaîne de % v. comme dans les exemples suivants :

x = 0.12345

print(\"%.2f\" % x)

print(\"%.20f\" % 1.6)

","title":" Clause SELECT"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Il faut être très prudent lorsque l'on manipule des nombres flottants. En effet, certaines opérations sur ces nombres n’ont pas les mêmes propriétés que sur les nombres réels ct il ne faut jamais oublier que les calculs sont inexacts.

Par exemple, une simple multiplication comme celle ci-dessous nous montre immédiatement les imprécisions du calcul.

x = 1.2 * 3

print(\"1.2 * 3 =\", x)

En ce qui conecrnc les propriétés des opérations, l'addition et la multiplication ne sont pas associatives, comme on peut le voir dans l’exemple suivant :.

x = 1.6 + (3.2 + 1.7)

print(\"%.20f\" % x)

y = (1.6 + 3.2) + 1.7

print(\"%.20f\" % y)

Ensuite, la multiplication n'est pas distributive par rapport à l'addition, comme on peut le voir ici :

x = 1.5 * (3.2 + 1.4)

print(\"%.20f\" % x)

y = 1.5 * 3.2 + 1.5 * 1.4

print(\"%.20f\" % y)

Au final, ces exemples montrent qu'il est très imprudent d'écrire des programmes dans lesquels on utilise des tests d'égalité entre flottants.

Par exemple, on retiendra que l'inprécision de la représentation des nombres réels conduit par exemple à des résultats surprenants comme :

print(0.1 + 0.2 == 0.3)

Aussi, plutôt que d'écrire un test d'égalité entre deux valeurs flottantes v1 et v2, il ost préférable d'écrire un test d’inégalité |v1-v2| < e entre la valeur

absolue de la différence v1 - v2 et une borne de précision e.

Par exemple, pour tester l'égalité à 10-12 près entre les variables x et y suivantes, on écrira :

x = 0.1 + 0.2

y = 0.3

print(\"x=\",\"%.20f\" % x)

print(\"y=\",\"%.20f\" % y)

print(\"x==y :\",x==y)

print(\"|x-y|<1e-12 ;\",abs(x - y) < 1e-12)

","title":"Propriétés des nombres flottants"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Exercice 214 Dounér la représentation flottante en simple précision de 128

ct —32,75. Solution page 485 1

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 215 Douuer la valeur décimale des nombres flottants suivants co-

dés en simple précision :

1 01111110 11110000000000000000000

0 10000011 11100000000000000000000.

Sotion page 485 Cl

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 216 On tape en Python l'expression arithmétique suivante.

>>> (1e25 + 16) - 1e25

Quel est le résultat attendu ? Quel est le résultat obtenu ? Pourquoi ?

Solution page 485 C

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 217 On tape en Python les instructions suivantes.

>>> x = 1e200

>>> y X XX

>> z=y/y

[Il

Quelles sont les valeurs de y et z? Pourquoi ? Solution page 185 ©

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 218 On tape en Python les instructions suivantes.

>>> X 1e200

>DDY=EXEXX

>>> z=y/7y

Quelles sont les valeurs de y et z? Pourquoi ? Solution page 486 O

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 219 Ecrire un programme qui, partant du nombre 1,0, le divise

vingt fois de suite par 8, puis le multiplie vingt fois de suite par 3, puis enfin

affiche la valeur obtenue au final. Expliquer le résultat observé.260 Chapitre 20. Keprèésentation approximative des nombres reels

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 220 Nous allons écrire un programme qui estime la valeur de x de

la façon suivante, On répète un grand nombre de fois l'opération consistant

à choisir au hasard un point dans un carré de côté 1. On compte combien

de points tombent dans le quart de cercle de rayon 1 centré sur l'un des

coins du carré. Le rapport de ce nombre au nombre total de points donne

une estimation de 7/4. Pour tirer un nombre réel entre 0 et l, on utilise

uniform(0, 1), de la bibliothèque random. Solution page 486 D

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 221

1. Trouver un nombre (fottant l) x tel que x + 1 == x.

2. Trouver le plus petit tel nombre.

Indication : 1 s'agit d’une puissance de

Solution page 486 0

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Exercice 222

1. Trouver un nombre flottant x différent de O tel que

2.0 %* 100 + x == 2,0 *x 100.

2. Trouver un tel nombre aussi grand que possible, £ que T

Solution page 487 0

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}]]

Détails: Écrit par : Richard GAUTHIER; Création : 6 Octobre 2020; Mis à jour : 6 Octobre 2020; Clics : 1296

[[{"text":"Afin de vérifier vos acquis, répondez aux questions suivantes.","posi":1}],[{"text":"Avec le langage Python, comment je peux nommer une variable (plusieurs réponses sont possibles)?"},{"chekbox":[{"label":"mavar=20","sol":true},{"label":"ma var=20","sol":false},{"label":"ma_var=20","sol":true},{"label":"1mavar=20","sol":false},{"label":"maVar=20","sol":true},{"label":"mavar1=20","sol":true}]}],[{"text":"On a écrit le script suivant :

var1 = 33.4

De quel type est la variable var1?

"},{"radio":[{"label":"int","sol":false},{"label":"float","sol":true},{"label":"string","sol":false}]}],[{"text":"On a écrit le script suivant :

var1 = 55

De quel type est la variable var1?

"},{"radio":[{"label":"int","sol":true},{"label":"float"},{"label":"string","sol":false}]}],[{"text":"On a écrit le script suivant :

var1 = \"La spécialité Nsi\"

De quel type est la variable var1?

"},{"radio":[{"label":"int","sol":false},{"label":"float"},{"label":"string","sol":true}]}],[{"text":"On a écrit le script suivant :

a = 5 / 2

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"2.5","sol":true},{"label":"2"},{"label":"10","sol":false},{"label":"25","sol":false}]}],[{"text":"On a écrit le script suivant :

a = 5 // 2

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"2.5","sol":false},{"label":"2","sol":true},{"label":"10","sol":false},{"label":"25","sol":false}]}],[{"text":"On a écrit le script suivant :

a = 5 * 2

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"2.5","sol":false},{"label":"2"},{"label":"10","sol":true},{"label":"25","sol":false}]}],[{"text":"On a écrit le script suivant :

a = 5 ** 2

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"2.5","sol":false},{"label":"2"},{"label":"10","sol":false},{"label":"25","sol":true}]}],[{"text":"On a écrit le script suivant :

a = 6

a = a + 1

a = a - 2

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"4","sol":false},{"label":"5","sol":false},{"label":"6","sol":true},{"label":"7","sol":false}]}],[{"text":"On a écrit le script suivant :

a = \"bienvenue\"

b = \"en\"

c = \"Nsi\"

d = a+b+c

print( d )

Quel résultat sera affiché?

"},{"radio":[{"label":"bienvenueenNsi","sol":true},{"label":"bienvenue en Nsi"},{"label":"bienvenue","sol":false},{"label":"Nsienbienvenue","sol":false}]}],[{"text":"On a écrit le script suivant :

a = \"bienvenue\"

b = a[0]

print( b )

Quel résultat sera affiché?

"},{"radio":[{"label":"b","sol":true},{"label":"i"},{"label":"0","sol":false},{"label":"e","sol":false}]}],[{"text":"On a écrit le script suivant :

a = \"bienvenue\"

b = a[ 1 ]

print( b )

Quel résultat sera affiché?

"},{"radio":[{"label":"b","sol":false},{"label":"i","sol":true},{"label":"0","sol":false},{"label":"e","sol":false}]}],[{"text":"On a écrit le script suivant :

a = \"bienvenue\"

b = a[-1]

print( b )

Quel résultat sera affiché?

"},{"radio":[{"label":"b","sol":false},{"label":"i"},{"label":"0","sol":false},{"label":"e","sol":true}]}],[{"text":"On a écrit le script suivant :

import math

a = math.pi

print( a )

Quel résultat sera affiché?

"},{"radio":[{"label":"3.14159","sol":true},{"label":"PI"},{"label":"math.pi","sol":false},{"label":"3","sol":false}]}],[{"text":"On a écrit le script suivant :

import turtle

turtle.forward(50)

turtle.left(60)

turtle.forward(50)

turtle.left(60)

turtle.forward(50)

turtle.left(60)

Quelle est la figure dessinée?

"},{"radio":[{"label":"un triangle équilatéral","sol":true},{"label":"un triangle isocèl"},{"label":"un carré","sol":false},{"label":"un cercle","sol":false}]}],[{"text":"On a écrit le script suivant :

a=4

if a < 4 :

print(\"oui\")

else ;

print(\"non\")

Quel résultat sera affiché?

"},{"radio":[{"label":"oui","sol":false},{"label":"non","sol":true},{"label":"4","sol":false},{"label":"-4","sol":false}]}],[{"text":"On a écrit le script suivant :

a=input(\"Rentrer un nombre \")

# 4 est rentré par l'utilisateur

b = a + 2

print(b)

Quel résultat sera affiché?

"},{"radio":[{"label":"32","sol":false},{"label":"5"},{"label":"23","sol":false},{"label":"TypeError: can only concatenate str (not \"int\") to str","sol":true}]}],[{"text":"On a écrit le script suivant :

for i in range(1,4):

print(i)

Quel résultat sera affiché?

"},{"radio":[{"label":"1

","sol":true},{"label":"1 2 3"},{"label":"6","sol":false},{"label":"1

","sol":false}]}],[{"text":"On a écrit le script suivant :

i = 1

while i < 4 :

print(i)

i = i + 1

Quel résultat sera affiché?

"},{"radio":[{"label":"1

","sol":true},{"label":"1 2 3"},{"label":"6","sol":false},{"label":"1

","sol":false}]}],[{"text":"On a écrit le script suivant :

ph = 8

if ph < 7 :

print(\"acide\")

elif ph == 7 ;

print(\"neutre\")

else ;

print(\"basique\")

Quel résultat sera affiché?

"},{"radio":[{"label":"basique","sol":true},{"label":"neutre"},{"label":"acide","sol":false},{"label":"9","sol":false}]}]]

Détails: Écrit par : Richard GAUTHIER; Création : 5 Octobre 2020; Mis à jour : 5 Octobre 2020; Clics : 1153

[[{"title":"SQL : Requêtes SQL et mises à jour","posi":0},{"text":"

Nous avons vu dans la séquence précédente comment créer des tables et les remplir.

Nous avons maintenant une base de données, c’est-à-dire un ensemble de tables, contenant des données cohérentes vis à vis de nos contraintes d’intégrité.

Nous allons maintenant voir deux autres utilisations d’un SGBD :

- la sélection de données ;

- la mise à jour des données.

La sélection va consister en l’écriture de requêtes SQL permettant de trouver toutes les données de la base vérifiant un certain critère. Le premier rôle du programmeur de bases de données va donc être celui qui consiste à traduire des questions que l’on se pose sur les données du langage naturel au langage

SQL, afin que le SGBD puisse y répondre.

Reprenons la bascs de données de la médiathèque municipale.

Quelles questions peut-on poser à la base de données? Il semble naturel que le SGBD puisse répondre aux questions suivantes, nécessaire au bon fonctionnement

de la médiathèque.

- Étant donné un code barre, quels sont les livres empruntés par l’utilisateur correspondant?

- Étant donné un ISBN. le livre correspondant est-il emprunté?

- Quels sont les utilisateurs en retard, c'est-à-dire ceux dont la date de retour est inférieure à une date donnée ?

- Quels sont tous les livres écrits par Voltaire qui ne sont pas empruntés?

- Quel est le nombre total de livres empruntés?

Une autre fonction importante du SGBD est la mise à jour des données.

Elle peut consister en une modification d’une ligne existante (par exemple, pour changer l'adresse d’un utilisateur ayant déménagé, sans modifier son

code barre, son nom où son e-mail) ou une suppression (par exemple lorsqu'un utilisateur rend un livre, il faut supprimer la ligne correspondante dans la table emprunt).

Pour les exemples plus parlants, nous utilisons dans la suite le SGBD libre PostgreSQL, avec une base de données de médiathèque fic-

tive. Les fichiers permettant de créer cette base sont disponibles librement

sur le site https://www.nsi-terminale.fr/. Ils utilisent la syntaxe SQL

standard et sont donc compatibles avec n'importe quel SGBD relationnel

respectant la norme SQL (et ont été testés avec un certain nombre d’entre

eux, libres et propriétaires).

"},{"text":""}],[{"text":"

Commençons par une requête simple. On considère la table livre, créée par l’ordre suivant :

CREATE TABLE livre (titre VARCHAR(300) NOT NULL,

editeur VARCHAR(90) NOT NULL,

annee INT NOT NULL,

isbn CHAR(14) PRIMARY KEY);

Où les entités suivantes sont insérées :

INSERT INTO livre VALUES ('Les Aventures de Huckleberry Finn', 'Flammarion', '2020', '978-2081509511');

INSERT INTO livre VALUES ('Fondation et Empire', 'Editions Denoël', '1999', '978-2207249123');

INSERT INTO livre VALUES ('Akira', 'Glénat', '2000', '978-2723428262');

INSERT INTO livre VALUES ('Les Robots', 'Editions Milan', '2017', '978-2745989857');

INSERT INTO livre VALUES ('Astérix chez les Pictes', 'Editions Albert René', '2013', '978-2864972662');

INSERT INTO livre VALUES ('Les Monades urbaines', 'Robert Laffont', '2016', '978-2221197691');

INSERT INTO livre VALUES ('Les Voyages de Gulliver', 'Primento', '2015', '978-2335008586');

INSERT INTO livre VALUES ('Lolita', 'Penguin UK', '2012', '978-0141391601');

INSERT INTO livre VALUES ('La Nuit des temps', 'Presses de la Cité', '2014', '978-2258116429');

INSERT INTO livre VALUES ('Ravage', 'Editions Gallimard', '2014', '978-2072534911');

INSERT INTO livre VALUES ('Les Lauriers de César', 'Educa Books', '2008', '978-2012101500');

INSERT INTO livre VALUES ('Niourk', 'French Pulp éditions', '2018', '979-1025100639');

INSERT INTO livre VALUES ('Le Meilleur des mondes', 'Plon', '2013', '978-2259221702');

INSERT INTO livre VALUES ('Berlin Alexanderplatz', 'Editions Gallimard', '1933', '978-2070219292');

INSERT INTO livre VALUES ('Fahrenheit 451', 'Simon and Schuster', '2011', '978-1439142677');

INSERT INTO livre VALUES ('La Mort d''Ivan Ilitch', 'Flammarion', '2015', '978-2081364509');

INSERT INTO livre VALUES ('Croisière sans escale', 'Editions Denoël', '1990', '978-2207500293');

INSERT INTO livre VALUES ('Le Vieil Homme et la Mer', 'Editions Gallimard', '2018', '978-2072762093');

INSERT INTO livre VALUES ('Mrs Dalloway', 'Flammarion', '2015', '978-2081358881');

INSERT INTO livre VALUES ('L''Idiot', 'Les Editions de Londres', '2019', '978-1911572909');

INSERT INTO livre VALUES ('Le Carnet d''or', 'Le Livre de poche', '1980', '978-2253025320');

INSERT INTO livre VALUES ('Les Grandes Espérances', 'BoD - Books on Demand', '2019', '978-2322185801');

INSERT INTO livre VALUES ('Astérix et Cléopâtre', 'Dargaud', '1999', '978-2012100060');

INSERT INTO livre VALUES ('Madame Bovary', 'UPblisher', '2016', '978-2759902293');

INSERT INTO livre VALUES ('Les Frères Karamazov', 'Les éditions Pulsio', '2016', '978-2371131118');

INSERT INTO livre VALUES ('Moby Dick', 'Campfire Graphic Novels', '2010', '978-8190732673');

INSERT INTO livre VALUES ('Demain les chiens', 'J''ai Lu', '2015', '978-2290112168');

INSERT INTO livre VALUES ('Le Tour de Gaule d''Astérix', 'Educa Books', '2007', '978-2012101685');

INSERT INTO livre VALUES ('1984', 'Houghton Mifflin Harcourt', '1983', '978-0547249643');

INSERT INTO livre VALUES ('Don Quichotte', 'Les éditions Pulsio', '2016', '978-2371130418');

INSERT INTO livre VALUES ('Le Château de Lord Valentin', 'Robert Laffont', '2017', '978-2221216361');

INSERT INTO livre VALUES ('Le Père Goriot', 'Primento', '2012', '978-2806231697');

INSERT INTO livre VALUES ('Le Procès', 'Flammarion', '2014', '978-2081351981');

INSERT INTO livre VALUES ('L''Homme qui rétrécit', 'Editions Gallimard', '2017', '978-2072457340');

INSERT INTO livre VALUES ('Chroniques martiennes', 'Editions Gallimard', '2016', '978-2072455162');

INSERT INTO livre VALUES ('Le Roi Lear', 'Éditions Actes Sud', '2015', '978-2330052768');

INSERT INTO livre VALUES ('Le Cadeau de César', 'Educa Books', '2005', '978-2012101531');

INSERT INTO livre VALUES ('La Planète des singes', 'Julliard', '2011', '978-2260019183');

INSERT INTO livre VALUES ('Orgueil et Préjugés', 'Fleurus', '2015', '978-2215130475');

INSERT INTO livre VALUES ('Une maison de poupée', 'Éditions Actes Sud', '2016', '978-2330068349');

INSERT INTO livre VALUES ('Vermilion Sands', 'Carroll & Graf Pub', '1988', '978-0881844221');

INSERT INTO livre VALUES ('La Grande Traversée', 'Seuil Jeunesse', '2014', '979-1023500448');

INSERT INTO livre VALUES ('L''Étranger', 'Editions Gallimard', '2012', '978-2072376429');

INSERT INTO livre VALUES ('L''Île des morts', 'POL Editeur', '2010', '978-2846825573');

INSERT INTO livre VALUES ('Par-delà le mur du sommeil', 'République des Lettres', '2018', '978-2824904269');

INSERT INTO livre VALUES ('Le Papyrus de César', 'Editions Albert René', '2015', '978-2864972716');

INSERT INTO livre VALUES ('La Main de Zeï', 'Bragelonne Classic', '2016', '978-2820511034');

INSERT INTO livre VALUES ('Beloved', 'Christian Bourgois', '2015', '978-2267028133');

INSERT INTO livre VALUES ('La Conscience de Zeno', 'République des Lettres', '2015', '978-2824902371');

INSERT INTO livre VALUES ('Delirium Circus', 'Bragelonne', '2013', '978-2820508935');

INSERT INTO livre VALUES ('Médée', 'Hatier', '2013', '978-2218972324');

INSERT INTO livre VALUES ('Nostromo', 'Oxford University Press', '2009', '978-0199555918');

INSERT INTO livre VALUES ('Au carrefour des étoiles', 'J''ai Lu', '1997', '978-2277118473');

INSERT INTO livre VALUES ('Le Vagabond', 'BnF collection ebooks', '2016', '978-2346014453');

INSERT INTO livre VALUES ('Les Buddenbrook', 'LGF/Le Livre de Poche', '1993', '978-2253063193');

INSERT INTO livre VALUES ('Les Métamorphoses', 'Le Livre de Poche', '2011', '978-2253158677');

INSERT INTO livre VALUES ('Jack Barron et l''Éternité', 'J''ai Lu', '2016', '978-2290105504');

INSERT INTO livre VALUES ('Hacker''s Delight', 'Addison-Wesley Professional', '2003', '978-0201914658');

INSERT INTO livre VALUES ('Astérix et les Normands', 'Dargaud', '2005', '978-2012101418');

INSERT INTO livre VALUES ('Le Temps incertain', 'Robert Laffont', '2011', '978-2221119709');

INSERT INTO livre VALUES ('Astérix en Corse', 'Dargaud', '2005', '978-2012101524');

INSERT INTO livre VALUES ('Les Fils de la Médina', 'Arles [France] : Actes sud', '2003', '978-2742744824');

INSERT INTO livre VALUES ('Le Grand secret', 'Presses de la Cité', '2014', '978-2258116405');

INSERT INTO livre VALUES ('Le Devin', 'Educa Books', '2010', '978-2012101517');

INSERT INTO livre VALUES ('Le Noir Dessein', 'Livre de poche', '1998', '978-2253062820');

INSERT INTO livre VALUES ('Astérix légionnaire', 'Educa Books', '2011', '978-2012101784');

INSERT INTO livre VALUES ('Romancero gitano', 'Greenbooks editore', '2020', '978-8832957402');

INSERT INTO livre VALUES ('The Practice of Programming', 'Addison-Wesley Professional', '1999', '978-0201615869');

INSERT INTO livre VALUES ('Crime et Châtiment', 'Editions Humanis', '2012', '979-1021900486');

INSERT INTO livre VALUES ('La Promenade au phare', 'LGF/Le Livre de Poche', '1983', '978-2253031536');

INSERT INTO livre VALUES ('L''Homme sans qualités', 'Contemporary French Fiction', '2011', '978-2757803691');

INSERT INTO livre VALUES ('Le Bruit et la Fureur', 'Gallimard Education', '1972', '978-2070361625');

INSERT INTO livre VALUES ('Les Plus qu''humains', 'adsaa', '1999', '000-0000000162');

INSERT INTO livre VALUES ('La Main gauche de la nuit', 'Robert Laffont', '2012', '978-2221128121');

INSERT INTO livre VALUES ('Mémoires d''Hadrien', 'Gallimard Education', '1974', '978-2070369218');

INSERT INTO livre VALUES ('Contes de l''absurde', 'Presses Pocket', '1978', '978-2266006095');

INSERT INTO livre VALUES ('Astérix et la Transitalique', 'Editions Albert René', '2017', '978-2864973270');

INSERT INTO livre VALUES ('L''Odyssée d''Astérix', 'Educa Books', '2008', '978-2864972051');

INSERT INTO livre VALUES ('Les Singes du temps', 'Robert Laffont', '2011', '978-2221119693');

INSERT INTO livre VALUES ('Les Contes de Canterbury', 'Gallimard Education', '2000', '978-2070406340');

INSERT INTO livre VALUES ('Sécheresse', 'La Cheminante', '2014', '978-2371270060');

INSERT INTO livre VALUES ('The Art of Computer Programming', 'Addison-Wesley Professional', '1997', '978-0321635747');

INSERT INTO livre VALUES ('L''Aveuglement', 'Contemporary French Fiction', '2000', '978-2020403436');

INSERT INTO livre VALUES ('Le Berceau du chat', 'Contemporary French Fiction', '2010', '978-2757820919');

INSERT INTO livre VALUES ('Anna Karénine', 'Bibliothèque russe et slave', '2018', '978-2371240087');

INSERT INTO livre VALUES ('La Montagne magique', 'Fayard', '2016', '978-2213703848');

INSERT INTO livre VALUES ('Le Domaine des dieux', 'French & European Publications', '1992', '978-0785909903');

INSERT INTO livre VALUES ('Cent ans de solitude', 'Contemporary French Fiction', '1995', '978-2020238113');

INSERT INTO livre VALUES ('Gargantua et Pantagruel', 'Livre de Poche Jeunesse', '2009', '978-2013230827');

INSERT INTO livre VALUES ('Contes', 'J''ai Lu', '2015', '978-2290117965');

INSERT INTO livre VALUES ('Guerre et Paix', 'Archipoche', '2016', '978-2352879183');

INSERT INTO livre VALUES ('Énéide', 'Belles Lettres', '1993', '978-2251013039');

INSERT INTO livre VALUES ('Seconde Fondation', 'adsaa', '1979', '000-0000000097');

INSERT INTO livre VALUES ('Les Jeux de l''esprit', 'FeniXX', '1971', '978-2402281775');

INSERT INTO livre VALUES ('Middlemarch', 'Wordsworth Editions', '1994', '978-1853262371');

INSERT INTO livre VALUES ('Œdipe roi', 'J''ai Lu', '2013', '978-2290080207');

INSERT INTO livre VALUES ('L''Amour aux temps du choléra', 'Grasset', '2009', '978-2246819554');

INSERT INTO livre VALUES ('Fictions', 'Gallimard Education', '1974', '978-2070366149');

INSERT INTO livre VALUES ('Astérix chez les Bretons', 'Dargaud', '2002', '978-2012100084');

INSERT INTO livre VALUES ('Le Château', 'Points', '2011', '978-2757827413');

INSERT INTO livre VALUES ('Le Voyageur imprudent', 'Editions Gallimard', '2014', '978-2072535031');

INSERT INTO livre VALUES ('Je suis une légende', 'Editions Gallimard', '2013', '978-2072457388');

INSERT INTO livre VALUES ('Le Maître du Haut Château', 'J''ai Lu', '2017', '978-2290157268');

INSERT INTO livre VALUES ('Les Âmes mortes', 'Bibliothèque russe et slave', '2018', '978-2371240001');

INSERT INTO livre VALUES ('Le Tambour', 'Contemporary French Fiction', '1997', '978-2020314305');

INSERT INTO livre VALUES ('Polymath', 'iMinds Pty Ltd', '2014', '978-1921746864');

INSERT INTO livre VALUES ('Seigneur de lumière', 'Editions Gallimard', '2014', '978-2072487958');

INSERT INTO livre VALUES ('Ulysse', 'Nathan', '2012', '978-2092532195');

INSERT INTO livre VALUES ('Pedro Páramo', 'New York : Grove Press', '1959', '000-0000000069');

INSERT INTO livre VALUES ('Ubik', 'Houghton Mifflin Harcourt', '2012', '978-0547728247');

INSERT INTO livre VALUES ('Algorithms', 'Addison-Wesley Professional', '2011', '978-0132762564');

INSERT INTO livre VALUES ('Fifi Brindacier', 'Hachette Romans', '2013', '978-2011179043');

INSERT INTO livre VALUES ('Le monde s''effondre', 'Editions Présence Africaine', '1972', '978-2708701915');

INSERT INTO livre VALUES ('La Naissance des dieux', 'Glénat BD', '2017', '978-2331035531');

INSERT INTO livre VALUES ('Hamlet', 'Primento', '2012', '978-2806240187');

INSERT INTO livre VALUES ('Les Enfants de minuit', 'Gallimard Education', '2010', '978-2070402632');

INSERT INTO livre VALUES ('Dune', 'Penguin', '2003', '978-1101658055');

INSERT INTO livre VALUES ('La Couleur tombée du ciel', 'Tiers Livre Éditeur', '2014', '978-2814510012');

INSERT INTO livre VALUES ('L''Éducation sentimentale', 'FeniXX', '1990', '978-2402282697');

INSERT INTO livre VALUES ('Obélix et Compagnie', 'Educa Books', '2008', '978-2012101555');

INSERT INTO livre VALUES ('Le Journal d''un fou', 'Bibebook', '2013', '978-2824709420');

INSERT INTO livre VALUES ('Les Hauts de Hurlevent', 'Le Livre de Poche', '2012', '978-2253174561');

INSERT INTO livre VALUES ('La Plaie', 'FeniXX', '1967', '978-2402255462');

INSERT INTO livre VALUES ('Astérix chez les Belges', 'Dargaud', '1979', '978-2012101562');

INSERT INTO livre VALUES ('Le Rouge et le Noir', 'Les Éditions de l''Ebook malin', '1971', '978-2367881171');

INSERT INTO livre VALUES ('À la recherche du temps perdu', 'Books LLC, Wiki Series', '2010', '978-1153611725');

INSERT INTO livre VALUES ('La storia', 'Editions Gallimard', '2004', '978-2070315017');

INSERT INTO livre VALUES ('L''Homme total', 'Presses Universitaires de France - PUF', '2011', '978-2130592150');

Rentrez les expressions ci-dessus dans votre base de donnée dans l'onglet SQL de phpmyadmin.

","title":"Sélection de données"},{"edit":"

Mettre le résultat ici de la requête sql.

"}],[{"text":"

Maintenant que la table livre est mise en place, on souhaite trouver les titres de tous les livres publiés après 1990 dans la base de données de la médiathèque.

Une telle requête peut s’écrire en SQL :

SELECT titre FROM livre WHERE annee >= 1990;

Sélectionner la base de donnée dans phpmyadmin et exécuter la requête SQL. Mettre le résultat ci-dessous et conclure.

Dans cette requête, la partie « FROM livre » indique la table sur laquelle porte la requête.

La partie « WHERE ... » indique que l’on ne sélectionne

que les lignes de la table Livre pour lesquelles la valeur de l’attribut annee est plus grande que 1990.

Enfin, la partie SELECT titre indique qu'on ne veut renvoyer que les valeurs de l’attribut titre des lignes trouvées. On remarque que le résultat d'une requête «SELECT ... » est une table, ici possédant une unique colonne titre.

","title":"Requête sur une table"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

L'expression se trouvant dans la partie WHERE doit être une expression booléenne.

Elle peut être construite à partir d'opérateurs de comparaison (<, <=, >, >=, = et <>), d'opérateurs arithmétiques (+, -, *, /, %), de constantes, de noms d’attributs, d'opérateurs logiques (AND, OR et NOT) et d'opérateurs spéciaux tels que l'opérateur de comparaison de textes LIKE.

Par exemple, si l’on souhaite afficher les titres de tous les livres publiés par Dargaud entre 1970 et 1980, on pourra écrire :

SELECT titre FROM livre WHERE annee >= 1970

AND annee <= 1980

AND editeur = 'Dargaud';

Tester la requête et mettre le résultat ci-dessous.

Si l’utilisation de l'égalité « = » est appropriée ici, on pourrait vouloir faire une requête approchée.

Par exemple, trouver les titres des livres qui contiennent le mot « Astérix » dans le titre.

Une telle requête s’écrira

SELECT titre FROM livre WHERE titre LIKE '%Astérix%';

Tester la requête et mettre le résultat ci-dessous.

La chaîne de caractères « '%Astérix%' » est un motif. L'opération s LIKE m s’évalue à vrai si et seulement si la chaîne de caractères s correspond au motif m.

Dans un motif, le symbole « % » est un joker et peut être substitué par n'importe quelle chaîne.

Le symbole «_» quant à lui représente n'importe quel caractère.

Ainsi, le motif « '%Astérix%' » correspond à n'importe quelle chaîne dans laquelle les caractères Astérix sont précédés ou suivis de caractères quelconques.

","title":"Clause WHERE"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La clause SELECT peut prendre trois formes ;

La première est celle où l’on liste explicitement les

attributs que l’on désire renvoyer. Si on veut renvoyer les titres et l’'ISBN des livres publiés après 1990, on écrira ceci :

SELECT titre, isbn FROM livre WHERE annee >= 1990;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Le résultat est de nouveau une table, mais cette fois avec les colonnes (ou attributs) titre et isbn.

Il est possible de renommer les colonnes au moyen du mot clé AS.

SELECT titre AS le_titre, isbn AS nom ,serie

FROM livre

WHERE annee >= 1990;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Ainsi, si la clause WHERE d’une requête permet de restreindre les lignes de la table que l’on renvoie (en ne gardant que celle vérifiant la condition), la clause SELECT permet de restreindre la liste des colonnes.

La seconde forme de la clause SELECT est celle que l’on utilise lorsqu'on veut conserver toutes les colonnes. En effet, il serait fastidieux de récrire toutes les colonnes d’une table. On peut utiliser à cette fin le symbole « * » qui signifie « toutes les colonnes de la table ».

SELECT * FROM livre WHERE annee >= 1990;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

La troisième utilisation de la clause SELECT est celle permettant d'appeler des fonctions d’agrégation. Ces dernières permettent d'appliquer une fonction à l’ensemble des valeurs d’une colonne et de renvoyer le résultat comme une table ayant une seule case (une ligne et une colonne).

Nous présentons quelques unes de ces fonctions :

- COUNT qui permet d'obtenir le nombre de résultats,

- AVG (pour l’anglais average) qui permet de calculer la moyenne d'une colonne,

- SUM qui permet d’en faire la somme,

- MIN et MAX qui permettent de trouver respectivement le minimum et maximum d’une colonne.

Si on souhaite savoir combien de livres contiennent la chaîne « Astérix » dans leur titre (plutôt que de renvoyer ces titres), on écrira la requête suivante :

SELECT COUNT(titre) AS total

FROM livre

WHERE titre LIKE '%Astérix%';

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Notons que nous avons choisi de renommer la colonne. En effet, le résultat n'étant pas directement une colonne d’une table existante, les SGBD choisissent un nom arbitraire, souvent peu parlant.

La fonction « COUNT » ne faisant que compter la taille de la colonne, elle peut s’appliquer à n'importe quel nom de colonne et même au symbole « * ». Il est donc courant d'écrire une requête de la forme

SELECT COUNT(*) AS total

FROM livre

WHERE titre LIKE '%Astérix%';

qui donnera le même résultat que précédemment.

Les fonctions AVG et SUM ne peuvent s'appliquer qu’à des colonnes dont le domaine est un nombre

On peut écrire par exemple

SELECT SUM(annee) AS somme FROM livre;

SELECT AVG(annee) AS moyenne FROM livre;

Tester les 2 requêtes dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Ici, en l’absence de clause WHERE, toutes les lignes sont sélectionnées. La somme et la moyenne des années sont calculées et renvoyées comme une

table.

Enfin, les fonctions MIN() et MAX() peuvent s'appliquer sur n'importe quelle colonne et ls comparaison pour son type sera utilisée pour déterminer le plus petit ou le plus grand élément.

SELECT MIN(annee) AS inf FROM livre;

SELECT MAX(annee}) AS sup FROM livre;

Tester les 2 requêtes dans phpmyadmin et mettre le résultat ci-dessous et conclure.

","title":" Clause SELECT"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Comme nous avons pu l'observer lors de nos premières requêtes, les résultats sont affichés par le SGBD dans un ordre a priori quelconque. La situation est même plus complexe. En effet, en fonction de certains paramètres, le SGBD peut choisir entre différentes

façons de calculer la requête.

L'ordre peut donc être modifié entre deux exécutions de la même requête. Si l’on désire obtenir les résultats dans un ordre particulier, on peut utiliser la clause ORDER BY en fin de requête.

SELECT titre FROM livre

WHERE annee >= 1990

ORDER BY titre ASC;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Ici, on demande au SGBD de trier les résultats par titre croissants (ASC pour l’anglais ascending).

Si on souhaite trier par valeurs décroissantes il suffit d'utiliser le mot clé DESC (pour l'anglais descending) à la place de ASC.

Supposons maintenant que l’on souhaite connaître toutes les années dans lesquelles un livre à été publié.

Nous envoyons la requête suivante :

SELECT annee FROM livre;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Vous constatez que toutes les années, mais la même année peut apparaître plusieurs fois. Si on souhaite retirer les doublons d’un résultat, le mot clé DISTINCT

peut être ajouté à la clause SELECT.

SELECT DISTINCT annee FROM livre;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Attention cependant, chaque ligne entière de résultat est considérée lors de la comparaison.

SELECT DISTINCT annee, isbn FROM livre;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

C’est pourquoi, la requête ci-dessus continuera d'afficher plusieurs fois la même année. En effet, comme l’isbn est unique pour chaque ligne, tous les couples annee, isbn de la table sont différents deux à deux (ils diffèrent par leur isbn même s'ils ont la même

année). Le mot clé DISTINCT n'aura donc ici aucun effet.

","title":"Tri et suppression des doublons"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les requêtes que nous avons vues nous permettent assez facilement de déterminer les livres qui ont été empruntés. Ces derniers sont simplement ceux dont l'ISBN est présent dans la table emprunt.

SELECT * FROM emprunt;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Cette réponse n’est cependant pas très satisfaisante. En effet, il serait plus naturel de pouvoir afficher les titres de ces livres plutôt que leur ISBN. Le problème est que les titres des livres sont présents uniquement dans la table livre.

L'opération de jointure de deux tables apporte une réponse à ce problème. Elle a déjà été étudiée en première dans le cadre du traitement de données en tables.

Étant données deux tables A et B, la jointure consiste à créer toutes combinaisons de lignes de A et de B

ayant un attribut de même valeur. Ici, on souhaiterait obtenir une « grande table » dont les colonnes sont celles de la table emprunt et celle de la table livre, en réunissant les lignes ayant ie même isbn.

Cela peut être fait au moyen de la directive JOIN.

SELECT * FROM emprunt

JOIN livre ON emprunt.isbn = livre.isbn;

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Cette requête crée la jointure des deux tables.

Comme on peut le voir, toutes les colonnes des deux tables ont été recopiées dans la sortie.

Chaque ligne est le résultat de la fusion de deux lignes ayant le même ISBN. Le choix de ces lignes est donné

par la condition de jointure indiquée par le mot clé ON.

La condition indique au SGBD dans quel cas deux lignes doivent être fusionnées.

Ici, on joint les lignes pour lesquelles les ISBN sont égaux.

On écri donc l'expression booléenne

« emprunt.isbn = livre.isbn ».

La notation portant le même nom.

La jointure peut être combinée avec les clauses SELECT et WHERE.

Par exemple, si on souhaite afficher uniquement les titres et les dates des livres empruntés qui sont à rendre avant le 1er février 2020, on peut écrire la requête suivante :

SELECT livre.titre, emprunt.retour

FROM emprunt

JOIN livre ON emprunt.isbn = livre.isbn

WHERE emprunt retour < '2020-02-01';

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

Même s’il n’y a pas d’ambiguïté ici, une bonne pratique consiste à préfixer les noms d’attributs par leur table dès que l’on utilise plus d’une table dans la requête. On n’est évidemment pas limité à une seule jointure.

Si on souhaite afficher les noms et prénoms des utilisateurs ayant emprunté ces livres, il suffit de joindre la table usager, en rajoutant une nouvelle clause JOIN ON, cette fois sur le code_barre de l'usager.

SELECT usager.nom, usager.prenom, livre.titre, emprunt.retour

FROM emprunt

JOIN livre ON emprunt.isbn = livre.isbn

JOIN usager ON usager.code_barre = emprunt.code_barre

WHERE emprunt.retour <'2020-02-01';

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

La requête ci-dessus fonctionne parfaitement mais est un peu fastidieuse à écrire. Il est possible de créer dans une requête un alias pour un nom de table au moyen du mot clé AS, comme pour le renommage de colonne.

La requête peut donc être réécrite de la manière suivante :

SELECT u.nom, u.prenom, l.titre, e.retour

FROM emprunt AS e

JOIN livre AS l ON e.isbn = l.isbn

JOIN usager AS u ON u.code_barre = e.code_barre

WHERE e.retour < '2020-02-01';

Tester la requête dans phpmyadmin et mettre le résultat ci-dessous et conclure.

La jointure est une opération fondamentale des bases de données relationnelles. En effet, comme nous l'avons vu, la modélisation relationnelle des données impose parfois un découpage des données.

Les relations entre ces dernières sont maintenues par des contraintes, notamment les contraintes de référence.

La jointure permet de reconstituer ce lien, en construisant « à la volée » de grandes tables contenant toutes les informations liées.

","title":"Jointure"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Considérons la requête

SELECT livre.titre, emprunt.retour

FROM emprunt

JOIN livre ON emprunt.isbn = livre.isbn

WHERE emprunt.retour < '2020-02-01';

Puisque l’on peut mettre des conditions arbitraires dans la clause WHERE, une manière alternative d'écrire la requête est la suivante :

SELECT livre.titre, emprunt.retour

FROM emprunt, livre

WHERE emprunt.isbn = livre.isbn

AND emprunt.retour < '2020-02-01';

Pour n'importe quel SGBD, ces deux requêtes sont équivalentes, tant du point de vue du résultat que des performances.

La seconde version est « l’ancienne » syntaxe SQL, utilisée avant l'introduction du mot clé JOIN dans la version du standard de 1992. La bonne pratique consiste à privilégier l’utilisation du mot clé JOIN. En effet, il rend plus lisible les grandes requêtes en séparant clairement prédicats de jointure et filtres

sur les données. Il permet aussi de communiquer clairement l'intention d'effectuer une jointure. Enfin, lors d’une utilisation avancée, il permet de changer la méthode de jointure (QUTER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN, etc.) tout en conservant la même syntaxe.

","title":"Nouvelle » syntaxe SQL pour les jointures"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les données stockées dans un SGBD ne sont a priori pas figées et peuvent être modifiées au cours du temps. Nous allons montrer deux types de modifications pouvant être faites sur les tables :

- la suppression d’un ensemble de lignes et

- la mise à jour de certains attributs d’un ensemble de lignes.

","title":"Modification des données"},{"edit":"

"}],[{"text":"

L'ordre DELETE FROM t WHERE c permet de supprimer de la table t toutes les lignes vérifiant la condition c.

Dans l'exemple de notre médiathèque, supposons que l'utilisateur Sébastien Petit, dont le code_barre est '934701281931582', ait rendu ses livres. Il faut supprimer de la table emprunt toutes les lignes pour lesquelles le code barre vaut '934701281931582', ce qui donne l’ordre suivant :

DELETE FROM emprunt WHERE code_barre = '934701281931582' ;

Après exécution de cet ordre, la recherche dans la table emprunt ne donne plus de résultats :

SELECT COUNT(*) AS total

FROM emprunt

WHERE code_barre = '934701281631582';

Attention, au même titre qu’une requête SELECT sans clause WHERE sélectionne toutes les lignes, un ordre DELETE sans clause WHERE efface toutes les lignes de la table. Il ne faut pas confondre « DELETE FROM » et « DROP TABLE + ». La première opération vide une table de son contenu, mais ne supprime pas la table.

Il est donc possible d’y ajouter de nouveau des données au moyen de l'instruction INSERT.

La seconde opération détruit la table (et ses données). La table ne peut donc plus être référencée.

Comme nous l'avons dit précédemment, les contraintes sont vérifiées à chaque mise à jour.

Essayons de supprimer le livre Hacker's delight de la

table livre, sachant que l’'ISBN de ce dernier est '978-0201914658'.

DELETE FROM livre WHERE isbn = '978-0201914658' ;

Ici, le SGBD nous indique que supprimer ce livre (et donc supprimer sa clé primaire de la table livre) violerait la contrainte de clé étrangère dans la table auteur_de.

Comme pour la destruction d’une table, il faut donc

supprimer en premier les lignes dont les attributs sont déclarés comme clés étrangères avant de supprimer celles contenant les clés primaires correspondantes.

Du point de vue de leur exécution, les ordres de modification de table sont soit entièrement exécutés, soit entièrement annulés.

Considérons la requête suivante :

DELETE FROM usager WHERE cp = '75001' OR cp = '75002' ;

qui efface de la table usager toutes les personnes dont le code postal est 75001 ou 75002. Si aucune de ces personnes n'apparaît dans la table emprunt, alors les suppressions peuvent être effectuées sans erreur.

Supposons maintenant que certaines de ces personnes ont emprunté un livre. Même si la SGDB rencontre en premier des personnes sans emprunt et les supprime, il lèvera une erreur dès qu’il rencontrera un usager référencé dans la table emprunt.

Dans ce cas, foutes les modifications déjà faites seront annulées et la table se trouvera dans l'état qu’elle avait avant la tentative d’exécution.

Les exécutions sont donc de type « tout où rien ».

","title":"Suppression de lignes"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le second type de modification est la mise à jour. Elle consiste à remplacer certains attributs d'un ensemble de lignes par de nouvelles valeurs.

La syntaxe est la suivante :

UPDATE t SET a1 = e1, ..., SET an = en WHERE c

Cette dernière signifie « sélectionne dans la table t toutes les lignes vérifiant la condition c et pour chacune de ces lignes, remplace la valeur courante de

l'attribut a par la valeur de l'expression e ».

Par exemple, si l'utilisateur Sébastien Petit souhaite mettre à jour son adresse email, on écrit ceci :

UPDATE utilisateur SET email = Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.'

WHERE code_barre = '934701281931582';

Les expressions de mise à jour peuvent mentionner des noms d’attributs.

Ces derniers sont alors remplacés par la valeur courante (avant mise à jour) de ces attributs.

Supposons par exemple que la médiathèque soit fermée au mois d'avril. On souhaite que tous les emprunts dont la date de rendu était en avril soient prolongés de 30 jours.

UPDATE emprunt SET retour = retour + 30

WHERE retour >= '2020-04-01';

Dans la mise à jour précédente, la clause « SET retour = retour + 30 » est similaire à la modification d’une variable dans un langage de programmation comme Python, c’est-à-dire prendre la valeur courante de retour, y ajouter 30 et écrire la nouvelle valeur dans retour.

","title":"Mise à jour"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Toute modification (création de table, suppression de table, mise à jour, suppression de ligne, insertion de ligne) qui ne viole pas de contrainte est définitive.

En cas de suppression ou de mise à jour, les anciennes données sont perdues. Il faut donc être particulièrement vigilant lors de la conception d’un programme effectuant des mises à jour dans une base de données.

Les bonnes pratiques recommandent l'utilisation de plusieurs « copies » de la base de données.

Une copie de test, utilisée pour le développement et une copie de « production » utilisée pour faire fonctionner le logiciel, une fois que ce dernier à été testé rigoureusement. La base de production doit par ailleurs être sauvegardée fréquemment pour éviter les risques liés à de mauvaises manipulations ou à des défaillances logicielles ou matérielles.

Comme nous l'avons vu, l’ordre « SELECT ... FROM » renvoie une table comme résultat. Il est possible de nommer cette dernière grâce au mot-clé INTO :

SELECT * INTO usager_paris FROM usager WHERE cp LIKE '75%';

Cet ordre crée une nouvelle table nommée usager_paris contenant le résultat de la requête.

Cette dernière a le même schéma que la table usager

car toutes les colonnes ont été copiées. En revanche, elle ne contiendra que les lignes pour lesquelles le code postal commence par 75.

La table usager_paris est ensuite utilisable comme n'importe quelle autre table. La clause WHERE permet de choisir les lignes à conserver. Par exemple,

SELECT * INTO usager2 FROM usager;

crée une copie conforme de usager alors que

SELECT * INTO usager3 FROM usager WHERE 1 = 0;

crée une table vide ayant le même schéma que usager (car la condition « 1 = 0») est toujours fausse.

Attention cependant, l'opération SELECT ... INTO ne copie pas les contraintes. Ainsi, dans la table usager3 ci-dessus, la colonne code_barre, bien qu’elle existe, n'est pas déclarée en tant que clé primaire. L'opération

SELECT INTO servira donc plutôt à sauvegarder un résultat temporaire de requête plutôt que créer une véritable copie.

Créer une copie conforme d’une table peut se faire en utilisant deux variations sur des opérations que nous connaissons bien.

La première est l'opération CREATE, utilsée comme ceci :

CREATE TABLE usager3 (LIKE usager INCLUDING ALL);

Cette syntaxe indique de créer la table usager3 comme une table de même schéma que usager, en incluant les contraintes (clés primaires, étrangères, CHECK, NOT NULL, ...).

L’inconvénient est que la table usager3 est vide. On peut cependant la remplir en utilisant une variation de l'order INSERT :

INSERT INTO usager3 (SELECT * FROM usager);

Ici, on dit d’insérer dans usager3 toutes les lignes renvoyées par la requête mise entre parenthèses. Cette dernière peut être arbitraire, mais doit renvoyer des lignes du même schéma que celles attendues pour la table usager3, en particulier on aurait pu utiliser une clause WHERE.

","title":"Copie de table"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

L'opération « SELECT ... INTO » permet de sauver le résultat d’une requête sous un certain nom de table. Il est donc possible d'effectuer sur ce résultat une nouvelle requête.

Cependant, cette opération va occuper de l’espace de stockage. Il ne faudra donc pas oublier de supprimer la table ainsi créée. Il est possible de créer une table de manière temporaire et d'exécuter une requête sur cette table en imbriquant la première requête dans la clause « FROM » de la seconde ou dans une clause « JOIN ... ON »:

SELECT * FROM (SELECT * FROM livre

WHERE annee >= 1990) AS tmp

WHERE tmp.annee <= 2000;

La requête ci-dessus calcule d’abord une table intermédiaire nommée tmp qui liste les livres publiés après 1990. Suite à quoi, la table tmp est refiltrée pour

ne garder que les livres pour lesquels l’année est inférieure à 2000.

Attention, il ne s’agit ici que d’une explication de « haut niveau ». En pratique, n'importe quel SGBD moderne évaluera cette deux requêtes imbriquées comme la requête équivalente :

SELECT * FROM livre

WHERE annee >= 1990

AND annee <= 2000;

Une autre manière d’imbriquer les requêtes consiste à utiliser une sous-requête dans la clause WHERE. En effet, le langage SQL identifie les valeurs scalaires et les tables à une seule « case » telles que celles renvoyées par les fonctions d’agrégation.

Par exemple, si on souhaite afficher les titres des livres dont l’année est la plus ancienne dans la base, on pourra écrire :

SELECT titre FROM livre

WHERE annee = (SELECT MIN(annee)

FROM livre);

Ici, la sous-requête calcule l’année minimum de la table livre (1933 dans notre base), puis affiche tous les titres de livres dont l’année vaut 1933.

Attention, la sous-requête ne doit pas nécessairement comporter une fonction d’agrégation. Il suffit qu'elle renvoie une table contenant une seule valeur

Ainsi, si nous voulons afficher les titres des livres publiés la même année que Moby Dick (sans connaître cette année), nous pouvons écrire :

SELECT titre FROM livre

WHERE annee =

(SELECT annee

FROM livre

WHERE titre = ’Moby Dick’);

Mais attention, si la sous-requête renvoie plusieurs résultats, le SGBD renverra une erreur :

# SELECT titre FROM livre WHERE annee =

(SELECT annee FROM livre WHERE titre LIKE ?{Astérix#’);

ERROR: more than one row returned by a subquery

used as an expression

Un opérateur utilisant la puissance des requêtes imbriquées est l'opérateur IN. L'expression e IN (g) renvoie vrai si et seulement si la valeur résultant de l'évaluation de e est l’une des lignes renvoyées par la requête g. Ainsi, pour exprimer la requête « afficher les titres des livres qui ont été publiés la même année qu'un livre dont le titre contient Astérix », on pourra écrire :

SELECT titre FROM livres

WHERE annee IN

(SELECT annee FROM livres

WHERE titre LIKE '%Astérix/');

","title":"Requêtes imbriquées"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

. Les requêtes de groupe sont explicitement hors

programme. Leur compréhension peut cependant aider lors de la création d'exercices, en particulier pour déterminer si la requête demandée est réalisable dans le fragment de SQL du programme de terminale.

Ces requêtes s'expriment au moyen de l'opérateur GROUP BY (éventuellement. accompagné de l'opérateur HAVING). Intuitivement, ces requêtes

permettent, de répondre à la question « donner le f de x pour chaque g distinct de la table t » où f est une fonction d’agrégation, x un attribut de la table et g un autre attribut appelé clé de groupe.

Cette requête s’écrira alors

SELECT g, f(x) FROM t GROUP BY g

Par exemple, si on souhaite connaître le nombre (f) de Livres (t) publiés pour chaque année (g) de la base, on écrira :

SELECT annee, COUNT(*) FROM livre GROUP BY annee;

","title":"Requêtes de groupe"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Avant de commencer les exercices, vous devez réaliser les étapes suivantes pour mettre à jour votre base sur :

http://217.182.207.90/phpmyadmin/

Etape 1 : Exporter votre base de données.

Etape 2 : Effacer toutes les tables de la base.

Etape 3 : Importer la base mediathèque.

A partir de cette base donner et tester le code SQL de chacune des requêtes ci-dessous.

Les mots en police fixe donnent une indication sur les attributs et les tables à utiliser dans la requête.

1. Tous les titres de livre.

2. Tous les noms d'usager.

3. Tous les noms d'usager en retirant les doublons.

4. Les titres des livres publiés avant 1980.

5. Les titres des livres dont le titre contient la lettre « À ».

6. Les isbn des livres à rendre pour le 01/01/2020.

7. Les noms d'auteurs triés par ordre alphabétique.

8. Les noms d'usagers vivant dans le 12ème ou 13ème arrondissement de Paris (codes postaux 75012 et 75013).

9. Les noms et adresses des usagers n’habitant pas dans une rue. (la chaîne « Rue » ne doit pas apparaître dans l’adresse).

10. Les années et titres des livres publiés lors d’une année bissextile.

On rappelle que ce sont les années divisibles par 4, mais pas celles divisibles par 100 sauf si elles sont divisibles par 400.

","title":"Exercice : requêtes simples, sans jointure ni imbrication"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

***** 9 et 10 pb sol

En utilisant cette base, donner et tester le code SQL

de chacune des requêtes ci-dessous.

1. Le titre des livres empruntés.

2. Le titre des livres empruntés à rendre avant le 31/03/2020.

3. Le nom et prenom de l’auteur du livre 1984”

4. Le nom et le prenom des usagers ayant emprunté des livres, sans doublons (ie. si un usager à emprunté plusieurs livres, il ne doit apparaître qu'une fois dans le résultat).

5. Même requête que précédemment, avec les noms triés par ordre alphabétique.

6. Les titre des livres publiés strictement avant Dune”.

7. Les noms et prenoms des auteurs des livres trouvés à la question précédente,

8. Comme la question précédente, en retirant les doublons.

9. Le nombre de résultats trouvés à la question précédente.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

SELECT titre FROM livre;

"},{"solution":"2.

SELECT nom FROM usager;

"},{"solution":"

SELECT DISTINCT nom FROM usager;

"},{"solution":"

4.
SELECT titre FROM livre WHERE annee <= 1980;

"},{"solution":"

SELECT titre FROM livre WHERE titre LIKE ’#A4’;

"},{"solution":"

6.
SELECT isbn FROM emprunt WHERE retour = '2020-01-01';

"},{"solution":"

7.
SELECT nom FROM auteur ORDER BY nom ASC;

"},{"solution":"

8.
SELECT nom FROM usager WHERE cp = '75012' OR cp = '75013';

"},{"solution":"

9.
SELECT nom, adresse FROM usager

WHERE NOT (adresse LIKE ’%Rue%');

"},{"solution":"

10.

SELECT annee, titre FROM livre WHERE annee % 4 = 0

AND (annee % 100 <> 0 OR annee % 400 = 0);

Dans ce dernier cas, on fera attention à l’utilisation des parenthèses, l’opérateur AND étant prioritaire sur le OR (comme en Python).

"}],[{"text":"

A l'aide de la base de données de la médiathèque, formuler simplement en francais les requêtes SQL suivantes.

1. SELECT * FROM livre WHERE titre LIKE '%Robot%';

2. SELECT nom, prenom FROM usager WHERE ville = 'Guingamp’;

3. SELECT u.nom, u.prenom

FROM usager AS u

JOIN emprunt AS e ON u.code_barre = e.code_barre

WHERE retour < '2020-04-02';

4. SELECT l.titre

FROM livre AS l

WHERE l.isbn IN (SELECT isbn FROM livres

WHERE annee > 1990);

5. Réécrire la requête 4 de façon à utiliser une seule clause SELECT.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

1. Renvoie tous les livres dont le titre contient « Robot ».

2. Renvoie le nom et le prénom des usagers habitant Guingamp.

3. Renvoie le nom et prénom des usagers devant rendre un livre avant le 2 avril 2020.

4. Renvoie les titres des livres publiés après 1990.

Cette dernière requête peut s’écrire :

SELECT l.titre

FROM livre AS l

WHERE l.annee > 1990;

"}],[{"text":"

En utilisant la base de données de la médiathèque, calculer tous les auteurs ayant collaboré sur un ouvrage et les renvoyer sous la forme (n1,p1,n2, p2, t) où les ni sont les noms des auteurs, pi leur prénoms et t le titre du livre sur lequel ils ont collaboré.

Si trois auteurs ont collaboré sur le même livre, on souhaite avoir trois lignes de résultats (auteur1/auteur2, auteur2/auteur3 et auteur1/auteur3) et non pas

les trois sur la même ligne.

Pour ne pas afficher deux fois le même couple, on demande en plus que n1 < n2.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

SELECT a1.nom, a1.prenom, a2.nom, a2.prenom, l.titre

FROM livre AS l

JOIN auteur_de AS ad1 ON l.isbn = ad1.isbn

JOIN auteur_de AS ad2 ON l.isbn = ad2.isbn

JOIN auteur AS a1 ON ad1.a_id = a1.a_id

JOIN auteur AS a2 ON ad2.a_id = a2.a_id

WHERE a1.nom < a2.nom;

Le cœur de cette requête est une jointure entre deux copies de la table auteur_de (nommée ad1 et ad2), sur le même isbn, celui que l’on utilise pour la jointure avec la table livre. La jointure entre ad1 et ad2 sur le

même isbn place sur la même ligne deux a_id de deux auteurs qui ont le même isbn. Il suffit alors de joindre avec les tables contenant les données.

"}],[{"text":"

On considère les trois tables décrites à la figure ci-dessous. Pour chacune des requêtes SQL ci-dessous, caleuler son résultat (à la main).

1. SELECT * FROM x WHERE b > 3;

2. SELECT DISTINCT e FROM z

WHERE e > 10 AND e < 50;

3. SELECT * FROM y WHERE c % 2 = 0 ORDER BY d ASC;

4. SELECT x.a , x.b FROM x

JOIN z ON z.a = x.a

WHERE z.e < 9;

5. SELECT DISTINCT x.b , y.d FROM x

JOIN z ON z.a = x.a

CREATE TABLE x (a INT PRIMARY KEY, b INT, CHECK (b >= 0));

CREATE TABLE y (c INT PRIMARY KEY, d INT, CHECK (d <= 30));

CREATE TABLE z (a INT REFERENCES X(a),

c INT REFERENCES Y(c), e INT, UNIQUE (a,c));

x:		y:		z:
a	b	c	d	a	c	e
1	1	9	9	1	11	30
2	2	10	10	2	14	9
2	2	11	9	5	15	1
4	2	12	20	7	17	3
5	1	13	30	1	10	50
6	9	14	9	2	9	8
7	1	15	1	2	15	15
		16	10	3	17	19
		17	10	4	16	12
				5	10	20
				2	11	30
				7	14	9
				7	9	12

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"1.

a	b
6	9

12
15
19
20
30

c	d
14 10 16 12	9 10 10 20

a	b
5 7 2	1 1 2

b	d
1 1 2 1 2 2	1 10 10 9 1 9

"}],[{"text":"

On considère les trois tables ci-dessous ;

x:		y:		z:
a	b	c	d	a	c	e
1	1	9	9	1	11	30
2	2	10	10	2	14	9
2	2	11	9	5	15	1
4	2	12	20	7	17	3
5	1	13	30	1	10	50
6	9	14	9	2	9	8
7	1	15	1	2	15	15
		16	10	3	17	19
		17	10	4	16	12
				5	10	20
				2	11	30
				7	14	9
				7	9	12

CREATE TABLE x (a INT PRIMARY KEY, b INT, CHECK (b >= 0));

CREATE TABLE y (c INT PRIMARY KEY, d INT, CHECK (d <= 30));

CREATE TABLE z (a INT REFERENCES X(a),

c INT REFERENCES Y(c), e INT, UNIQUE (a,c));

Pour chaeune des modifications ci-dessous, indiquer si elle réussit ou si elle échoue. Si elle réussit, indiquer comment la table est modifiée. Si elle échoue, expliqner

pourquoi.

Les questions sont indépendantes les unes des autres.

1, UPDATE x SET b = b +a;

2. UPDATE x SET b = b - 2;

3. INSERT INTO z VALUES (1, 17, 1);

4. INSERT INTO z VALUES (1, 18, 1};

5. INSERT INTO z VALUES (1, 10, 1);

6. DELETE FROM y WHERE c >= 12 AND c <= 13;

7. DELETE FROM y WHERE c >= 12 AND c <= 14;

8. INSERT INTO y VALUES (40, 20);

9. INSERT INTO y VALUES (20, 40);

10. DELETE FROM z

WHERE a % 2 = 0 OR c % 2 = 0 0R e % 2 = 0;

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

1. Succès. La table x devient :

a	b
1 2 3 4 5 6 7	2 4 5 6 6 15 8

2. Échec. La ligne (1,1) deviendrait (1,-1) après mise à jour, ce qui viole la contrainte « CHECK (b >= 0) ».

3. Succès. La ligne (1,17,1) est ajoutée à la table z.

4. Échec. La valeur 18 n’est pas une clé primaire dans la table y.

5. Échec. Une ligne (1,10,50) est déjà présente dans la table.

6. Succès. La table y devient :

c	d
9 10 11 14 15 16 17	9 10 9 9 1 10 10

7. Échec. La table z contient des entrées avec 11 ou 14. Les clés primaires correspondantes dans y ne peuvent pas être supprimées.

8. Succès. La ligne (40,20) est ajoutée à la table y.

9. Échec. La valeur 40 viole la contrainte « CHECK a <= 30 »

10. Succès. La table z devient :

a	c	e
5 7 3	15 17 17	1 3 19

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 5 Octobre 2020; Mis à jour : 6 Octobre 2020; Clics : 3729

Page 46 sur 79

1ère Générale NSI

Term. Générale NSI

Terminale STI2D SIN

Bts Ccst

Technico-commercial 3.0

Vidéos YouTube

tnsi json sequence 16 ; S.D. - Listes chaînées

tnsi json sequence 14 SQL - Systèmes de Gestion de Bases de Données

1nsi json Représentation approximative des nombres réels

1nsi json devoir 2 python quiz

tnsi json sequence 13 SQL Requêtes SQL et mises à jour