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)

Supports de TD / TP

-- à venir

---

---

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.

1. 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...

1.1. 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...

1.1.1. 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).

1.1.2. 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.

1.1.3. 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)