Chapitre 1: Codage numérique de l’information
I/ Codage des nombres.
1) Entiers naturels.
Un ordinateur étant fini, on ne peut coder que des parties finies de I â„• : [|0;N[|
[| et |] = entiers naturels.
On peut coder ça avec des signaux en tout ou rien(TOR).
​
Avec K signaux, on peut coder 2^k possibilités.
​
Si on code de manière systématique le dernier signal nous dis si le nombre du signal est pair ou impair.
Exemple : 1001 représente un chiffre impair.
Le premier signal nous dit si le nombre est plus grand ou plus petit que 2^k/2 = 2^k-1
Exemple : 0101 est inférieur à 2^4 /2 <=> 8
Le premier signal à pour poids 2^k-1
Le second signal à pour poids 2^k-2
L’avant dernier signal à pour poids 2^1
Le dernier signal à pour poids 2^0
Dans un ordinateur on travaille avec un nombre fixés de chiffres.
bit = chiffre binaire
1 octet = 8 bits <=> 256 possibilités
2 octets = 16 bits <=> 65536 possibilités
4 octets = 32 bits <=> 4294967296 possibilités
Théorème : Tout nombre entier entre 0 et 2^k peut s’écrire de manière unique comme somme de 2i distincts avec i < k.
210 ≈ 102
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2) Entiers relatifs.
Une possibilité simple :
​
0 = + Valeur absolue sur 15 bits
1 = -
Mauvaise méthode car +0 = -0
- 32768 au lieu de 32768
+216 → revient à négliger les chiffres au-delà du 16e
Cette méthode a l’avantage que la plupart des calculs marchent exactement pareil, on considère le nombre comme un naturel ou un relatif.
C’est le même principe en trigonométrie :
· Tout point du cercle peut se coder par un angle dans [0;2π[ ou dans [-π ;π[
· Tout bloc de 16 bits peut coder un entier dans [0;2^16[ ou dans [-2^15;2^15[
3) Valeurs approchées de réels.
Méthode simple : calculs en virgule / dénominateur fixe.
[0 ;65536[ <=> [0,00;655,36[ selon l’amplitude à laquelle on regarde le nombre.
Inconvénient : la précision coûte de l’amplitude.
Nombre d’Avogadro ≃ 6,0221×10^23 mol-1
Masse de l’électron ≃ 9,109×10^-31 kg
En dénominateur fixe, il faudrait une amplitude de 10^24/10^-34=10^55 environ égal à 2^183
=> Trop lourd.
Codage en virgule flottante :
x = s * m * 2e
m = mantisse: entier borné
e = exposant : petit entier
s = signe négatif ou positif
​
​
Précision : 2^23 ≈ 7 chiffre décimales
Amplitude : e ∈ [0;256[ <=> [-128;128[
= nombre à virgule flottante, précision simple.
= nombre à virgule flottante, précision double.
II) Objets composites.
1) Structures.
​
On veut stocker plusieurs informations qui vont ensemble.
Exemple : une date
- jour : 31 jours max dans un mois donc 1 octet
- mois : 12 mois dans une année donc 1 octet
-année : On cherche à écrire une date historique donc 2 octet [-32768;32768[
On les met simplement côte à côte tel que :
Une structure, c’est un bloc de mémoire composé de champs d’un certain type, avec chacun une talle fixe et un emplacement fixe.
2) Tableaux.
Utilisé pour stocker un nombre indéterminé.
Tableau de 5 éléments de 4 octets.
Pour accéder à l’élément n°3 on fait 3*4 = 12
L’élément n°3 commence donc à l’octet n°12
La taille du tableau n’est pas indiqué dans le tableau lui même, il faut une variable supplémentaire.
Beaucoup de langage stockent le tableau et sa taille dans sa structure.
3) Texte.
Il nous faut un catalogue de caractère.
Historiquement on codait 1 octet par caractère, en utilisant un catalogue adapté à 6 langue.
Problème → Certaines langues ont trop de caractères et même sans ça on aimerait pouvoir faire des textes multilingues.
Solution :
· Un unique catalogue qui combine toutes les langues : Unicode (~ 100 000 caractères)
· Plusieurs octets par caractère :
- 32 bits par caractère.
- 1 à 6 octets par caractère.
UTF-8 codage de longueur variable.
​
Codage de texte avec mise en forme :
· Par le bas : on ajoute des annotations dans le texte, identifiées par des caractères spéciaux.
Exemple HTML (HyperText Markup Language) :
<p> J’ai <i> très </i> faim </p> <=> J’ai très faim
<p> indique un paragraphe
<i> indique que les caractères qui suivent sont écris en italique.
</> désigne la fin des caractères spéciaux.
· Par le haut : on code (en octet) en annonçant le type, la taille, puis le contenu.
1 : Numéro du paragraphe (inventé).
2 : Taille du paragraphe (inventé).
3 : Indique que c’est un texte.
4 : Taille.
5 : Mise en page (0 = aucune, 4 = italique).
​
III) Structures de données.
1) Notion de pointeur.
Définir une structure pour stocker les infos d’une personne :
Nom :
Prénom :
Date de naissance : 4 octets (jour + mois + année)
Problème : comment mettre des champs de taille variable dans une structure ?
On met leur contenu ailleurs dans la mémoire.
Personne : une case par octet
1 : Emplacement qui va indiquer l’emplacement du nom (=pointeur).
2 : Longueur du nom.
3 : Emplacement qui va indiquer l’emplacement du prénom (=pointeur).
4 : Longueur du prénom.
Un pointeur : une variable qui est prévu pour contenir le numéro d’une case « mémoire »
Nom d’une case mémoire : « adresse »
T, un tableau de valeurs de type quelconque ordonné
Comment (algorithme) le classer du plus petit au plus grand ?
· Tri à bulles : n²/2 on déplace le premier chiffre rencontré si il est plus petit sinon on prend le plus petit des deux.
Mais parfois plus rapide avec une variable qui compte le nombre d’échange.
Si il n’y a pas d’échange alors c’est terminé.
· Tri par sélection : n²/2 ressemble au tri par bulle mais en déplaçant les valeurs du tableau.
· Tri par insertion : n²/2 Utilisation de la fonction logarithme de la taille d’un nouveau tableau pour comparer avec la valeur du milieu.
· Tri rapide : n log(n) en moyenne, n² au pire des cas mais très improbable.
Prend le premier nombre, celui du milieu et le dernier et prend le milieu et le place au milieu du tableau en libérant sa case.
DdoS : Distributated Denial of Service.
SETI @ home : Search for ExtraTerrestrial Intelligence.
Définition :
Un algorithme récursif est un algorithme dont une des étapes consiste à appliquer le même algorithme à d’autres données.
Pour que ça marche il faut :
· que certaines données puissent se traiter sans passer par ces étapes.
· que, quand on passe par ces étapes, ce soit sur des données plus petites ou plus généralement plus proches de celles qu’on peut traiter directement.
Exemple : Tri par fusion
​
ORGANIGRAMME à rajouter
​
Conventions de passage de paramètres et résultat
I/ Style fonctionnel ou impératif.
1) Style impératif.
C’est quand un programme est une succession d’actions.
Écrire plusieurs fois la même action donne éventuellement des résultats différents.
Exemple : i = i + 1,
2) Style fonctionnel.
C’est quand un programme est un calcul, lui même constitué de calculs plus simples.
Exemple : calcul de n! dans les deux styles :
JavaScript:
f = 1 ;
for(i = 0 ; i ≤ n ; i++){
f = f * i ;
}
print f ;
Camel :
let rec factorielle n =
if n = 0 then 1
else factorielle(n-1) * n
A la place de boucles, on utilise des fonctions récursives.
Avantage : démontrer le comportement du programme est plus facile.
Inconvénients :
- tout ce qui est affichage, dialogue avec l’utilisateur, réseau, etc, est naturellement impératif.
- si on ne fait pas attention chaque appel récursif demande de se rappeler ou on en est ça consomme de la mémoire.
Factorielle en récursif terminal
let factorielle n =
let rec fact f n =
if n = 0 then f
else fact (n*f) (n-1)
in fact 1 n
On remarque que la version récursive de fibonacci est très lente car elle calcule plein de fois la même chose .
On pourrait retenir le résultat la première fois et le réutiliser :
ça s’appelle mémoiser :
if (meme[n] == *) {
r = …. ;
memo[n] = r ;
return r ;
} else {
return memo[n] ;