Algorithme et Programmation 1 PDF

Algorithme et Programmation 1 TRONC COMMUN MIPC SEMESTRE 1 ALGORITHMIQUE ET PROGRAMMATION 1 1 Le cours Algorithme et Programmation 1 est dédié aux étudiants tronc commun MIPC en S1 Objectifs : ❑ Apprendre les concepts de base de l'algorithmique et de la programmation ❑ Être...

Algorithme et Programmation 1 TRONC COMMUN MIPC SEMESTRE 1 ALGORITHMIQUE ET PROGRAMMATION 1 1 Le cours Algorithme et Programmation 1 est dédié aux étudiants tronc commun MIPC en S1 Objectifs : ❑ Apprendre les concepts de base de l'algorithmique et de la programmation ❑ Être capable de mettre en œuvre ces concepts pour analyser des problèmes simples et écrire les programmes correspondants Plan : ◦ Généralités ◦ Algorithmique ◦ Langage C ALGORITHMIQUE ET PROGRAMMATION 1 2 Chapitre 1 : généralités ❑Composants d’un ordinateur ❑Systèmes de numération et Codage Chapitre 2 : Les éléments de base d’un algorithme et leurs représentation en langage C ❑Initiation Algorithmique ❑Introduction Langage C ❑Types de bases, constantes, variables ❑Expressions et Opérateurs ❑Lecture et Ecriture Chapitre 3 : La sélection en algorithmique et en langage C ❑Sélection avec une seule alternative ❑Sélection avec deux alternatives ❑Imbrication de la sélection ❑Le choix multiple Chapitre 4 : Les boucles en algorithmique et en langage C ❑Boucle répéter … jusqu’à / do … while ❑Boucle tant que / while ❑Boucle pour/ for ALGORITHMIQUE ET PROGRAMMATION 1 3 Chapitre 1: Généralités COMPOSANTS D’UN ORDINATEUR ALGORITHMIQUE ET PROGRAMMATION 1 4  Définitions : Informatique : L’informatique c’est la science de traitement de l’information d’une façon automatique ALGORITHMIQUE ET PROGRAMMATION 1 5  Définitions : Information : L’information est un renseignement qui permet de construire , de reconstruire ou d’enrichir la connaissance sur un sujet. L’information peut être présentée sous plusieurs formes : Texte, Image, Son, Vidéo, etc.) ALGORITHMIQUE ET PROGRAMMATION 1 6  Définitions : Traitement de l’information : Données Résultat Traitement automatique c’est un traitement effectuée en totalité par la machine ALGORITHMIQUE ET PROGRAMMATION 1 7  Définitions : Système Informatique : Un système informatique est un ensemble de composants matériels (hardware) et logiciels (software) pour le traitement d’information (collecter, stocker, acheminer, présenter, supprimer les informations). Système Informatique : Matériel Logiciel ALGORITHMIQUE ET PROGRAMMATION 1 8  Définitions : Ordinateur Un ordinateur est une machine composée de circuit électroniques, utilisé pour le traitement de données sous format binaire. Il est capable de réaliser les opérations suivantes : ✓ Acquisition de l’information ✓ Stockage de l’information ✓ Transformation de l’information par son traitement ✓ Restitution de l’information Remarque : L’ordinateur est un exemple de système informatique. ALGORITHMIQUE ET PROGRAMMATION 1 9  Composants d’un ordinateur (Architecture de von Neumann) Architecture de Von Neuman décompose l’ordinateur en 4 parties essentielles : Mémoire 1. La mémoire qui contient à la fois les instructions et les données demandées par le calcul. 2. l’unité arithmétique et logique (UAL) ou unité de traitement : son rôle est d’effectuer les opérations de base; Unité arithmétique Unité de contrôle Et Logique 3. l’unité de contrôle, chargée du séquençage des opérations; 4. les dispositifs d’entrée-sortie, qui permettent la Processeur communication avec le monde extérieur. Entrée Sortie John Von Neumann, est un mathématicien et physicien né le 28 décembre 1903 à Budapest. ALGORITHMIQUE ET PROGRAMMATION 1 10  Composants d’un ordinateur (Architecture de von Neumann) ❑Unités d’entrées/Sorties(E/S) : servant au transfert de l’information entre l’unité centrale et les unités périphériques. ❑Unités Périphériques : Toutes les unités destinés à la lecture ou la l’écriture de l’information (ex. clavier, imprimante, disques durs,…) ❑Unité centrale : Unité centrale de traitement (UCT/CPU)+ Mémoire centrale (principale) ❑CPU ou bien processeur : Comporte l’unité de commande et de contrôle(UCC)+ l’unité arithmétique et logique (UAL). ❑UCC(Unité de commande et de contrôle) : commande et contrôle le fonctionnement de l’UAL, de la mémoire et des E/S. Elle se charge de chercher l’instruction à exécuter dans la mémoire principale( et les données qu’elles utilisent), décode cette instruction, et envoie en cas échéant un signal à l’UAL pour se préparer à l’execution. ❑UAL : réalise les opérateurs arithmétiques et logiques et de comparaison contenu dans l’instruction et effectue aussi des échanges avec la mémoire. ALGORITHMIQUE ET PROGRAMMATION 1 11  Composants d’un ordinateur Un ordinateur est traditionnellement composé d’une unité centrale, essentiellement une mémoire centrale un processeur, ainsi que des périphériques d’entrée et périphériques de sorties. Les périphériques d'entrées permettent d'envoyer de l'information à l'unité centrale. Ce sont par exemple, le clavier, la souris, le microphone, le scanner... Les périphériques de sortie reçoivent de l'information de l'unité centrale et la communiquent vers l'extérieur : l'écran, l'imprimante, les hauts parleurs... Remarques : L’unité centrale d’un point de vue techniques est le CPU+ mémoire principale. Elle joue le rôle du cerveau de l’ordinateur. ALGORITHMIQUE ET PROGRAMMATION 1 12 Composants d’un ordinateur 1.L’écran : affiche les informations (texte, image, vidéo, …) 2.La carte mère : regroupe les principaux circuits de l’ordinateur 3.Le microprocesseur : exécute les instructions des programmes 4.Les connecteurs pour périphériques (disques durs, …) 5.La mémoire vive(RAM): stocke momentanément les données et les programmes 6.Les cartes d’extension : ajoutent des fonctionnalités à l’ordinateur (ports, TV, vidéo, …) 7.L’alimentation : fournit aux divers composants une énergie électrique régulée 8.Le(s) lecteur(s)/graveurs optique(s) : CD, DVD,… 9.Le(s) disques dur(s) : stocke de façon durable les données et les programmes 10.Le clavier : permet la saisie de caractères, … 11.La souris : permet le pointage d’éléments sur l’écran ALGORITHMIQUE ET PROGRAMMATION 1 13 Carte Mère La carte mère est le circuit imprimé qui supporte la plupart des composants et des connecteurs nécessaires au fonctionnement d’un ordinateur. 14 ALGORITHMIQUE ET PROGRAMMATION 1  Carte Mère Les différents composants électroniques de l’ordinateur sont architecturés autour d’une carte principale, appelée la carte-mère.  PCI (Peripheral Component Interconnect = interconnexion de composants périphériques) connecteur des cartes d’extensions comme : carte son, carte réseau, carte d’acquisition...  Chipset (jeu de circuits) est un circuit électronique chargé de coordonner les échanges de données entre les divers composants de l'ordinateur (CPU, RAM, ROM, périphériques...).  AGP (Accelerated Graphic Port = port graphique accéléré) est le connecteur de la carte graphique.  IDE (Integrated Drive Electronics = électronique de commande intégrée) connecteur de disque dur, de lecteur de disque et de lecteur de disquette. ALGORITHMIQUE ET PROGRAMMATION 1 15  Processeur CPU Le processeur ou CPU Le processeur exécute les différents programmes informatiques et effectue les calculs nécessaires au bon fonctionnement de l'ordinateur (calculs, comparaison…). placé sur un support appelé socket, et équipé d’un radiateur et d’un ventilateur(c’est le composant de la carte mère le plus gourmand en énergie). ventilateur + radiateur = ventirad ALGORITHMIQUE ET PROGRAMMATION 1 16  Chipset Le chipset permet de gérer les différents flux de données qui transitent entre le processeur, la mémoire et les autres composants. ❑Le chipset se divise en deux parties distinctes : ❑Le Northbridge, pour les périphériques « rapide »(mémoire, PCI Express, etc.); ❑Le Southbridge pour les périphériques « lents » (PCI, disques durs et SSD, USB/SATA3). ALGORITHMIQUE ET PROGRAMMATION 1  BUS ❑Un bus informatique est un dispositif de transmission de données partagé entre plusieurs composants d’un système numérique. ❑Sur une carte mère, ils en existe de différents type. ALGORITHMIQUE ET PROGRAMMATION 1 18  Mémoire ❑La mémoire est un dispositif électronique qui sert à stocker des informations. C’est un composant essentiel, présent dans tous les ordinateurs, les consoles de jeux, les GPS et de nombreux appareils électroniques. ❑Mémoire de masse ou mémoire de stockage ❑ Un disque dur (HDD) est un appareil de stockage d'ancienne génération utilisant des plateaux mécaniques et une tête de lecture/écriture mobile pour accéder aux données. ❑ Un disque SSD est un type d'appareil plus récent et plus rapide qui stocke les données sur des puces mémoire accessibles instantanément. ALGORITHMIQUE ET PROGRAMMATION 1 19  Mémoire La mémoire vive « RAM » ( Random Access Memory) : ❑La RAM ou mémoire vive est la mémoire principale du système, c'est-à-dire qu'il s'agit d'un espace permettant de stocker de manière temporaire des données et les instructions lors de l'exécution d'un programme. ❑Son contenu est modifiable c.-à-d., on peut lire et écrire, et s’efface quand la machine n’est plus sous tension électrique. ❑Elle est caractérisée par sa capacité mesurée Mo /Giga-octets. 512 Mo, 1Go, 2Go ,4Go … ALGORITHMIQUE ET PROGRAMMATION 1 20  Mémoire Mémoire morte (ROM ou Read Only Memory) : ❑Permet de stocker des données nécessaires au démarrage de l'ordinateur (BIOS), son contenu ne peut pas être modifié. ❑La ROM conserve les données même quand elle n'est plus sous tension. Mémoire flash ❑est une mémoire de masse à, c'est-à-dire possédant les caractéristiques d'une mémoire vive mais dont les données ne disparaissent pas lors d'une mise hors tension. Les données sont conservées lorsque l'alimentation électrique est coupée. ALGORITHMIQUE ET PROGRAMMATION 1 21 BIOS ❑BIOS = Basic Input/Output System ❑Le BIOS est un petit programme. Il est situé au niveau de la ROM. ❑Le BIOS est le premier programme chargé en mémoire dès que vous allumez votre ordinateur. Il assure plusieurs testes avant de charger le système d’exploitation. ALGORITHMIQUE ET PROGRAMMATION 1 CMOS = Complementary Metal Oxide Semiconductor ❑Certaines informations de l’ordinateur doivent être conservées même lorsque l’ordinateur est éteint. Par exemple : La configuration de l’ordinateur, la date et l’heure du système, etc. ❑Pour cela, la carte mère contient une petite mémoire, appelée CMOS. ❑Cette mémoire ne peut pas fonctionner sans tension électrique. C’est pourquoi il y a une Pile dans la carte mère pour alimenter le CMOS. Pile de la CMOS ALGORITHMIQUE ET PROGRAMMATION 1 Vue d’ensemble d’une carte mère ALGORITHMIQUE ET PROGRAMMATION 1 24 Vue d’ensemble d’une carte mère ALGORITHMIQUE ET PROGRAMMATION 1 25 Fichiers ❑Un fichier est une collection de données numériques destinée à être stockée sur une mémoire de masse(disque dur, clé USB, mémoire interne de smartphone, …). ❑Techniquement un fichier est constitué d’une séquence d’octets. L’essence du fichier sont les informations qu’il contient, mais il comporte également un certain nombre de métadonnées fournissant des informations très diverses sur le fichier et son contenu : ❑La taille du fichier, ❑Son auteur, ❑Les utilisateurs autorisés à le manipuler, ❑La date de la dernière modification, ❑… ALGORITHMIQUE ET PROGRAMMATION 1 26 Fichiers ❑Les fichiers permettent au système d’exploitation et aux applications (traitement de texte, lecteur multimédia, navigateurs web, …) d’avoir accès aux informations stockées sur mémoire de masse. ❑Exemples de noms de fichier : ❑Un fichier possède un nom de fichier qui sert à désigner son ❑Readme.text : fichier texte contenu. Ce nom comprend souvent un préfixe et un suffixe ❑Cmd.exe : fichier appelé extension, qui renseigne sur la nature des informations exécutable(application) qu’il contient. ❑Projet.zip : archive(méthode zip) compressée ❑Selon la nature et le format du contenu, les fichiers peuvent ❑Simpsons.avi : fichier vidéo être qualifiés d’exécutables, de compressés, de textes, de ❑Led_zeppelin.mp3 : fichier audio documents, d’images, d’audio ou de vidéos. ALGORITHMIQUE ET PROGRAMMATION 1 27  Système d’exploitation ❑ Un système d’exploitation, définit par un ensemble de programmes chargé d’établir une relation entre les différentes ressources matérielles, les applications et l’utilisateur. ❑ Les systèmes d’exploitation les plus répondus sont Windows, MAC OS, Linux et Unix pour les PC et serveurs. ❑ Pour les téléphones, on trouve Android, iOS, Symbian et Windows Phone. ALGORITHMIQUE ET PROGRAMMATION 1 28 Généralités : SYSTÈMES DE NUMÉRATIONS ALGORITHMIQUE ET PROGRAMMATION 1 29  Représentation de l’information ❑Lorsque le processeur, vas traiter les instructions pour faire tourner vos programmes, il vas manipuler des 0 et des 1. ❑De même, tout ce qui est stocké sur notre ordinateur est stocké sous forme binaire. ❑Donc, les photos, les vidéos, les fichiers texte, tout ce qui est sur votre ordinateur est en réalité représenté en mémoire par une suite de 0 et de 1. ALGORITHMIQUE ET PROGRAMMATION 1 30 Représentation de l’information ❑On appelle cela le langage binaire ou en base 2, c’est le langage utilisé par les différents composants de votre ordinateur pour communiquer et échanger les données entre eux. ❑Les être humain lorsque nous comptons nous utilisons les nombres 1, 2, 3 …10. Parce que nous avons dix dois. Nous comptons en base 10. ❑Pourquoi les ordinateurs calculent en base 2 ? ALGORITHMIQUE ET PROGRAMMATION 1 31 Représentation de l’information ❑Un processeur marche avec du courant électrique, pour communiquer un autre composant de l’ordinateur il doit lui envoyer des signaux électriques. ❑De plus si on regarde de quoi est constitué un processeur, il est composé de plusieurs Milliards de transistors. ❑Un transistor c’est comme un petit interrupteur commandé électriquement, Quand il laisse passer le courant on dit que cela correspond à 1 alors que si le courant ne passe pas, cela correspond à 0. ❑Plus le processeur a des transistors plus il peut faire des opérations rapidement. ALGORITHMIQUE ET PROGRAMMATION 1 32 Représentation de l’information ❑Pour les êtres humains il est difficile de comprendre ces séquences de 0 et 1. C’est pour cette raison qu’il est utile de procéder aux conversions de ces séquences vers des bases plus conviviales comme la base décimale, octale ou Hexadécimale : ▪ Le Système de numération décimale utilise les dix chiffres 0,1, 2, 3, 4, 5 , 6, 7, 8,9. ▪ Le système de numération binaire; utilise exclusivement les deux chiffres 0 et 1. ▪ Le système de numération octale utilise les huit chiffre 0,1,2,3,4,5,6,7 ▪ Le système de numération hexadécimale; utilise les seize chiffes 0,1, 2, 3, 4, 5 , 6, 7, 8,9, A, B, C, D,E,F. ALGORITHMIQUE ET PROGRAMMATION 1 33 Système de numération ❑Un système de numération est un ensemble de règles permettant de représenter les nombres. ❑Un système de numération se définit par deux éléments : ▪ La base du système ▪ Les symboles du système ALGORITHMIQUE ET PROGRAMMATION 1 34 Système décimal Système décimal ❑C’est le système usuel dans la vie quotidienne. La base du ▪ 0 système décimal est la base de 10 et ses symboles ont les dix ▪ 1 chiffres: 0,1,2,3,4,5,6,7,8,9. ▪ 2 ❑Cela veut dire qu’en décimal, les dix chiffres précédents sont ▪ 3 suffisants pour exprimer n’importe quel nombre. ▪ 4 ▪ 5 ❑Cependant, la machine ne peut assimiler que les deux 0 et 1, ▪ 6 il serait important de savoir comment exprimer les nombres décimaux en binaires et comment effectuer l’opération inverse ▪ 7 et on parle de la conversion de base. ▪ 8 ▪ 9 ▪ 10 ▪ 11 ▪ … ▪ 99 ▪ 100 ALGORITHMIQUE ET PROGRAMMATION 1 35 Le système Binaire Système décimal Système Binaire C’est la base utilisée en informatique pour ▪ 0 la représentation des informations au ▪ 1 niveau machine. Ce système possède deux ▪ 10 chiffres : 0 et 1. Ces deux états sont les seuls ▪ 11 que la machine peut assimiler. ▪ 100 ▪ 101 ▪ 110 ▪ 111 ▪ 1000 ▪ 1001 ▪ 1010 ▪ 1011 ▪ … ▪ 1011 1001 ▪ 10111010 ALGORITHMIQUE ET PROGRAMMATION 1 36 Système octal La base du système octal est 8. En octal, les nombres sont représentés sous forme de combinaisons de chiffres parmi les suivants : 0,1,2,3,4,5,6 et 7. ALGORITHMIQUE ET PROGRAMMATION 1 37 Système Hexadécimal Hexadécimal Décimal Le système hexadécimal (base 16) utilise 16 chiffres pour la 0 0 représentation des nombres, à savoir : 1 1 Les chiffres du système décimal: 0,1,2,3,4,5,6,7,8,9. 2 2 3 3 Les six(6) premières lettre de l’alphabet: A, B, C, D, E, F. Le tableau suivant donne l’équivalent décimal d’un chiffre 4 4 hexadécimal: … … 9 9 A 10 B 11 C 12 D 13 E 14 F 15 10 16 ALGORITHMIQUE ET PROGRAMMATION 1 38 Notation Soit N un nombre quelconque exprimé dans une base b. N sera noté comme suit : 𝑵 = (𝒂𝒏−𝟏 𝒂𝒏−𝟏 𝒂𝒏−𝟏 … 𝒂𝟎 )𝒃 Tel que : b: base du système de numération. 𝑎𝑖 symbole du système, i=0,…,n-1. avec 𝑎𝑖 < 𝑏 ALGORITHMIQUE ET PROGRAMMATION 1 39 Exemples ❑𝑵𝟏 = (𝟏𝟗𝟎𝟏𝟕)𝟏𝟎 En Décimal, avec : 𝑎4 = 1, 𝑎3 = 9, 𝑎2 = 0, 𝑎1 = 1, 𝑎0 = 7. On remarque que les 𝑎𝑖 sont tous inférieurs à la base 10. (𝑎𝑖 < 10). ❑𝑵𝟐 = (𝟏𝟎𝟏𝟏𝟏𝟎𝟏)𝟐 En Binaire, avec : 𝑎6 = 1, 𝑎5 = 0, 𝑎4 = 1, 𝑎3 = 1, 𝑎2 = 1, 𝑎1 = 0, 𝑎0 = 1. ❑𝑵𝟑 = (𝟏𝟑𝟕𝟎)𝟖 En Octal, avec : 𝑎3 = 1, 𝑎2 = 3, 𝑎1 = 7, 𝑎0 = 0. ❑𝑵𝟒 = (𝑨𝟗𝟏𝟐𝟎)𝟏𝟔 En Hexadécimal, avec : 𝑎4 = 𝐴, 𝑎3 = 9, 𝑎2 = 1, 𝑎1 = 2, 𝑎0 = 0. ❑𝑵𝟓 = (𝟏𝟖𝟎𝟗𝟓)𝟖 La notation 𝑁5 = (18095)8 n’est pas correcte, car tous les chiffres doivent être inférieurs à 8 ce qui n’est pas le cas pour le 2éme chiffre et aussi pour le 4éme (𝑎1 = 9 > 8) 𝑒𝑡(𝑎3 = 8). ALGORITHMIQUE ET PROGRAMMATION 1 40 Conversion en décimal L’exemple suivant illustre la méthode de conversion, en décimal, d’un nombre exprimé dans une base b quelconque. 𝑵 = (𝒂𝒏−𝟏 𝒂𝒏−𝟏 𝒂𝒏−𝟏 … 𝒂𝟎 )𝒃 Pour avoir la représentation en décimal du nombre N exprimé dans une base b quelconque, il suffit d’effectuer le calcul suivant : La formule générale s’écrit comme suit: i étant le poids du chiffre 𝑎𝑖 ALGORITHMIQUE ET PROGRAMMATION 1 41 Conversion en décimal Par convention, l’écriture d’un nombre N s’effectue par la juxtaposition de chiffres possédants chacun un poids égal à une puissance entière de la base de numération. Les chiffres s’écrivent de la gauche vers la droite par valeur décroissante de leur poids. Le poids d’un chiffre dépond donc de son rang et du système de numération adopté : En base décimale : écriture décimale En base 2 et 16 : écriture binaire et hexadécimale ALGORITHMIQUE ET PROGRAMMATION 1 42 Exemples On considère le nombre : Les poids des chiffres N=(1023)4 On commence par définir le poids de chaque 3 2 1 0 chiffre et cela en les numérotant de droite = gauche et en commençant la numérotation de 0. 1 0 2 3 Puis on multiple chaque chiffre 𝑎𝑝 de poids p par la base b élevée à la puissance p. (𝑎𝑝 + 𝑏 𝑝 ). ALGORITHMIQUE ET PROGRAMMATION 1 43 Conversion : Binaire -> Décimal La conversion en décimal d’un nombre exprimé en binaire s’effectue suivant le même principe. Les poids des chiffres Soit à convertir en décimal, le nombre N exprime en binaire comme suit: 𝑁 = (10111001)2 76543210 Ainsi le nombre N en décimal est calculé comme suit : 10111001 ALGORITHMIQUE ET PROGRAMMATION 1 44 Conversion : Octal -> Décimal Soit à convertir en décimal, le nombre X exprime en octal comme suit: Les poids des chiffres 𝑋 = (175)8 Ainsi le nombre X en décimal est calculé comme suit : 210 175 ALGORITHMIQUE ET PROGRAMMATION 1 45 Conversion : Hexadécimal -> Décimal Soit à convertir en décimal, le nombre X exprime en Hexadécimal comme suit: Les poids des chiffres 𝑋 = (𝐴24)16 Le tableau précédent nous donne l’équivalent de la lettre A en décimal : 210 A24 ALGORITHMIQUE ET PROGRAMMATION 1 46 Exercice Réponses ALGORITHMIQUE ET PROGRAMMATION 1 47 Passage de la base 10 à la base 2, 8, 16 Pour exprimer en binaire, un nombre exprimé dans une base b, on dispose d’une méthode par division successives: 1) Effectuer la division X/b = 𝑿𝟎 et le reste 𝒓𝟎 Conversion par division successives Si 𝑿𝟎 =0 alors aller à l’étape 3) sinon aller à l’étape 2) ❑Soit X un nombre exprimé dans la base 2) Effectuer la division 𝑿𝒊 /b= 𝑿𝒊+𝟏 et le reste 𝒓𝒊+𝟏 10. Pour l’exprimer dans une autre base b, il suffit d’effectuer des divisions Si 𝑿𝟎 =0 alors aller à l’étape 3) sinon aller à l’étape 2) successives sur b(2, 8, ou 16) jusqu’à l’obtention d’un résultat nul. 3) Arrêter la division. Le résultat est (𝑿)𝟏𝟎 = ❑Les étapes à suivre sont les suivantes : (𝒓𝒎 𝒓𝒎−𝟏 … 𝒓𝟏 𝒓𝟎 )𝒃 Soit Xi : le résultat de la division. ri: le reste de la division n°i ALGORITHMIQUE ET PROGRAMMATION 1 48 Exemple: Passage de la base 10 à la base 2 Soit le nombre Y= (115)10 , convertir ce nombre en binaire : 115 2 𝐫𝟎 1 57 2 1 28 2 0 14 2 0 7 2 1 3 2 1 1 2 1 0 Résultat=0, donc arrêt 𝐫𝟔 ALGORITHMIQUE ET PROGRAMMATION 1 49 Exemple: Passage de la base 10 à la base 8 Le passage de base 10 à la base 8 s’effectue de la même manière que le passage de la base 10 à la base 2. Soit le nombre Y= (125)10 , 125 8 convertir ce nombre en octal : 𝐫𝟎 5 15 8 Pour cela, on va effectuer les divisions successives de Y sur 8. 7 1 8 Les restes de ces divisions vont 1 constituer les chiffres Y exprimé en 0 Résultat=0, donc arrêt Octal. 𝐫𝟐 ALGORITHMIQUE ET PROGRAMMATION 1 50 Exemple: Passage de la base 10 à la base 16 Soit le nombre Y= (2596)10 , convertir ce nombre en binaire : Pour cela, on va effectuer les divisions successives de Y sur 16. 2596 16 Les restes de ces divisions vont constituer les chiffres Y exprimé en 𝐫𝟎 4 162 16 Hexadécimal. 2 10 16 10 0 Résultat=0, donc arrêt 𝐫𝟐 ALGORITHMIQUE ET PROGRAMMATION 1 51 Remarques L'arithmétique de l'ordinateur est fondée sur le système binaire. C'est pourquoi il connaît comment passer de l'octal ( ou de hexadécimal) au binaire et inverssement. Pour convertir un nombre octal(ou de hexadécimal) en binaire, il faut passer par une base intermédiaire qui est la base 10. ALGORITHMIQUE ET PROGRAMMATION 1 52 Exercice ALGORITHMIQUE ET PROGRAMMATION 1 53 ALGORITHMIQUE ET PROGRAMMATION 1 54 ALGORITHMIQUE ET PROGRAMMATION 1 55 ALGORITHMIQUE ET PROGRAMMATION 1 56 ALGORITHMIQUE ET PROGRAMMATION 1 57 ALGORITHMIQUE ET PROGRAMMATION 1 58 ALGORITHMIQUE ET PROGRAMMATION 1 59 ALGORITHMIQUE ET PROGRAMMATION 1 60 Conversion de nombres réels du décimal en binaire et inversement ALGORITHMIQUE ET PROGRAMMATION 1 61 Binaire->Décimal (𝟏𝟎𝟏, 𝟏𝟏)𝟐 = ( 𝟓, 𝟕𝟓 )𝟏𝟎 (𝟏𝟏𝟎𝟏, 𝟎𝟏)𝟐 = (13,25)𝟏𝟎 2 1 0 -1 -2 (𝟏, 𝟏𝟎𝟏)𝟐 = ( 1,625)𝟏𝟎 101,1 1 = 𝟐𝟐 + 𝟐𝟎 + 𝟐−𝟏 + 𝟐−𝟐 = 4+1+1/2+1/4 =5+0,5+0,25 =5,75 ALGORITHMIQUE ET PROGRAMMATION 1 62 Décimal>Binaire (𝟑𝟐, 𝟔𝟐𝟓)𝟏𝟎 = ( 100000,101 )𝟐 (𝟏𝟐, 𝟓)𝟏𝟎 = ( 1100,1 )𝟐 (𝟑𝟐)𝟏𝟎 = ( 𝟏𝟎𝟎𝟎𝟎𝟎 )𝟐 (𝟔, 𝟏)𝟏𝟎 = (110,000110)𝟐 (𝟎, 𝟔𝟐𝟓)𝟏𝟎 = ( 1 0 1 )𝟐 On va opter à la division consécutives de la partie entière et la multiplication 0,625*2= 𝟏, 𝟐𝟓 consécutives pour la partie 0,25*2= 0,5 fractionnaires 0,5*2=1,00 0,0*2=0 ALGORITHMIQUE ET PROGRAMMATION 1 63 Nombres binaires signés - complément à 2 des nombres négatifs ALGORITHMIQUE ET PROGRAMMATION 1 64 Nombres binaires signés ❑Un ordinateur ne comprend que des 0 et 1, il exprimer le signe négatif par des 0 et des 1. (−𝟓)𝟏𝟎 = ( −𝟏𝟎𝟏 )𝟐 ❑Le premier bit d’un nombre signé est appelé bit de signe, donc on a deux possibilités : ▪ 0: Signe positif ▪ 1 : Signe négatif 𝟏𝟎𝟎𝟏𝟏 ❑Comment coder un nombre signé en binaire ? ALGORITHMIQUE ET PROGRAMMATION 1 65 Nombre binaire signé On converti le nombre comme un nombre simple en binaire et on lui ajoute le signe – (−𝟓)𝟏𝟎 = ( −𝟏𝟎𝟏 )𝟐 provisoirement. Dans l’exemple (-101) est codé sur 3 bits, il −𝟒 ≤ 𝑵 ≤ 𝟑 faut par la suite vérifier est ce que les 3 bits -5 n’appartient par à l’intervalle, donc 3 bits ne sont sont suffisant pour coder le nombre -5 en tant pas suffisants, il faut ajouter des zéro à gauche que nombre signé, donc on applique simplement la formule suivante : (−𝟓)𝟏𝟎 = ( −𝟎𝟏𝟎𝟏 )𝟐 −𝟐𝒏−𝟏 ≤ 𝑵 ≤ 𝟐𝒏−𝟏 − 𝟏 −𝟖 ≤ 𝑵 ≤ 𝟕 ▪ N : Nombre à représenter -5 appartient par à l’intervalle -8 et 7, donc 4 bits sont ▪ n : nombre de bits suffisant ALGORITHMIQUE ET PROGRAMMATION 1 66 Nombre binaire signé-Complément à deux Pour exprimer (−𝑵)𝟏𝟎 en binaire il faut calculer le Complément à 2 de (−𝑵)𝟐 : (−𝟓)𝟏𝟎 = ( −𝟎𝟏𝟎𝟏 )𝟐 -N = CA2(N) -0101= CA2(0101) Pour calculer le CA2, Il faut commencer tout d’abord par calculer le CA1 de N et ajouter et ajouter 1 à ce CA1. CA1(0101)=1010 Le CA1 consiste à inverser tous ses bits (0 devient 1 et devient 0). CA2(-0101)=1010+1 = 1011 (−𝟓)𝟏𝟎 = (1011)𝟐 ALGORITHMIQUE ET PROGRAMMATION 1 67 Convertir un nombre binaire signé en décimal Pour convertir un nombre binaire signé, s’il est négatif(le bit de signe égale à 1) il faut utiliser le complément Binaire signé 10011 à deux. Par exemple convertir le nombre Complément à 1 01100 binaire signé : + 1 10011 ------------ Nombre négatif Complément à 2 01101 ( 𝟏𝟎𝟎𝟏𝟏 )𝟐 = (−𝟏𝟑)𝟏𝟎 ALGORITHMIQUE ET PROGRAMMATION 1 68 Soustraction binaire (Addition de nombres binaires signés) ALGORITHMIQUE ET PROGRAMMATION 1 69 Soustraction Nombre binaire signé 110-10= 0100 - 0110 10 + 110 (6) + 0110 1000-111= 00001 ----------- - 010 (-2) - 0010 ----------- ----------- 111-1000= 1111 La première chose il La deuxième chose il Il faut faut égaliser le nombre 10110-1= 010101 de bits faut convertir la complémenter à soustraction en addition le nombre -0010 −𝟐𝒏−𝟏 ≤ 𝑵 ≤ 𝟐𝒏−𝟏 − 𝟏 0110 + 1110 −𝟒 ≤ 𝟔 ≤ 𝟑 ----------- 10100 6 n’appartient par à l’intervalle, Il faut avoir 4 bit en il faut ajouter des zéro à gauche résultat, dans l’exemple on −𝟖 ≤ 𝟔 ≤ 𝟕 a 5, il y a un dépassement donc il faut éliminer le premier bit ALGORITHMIQUE ET PROGRAMMATION 1 70