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

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 inverse tous les bits,
• on ajoute 1.

Par exemple, pour représenter -43 :

• 43 : 00000000000000000000000000101011,
• on inverse tous les bits : 111111111111111111111111111010100,
• on ajoute 1 : 111111111111111111111111111010101.

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

Une méthode pratique de tête : Pour convertir un nombre en son complément à deux, il faut garder tout les "0" de la droite jusqu'au premier 1(on le garde aussi), puis on inverse tous les suivants. Exemple :

• 56 : 00000000000000000000000000111000,
• -56 : 11111111111111111111111111001000,

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.

Complexité, approximations asymptotiques

La notion de complexité d'un programme est fondamentale pour pouvoir évaluer l'intérêt pratique d'un programme. La complexité observée lors de test ou de benchmark est parfois suffisante mais ne prend en compte que certaines exécutions (celles qui sons testées par les tests). Il est souvent nécessaire de se faire une idée de la complexité théorique d'un programme pour pouvoir prédire son temps d'exécution (ou ses besoins en ressources) pour les exécutions futures.

Première approche de la complexité

Tout d'abord, nous nous intéresserons surtout à la complexité en temps, et (presque) jamais à la complexité en espace. Il ne faut pas en déduire que seule la complexité en temps est importante !

L'idée de base est de compter en combien de temps va s'exécuter un programme donné, mais la question elle même est mal posée :

• comment compte-t'on ?
• et surtout, que compte-t'on ?

Chronométrer le temps d'exécution ne permet pas de faire d'analyse fine, et ne permet pas facilement de prédire le comportement général de votre programme. Comme le temps dépend beaucoup du processeur utilisé, l'idéal serait de pouvoir compter le nombre de cycle nécessaires au programme. Cela est généralement impossible car cela dépend du type de processeur utilisé ainsi que des optimisations faites par le compilateur.

La complexité en temps d'un algorithme, c'est une estimation du nombre d'opérations atomiques effectuées par cette algorithme avant qu'il ne termine. Cette estimation doit être donnée comme une fonction dépendant de la taille de l'entrée sur laquelle est lancé l'algorithme.

La notion d'opération atomique est assez intuitive : c'est une opération algorithmique qui n'est pas divisible en sous-opérations. En première approximation, une opération est atomique si elle ne porte que sur des objets de type entier, caractère ou booléen. (Les types codés sur un ou deux mots). Un test (si (n==42) alors ...) ou une affectation (x:=3,1415926536) sont des opérations atomiques ; mais l'initialisation d'un tableau n'est pas atomique. (Il y a autant d'opérations qu'il y a d'éléments dans le tableau...)

Exemple : la recherche du maximum dans un tableau d'entiers positifs peut se faire comme suit

max = 0
pour i:=1 à taille
faire
  si (max < Tab[i])
  alors max:=Tab[i]
finfaire
affiche("Le maximum est %i.\n",max)

Le nombre d'opérations est le suivant :

• une opération pour l'initialisation de max
• une opération pour l'initialisation de i à 1
• un test pour voir si i==taille
• une opération pour le test max < Tab[1]
• "peut-être" une opération pour l'affectation max:=Tab[1]
• puis, pour chaque élément suivant du tableau :
  • un incrément du compteur
  • une affectation du compteur
  • un test pour voir si on a atteint la fin du tableau
  • un test
  • peut-être une affectation

Au total, si $n$ est la taille du tableau, on obtient entre $4n$ et $5n$ opérations. De manière générale, on s'intéresse surtout au pire cas ; on dira donc que cet algorithme s'exécute en "au plus $5n$ opérations".

Le code Python correspondant serait :

 def maximum(t):
     """renvoie le maximum d'un tableau t d'entiers positifs."""
     max = 0
     for e in t:
         if e > max:
             max = e
     return(max)

Le nombre d'operations est similaire, mais il n'est pas facile de savoir exactement combien d'etapes sont effectué lors de l'affectation des valeurs du tableau à e...

Approximations asymptotiques

On ne peut habituellement pas compter de manière aussi précise le nombre d'opérations ; et ça n'a pas toujours du sens de vouloir être trop précis. (Est-ce que i:=i+1 correspond à une ou deux opérations atomiques ?) Nous allons donc utiliser les approximations asymptotique pour compter la complexité... Le but sera alors de distinguer les algorithmes "rapides", "lents", ou "infaisables". La notion de "grand O" permet de faire ça de manière systématique.

définition

si $f$ et $g$ sont des fonctions de $\mathbb {N}$ dans $\mathbb {N}$, on dit que $f$ est un "grand O" de $g$, et on écrit $f=O(g)$ si le quotient $|f(n)| \over |g(n)|$ est borné. Plus précisément, ça veut dire que $\exists B,\forall n,{|f(n)| \over |g(n)|}<B$ c'est à dire, quand $f$ et $g$ sont positives : $\exists B,\forall n,f(n)<B\times g(n)$

Le but de cette définition est multiple :

• elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("$4n$ et $5n$, c'est presque la même chose")
• elle permet d'ignorer les cas initiaux et autres phénomènes négligeables
• elle permet de simplifier les calculs de complexité

Propriétés

• si $f=O(h)$ et $g=O(h)$ alors $\alpha f+\beta g=O(h)$
• si $f=O(g)$ et $g=O(h)$ alors $f=O(h)$
• si $f=O(g)$ et $f'=O(g')$ alors $f\times f'=O(g\times g')$
• si $f=O(g)$ et $f'=O(g')$ alors $f+f'=O(|g|+|g'|)$

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : $\log$, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
Pour $n$ très grand :

$1<\log(\log(n))<\log(n^{g})<\log(n)<\log(n^{k})<\log(\exp(n))<n^{g}<n<n^{k}<\exp(\log(n))<\exp((n^{g}))<\exp(n)<\exp(n^{k})<\exp(\exp(n))$
Avec $g<1$ et $k>1$.

---À compléter ? C'est vous qui voyez...---