Comment représenter des ensembles dynamiques? Dont le nombre d'éléments peut varier dans le temps? Les tableaux ont leur dimension fixée à leur création. Il faut donc considérer le nombre maximal d'éléments. C'est du gachis (en place mémoire) si on a beaucoup d'ensembles.
Symétriquement, comment représenter des vecteurs (ou matrices) creux? Si on prend un vecteur, on prend un espace mémoire pour ttes les valeurs de l'indice, et donc pour les valeurs inutiles.
En informatique, on utilise des listes dont les éléments sont tous les éléments de l'ensemble (ou des paires indice/valeur), et qu'on ne peut accéder que séquentiellement.
Inductivement, une liste d'entiers est définie par l'équation récursive
type 'a list = [ ] | 'a :: list ;;Une liste est soit la liste vide
[ ], soit ``cons'' d'un entier
et d'une liste. Dans le deuxième cas, il s'agit d'une paire avec le
tag ``cons''.
Exemples de listes:
[ ] 3 :: [ ] 3::5:[ ] 3::5::7::[ ]de longueur 0, 1, 2, 3, etc. Une notation équivalente et plus concise est:
[ ] [3] [3;5] [3;5;7]
Remarque: il peut y avoir 2 fois le même élément
[3;2;3]. L'élément d'une liste est de type
quelconque, mais une liste est homogène (comme les tableaux).
Le type list (polymorphe) est prédéfini (comme pour les vecteurs). Pas besoin de le déclarer. Ainsi
let x = [1;2;3] and y = [ ] ;; x : int list = [1; 2; 3] y : 'a list = [ ]
x n'est pas la liste vide [
], la valeur de son premier élément (sa
tête) est hd x (``head of x''), le reste de la
liste (sa queue) est tl x (``tail of x''). Le type
prédéclaré d'une liste est bien récursif
puisque
#let x = [1;2;3] and y = [ ] ;; x : int list = [1; 2; 3] y : 'a list = [ ] #hd x;; - : int = 1 #tl x ;; - : int list = [2; 3] #hd (tl x);; - : int = 2 #tl (tl x) ;; - : int list = [3]Remarque:
hd et tl est le pendant de
fst et snd pour les paires.
On peut faire du filtrage sur les listes. Des motifs autorisés sont
motif_1 :: motif_2 [ ] [motif_1; ... ; motif_n]Par exemple:
let x::y = [1;2;3] in ...
match [1;2;3] with
[ ] -> e_1
| x::y -> e_2
Il est souvent plus simple (et efficace) de coupler définition récursive de fonctions et la définitions récursive du type des listes. Calculons par exemple la longueur d'une liste
let rec longueur x =
if x = [ ] then 0
else
1 + longueur (tl x);;
ou
let rec longueur x = match x with
[ ] -> 0
| _ :: y -> 1 + longueur y;;
ou
let rec longueur = function
[ ] -> 0
| _ :: y -> 1 + longueur y;;
On aurait pu écrire cette fonction sous forme itérative
let longueur x =
begin
let res = ref 0 and y = ref x in
while !y <> [ ] do
incr res;
y := tl !y;
done;
!res
end;;
On remarque que c'est un peu plus compliqué et surtout
qu'on peut se tromper plus facilement.
Une liste d'entiers ordonnée a tous ses éléments en ordre croissant. Voici 2 fonctions pour l'imprimer et insérer un nouvel élément.
let rec imprimer (x) = if x <> [ ] then
begin
printf "%d " (hd x);
imprimer y
end;;
let rec insérer v = function
[ ] -> [v]
| x :: y ->
if v < x then
v :: x :: y
else
x :: insérer v y ;;
Ce dernier exemple peut bénéficier de la construction syntaxique
as dans le filtrage
let rec insérer v = function
[ ] -> [v]
| x :: y as z ->
if v < x then
v :: z
else
x :: insérer v y ;;
x et y deux listes triées. Comment
les fusionner (par interclassement)?
let rec fusion = function
[ ], y -> y
| x, [ ] -> x
| (x1::x2), (y1::y2) ->
if x1 <= y1 then
x1 :: fusion (x2, y1::y2)
else
y1 :: fusion (x1::x2, y2) ;;
ou mieux:
let rec fusion = function
[ ], y -> y
| x, [ ] -> x
| (x1::x2 as x), (y1::y2 as y) ->
if x1 <= y1 then
x1 :: fusion (x2, y)
else
y1 :: fusion (x, y2) ;;
ou encore:
let rec fusion x y = match x, y with
[ ], y -> y
| x, [ ] -> x
| (x1::x2), (y1::y2) ->
if x1 <= y1 then
x1 :: fusion x2 y
else
y1 :: fusion x y2 ;;
Pour couper en 2 la liste, on peut soit trouver sa longueur n et fabriquer 2 listes des n/2 premiers éléments et des n - n/2 derniers. Ou on peut fabriquer directement ces 2 listes en parcourant simultanément la liste à 2 vitesses différentes.
A la fin des fin, ce tri est tjrs en n log n opérations. (Le tri fusion peut se faire aussi bien sûr dans un tableau, mais c'est assez subtil).
Les éléments des listes sont souvent composites, car ce sont des agrégats d'information. Par exemple, un polynôme (d'une seule variable) est une liste de paires (degré, coefficient), éventuellement triée par degré décroissant. Au lieu d'utiliser les paires ou n-uplets, on préfère avoir des n-uplets avec tag, ie des enregistrements. Il faut déclarer le type des enregistrements. Les déclarations de type sont de nouvelles phrases au toplevel. Après on utilise les constantes de type record comme toutes les autres constantes:
type monome = {coeff: float; degré: int} ;;
let p = [ {coeff = 4.; degré = 2}; {coeff = -1.; degré = 0}] ;;
qui donne comme résultat
Type monome defined.
p : monome list = [{coeff=4.0; degré=2}; {coeff=-1.0; degré=0}]
pour représenter le polynôme p[x] = 4x^{2} -1.
L'ordre des champs n'a pas d'importance. Un autre type enregistrement
très fréquent est celui des points du plan:
type point = {x: int; y: int} ;;
let p1 = {x = 4; y = 2} and p2 = {x = -3; y = 4} ;;
On peut faire du filtrage comme sur les paires
match m with
{coeff = c; degré = deg} -> e_1
On suppose les polynômes triés par ordre de degré croissant
let addition p q = match p, q with
[ ], q -> q
| p, [ ] -> p
| {coeff = c1; degré = d1} :: p1,
{coeff = c2; degré = d2} :: p2 ->
if d1 < d2 then
{coeff = c1; degré = d1} :: addition p1 q
else
if d1 = d2 then
{coeff = c1+c2; degré = d1} :: addition p1 p2
else
{coeff = c2; degré = d2} :: addition p q1 ;;
Pour imprimer le résultat:
let rec imprimer p = match p with
[ ] -> ()
| {coeff = c1; degré = d1} :: p1 ->
begin
imprimer p1;
if p1 <> [ ] then
printf " + ";
printf "%2.2fx^%d" c1 d1
end ;;
Exercice: faire la multiplication et la division.
Comment copier, renverser, concaténer deux listes?
LISP List Processing Language par John McCarthy
en 1960 (MIT, puis Stanford). Ce fut le langage de
l'intelligence artificielle. La version moderne de Lisp
s'appelle Scheme (Abelson et Sussman, MIT); sa version typée
n'est pas loin de ML!
let rec append p q = match p, q with
[ ], q -> q
| (x1::p1), q -> x1 :: append p1 q ;;
let rec reverse p = match p with
[ ] -> [ ]
| (x1::p1) -> append (reverse p1) [x1] ;;
let rec map f p = match p with
[ ] -> [ ]
| (x1::p1) -> (f x1) :: map f p1 ;;
let rec do_list f p = match p with
[ ] -> ()
| (x1::p1) ->
begin f x1 ; do_list f p1 end ;;
let rec mem x p = match p with
[ ] -> false
| (x1::p1) -> (x = x1) || mem x p1 ;;
Essayer de bien comprendre l'occupation mémoire des paramètres
ou résultats de ces fonctions.
Comme pour les polynômes, on peut représenter les grands nombres par des listes de chiffres dans une certaine base B. Pour simplifier la lecture et l'impression, nous prendrons B=10 ou B=100 ou B=1000, etc.
Deux représentations sont possibles: little endian chiffre le moins significatif en tête (comme sur le Vax, l'Alpha et le Pentium), big endian sinon (MC 68000, Sparc). Nous prenons petit endien.
On fait facilement la lecture et l'impression, l'addition et la multiplication (comme on a appris à l'école primaire). Comment faire la division et le test de primalité, utiles pour faire de la cryptographie?
Pour la division, la méthode de Knuth (vol2) n'est pas très dure, mais un peu longue. On a besoin de 2 lemmes:
On veut diviser u par v, ie u = q v + r où 0 <= r < v. D'abord, on voit que toute la difficulté est de traiter le cas où u/v < B. On fera ensuite l'opération chiffre par chiffre du quotient.
Quand u/v < B, une bonne approximation du quotient s'obtient en regardant les 2 premiers chiffres de u et le premier chiffre de v, notamment quand le premier chiffre v1 de v vérifie v1 >= E(B/2) où E(x) est la partie entière de x.
En effet, posons u = u_0 u_1...u_n et v = v_1...v_n en base B. Supposons u/v < B. Calculons q' = min{E((u_0*B + u_1)/v_1), B-1}. Alors
Lemme 1: q' >= q
Lemme 2: Si v1 >= E(B/2), alors q'-2 <= q <= q'
*B + u_{j+1})/v_1).*v_2 > (u_j*B+u_{j+1})*B+u_{j+2}, décrémenter q'.*v.
L'horreur en crypto est la gestion du partage des secrets. La méthode RSA (inventée en 1978) utilise un système à 2 clés: une publique et une autre secrète. (Cf le cours de Demazure et Morain en majeure Math et Info pour plus de renseignements, ou le livre ``Applied Cryptography'' de Schneier.)
Soit n=pq où p, q sont premiers. On encode avec une clé e première avec (p-1)(q-1). On décode avec une clé d telle que
e d = 1 mod (p-1)(q-1)
On suppose les messages m coupés en morceaux m_i < n, et on fait
c_i = m_i^e mod n
On décode par m_i = c_i^d mod n
On vérifie que c_i^d = m_i mod n
On oublie donc p et q. La clé e est publique. Seul le récepteur a une clé secrète, très difficile à deviner. Typiquement, pq a une centaine de chiffres décimaux.
Il faut donc trouver de grands nombres premiers p, q. (50 à 100 chiffres). Pour aller vite, on peut faire des tests probabilistes pour savoir si p est premier:
Méthode 1 (Lehmann)
1- Choisir un nombre aléatoire a tel que a < p
2- Calculer a^{(p-1)/2} mod p
3- Si a^{(p-1)/2} <> 1 ou -1, répondre NON.
4- Sinon p est premier à 50%.
(On itère donc pour 10 valeurs de a).
1- Choisir un nombre aléatoire a tel que a < p
2- Poser j=0 et z= {a}^m mod p
3- Si z=1 ou z=p-1, alors p peut être premier.
4- Si j>0 et z=1, alors répondre NON.
5- Faire j=j+1. Si j<b et z <> p-1, faire z=z^2 mod p et
revenir en (4). Si z=p-1, alors répondre OUI.
6- Si j=b et z <> p-1 alors répondre NON.
Sur un nombre de 256 bits, se tromper après 6 tests est inférieur à 1/2^{51}.