[[{"text":"Vous allez répondre à un QCM sur la partie 1 du programme de NSI : Encodage des données.
Le code ASCII de la lettre A est 0x41, celui de la lettre B est 0x42, celui de la lettre C est 0x43, etc. Quel est le code ASCII, en hexadécimal, de la lettre X (c'est la 24e lettre de l'alphabet usuel). ","theme":"A","nume":"2","sujet":3,"annee":2020},{"radio":[{"label":" 0x58","sol":true},{"label":" 0x64"},{"label":" 0x7A"},{"label":" 0x88"}]}],[{"text":"Quelle est la représentation en binaire de l'entier 64 sur un octet ?","theme":"A","nume":"3","sujet":3,"annee":2020},{"radio":[{"label":" 0101 0000"},{"label":" 1100 0100"},{"label":" 0100 0000","sol":true},{"label":" 0000 1100"}]}],[{"text":"Le codage d’une couleur se fait à l'aide de trois nombres compris chacun, en écriture décimale, entre 0 et 255 (code RVB).
La couleur « vert impérial » est codée, en écriture décimale, par (0, 86, 27).
Le codage hexadécimal correspondant est :","theme":"A","nume":"4","sujet":3,"annee":2020},{"radio":[{"label":" (0, 134, 39)"},{"label":" (0, 134, 1B)"},{"label":" (0, 56, 1B)","sol":true},{"label":" (0, 56, 39)"}]}],[{"text":"Quelle est l’écriture hexadécimale de l’entier dont la représentation en binaire non signé est 1100 0011 ? ","theme":"A","nume":"5","sujet":3,"annee":2020},{"radio":[{"label":" BB"},{"label":" C3","sol":true},{"label":" CB"},{"label":" 7610"}]}],[{"text":"Quel est le nombre maximal de bits du produit de deux entiers positifs codés sur 8 bits ?","theme":"A","nume":"6","sujet":3,"annee":2020},{"radio":[{"label":"8 "},{"label":" 16 ","sol":true},{"label":" 32 "},{"label":" 64"}]}],[{"text":"Un nombre entier signé est codé en complément à deux sur 8 bits par : 0111 0101. Que peut-on dire ?","theme":"A","nume":"1","sujet":4,"annee":2020},{"radio":[{"label":" c'est un nombre positif","sol":true},{"label":" c'est un nombre négatif"},{"label":" c'est un nombre pair"},{"label":" 7 bits auraient suffi à représenter cet entier signé en complément à deux"}]}],[{"text":"Comment s'écrit en base 16 (en hexadécimal) le nombre dont l'écriture binaire est 0010 1100 ? ","theme":"A","nume":"2","sujet":4,"annee":2020},{"radio":[{"label":" 1D"},{"label":" 2C","sol":true},{"label":" 3C "},{"label":" 3E"}]}],[{"text":"On considère les nombres dont l'écriture en base 16 (en hexadécimal) sont de la forme suivante : un 1 suivi de 0 en nombre quelconque, comme 1, 10, 100, 1000 etc.
Tous ces nombres sont exactement :","theme":"A","nume":"3","sujet":4,"annee":2020},{"radio":[{"label":" les puissances de 2"},{"label":" les puissances de 8"},{"label":" les puissances de 10"},{"label":" les puissances de 16","sol":true}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier qui s'écrit 106 en base 10 ? ","theme":"A","nume":"4","sujet":4,"annee":2020},{"radio":[{"label":" 6A","sol":true},{"label":" A6"},{"label":" 64 "},{"label":" 46"}]}],[{"text":"Quel est le résultat de l'addition binaire 0010 0110 + 1000 1110 ? ","theme":"A","nume":"5","sujet":4,"annee":2020},{"radio":[{"label":" 1010 1110"},{"label":" 0000 0110"},{"label":" 1011 0100","sol":true},{"label":" 0101 0001"}]}],[{"text":"Combien de bits doit-on utiliser au minimum pour représenter en base 2 le nombre entier 72 ?","theme":"A","nume":"6","sujet":4,"annee":2020},{"radio":[{"label":"2 "},{"label":"6 "},{"label":"7 ","sol":true},{"label":"8","sol":false}]}],[{"text":"Le résultat de la soustraction en binaire 101001 - 101 est égal au nombre binaire :","theme":"A","nume":"1","sujet":5,"annee":2020},{"radio":[{"label":" 100000"},{"label":" 101110"},{"label":" 100100","sol":true},{"label":" 100110"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont l'écriture hexadécimale (en base 16) est 3F ? ","theme":"A","nume":"2","sujet":5,"annee":2020},{"radio":[{"label":" 18"},{"label":" 45"},{"label":" 63","sol":true},{"label":" 315"}]}],[{"text":"Quel est l'entier relatif codé en complément à 2 sur un octet par le code 1111 1111 ? ","theme":"A","nume":"3","sujet":5,"annee":2020},{"radio":[{"label":" – 128"},{"label":" – 127","sol":false},{"label":"–1 ","sol":true},{"label":" 255"}]}],[{"text":"Quelle est, en écriture décimale, la somme d'entiers dont l'écriture en base 16 (hexadécimale) est 2A + 2 ? ","theme":"A","nume":"4","sujet":5,"annee":2020},{"radio":[{"label":" 22"},{"label":" 31"},{"label":" 49 "},{"label":" 44","sol":true}]}],[{"text":"Laquelle de ces affirmations concernant le codage UTF-8 des caractères est vraie ?","theme":"A","nume":"6","sujet":5,"annee":2020},{"radio":[{"label":" le codage UTF-8 est sur 7 bits"},{"label":" le codage UTF-8 est sur 8 bits"},{"label":" le codage UTF-8 est sur 1 à 4 octets","sol":true},{"label":" le codage UTF-8 est sur 8 octets"}]}],[{"text":"Soit 𝑛 l'entier dont la représentation binaire en complément à deux codée sur 8 bits est 0110 1110. Quelle est la représentation binaire de −𝑛 ?","theme":"A","nume":"1","sujet":6,"annee":2020},{"radio":[{"label":" 0001 0001"},{"label":" 0001 0010"},{"label":" 1001 0001","sol":false},{"label":" 1001 0010","sol":true}]}],[{"text":"À quoi sert le codage en complément à 2 ?","theme":"A","nume":"3","sujet":6,"annee":2020},{"radio":[{"label":" à inverser un nombre binaire"},{"label":" à coder des nombres entiers négatifs en binaire","sol":true},{"label":" à convertir un nombre en hexadécimal"},{"label":" à multiplier par 2 un nombre en binaire"}]}],[{"text":"Quel est le plus grand entier positif que l'on peut coder sur un mot de 16 bits ?","theme":"A","nume":"1","sujet":7,"annee":2020},{"radio":[{"label":" 215−1=32767"},{"label":" 215 = 32768"},{"label":" 216−1=65535","sol":true},{"label":" 216 = 65536"}]}],[{"text":"Combien de bits sont nécessaires pour représenter 15 en binaire ?","theme":"A","nume":"2","sujet":7,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 "},{"label":"4 ","sol":true},{"label":"5"}]}],[{"text":"Deux entiers positifs ont pour écriture en base 16 : A7 et 84. Quelle est l'écriture en base 16 de leur somme ?","theme":"A","nume":"4","sujet":7,"annee":2020},{"radio":[{"label":" 1811"},{"label":" 12B"},{"label":" 13A","sol":true},{"label":" A784"}]}],[{"text":"Quelle est la valeur de l’entier négatif –42 codé en complément à deux sur un octet (8 bits) ?","theme":"A","nume":"6","sujet":7,"annee":2020},{"radio":[{"label":" –0010 1010"},{"label":" 0010 1010"},{"label":" 1101 0101"},{"label":" 1101 0110","sol":true}]}],[{"text":"Parmi les caractères ci-dessous, lequel ne fait pas partie du code ASCII ?","theme":"A","nume":"2","sujet":8,"annee":2020},{"radio":[{"label":"a "},{"label":"B "},{"label":"@ "},{"label":"é","sol":true}]}],[{"text":"Quelle est l'écriture en hexadécimal (base 16) du nombre entier positif qui s'écrit 1110 1101 en base 2 ? ","theme":"A","nume":"3","sujet":8,"annee":2020},{"radio":[{"label":" DE"},{"label":" ED","sol":true},{"label":" EDF"},{"label":" FEFD"}]}],[{"text":"Que peut-on dire du programme Python suivant de calcul sur les nombres flottants ?
x = 1.0
while x != 0.0:
x = x - 0.1","theme":"A","nume":"1","sujet":9,"annee":2020},{"radio":[{"label":" l'exécution peut ne pas s'arrêter, si la variable x n'est jamais exactement égale à 0.0","sol":true},{"label":" à la fin de l'exécution, x vaut – 0.00001"},{"label":" à la fin de l'exécution, x vaut 0.00001"},{"label":" l'exécution s'arrête sur une erreur FloatingPointError"}]}],[{"text":"Combien de bits faut-il au minimum pour coder le nombre décimal 4085 ?","theme":"A","nume":"1","sujet":10,"annee":2020},{"radio":[{"label":"4"},{"label":" 12","sol":true},{"label":" 2042"},{"label":" 2043"}]}],[{"text":"Quelle est la représentation binaire du nombre entier 173 ?","theme":"A","nume":"3","sujet":10,"annee":2020},{"radio":[{"label":" 1010 1101","sol":true},{"label":" 1011 0101"},{"label":" 1011 0100"},{"label":" 1011 1101"}]}],[{"text":"Quelle est l'écriture décimale du nombre qui s'écrit 11,0101 en binaire ?","theme":"A","nume":"5","sujet":10,"annee":2020},{"radio":[{"label":"3"},{"label":" 3,0101"},{"label":" 3,05"},{"label":" 3,3125","sol":true}]}],[{"text":"Quelle est l'écriture binaire sur 8 bits en complément à deux de l'entier négatif –108 ?","theme":"A","nume":"6","sujet":10,"annee":2020},{"radio":[{"label":" 1000 1000"},{"label":" 0110 1100"},{"label":" 1001 0100","sol":true},{"label":" 1110 1100"}]}],[{"text":"Combien de nombres entiers positifs peut-on coder en binaire sur 4 bits ?","theme":"A","nume":"3","sujet":11,"annee":2020},{"radio":[{"label":"4"},{"label":" 16","sol":true},{"label":" 64"},{"label":" 256"}]}],[{"text":"La couleur « bleu roi » a pour code RGB (65,105,225), sa représentation en hexadécimal est :","theme":"A","nume":"4","sujet":11,"annee":2020},{"radio":[{"label":" #2852C2"},{"label":" #4169E1","sol":true},{"label":" #33A5C61"},{"label":" #C3T622"}]}],[{"text":"Quel est le nombre minimum de bits qui permet de représenter les 7 couleurs de l'arc-en-ciel ?","theme":"A","nume":"5","sujet":11,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 ","sol":true},{"label":"4 "},{"label":"5"}]}],[{"text":"Quelle est l’écriture décimale de l’entier dont la représentation en binaire non signé est 0001 0101 ? ","theme":"A","nume":"1","sujet":12,"annee":2020},{"radio":[{"label":" 15"},{"label":" 21","sol":true},{"label":" 111"},{"label":" 420"}]}],[{"text":"Combien de bits sont nécessaires pour écrire le nombre entier 16 en base 2 ?","theme":"A","nume":"2","sujet":12,"annee":2020},{"radio":[{"label":"4 "},{"label":"5 ","sol":true},{"label":"6 "},{"label":"7"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont la représentation binaire est 1101 0101 ? ","theme":"A","nume":"3","sujet":12,"annee":2020},{"radio":[{"label":" 135"},{"label":" 213","sol":true},{"label":" 231"},{"label":" -42"}]}],[{"text":"Combien de valeurs entières positives ou nulles un octet peut-il représenter ?","theme":"A","nume":"4","sujet":12,"annee":2020},{"radio":[{"label":"2 "},{"label":"8"},{"label":" 16 "},{"label":" 256","sol":true}]}],[{"text":"L'entier positif 255 se représente en hexadécimal (base 16) par :","theme":"A","nume":"3","sujet":13,"annee":2020},{"radio":[{"label":" 99 "},{"label":" AA "},{"label":" CC "},{"label":" FF","sol":true}]}],[{"text":"Quelle est l'écriture décimale de l'entier qui s'écrit 1010 en binaire ?","theme":"A","nume":"2","sujet":14,"annee":2020},{"radio":[{"label":"5 "},{"label":" 10 ","sol":true},{"label":" 20 "},{"label":" 22"}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier dont la représentation binaire s'écrit : 0100 1001 1101 0011 ?","theme":"A","nume":"1","sujet":15,"annee":2020},{"radio":[{"label":" 18899"},{"label":" 3D94"},{"label":" 49D3","sol":true},{"label":" 93A3"}]}]]
Consignes :
- 1 seul moniteur d'allumé;
- 1 seul onglet ouvert sur sciencesappliquees.com dans le navigateur chrome;
- Aucun autre logiciel doit être exécuté pendant le test.
Si vous enfreignez une de ces consignes, vous aurez 0 avec 2 heures de colles pour tentative de triche!
","title":""}],[{"text":"Quel est un avantage du codage UTF8 par rapport au codage ASCII ?","theme":"A","nume":"1","sujet":3,"annee":2020},{"radio":[{"label":" il permet de coder un caractère sur un octet au lieu de deux"},{"label":" il permet de coder les majuscules"},{"label":" il permet de coder tous les caractères","sol":true},{"label":" il permet de coder différentes polices de caractères"}]}],[{"text":"On considère les codes ASCII en écriture hexadécimale (en base 16).Le code ASCII de la lettre A est 0x41, celui de la lettre B est 0x42, celui de la lettre C est 0x43, etc. Quel est le code ASCII, en hexadécimal, de la lettre X (c'est la 24e lettre de l'alphabet usuel). ","theme":"A","nume":"2","sujet":3,"annee":2020},{"radio":[{"label":" 0x58","sol":true},{"label":" 0x64"},{"label":" 0x7A"},{"label":" 0x88"}]}],[{"text":"Quelle est la représentation en binaire de l'entier 64 sur un octet ?","theme":"A","nume":"3","sujet":3,"annee":2020},{"radio":[{"label":" 0101 0000"},{"label":" 1100 0100"},{"label":" 0100 0000","sol":true},{"label":" 0000 1100"}]}],[{"text":"Le codage d’une couleur se fait à l'aide de trois nombres compris chacun, en écriture décimale, entre 0 et 255 (code RVB).
La couleur « vert impérial » est codée, en écriture décimale, par (0, 86, 27).
Le codage hexadécimal correspondant est :","theme":"A","nume":"4","sujet":3,"annee":2020},{"radio":[{"label":" (0, 134, 39)"},{"label":" (0, 134, 1B)"},{"label":" (0, 56, 1B)","sol":true},{"label":" (0, 56, 39)"}]}],[{"text":"Quelle est l’écriture hexadécimale de l’entier dont la représentation en binaire non signé est 1100 0011 ? ","theme":"A","nume":"5","sujet":3,"annee":2020},{"radio":[{"label":" BB"},{"label":" C3","sol":true},{"label":" CB"},{"label":" 7610"}]}],[{"text":"Quel est le nombre maximal de bits du produit de deux entiers positifs codés sur 8 bits ?","theme":"A","nume":"6","sujet":3,"annee":2020},{"radio":[{"label":"8 "},{"label":" 16 ","sol":true},{"label":" 32 "},{"label":" 64"}]}],[{"text":"Un nombre entier signé est codé en complément à deux sur 8 bits par : 0111 0101. Que peut-on dire ?","theme":"A","nume":"1","sujet":4,"annee":2020},{"radio":[{"label":" c'est un nombre positif","sol":true},{"label":" c'est un nombre négatif"},{"label":" c'est un nombre pair"},{"label":" 7 bits auraient suffi à représenter cet entier signé en complément à deux"}]}],[{"text":"Comment s'écrit en base 16 (en hexadécimal) le nombre dont l'écriture binaire est 0010 1100 ? ","theme":"A","nume":"2","sujet":4,"annee":2020},{"radio":[{"label":" 1D"},{"label":" 2C","sol":true},{"label":" 3C "},{"label":" 3E"}]}],[{"text":"On considère les nombres dont l'écriture en base 16 (en hexadécimal) sont de la forme suivante : un 1 suivi de 0 en nombre quelconque, comme 1, 10, 100, 1000 etc.
Tous ces nombres sont exactement :","theme":"A","nume":"3","sujet":4,"annee":2020},{"radio":[{"label":" les puissances de 2"},{"label":" les puissances de 8"},{"label":" les puissances de 10"},{"label":" les puissances de 16","sol":true}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier qui s'écrit 106 en base 10 ? ","theme":"A","nume":"4","sujet":4,"annee":2020},{"radio":[{"label":" 6A","sol":true},{"label":" A6"},{"label":" 64 "},{"label":" 46"}]}],[{"text":"Quel est le résultat de l'addition binaire 0010 0110 + 1000 1110 ? ","theme":"A","nume":"5","sujet":4,"annee":2020},{"radio":[{"label":" 1010 1110"},{"label":" 0000 0110"},{"label":" 1011 0100","sol":true},{"label":" 0101 0001"}]}],[{"text":"Combien de bits doit-on utiliser au minimum pour représenter en base 2 le nombre entier 72 ?","theme":"A","nume":"6","sujet":4,"annee":2020},{"radio":[{"label":"2 "},{"label":"6 "},{"label":"7 ","sol":true},{"label":"8","sol":false}]}],[{"text":"Le résultat de la soustraction en binaire 101001 - 101 est égal au nombre binaire :","theme":"A","nume":"1","sujet":5,"annee":2020},{"radio":[{"label":" 100000"},{"label":" 101110"},{"label":" 100100","sol":true},{"label":" 100110"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont l'écriture hexadécimale (en base 16) est 3F ? ","theme":"A","nume":"2","sujet":5,"annee":2020},{"radio":[{"label":" 18"},{"label":" 45"},{"label":" 63","sol":true},{"label":" 315"}]}],[{"text":"Quel est l'entier relatif codé en complément à 2 sur un octet par le code 1111 1111 ? ","theme":"A","nume":"3","sujet":5,"annee":2020},{"radio":[{"label":" – 128"},{"label":" – 127","sol":false},{"label":"–1 ","sol":true},{"label":" 255"}]}],[{"text":"Quelle est, en écriture décimale, la somme d'entiers dont l'écriture en base 16 (hexadécimale) est 2A + 2 ? ","theme":"A","nume":"4","sujet":5,"annee":2020},{"radio":[{"label":" 22"},{"label":" 31"},{"label":" 49 "},{"label":" 44","sol":true}]}],[{"text":"Laquelle de ces affirmations concernant le codage UTF-8 des caractères est vraie ?","theme":"A","nume":"6","sujet":5,"annee":2020},{"radio":[{"label":" le codage UTF-8 est sur 7 bits"},{"label":" le codage UTF-8 est sur 8 bits"},{"label":" le codage UTF-8 est sur 1 à 4 octets","sol":true},{"label":" le codage UTF-8 est sur 8 octets"}]}],[{"text":"Soit 𝑛 l'entier dont la représentation binaire en complément à deux codée sur 8 bits est 0110 1110. Quelle est la représentation binaire de −𝑛 ?","theme":"A","nume":"1","sujet":6,"annee":2020},{"radio":[{"label":" 0001 0001"},{"label":" 0001 0010"},{"label":" 1001 0001","sol":false},{"label":" 1001 0010","sol":true}]}],[{"text":"À quoi sert le codage en complément à 2 ?","theme":"A","nume":"3","sujet":6,"annee":2020},{"radio":[{"label":" à inverser un nombre binaire"},{"label":" à coder des nombres entiers négatifs en binaire","sol":true},{"label":" à convertir un nombre en hexadécimal"},{"label":" à multiplier par 2 un nombre en binaire"}]}],[{"text":"Quel est le plus grand entier positif que l'on peut coder sur un mot de 16 bits ?","theme":"A","nume":"1","sujet":7,"annee":2020},{"radio":[{"label":" 215−1=32767"},{"label":" 215 = 32768"},{"label":" 216−1=65535","sol":true},{"label":" 216 = 65536"}]}],[{"text":"Combien de bits sont nécessaires pour représenter 15 en binaire ?","theme":"A","nume":"2","sujet":7,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 "},{"label":"4 ","sol":true},{"label":"5"}]}],[{"text":"Deux entiers positifs ont pour écriture en base 16 : A7 et 84. Quelle est l'écriture en base 16 de leur somme ?","theme":"A","nume":"4","sujet":7,"annee":2020},{"radio":[{"label":" 1811"},{"label":" 12B"},{"label":" 13A","sol":true},{"label":" A784"}]}],[{"text":"Quelle est la valeur de l’entier négatif –42 codé en complément à deux sur un octet (8 bits) ?","theme":"A","nume":"6","sujet":7,"annee":2020},{"radio":[{"label":" –0010 1010"},{"label":" 0010 1010"},{"label":" 1101 0101"},{"label":" 1101 0110","sol":true}]}],[{"text":"Parmi les caractères ci-dessous, lequel ne fait pas partie du code ASCII ?","theme":"A","nume":"2","sujet":8,"annee":2020},{"radio":[{"label":"a "},{"label":"B "},{"label":"@ "},{"label":"é","sol":true}]}],[{"text":"Quelle est l'écriture en hexadécimal (base 16) du nombre entier positif qui s'écrit 1110 1101 en base 2 ? ","theme":"A","nume":"3","sujet":8,"annee":2020},{"radio":[{"label":" DE"},{"label":" ED","sol":true},{"label":" EDF"},{"label":" FEFD"}]}],[{"text":"Que peut-on dire du programme Python suivant de calcul sur les nombres flottants ?
x = 1.0
while x != 0.0:
x = x - 0.1","theme":"A","nume":"1","sujet":9,"annee":2020},{"radio":[{"label":" l'exécution peut ne pas s'arrêter, si la variable x n'est jamais exactement égale à 0.0","sol":true},{"label":" à la fin de l'exécution, x vaut – 0.00001"},{"label":" à la fin de l'exécution, x vaut 0.00001"},{"label":" l'exécution s'arrête sur une erreur FloatingPointError"}]}],[{"text":"Combien de bits faut-il au minimum pour coder le nombre décimal 4085 ?","theme":"A","nume":"1","sujet":10,"annee":2020},{"radio":[{"label":"4"},{"label":" 12","sol":true},{"label":" 2042"},{"label":" 2043"}]}],[{"text":"Quelle est la représentation binaire du nombre entier 173 ?","theme":"A","nume":"3","sujet":10,"annee":2020},{"radio":[{"label":" 1010 1101","sol":true},{"label":" 1011 0101"},{"label":" 1011 0100"},{"label":" 1011 1101"}]}],[{"text":"Quelle est l'écriture décimale du nombre qui s'écrit 11,0101 en binaire ?","theme":"A","nume":"5","sujet":10,"annee":2020},{"radio":[{"label":"3"},{"label":" 3,0101"},{"label":" 3,05"},{"label":" 3,3125","sol":true}]}],[{"text":"Quelle est l'écriture binaire sur 8 bits en complément à deux de l'entier négatif –108 ?","theme":"A","nume":"6","sujet":10,"annee":2020},{"radio":[{"label":" 1000 1000"},{"label":" 0110 1100"},{"label":" 1001 0100","sol":true},{"label":" 1110 1100"}]}],[{"text":"Combien de nombres entiers positifs peut-on coder en binaire sur 4 bits ?","theme":"A","nume":"3","sujet":11,"annee":2020},{"radio":[{"label":"4"},{"label":" 16","sol":true},{"label":" 64"},{"label":" 256"}]}],[{"text":"La couleur « bleu roi » a pour code RGB (65,105,225), sa représentation en hexadécimal est :","theme":"A","nume":"4","sujet":11,"annee":2020},{"radio":[{"label":" #2852C2"},{"label":" #4169E1","sol":true},{"label":" #33A5C61"},{"label":" #C3T622"}]}],[{"text":"Quel est le nombre minimum de bits qui permet de représenter les 7 couleurs de l'arc-en-ciel ?","theme":"A","nume":"5","sujet":11,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 ","sol":true},{"label":"4 "},{"label":"5"}]}],[{"text":"Quelle est l’écriture décimale de l’entier dont la représentation en binaire non signé est 0001 0101 ? ","theme":"A","nume":"1","sujet":12,"annee":2020},{"radio":[{"label":" 15"},{"label":" 21","sol":true},{"label":" 111"},{"label":" 420"}]}],[{"text":"Combien de bits sont nécessaires pour écrire le nombre entier 16 en base 2 ?","theme":"A","nume":"2","sujet":12,"annee":2020},{"radio":[{"label":"4 "},{"label":"5 ","sol":true},{"label":"6 "},{"label":"7"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont la représentation binaire est 1101 0101 ? ","theme":"A","nume":"3","sujet":12,"annee":2020},{"radio":[{"label":" 135"},{"label":" 213","sol":true},{"label":" 231"},{"label":" -42"}]}],[{"text":"Combien de valeurs entières positives ou nulles un octet peut-il représenter ?","theme":"A","nume":"4","sujet":12,"annee":2020},{"radio":[{"label":"2 "},{"label":"8"},{"label":" 16 "},{"label":" 256","sol":true}]}],[{"text":"L'entier positif 255 se représente en hexadécimal (base 16) par :","theme":"A","nume":"3","sujet":13,"annee":2020},{"radio":[{"label":" 99 "},{"label":" AA "},{"label":" CC "},{"label":" FF","sol":true}]}],[{"text":"Quelle est l'écriture décimale de l'entier qui s'écrit 1010 en binaire ?","theme":"A","nume":"2","sujet":14,"annee":2020},{"radio":[{"label":"5 "},{"label":" 10 ","sol":true},{"label":" 20 "},{"label":" 22"}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier dont la représentation binaire s'écrit : 0100 1001 1101 0011 ?","theme":"A","nume":"1","sujet":15,"annee":2020},{"radio":[{"label":" 18899"},{"label":" 3D94"},{"label":" 49D3","sol":true},{"label":" 93A3"}]}]]
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1389
[[{"title":"S.D. : Listes chaînées","posi":0},{"text":"
"},{"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.
![\"\"](\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAfwAAABMCAYAAACI7wXSAAAVMklEQVR4Ae1dT4gcxReeo4h/Al486UUEIYcEPQgeFBTU9aBsyE1RDD89eJCwIOiyCsviIexJNgdlRQ2OJ5NDYBHE1YOgB2ESCGwOgUgIMgYPoyRkDjnUj7frN1Nd21Vd1V1vetr9Bobq6Vf96vVX33vfVE/PTM8kPG7fvm3kqfXQ9i9xX7x4USv8XWy6jA/xD1NDGx9t/+R/u/NL/Il/GIGwNUd96IWHKFpzDFj0WHyl7V9Go+AXMbdfEX8bjf3b2vho+5czIv/3zyv2EH8gUd5q46PtX87qoPOfgl/O7Vp7tQnbdf9MuDCttOeX+BP/MAJhqzY/tf2T/8ZQ8MMcT7JqE7br/plwYTppzy/xJ/5hBMJWbX5q+yf/KfhhhidatQnbdf9MuDChtOeX+BP/MAJhqzY/tf2T/xT8MMMTrdqE7bp/JlyYUNrzS/yJfxiBsFWbn9r+yX8KfpjhiVZtwnbdPxMuTCjt+SX+xD+MQNiqzU9t/+Q/BT/M8ESrNmG77p8JFyaU9vwSf+IfRiBs1eantn/yn4IfZniiVZuwXffPhAsTSnt+iT/xDyMQtmrzU9s/+U/BDzM80apN2K77Z8KFCaU9v8Sf+IcRCFu1+antn/yn4IcZnmjVJmzX/TPhwoTSnl/iT/zDCISt2vzU9k/+U/DDDE+0ahO26/6ZcGFCac8v8Sf+YQTCVm1+avsn/yn4YYYnWrUJ23X/TLgwobTnl/gT/zACYas2P7X9k/8U/DDDE63ahO26fyZcmFDa80v8iX8YgbBVm5/a/sl/Cn6Y4YlWbcJ23T8TLkwo7fkl/sQ/jEDYqs1Pbf/kf4LgP/7446bX6/HZMgZvvvlmOCsbWJlwfvDI//nIffLfz1Ht/HX9Uw/mIyc+/fRTPykcS/Sf57DgzcfksuA5DLZeugXJMjXeJP/J/8Yk+o/9PSsFfz5yQlXw33rrLSMDdO2Jgv3YY491LnbBGvFT8P1ldxaCT/63k/vkv5/3sGjyX8Zw/UPwu6YFiBfxv/rqq53UBMQv5xP7SF7hS8Hr4gMFQwS/iw/ET8H3z55bkPw90y3An/xPxy7HEcCf/Pejqcl/GdX1X0dw/NHP3oL4RfC7+ED8FPyS2UPBoOCXgPPvLjeh/T3rWy5evFj/4IojNeMHfyj4FZOgZAb+FHw/wJr8l1Fd/3UExx/97C2I/0AJvhTgmKcIpQDEgjd7YsqIKHjHjh2Lmq+YOWWfOO4LTuR/O7zHqOR/PFdnldcQzJQVJuZzHlrE33XBX1lZidYEXtKfB+ZFxICCxxWOHyx3BeLvmW4B/nzDm45djiOAP/nvR1OT/zKq6x+CScH3z4mmpQ7+FHzNGcnomwWvGky3IFUfEd8D+FPw4zHL2RP4U/D9qGryX0Z1/dcRHH/0s7cg/q6v8FPecFHwZ8+zWiOy4FXD5hak6iPiewB/Cn48Zjl7An8Kvh9VTf7LqK5/CGaK4Pijn70F8VPwS7BHwrHglYAzg13AnwXPD7ZbkPw90y3An/xPxy7HEcCf/Pejqcl/GdX1D8Gk4PvnRNNSB3+u8DVnJKNvFrxqMN2CVH1EfA/gT8GPxyxnT+BPwfejqsl/GdX1X0dw/NHP3oL4ucIvwR4Jx4JXAs4MdgF/Fjw/2G5B8vdMtwB/8j8duxxHAH/y34+mJv9lVNc/BJMrfP+caFrq4M8Vfs0ZuXHjhjl9+rSRr8k98sgj5q677tr92uI999xjDh8+bF5//XXT7/fNnTt3ao5QPIwFr4hH2Su3IJX1qbsP+FPw9xAk/+sxSb4yp/XQ5L/E7PqvIzha517HL+LnCr8EPRa8PVCuXbtm3n777eg/ETp06JD58MMPGws/8OcKp4Sc/+5yC5K/Z7oF+B90wSf/07ljH0HBt9Fod5uCH8CfBc/s/t4yVvIgS2wrVwG+++67AMJhE/Cn4PtxguB/8cUX5qeffvJ3rGEB/gdZ8OXSLflfgzzWIW0JvuTE77//bkWSvon8wpGofbykD0SKreDiPos9mr2qg//cXNIf/to3659smM1vBs1Q8ByNgl33p3Xfe++96FU9JqKsrZsciJ+C75lg65KjFDbB/plnnskm/MA/p+CPrgzM2c82zPLJJbN08oQ5cXzRnDi5ZvrfD8w4zydBE7AQP/k/gWTfhito+zpk2NGW4MsbYMmJN954o7bwu/igvtWtafvgvDk0v5zvm/XVZbP8vjyXzPLq+m4+jMb7ejfegfi1Lukj5zCOtDkf8JuCf3QECD5nwZue/Mis43/mj2wahbmd/DRtnYL3wQcfZBF7TNCXX345PfXILeBPwfcDZhckuYcCeOcQfuCfhf/jHbP+YtVfay6arUsj/8kmWhA/+e8HzuaPv1czS1uCL1E//fTTk5yoI/wuPsivFMHxoTc4szSJDX7ddvnMIKs2wD8Fv2RWUDCyFDzH//jC5nSyX+xnnVQMhfhTC97XX389jQ1vSjK0g0HalQzET8HHjO5v7YKEVT6SWtomwg/8m/N/aNaPVIn91N6/lOftL+In//fzBnts/mBf7rZNwccq386JFOF38YGfpoJ/9Vy12GOshU/S6mZo/uCTgl+CEgpG84I3dT4eDc0v5zbMUVtA50jwb926ZR588EEVwX/22WenQERsAX8Kvh8styDZq3wkt7R1hB/4N+X/zpnFAp8W3u+bwfXR7iV8yYetT04U7L3euhn6TznagvhTBJ/8j4Y3umObgi9B2qt8OydihN/NLxzfSPBvDsyCXf97C6b/29W9fLg5MoPvN4v60OuZrevRcAc7In4KfglMKBhNC565c9WsH18wR32rnDkSfLm7HqTQaL/99tsSpMt3AX8Kfjk+stctSGWrfHseU4Qf+Dfj/9CsWcXt6Op26ckMzy8XeLeZYZWP+FMEn/wvnZ5GO9sW/LJVvp0TIeF38wvHNRH8ItdPmEHZp1jD7cKbghz5IJOI+Cn4JZRGwWhW8IwxY/cd3fTy5e4EzJHga63uQbTnn3++BOnyXcCfgl+Oj+x1C5Ls863yMQfSxgg/8G/E/+H2pMj0eotm4L1aPzIb1hvixTM7/pOOtCD+FMEn/yPBTejWtuBLqL5Vvp0TZcLv5hf6NxH8rZNHJzmxdM5/LWv7/Wm/HPkgOCB+Cn4JgVEwGhU88XtnZPq7d2GumbXVveeSfQPTnAi+fIUOhNBs//zzzxK09+8C/hT8/dhgj1uQZH/VKt+e25DwA/8m/B9fir1XZWz6x6dvhBc/m73gk/9gVd52HgS/apVv54Qt/G5+oV99wR+bTeuNbWjlvm29MTjxTfN8kFlF/BT8Eo7nKHglbvd2XelPwO/NieDnvjMf5HLb2Mv6wJ+C72VR6Qpfeses8u15KRN+4N9E8M31s1OeHw/dnDo2m9ab4BwrGsQfu8In//08a2KZB8GX+GNW+XZOiPBfvnx5N8dw/rDXF3xjRpcHZvvHbbP9/bbZKbucL4PdHJgT1kdh/cveS2MILapF/BT8ErhQMBoVvBK/smt8ef4E/+WXX54WZ4tsIEmudnV11YNKcTfwp+AXcbFfuSsQ2FJW+fa82sIP/DX4jzjRDn9cK3AvtPLBMVUt4o8VfPK/CtF69nkR/JRVvp0Tr7322uR7/NjfRPC9KMrvUIzH5uqFrYLY93rLZpjpNyoQPwW/ZBZQMDQK3jwK/pNPPlkouiAH2+ml5oOChQj/o48+ussHDf7b6Xb1+3WHd2tZChzyN1bwyf+Dx/OUfJYVP/rnFfzix1kYY69dMIO/7Gxptg3fFPwSHFEwNArePAr+E088MSE0iMH24BbBBx54QFfwx0PTf39hH+dyXb5E/sYKPvl/cLkeU+fuv//+CVezC771cZYby+aP/hv7SmQruAu+KfglMKFgHBTBl+/JgxCardypLwlT9Xz44Yd343nqqacq+1b58tk3NjaMPH32HPtXVlbU/Ifih2CnzqV8/i8fCejxf2wG3xQv4e/FuGC2Mn1WKemM+GMFn/yvzsk6+dAW/91YP/7441r17b777jMfffSRGY1Gk+PFd87HzvlNs3Zqw6yvLhW+jofcXcsk+vBHwS+ZPRSMgyL4Kf+IB+LUaWOTBfjzM/wScv67y/cZvvxxSOrcQOgxGvDPyf/hb32zWHJ/iPwYT67PKd34YwWf/Adyedt5+Qw/9UZWWdEvLy+b4XC6wkZOxdawukgOL5x18mQty49RIf4DJfgoklXt0aN734PMWfBAgHm8pP/5558niwQIlNLG/sQuBEcEv2qu5tkuBW/W8T300EPRcynJj7uR7Tjz8n9szlrfK57w5cU188sV363KyJZ6LfgTK/jk/20VnrbBf5vHsi38nnCu5A2nbZMVPYTe9YN+2oIvjB9fsm7s7h0129P3HfUS4j/0tTy5sunOje91z2dw9+cteMU5mkfB/+OPP6KTAsRPbeUvc2MfKNgU/LRCLMUoZl58Qo88yMf/sdk66X4+vGj6v2WoYAEygT+xgk/+p/EMPKlq50HwhetVORESepwjfNQW/NHArP1P/ilyySyd2g7/h8qdncLd+psXmn81D/F3fYWfJPiBGlEwoWAclBW+nPyxY8cqEwOkqdPGfiVPYgH+vKRfoGXhBQqRvRP3Pvjmx710bx9rbwP/pvzf+ab4W/kLq2fNKNPXjOx43W3EHyv4cjz576LY/HXbl/SrvqIql+7xGb17tm5+IafqCn7hh6h6i2YnlAeO4Oe4mRXxd13wU/Cfi7/HnccVvpD9559/VhP8Q4cOmb///tvNKe9rFGwKvheiyWUt9Ah9dh8r9PAF/BsJvvNHIYuf5fvnL8TpaxF/iuCT/z406+9vW/B9n92HhB5nm1vw5WfW7XtYzl7BSPvbgkYEf5Z6/7G+PRR8HzLWCrNRwfP4L0zmnPzSHkJ95513VET/9OnTGCKqRcGm4PvhcgtS2eo+VegxGvBvwv/xhQ2LS8tZbjxCfFUt4k8RfPFJ/lchm2ZvU/DLVvcxQo8zdPMLgpmywoSvvXZU/KvoI2tm52axx+6rv4q/tNc7smFy3OmC+LnCL8EcBaNJwStxu7trngVfAsz9IyQiOqkP4E/B9yNnFyR3dV9X6DEa8G/C/50zxcv5vSNyI2zVs2eWzl1FGLVbxJ8q+DIg+V8b9n0Htin49uo+RehxEnZ+yT4IZn3BN2b0q/tDUwtm8/zAXL0+NFcvDczZT5Ym42C8HJ/f2/FT8DHDVouC0aTgWe4Km/Mu+NeuXTOHDx/eRzwQMKV95ZVXCuce+wL4U/D9iNkFCav7pkKP0YB/E/7vv1nPvXmv/PVCC3+eg/OWlvy30Wi23ZbgY3VfR+hxxnZ+yT7UvSaCb8zYbJV9Y8Xz7YETGT8GQ/wUfMyw1eYoeJa74uaV2D8VKR6W8grx11nhyDg3btwwL7zwwoTkIEtKK99trvtA/BR8P4IoSLK6zyX0GA34NxP86V98pvCm7RW+YED+gwnN2rYE/9133/XejBd7Rsgv9AeHmwn+nred8+5K33nze2TJbF3KcSEf0U/fsFDwp5hMtnIUvImzFjYQf13BR8inTp0y9957b5Lwy9fv+v0+XNRqET8F3w8fCpL8CljuB/BvIvi5Y0rxh/jJfz9q4I+/R3NLW4KfIydcfHIK/i6yd0Zm59dt0z/TN1vyD3rn+ubs+W2zcz1/Pst4iD9V8OUNjuRT1fPuu++ejIGxqo4Re2yNgc+UN1xzcZd+8zSq9iBACkBNC56M9M8//xgR/qrfG3/uueeM/IBJjgfip+D70XQLkr9nugX4xyZj+gi6RyB+8t+PsyZ/MGpbgo/xm7QuPnUEp8n4uY9F/HUEH8dqtLE1BmNT8EuYkbPg2e7lUucPP/xgvvrqq93fiJeVvHyd6datW3a3xtuIn4Lvh9ItSP6e6RbgH5uM6SPoHoH4cwi+HSn5b6NRvU3Br8ZoVj0gmBT8EsRRMFjwSsCZwS7gT8H3g03B92MD/uQWfP+IeS2In/z346rJfxnV9Q/BTFlh+qOfvQXxU/BLsEfCUfBLwJnBLuDPgucH2y1I/p7pFuBP/qdjl+MI4E/++9HU5L+M6vqHYFLwnRsMPd8wAF5VbWyNgZ8U/PkZvj9/5srCglc9HW5Bqj4ivgfwj03GeM+z6Yn4ucL3463JH4zKS/pAov0Wgpm6wm8/8r0IED8Fv2RGWPBKQHF2seA5gFgvwR8KvgXKDDeBP1f4ftC189f1X0dw/NHP3oL4Kfgl2CPhWPBKwJnBLuDPgucH2y1I/p7pFuBP/qdjl+MI4E/++9HU5L+M6vqHYKasMP3Rz96C+Cn4Jdgj4VjwSsCZwS7gz4LnB9stSP6e6RbgT/6nY5fjCOBP/vvR1OS/jOr6h2BS8P1zommpgz8/w9eckYy+WfCqwXQLUvUR8T2APwU/HrOcPYE/Bd+Pqib/ZVTXfx3B8Uc/ewvi5wq/BHskHAteCTgz2AX8WfD8YLsFyd8z3QL8yf907HIcAfzJfz+amvyXUV3/EEyu8P1zommpgz9X+JozktE3C141mG5Bqj4ivgfwp+DHY5azJ/Cn4PtR1eS/jOr6ryM4/uhnb0H8XOGXYI+EA0hs8373MhZPFrwScv67yy1I/p7pFvK/Hb67eUH++7mryX8Z1fXvzg1ft5MjKVdYklf4nNR2JhW4s+C1U/Ao+O3ynvz38x4WV5CxP1fr+secsG03N1QEX5xubGzsPmVb46npXy7byPOll15SiX2W+ORKYNePm9CuPcfrrv7wyCznVyO3yP9q9pL/YYxcfHLzVLP+I9aVlZVJ/UdOSAt7k1Y7/pD/8MxNrdErfDnEnfCpmzxb2v4lyq4KDvGv5pg2f7run/wPc0h7fok/8Q8jELbm4GcPTg5KK4J/UM51Hs+T+N9ulX/En/jPY12YVUwHnf8U/NvtFoBZEX1exjnoCdf2PBD/dvOd+BP/NmsAL+mHr6IkWTGRSQcldO66fzlVKXhaj67jox0/8Q8zj/i3iw/x18efgh/GOMmqTdiu+xcwKfh+SmnPL/H3Yy8W4t8uPsRfH38KfhjjJKs2YbvuX8Ck4PsppT2/xN+PvViIf7v4EH99/Cn4YYyTrNqE7bp/AZOC76eU9vwSfz/2YiH+7eJD/PXxp+CHMU6yahO26/4FTAq+n1La80v8/diLhfi3iw/x18efgh/GOMmqTdiu+xcwKfh+SmnPL/H3Yy8W4t8uPsRfH38KfhjjJKs2YbvuX8Ck4PsppT2/xN+PvViIf7v4EH99/P8PrELQu7XNQhMAAAAASUVORK5CYII=\")
![\"liste11.png](\"https://sciencesappliquees.com/images/nsi/liste12.png\")
![](\"https://sciencesappliquees.com/images/nsi/liste1.png\")
"}],[{"text":"
","title":"Définition récursive des listes chaînées"},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste3.png\")
![](\"https://sciencesappliquees.com/images/nsi/liste4.png\")
"}],[{"text":"
","title":"Opérations sur les listes"},{"edit":""}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste5.png\")
","title":"Longueur d'une liste"},{"edit":"
"}],[{"text":"
"}],[{"text":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste6.png\")
","title":"Concaténation de deux listes"},{"edit":"
"}],[{"text":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste7.png\")
![](\"https://sciencesappliquees.com/images/nsi/liste8.png\")
","title":"Modification d'une liste"},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste9.png\")
![](\"https://sciencesappliquees.com/images/nsi/liste10.png\")
","title":"Du danger des listes mutables"},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/liste11.png\")
","title":"Encapsulation dans un objet"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":""}]]
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
| 1 | 1 | 2 | 3 | 5 | 8 | 13 |
il faut d'une façon où d'une autre construire le nouveau tableau
| v | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
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.
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 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.
| 1 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Enfin, on écrit la valeur v dans la première case du tableau.
| v | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
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.
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.
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.
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.
Mettre le résultat ici.
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":"Dans cette section, nous allons programmer quelques opérations fondamentales sur les listes.
D'autres opérations sont proposées en exercices.
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.
Mettre le résultat ici (code et figure).
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.
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).
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.
Mettre le résultat ici (code et figure).
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).
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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.
É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).
def listeN(n):
lst = None
while n > 0:
lst = Cellule(n, lst)
n -= 1
return lst
l2 = listeN(5)
afficher(l2)
É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
Mettre le résultat ici (code et figure).
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)
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
Mettre le résultat ici (code et figure).
def insertion_en_tete(lst,x):
lst.suivante = Cellule(lst.valeur,lst.suivante)
lst.valeur = x
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
Mettre le résultat ici (code et figure).
def insertion_en_queue(lst,x):
if lst.suivante is None :
lst.suivante = Cellule(x,None)
else :
insertion_en_queue(lst.suivante,x)
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
Mettre le résultat ici (code et figure).
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)
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
Mettre le résultat ici (code et figure).
def sup_tete(lst) :
lst.valeur = lst.suivante.valeur
lst.suivante = lst.suivante.suivante
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
Mettre le résultat ici (code et figure).
def sup_queue(lst) :
if lst.suivante.suivante is None :
lst.suivante = None
else :
sup_queue(lst.suivante)
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
Mettre le résultat ici (code et figure).
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)
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 :
c
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
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.
É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
Mettre le résultat ici (code et figure).
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))
É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
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))
É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).
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)
É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).
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))
É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
Mettre le résultat ici (code et figure).
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)
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
Mettre le résultat ici (code et figure).
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.
É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
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)
É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>
Mettre le résultat ici (code et figure).
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))
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
Mettre le résultat ici (code et figure).
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)
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).
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1587
[[{"title":"SQL - Systèmes de Gestion de Bases de Données","posi":0},{"text":"
"},{"text":""}],[{"text":"
","title":"Historique"},{"edit":"
"}],[{"text":"
","title":"Transactions"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Propriétés ACID"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"interaction entre un SGBD et un programme"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Ordres paramétrés"},{"edit":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}]]
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.
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.
Mettre ici les résultats.
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.
Mettre le résultat ici.
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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;
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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.
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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 mariadbUn 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).
Mettre le résultat ici (code et figure).
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 = '
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
1. Atomicité.
2. Cohérence.
3. Durabilité.
4. Isolation.
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 ».
Mettre le résultat ici (code et figure).
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.
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
Mettre le résultat ici (code et figure).
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.
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.
Mettre le résultat ici (code et figure).
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.
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 ?
Mettre le résultat ici (code et figure).
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.
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).
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()
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).
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>
<head><title></title></head>
<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
- Clics : 1355
[[{"title":"Représentation approximative des nombres réels","posi":0},{"text":"
"},{"text":""}],[{"text":"
","title":"Écriture scientifique"},{"edit":"
"},{"text":"
"}],[{"text":"
","title":"Norme IEEE 754"},{"edit":"
"}],[{"text":"
","title":"Les flottants en Python"},{"edit":"
"}],[{"text":"
","title":" Clause SELECT"},{"edit":"
"}],[{"text":"
","title":"Propriétés des nombres flottants"},{"edit":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":""}],[{"text":"
"},{"solution":""}]]
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.
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 103
Mettre le résultat ici de la requête sql.
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.
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.
Mettre le résultat ici (code et figure).
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.
Mettre le résultat ici (code et figure).
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)
Mettre le résultat ici.
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)
Mettre le résultat ici (code et figure).
Exercice 214 Dounér la représentation flottante en simple précision de 128
ct —32,75. Solution page 485 1
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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 ©
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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
Mettre le résultat ici (code et figure).
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).
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1311
[[{"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 :
"},{"radio":[{"label":"int","sol":false},{"label":"float","sol":true},{"label":"string","sol":false}]}],[{"text":"On a écrit le script suivant :
"},{"radio":[{"label":"int","sol":true},{"label":"float"},{"label":"string","sol":false}]}],[{"text":"On a écrit le script suivant :
"},{"radio":[{"label":"int","sol":false},{"label":"float"},{"label":"string","sol":true}]}],[{"text":"On a écrit le script suivant :
var1 = 33.4
De quel type est la variable var1?
var1 = 55
De quel type est la variable var1?
var1 = \"La spécialité Nsi\"
De quel type est la variable var1?
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":"12
3
","sol":true},{"label":"1 2 3"},{"label":"6","sol":false},{"label":"12
3
4
","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":"12
3
","sol":true},{"label":"1 2 3"},{"label":"6","sol":false},{"label":"12
3
4
","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
- Clics : 1166