INFO204 : science informatique

Ce wiki est un complément de cours pour le cours « info-204 : science informatique ». La participation au wiki est fortement encouragée.

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style PrenomNom...)

Je vous conseille d'aller lire ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fautes d'hortographe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

---

---

Administration

Contrôle continu

À partir de la deuxième séance de TD, chaque séance commencera par une petite interrogation de 10 / 15 minutes sur le contenu du cours et des TD précédents.

Ces notes serviront de première note pour la moyenne finale. (Il y aura également deux contrôles « traditionnels ».)

Cours

• cours 1 (semaine 2) : la base 2
• TD 1 (semaine 3) : fin du cours, début du TD 1 (exercice 1, questions 1, 2, 4 et 5, début de l'exercice 3)
• cours + TD (semaine 4) : TD1, cours (base héxadecimale, représentation complément à 1)
• TD (semaine 5) : interro 1, cours (représentation des flottants, code ASCII)
• cours (semaine 5) : cours (ASCII, encodage), TD 2
• TD (semaine 9) : fin du TD2, quelques mots sur l'encodage des images (PNM)

Supports de TD / TP

• TD1, format pdf

---

---

Introduction

Slogan de ce cours :

« l'informatique ne s'intéresse pas plus aux ordinateur que l'astronomie ne s'intéresse aux télescope s. »

C'est de Edsger Wybe Dijkstra (1930—2002), un grand monsieur de l'informatique.

Rappels (??) historiques

L'informatique vient des mathématiques ! Les deux pionniers de l'informatique sont :

• John von Neumann (1903—1957) : mathématicien américain (d'origine hongroise)
• Alan Mathison Turing (1912—1954) : mathématicien anglais.

On peut également ajouter Alonzo Church (1903—1995) et Kurt Gödel (1906—1978), mais leur liens avec l'informatique ont été reconnus plus tardivement. (Logique, calculabilité, programmation fonctionnelle, ...)

Ce sont eux (avec quelques autres) qui invente le modèle des ordinateurs actuels : architecture de von Neumann.

Alan Turing est également l'inventeur de la machine de Turing : un ordinateur théorique et idéal pour raisonner sur les algorithmes.

Sinon :

• L'ENIAC est souvent considéré comme le premier ordinateur. Entièrement électroniques (pas de pièces mécaniques), il pèse environ 30 tonnes... C'était en 1946.
• Le premier ordinateur commercialisé est l'UNIVAC, en 1956.

La base 2 : théorie et applications

Tous les ordinateurs actuels sont « binaires ». Ce n'est pas nécessaire : certains des premiers ordinateurs étaient décimaux (ENIAC et UNIVAC par exemple) et il y a eu quelques prototypes d'ordinateurs ternaires en Russie.

Pour comprendre comment un ordinateur calcul, il faut donc commencer par comprendre le binaire...

Compter en binaire

Introduction

Notre système de numérotation est décimal : on a 10 chiffres (0, 1, 2, 3, 4, 5, 6, 7, 8 et 9). On a une notion d'unité (chiffre le plus à droite), de dizaine (deuxième chiffre en partant de la droite) etc.

• 10 unités font une dizaine,
• 10 dizaines font une centaine,
• etc.

La raison pour laquelle notre système de numérotation est décimal est probablement ... qu'on possède 10 doigts. Les aztèques comptaient vraisemblablement en base 20.

Remarque : la numérotation romaine n'est pas un vrai système de numérotation car on ne peut pas représenter tous les nombres entiers...

Compter

Définition : en binaire, il n'y a que deux chiffres appelés bits. Le 0 et le 1. On compte en suivant le même principe qu'en décimal.

Par l'exemple :

• les bits 0 et 1 correspondent ainsi aux nombres 0 et 1,
• le nombre 2 s'écrit en binaire comme 10, et 3 comme 11,
• 1101 représente le nombre 13,
• ...

Remarque : en base 10, « 10000 » (un « 1 » suivi de 4 « 0 ») correspond au nombre 10^4 ; en base 2, « 100000 » (le bit « 1 » suivi de 5 « 0») correspond au nombre 2^5 (càd 32).

Cette dernière remarque permet de trouver facilement à quel nombre correspond une écriture en base 2. On décompose le nombre en puissances de 2. Par exemple, pour 1001101

• 1000000 correspond à 2^6 = 64,
• 0001000 correspond à 2^3 = 8,
• 0000100 correspond à 2^2 = 4,
• 0000001 correspond à 2^0 = 1,
• 1001101 correspond donc à 64+8+4+1 = 77.

Le vocabulaire correspondant à dizaine / centaine / millier n'existe pas, mais on pourrait réutiliser certaines unités de mesure (volume pour les liquides en Angleterre, vers 1300...) :

          2 gills = 1 chopin
        2 chopins = 1 pint
          2 pints = 1 quart
         2 quarts = 1 pottle
        2 pottles = 1 gallon
        2 gallons = 1 peck
          2 pecks = 1 demibushel
    2 demibushels = 1 bushel or firkin
        2 firkins = 1 kilderkin
     2 kilderkins = 1 barrel
        2 barrels = 1 hogshead
      2 hogsheads = 1 pipegshead
          2 pipes = 1 tun                        (un peu moins de 1000 litres)

Plus traditionnellement, on parle :

• du bit de poids faible pour le bit « unité » (le plus à droite),
• du bit de poids fort pour le bit le plus à gauche,
• du bit numéro i pour le ième bit en partant de la droite (en commençant à compter à 0).

Opérations

Pour additionner deux nombres en binaire, on procède comme en décimal : bit à bit en partant de la droite et en utilisant :

+	0	1
0	0	1
1	1	0 avec une retenue

Pour les retenues, c'est comme pour l'addition en base 10...

Pour multiplier, il suffit de savoir faire des addition, car la table de multiplication est vraiment simple :

*	0	1
0	0	0
1	0	1

Par exemple :

          100101
        *  11001
   =================
          100101
    +    000000.          (facultatif)
    +   000000..          (facultatif)
    +  100101...
   -----------------      (addition partielle)
       101001101
    + 100101....
   =================      (addition finale)
      1110011101

Remarque : sur un seul bit, le « * » correspond au « et » logique, et le « + » sans retenue correspond au « ou exclusif ». (Le ou exclusif, ou XOR est parfois noté « ⊕ ».)

On peut aussi définir le « ou » et le « non » logique.

Nombre de bits nécessaire pour écrire un nombre

• Avec un unique bit, on peut simplement écrire les nombres 0 et 1.
• Avec 2 bits, on peut écrire les nombres 0, 1 , 2 et 3.
• Avec 3 bits, on peut aller jusqu'à 7.
• ...

Ajouter un bit permet de doubler le nombre d'entiers qu'on peut écrire. Ainsi, avec i bits, on pourra écrire 2*2*...*2 (i fois) nombres, càd 2^i nombres.

Comme on part de 0, les nombres que l'on peut écrire avec i bits sont exactement 0, 1, 2, ..., 2^i-1.

On peut calculer le i en fonction du n de la manière suivante :

2^i-1 ≤ n < 2ⁱ    ⟺    i-1 ≤ log(n) < i    ⟹    i-1 = ⌊log(n)⌋    ⟺    i = ⌊log(n)⌋+1

(rappel : log(n) = ln(n)/ln(2) et ⌊x⌋ est la partie entiere inferieure de x.)

La plupart des ordinateurs utilisent 32 bits (4 octets) pour stocker un nombre entier. On peut donc écrire 2³² (= 4 294 967 296) ou 2⁶⁴ (= 18 446 744 073 709 551 616) nombres entiers. En général, comme on a accès aux nombres négatifs, on peut plus ou moins aller de -2 milliards jusqu'à +2 milliards. Si on veut aller plus loin, il faut :

• soit utiliser des entiers plus grands (stocker par exemple sur 64 bits si l'ordinateur le permet),
• soit découper les entiers trop gros en plusieurs morceaux de 32 bits et faire les opérations à la main.

Remarque : sachant que log(10) = ln(10)/ln(2) ≈ 3.3, on peut facilement estimer le nombre de bits nécessaires pour écrire, par exemple, 41830471434 :

• le logarithme en base 10 de 41830471434 est environ 10 car le nombre possède 11 chiffres (la valeur réelle est environ 10.62149). Arrondissons à 11 pour avoir une borne supérieure.
• son logarithme en base 2 est donc environ 11 × 3.3 soit 36,3 (la valeur réelle est environ 35.28384).
• il faut donc environ 37 bits pour écrire 41830471434. (La valeur exacte est 36.)

Ce calcul fonctionne car :

log(x) = ln(x) / ln(2) = ln(x) / ln(10) × ln(10) / ln(2) = log₁₀(x) × ln(10)/ln(2)

Base hexadécimale

Comme il n'y a pas suffisament de chiffres, on est obligé d'utiliser des lettres : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e et f.

Il suffit de grouper les bits par paquets de 4 et d'appliquer la rêgle suivante :

 0000  <->  0
 0001  <->  1
 0010  <->  2
 0011  <->  3
 0100  <->  4
 0101  <->  5
 0110  <->  6
 0111  <->  7
 1000  <->  8
 1001  <->  9
 1010  <->  a
 1011  <->  b
 1100  <->  c
 1101  <->  d
 1110  <->  e
 1111  <->  f

Il est donc très facile de changer entre la base 2 et la base 2. Cela est vrai dès que l'on veut changer entre la base b et la base b^k : il suffit de grouper les « chiffres » par paquets de k.

Par exemple, pour 001110110000110001110010₂ :

 0011 1011 0000 1100 0111 0010 --> 3 b 0 c 7 2

On obtient donc 3b0c72₁₆.

Les nombres négatifs

Les nombres entiers sont stockés sur un nombre fini de bits (32 ou 64 en général). Les entiers « natifs » sont donc en nombre limité. Quand on dépasse la capacité d'un entier, les bits qui « dépassent » sont en général oubliés, et on obtient par exemple que

ffffffff₁₆ + 1 = 0

Pour les nombres négatifs, il existe plusieurs codages. Le plus simple est d'utiliser le bit de poids fort (le plus à gauche) pour donner le signe (1 pour négatif, 0 pour positif).

Par exemple, sur 32 bits :

• 00000000000000000000000000010011 représente 19,
• 10000000000000000000000000010011 représente -19.

Un autre codage est le complément à 1, où pour un nombre négatif, chaque bit est inversé :

• 00000000000000000000000000001010 représente 10,
• 11111111111111111111111111110101 représente -10.

Dans ces deux cas, remarquez que l'on peut représenter 0 de deux manières...

Le codage le plus courant est en fait le complément à 2. Un nombre positif est représenté par son écriture en base 2, et pour un nombre négatif :

• on prend sa valeur absolue en base 2,
• on ajoute 1,
• on inverse tous les bits.

Par exemple, pour représenter -43 :

• 43 : 00000000000000000000000000101011,
• on ajoute 1 : 00000000000000000000000000101100,
• on inverse tous les bits : 11111111111111111111111111010011.

Avec ce codage, 0 n'a qu'une seule représentation. 11111111111111111111111111111111 représente l'entier -1.

Dans tous les cas, pour savoir si un nombre est positif ou négatif, il suffit de regarder son bit de poids fort :

• 0 veut dire positif ou nul,
• 1 veut dire négatif (ou nul pour le complément à 1 ou la valeur absolue signée).

Le gros avantage du complément à 2 est que l'algorithme de l'addition ne change pas ! On additionne en complément à 2 comme on additionne les nombres positifs...

Les nombres « réels »

Un flottant, c'est un bit de signe, une mantisse et un exposant.

La norme IEEE754 pour les flottants 32 bits :

• exposant sur 8 bit : 00000001 pour -126 jusqu'à 11111110 pour 127 (11111111 est réservé pour des valeurs spéciales),
• la mantisse est sur 23 bits et ne représente que les bits « après la virgule ». (L'unique bit avant la virgule est forcément un 1.)
• 0 est représenté par 0 00000000 000...000,
• il y a un 0 « négatif » -0 : 1 00000000 000...000,
• il y a plusieurs types de valeurs spéciales :
  • l'infini +inf représenté par 0 11111111 000...000
  • moins l'infini -inf représenté par 1 11111111 000...000
  • les nombres dénormalisés (tous petits), pour lesquels on ne suppose pas que le premier bit de la mantisse est 1, de la forme 0/1 00000000 ... où la mantisse n'est pas nulle
  • les « not a number » NaN, de la forme 0/1 11111111 ... où la mantisse n'est pas nulle.

Les caractères et tout le reste...

code ASCII (American Standard Code for Information Interchange) pour les caractères

• 65 pour A (66 pour B etc),
• 97 pour a (98 pour b etc),
• 91 pour [, 92 pour / et 93 pour ],
• 48 pour 0, 49 pour 1 (50 pour 2 etc),
• 32 pour l'espace,
• ...

Mais aussi :

• 7 pour le bip système,
• 8 pour « backspace »,
• 9 pour une tabulation,
• 10 pour une fin de ligne (« line feed »)
• ...

Seulement 7 bits nécessaires. Le bit de poids fort est utilisé pour obtenir les accents.

Tout le monde n'utilise pas les mêmes accents, la conséquence du bit de poids fort dépend donc d'un encodage régional. (En Europe de l'ouest, encodage ISO-8859-1 ou ISO-8859-15 en général.)

L'unicode contient tous les accents possibles, ainsi que les caractères asiatiques (par exemple), mais il nécessite 32 bits, ce qui est assez inefficace pour les textes européens. On utilise donc un codage spécifique (UTF-8) qui utilise 8 bits pour les caractères courants, 16 bits pour les caractères moins courants, 24 bits pour les encore moins courants et 32 bit pour ce qui reste.

Pour reconnaître les octets, on utilise :

• caractère sur un octet (ASCII) : 0bbbbbbb,
• caractère sur deux octets : 110bbbbb 10bbbbbb,
• caractère sur trois octets : 1110bbbb 10bbbbbb 10bbbbbb,
• caractère sur quatre octets : 11110bbb 10bbbbbb 10bbbbbb 10bbbbbb.

Ceci permet de représenter 2⁷ + 2⁵⁺⁶ + 2⁴⁺⁶⁺⁶ + 2^3+6+6+6 = 2164864 caractères.