Cours de NSI PDF (2019-2020)

NSI première NSI en première (2019-2020) Résumé Types simples Quelques personnages importants Le mathématicien Al Kh...

NSI première NSI en première (2019-2020) Résumé Types simples Quelques personnages importants Le mathématicien Al Khwârizmî a écrit de nombreux ouvrages en arabe. La traduction de ces ou- vrages en latin permet l’arrivée en Europe, seulement vers le XIIe , du zéro déjà utilisé par les mathémati- ciens arabes. Le zéro était déjà utilisé par les Indiens en tant que nombre à partir du Ve. Gottfried Wilhelm Leibniz (1646-1716) construit une machine à calculer permettant d’effectuer des additions et des multiplications et expose les principes du calcul binaire. George Boole (1815-1864) est considéré avec Augustus de Morgan comme le fondateur de la logique mathématique. (valeurs 1 pour vraie et 0 pour fausse). Djon Atanasov (1903-1995) envisage la construction d’un calculateur électronique en utilisant le système binaire, en s’inspirant des idées de Leibniz. Toute information est codée en n’utilisant que des 0 et des 1. Avec Clifford Berry, il construit ce calculateur (sans programme enregistré). L’ABC (Atanasov Berry Computer) entre en service à la fin 1939. L’invention du premier ordinateur électronique est attribuée à Atanasov. Presper Eckert et John Mauchly, conçoivent et construisent l’ENIAC dans les années 1940 sur la base des idées d’Atanasov. 1 Représentation numérique de l’information L’utilisation uniquement de deux symboles facilite la mesure des états de circuits électroniques (ou- vert ou fermé, faux ou vrai, 0 ou 1). Ces valeurs 0 et 1 s’appellent des chiffres binaires ou bit en anglais (pour binary digit). Une variable qui n’a que deux états comme 0 ou 1, ou alors faux ou vrai, s’appelle aussi un booléen (de George Boole). Une machine reçoit de l’information, la mémorise, la modifie, la transmet à l’aide d’une multitude de petits circuits électroniques. Avec 8 circuits, on peut construire un circuit qui décrit le mot 01000001 par exemple. Composé de 8 bits, on l’appelle un octet. Remarque : avec 8 bits, on peut en particulier représenter l’ensemble des caractères disponibles sur un clavier. Numérisation Pour pouvoir être numérisée, l’information est d’abord discrétisée, puis représentée par une suite de 0 et de 1 et enfin enregistrée sur un support. Le type de support est unique et peut contenir toutes sortes d’informations en permettant de les voir ou de les entendre. Un nombre, une touche du clavier (donc du texte) sont représentés par des nombres entiers, écrits ensuite en binaire. Une image est décomposée en petits carrés nommés pixels (pour picture elements). La quantité de rouge, de vert et de bleu est aussi un nombre entier de 0 à 255 dans le système RGB par exemple. 2 Nombres entiers 2.1 Notion de base La base dix Dix chiffres sont nécessaires, (0, 1, 2,..., 9). Le nombre dix s’écrit avec deux chiffres : 10. Tableau avec les puissances de dix : Serge Bays 1 Lycée Les Eucalyptus  NSI première... 1000 = 103 100 = 102 10 = 101 1 = 100... 7 2 5 3 L’utilisation du chiffre 0 est déterminante.... 10000 = 104 1000 = 103 100 = 102 10 = 101 1 = 100... 2 0 3... 0 0 2 0 3 Quel que soit le nombre de 0 écrits à gauche, le nombre se lit "deux cent trois" et s’écrit 203. Le mot zéro vient de l’arabe "sifr", traduction du mot indien "sunya" qui signifie "vide". Le mot arabe "sifr" est aussi à l’origine du mot "chiffre". La base deux En base deux il n’y a que deux chiffres, 0 et 1, et le nombre deux s’écrit avec deux chiffres 10. On obtient l’écriture en base deux, ou l’écriture binaire, d’un nombre, avec les restes obtenus dans les divisions euclidiennes par 2 successives jusqu’à obtenir un quotient nul. 11 = 5 × 2 + 1, r1 = 1 5 = 2 × 2 + 1, r2 = 1 2 = 1 × 2 + 0, r3 = 0 1 = 0 × 2 + 1, r4 = 1 Nous obtenons l’écriture de 11 en base deux notée 10112 , soit r4 r3 r2 r1. Avec un tableau :... 8 = 23 4 = 22 2 = 21 1 = 20... 1 0 1 1 Un bit prend soit la valeur 0, soit la valeur 1. Un octet, byte en anglais, est constitué de 8 bits consé- cutifs. L’octet est par exemple utilisé comme unité de référence pour mesurer la capacité des mémoires. Remarque : pour multiplier par b un nombre écrit en base b, il suffit d’ajouter un zéro à droite du nombre. Une base quelconque Pour écrire les entiers naturels en base b, on a besoin de b chiffres et le nombre b s’écrit avec deux chiffres 10. En base seize, on a besoin de 16 chiffres notés : 0, 1, 2, 3, 4, 5 , 6, 7, 8, 9, puis A (dix), B (onze), C (douze), D (treize), E (quatorze) et F (quinze). Un octet s’écrit simplement en base seize. On partage l’octet en deux et chaque partie de quatre bits s’écrit avec un chiffre de la base seize. Par exemple le nombre écrit 11010101 en base deux s’écrit D5 en base seize. En effet 11010101 se partage en 1101 et 0101 qui donnent respectivement D et 5 en base seize : 110101012 = 11012 × 100002 + 01012 = D16 × 1016 + 516 = D516. 2.2 Représentation en machine Dans une machine, on utilise l’écriture binaire pour représenter un entier naturel. Avec des octets, soit huit bits, on peut représenter les entiers naturels de 0 (00000000 en base deux) à 255 (1111 1111 en base deux). Donc 45 est représenté par 00101101. Si on utilise seize bits, soit deux octets, on peut représenter les entiers naturels jusqu’à 65535 (1111 1111 1111 1111 en base deux) et dans ce cas 45 est représenté par 0000000000101101. Avec n bits, on peut représenter les nombres entre 0 et 2n − 1, c’est-à-dire tout nombre k qui s’écrit : Serge Bays 2 Lycée Les Eucalyptus  NSI première n−1 X k= bi 2i avec bi ∈ {0, 1} i=0 Addition de nombres binaires Pour additionner deux nombres en binaire on procède comme en base dix. À partir de 0 + 0 = 0, 1 + 0 = 0 + 1 = 1 et 1 + 1 = 10, on pose l’addition comme, avec le système de retenue. Par exemple : 1 1 0 1 treize + 1 0 0 1 neuf 1 1 retenues 1 0 1 1 0 vingt-deux Attention, si la taille des entiers est limitée, par exemple avec quatre bits, alors dans l’addition ci- dessus le bit à gauche est perdu. Donc pour la machine, la somme de 1101 et de 1001 vaut 0110. Autrement dit, si nous demandons à la machine de calculer 13 + 9, elle nous répond 6 ! 2.3 Entiers relatifs L’idée d’utiliser un bit pour le signe et les autres bits pour la valeur absolue a de nombreux inconvé- nients en particulier pour effectuer des opérations. Avec quatre bits, par exemple, le bit à gauche est perdu et seize, (1 0000), est équivalent en machine à 0 (0 0000). Donc sur quatre bits, l’opposé r0 d’un nombre r s’obtient par la différence r0 = 16 − r = 24 − r puisque r + r0 = 24 (= 0 pour la machine). De manière générale, avec n bits, la représentation en machine d’un entier négatif r, est l’écriture binaire de la différence 2n − r. Cette représentation s’appelle le complément à 2n. En pratique, pour trouver la représentation d’un entier négatif r, on prend l’écriture binaire de −r (qui est un entier positif), on inverse les bits de cette écriture et on ajoute 1. Dans toutes ces écritures, le nombre de bits utilisés est fixé. Exemple avec 6 bits, pour obtenir le codage de −12 : 001100 (codage de 12 en binaire sur 6 bits) 110011 (complément à un, on inverse chaque bit) 110100 (on ajoute 1) : représentation de −12 en complément à deux sur 6 bits. Avec n bits, on peut représenter les 2n nombres compris entre −2n−1 et 2n−1 − 1. Les nombres négatifs ont tous le bit de poids fort égal à 1. Les écritures binaires des entiers naturels de 0 à 2n−1 − 1 représentent les entiers relatifs positifs ou nul correspondants. Les écritures binaires des entiers naturels de 2n−1 à 2n − 1 représentent les entiers relatifs négatifs de −2n−1 à −1. Ainsi, si la machine utilise un octet, soit huit bits, on peut écrire les entiers naturels n de 0 à 255 et donc représenter les entiers relatifs de −27 = −128 à 27 − 1 = 127. Les nombres n de 0 à 127, (de 0000 0000 à 0111 1111 en base deux), servent à représenter les entiers relatifs positifs ou nul r avec n = r et les nombres n de 128 à 255, (de 1000 0000 à 1111 1111 en base deux), représentent les entiers relatifs négatifs r avec n = r + 256. Remarque 1 : quel que soit le nombre n de bits utilisés, le nombre −1 est représenté par le nombre 2n − 1 écrit en binaire, donc par une suite de 1. Remarque 2 : nous avons un principe équivalent sur le cercle trigonométrique gradué de degré en degré. Si nous le parcourons dans le sens direct, chaque graduation correspond à un nombre positif, dans l’ordre 0, 1, 2,... , 178, 179, 180, 181,... , 358, 359 (ceci correspond aux entiers naturels). Chaque gra- duation peut aussi correspondre à un entier relatif, dans l’ordre 0, 1, 2,... , 178, 179, -180, -179,... , -3, -2, -1. Ce principe se trouve aussi dans la lecture de l’heure. Nous pouvons dire "dix heures quarante" ou "onze heures moins vingt". Et cinquante-neuf correspond à "moins une". Serge Bays 3 Lycée Les Eucalyptus  NSI première 2.4 Programmation Avec certains langages, le nombre d’octets avec lequel on travaille sur les entiers peut être précisé (un octets, deux octets, quatre octets, huit octets). En langage Python, la taille gérée par le langage est à priori illimitée. Les entiers sont représentés par le type int (integer). Cependant, si un nombre dépasse la taille maximale utilisable par le processeur, les calculs sont ralentis puisque ce nombre est découpé en deux ou plusieurs parties par Python qui s’occupe des différentes opérations à effectuer. Il est facile de vérifier que les calculs avec des entiers longs prennent en Python plus de temps qu’avec des nombres flottants par exemple. Cependant ces calculs sont exacts ! La plupart des processeurs calculent avec des tailles limitées à 32 ou 64 bits. Les langages de pro- grammation en général font de même et les calculs sont gérés directement par le processeur. Pour simplifier, supposons que les entiers sont codés sur deux octets. Le langage nous permet le choix de travailler uniquement sur des entiers naturels, appelés entiers non signés (sans signe). Nous avons alors à notre disposition les nombres de 0 à 65535. Si notre programme est amené à demander le calcul 65500+40, le reste du programme risque d’être fort compromis puisque le résultat de l’addition sera 4. (En binaire, le résultat est 1 0000... 0100 et le 1 à gauche disparaît). De même le résultat du produit 32 × 2048 sera 0. Avec des entiers relatifs, appelés entiers signés, toujours sur deux octets, nous disposons des nombres de −32768 à 32767. Donc, par exemple, le calcul 32000 + 1000 aura pour résultat −32536. Le programme ci-dessous, écrit en C++, permet de constater ces résultats. #include using namespace std; int main(){ unsigned short a; a = 65500 + 40; cout 2 and 0 0 Serge Bays 5 Lycée Les Eucalyptus  NSI première >>> 0 or 5 5 >>> 2 or 0 2 >>> 2 or 5 2 L’expression not a ne peut avoir pour valeur que False ou True. Table de vérité Dans cette table, F signifie False et T signifie True. Nous résumons ici les principaux résultats pour des expressions booléennes simples. a b not a not b a and b a or b not a and not b not a or not b T T F F T T F F T F F T F T F T F T T F F T F T F F T T F F T T Nous pouvons déduire, en comparant les valeurs de not a and not b avec celles de a or b, que not a and not b est équivalente à not (a or b), et en comparant les valeurs de not a or not b avec celles de a and b, que not a or not b est équivalente à not (a and b). Ces deux équivalences s’appellent les lois de Morgan. Un autre opérateur joue un rôle majeur dans le calcul booléen et le fonctionnement d’une machine. Il s’agit de l’opérateur logique XOR, le OU exclusif : a XOR b est équivalent à (a ET (NON b)) OU ((NON a) ET b). Considérons a et b, deux chiffres binaires ou deux booléens, et les deux variables s = a XOR b et r = a ET b. La valeur de s représente la somme sur un bit et la valeur de r la retenue sur 1 bit. Nous avons vu des opérateurs qui s’utilisent sur les bits : ∼ (inversion des bits), & (et logique), | (ou logique). Nous disposons aussi de l’opérateur ∧ (ou exclusif). >>> 1 & 1 1 >>> 1 & 0 0 >>> 0 & 1 0 >>> 0 & 0 0 Dans chaque cas, l’expression a & b a pour valeur la retenue dans l’addition a+b. De même, l’expression a ∧ b a pour valeur le chiffre des unités dans l’addition a+b. »> 1∧1 0 »> 1∧0 1 »> 0∧1 1 »> 0∧0 Serge Bays 6 Lycée Les Eucalyptus  NSI première 0 L’opérateur ∧ s’utilise sur les bits mais il n’y a pas d’opérateurs logiques pour XOR comme and pour ET. Une possibilité est d’écrire une fonction xor qui prend en paramètres deux variables a et b et renvoie a XOR b. Contrairement aux opérateurs and et or, l’évaluation de chacune des deux valeurs a et b est obligatoire dans tous les cas. def xor(a, b): return (a and not(b)) or (not(a) and b) Serge Bays 7 Lycée Les Eucalyptus