Planche 1
Planche 2
Plan
- listes
- types récursifs et fonctions récursives
- listes ordonnées
- fusion et tri fusion
- tableaux creux et polynômes
- grands nombres et cryptographie
Planche 3
Listes
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 Þ gachis (en place mémoire).
Symétriquement, comment représenter des vecteurs (ou matrices) creux?
Un tableau prend l'espace mémoire nécessaire pour toutes les valeurs
de l'indice, et donc pour les valeurs inutiles.
D'où la structure de données des listes dont les éléments sont
les éléments non consécutifs de l'ensemble (ou des paires [indice,
valeur] dans le cas des vecteurs ou matrices creux). On ne peut
accèder que séquentiellement aux éléments d'une liste.
Inductivement, une liste d'entiers est définie par l'équation récursive
type 'a list = Liste_vide | Constructeur of 'a * 'a list;;
Une liste est inductivement soit la liste vide, soit une paire
(élément, liste).
Planche 4
Listes
Le type liste est prédéfini en Ocaml, ainsi que ses notations pour les
constantes.
[] 3 :: [] 3::5:[] 3::5::7::[]
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).
let x = [98;10;12] and y = ["patrie";"gloire";"sciences"] and z = [] ;;
x : int list = [98; 10; 12]
y : string list = ["patrie"; "gloire"; "sciences"]
z : 'a list = []
Une liste non vide est aussi appelée doublet (cons en anglais)
let hd (v::x) = v;; donne le premier élément d'un doublet (head)
let tl (v::x) = x;; donne le second élément d'un doublet (tail)
Planche 5
Listes en Ocaml -- bis
Souvent, on couple définitions récursives du type des listes et des
fonctions associées.
let rec longueur x =
if x = [] then 0
else 1 + longueur (tl x);;
let rec imprimer x = if x <> [] then
begin printf "%d " (hd x); imprimer (tl x) end;;
On aurait pu écrire ces fonctions sous forme itérative
let longueur x =
let res = ref 0 and y = ref x in
while !y <> [] do
incr res;
y := tl !y;
done;
!res;;
On remarque que c'est un peu plus compliqué et surtout
qu'on peut se tromper plus facilement.
Planche 6
Listes en Java
class Liste {
int hd;
Liste tl;
Liste (int x, Liste a) {
hd = x;
tl = a;
}
Pour créer une liste, on appelle le constructeur (plusieurs fois)
Liste a = null;
Liste b = new Liste(3, null);
Liste c = new Liste (3, new Liste (5, new Liste (7, null)));
On représente la liste vide par l'absence de référence:
static boolean estVide (Liste a) { return a == null; }
Planche 7
Listes en Java -- bis
On associe aussi définitions de fonctions et du type récursif des listes.
static int longueur (Liste a) {
if (a == null)
return 0;
else
return 1 + longueur (a.tl);
static void imprimer (Liste a) {
if (a != null) {
System.out.print (a.hd);
imprimer (a.tl);
}
}
Planche 8
Listes en Java -- ter
Pour compliquer, on réécrit ces programmes itérativement.
static int longueur (Liste x) {
int res = 0;
Liste y = x;
while (y != null) {
++res;
y = y.tl;
}
return res;
}
ou encore
static int longueur (Liste x) {
int res = 0;
for (Liste y = x; y != null; y = y.tl)
++ res;
return res;
}
Planche 9
Listes triées
Liste dont tous les éléments en ordre croissant.
let rec insérer v x =
if x = [] then [v]
else
if v < (hd x) then v :: x
else (hd x) :: insérer v (tl x) ;;
en Java
static Liste inserer (int v, Liste x) {
if ( x == null )
return new Liste (v, null)
else
if ( v < x.hd )
return new Liste (v, x)
else
return new Liste (x.hd, inserer (v, x.tl));
Exercice: écrire ces programmes itérativement.
Planche 10
Fusion de listes triées
let rec fusion x y =
if x = [] then y
else if y = [] then x
else if (hd x) <= (hd y) then
(hd x) :: fusion (tl x) y
else
(hd y) :: fusion x (tl y) ;;
en Java
static Liste fusion (Liste x, Liste y) {
if (x == null)
return y;
else if (y == null)
return x;
else if ( x.hd <= y.hd )
return new Liste (x.hd, fusion (x.tl, y));
else
return new Liste (y.hd, fusion (x, y.tl));
Planche 11
Tri fusion sur les listes
Principe: on coupe une liste en deux, on trie les deux moitiés et on
fusionne les résultats.
Pour couper en deux 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. On peut aussi fabriquer directement ces 2 listes en
parcourant simultanément la liste à 2 vitesses différentes.
A la fin des fin, ce tri est toujours en O(n log n) opérations,
quelquesoit les valeurs d'entrée des données (Le tri fusion peut se
faire aussi bien sûr dans un tableau, mais c'est un peu plus dûr).
Exercice: programmer ce tri.
Planche 12
Polynômes creux en Java
class Monome {
double coeff;
int degre;
Monome (double c, int d) { coeff = c; degre = d; }
public String toString () {
return coeff + "x^" + degre;
}
class Polynome {
Monome hd;
Polynome tl;
Polynome (Monome m, Polynome p) { hd = m; tl = p; }
}
Pour p[x] = 4x2 -1, on écrit:
Polynome p = new Polynome (new Monome (4, 2),
new Polynome (new Monome (-1, 0), null));
Planche 13
Addition de polynômes creux
static Polynome addition (Polynome p, Polynome q) {
if (p == null) return q;
else if (q == null) then p;
else if (p.hd.degre < q.hd.degre)
return new Polynome (p.hd, addition (p.tl, q));
else if (p.hd.degre = q.hd.degre)
return new Polynome (
new Monome (p.hd.coeff + q.hd.coeff, p.hd.degre),
addition (p.tl, q.tl));
else
return new Polynome (q.hd, addition (p, q.tl));
}
Planche 14
Polynômes creux en Ocaml
type monome = {coeff: float; degré: int} ;;
let p = [ {coeff = 4.; degré = 2}; {coeff = -1.; degré = 0}] ;;
qui donne comme résultat
type monome = {coeff: float; degré: int }
val p : monome list = [coeff=4.0; degré=2; coeff=-1.0; degré=0]
pour représenter le polynôme p[x] = 4x2 -1.
Planche 15
Addition de polynômes creux en Ocaml
let rec addition p q =
if p = [] then q
else if q = [] then p
else if (hd p).degré < (hd q).degré then
{coeff = (hd p).coeff; degré = (hd p).degré} :: addition (tl p) q
else if (hd p).degré = (hd q).degré then
{coeff = (hd p).coeff +. (hd q).coeff ; degré = (hd p).degré}
:: addition (tl p) (tl q)
else
{coeff = (hd q).coeff; degré = (hd q).degré} :: addition p (tl q) ;;
Planche 16
Filtrage (Ocaml)
On peut réécrire le programme précédent en utilisant le filtrage.
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 ;;
Planche 17
Filtrage (Ocaml) -- bis
Idem pour le programme d'impression
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 ;;
L'avantage du filtrage est qu'il force à considérer tous les cas de la
définition du type inductif. Sinon un message est émis
("pattern-matching is not exhaustive'').
Exercices: faire la multiplication et la division.
Planche 18
Fonctions classiques sur les listes
Comment copier, renverser, concaténer deux listes? LISP List Processing Language [John McCarthy MIT-1960] fut le
langage de l'intelligence artificielle. La version moderne de Lisp
s'appelle Scheme [Abelson et Sussman, MIT]; sa version typée
est 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 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.
Planche 19
Destruction dans les listes -- GC
Jusqu'à présent toutes nos listes ont une valeur constante.
static Liste supprimer (int x, Liste a) {
if (a != null) return null;
else if (a.hd == x) return a.tl;
else return new Liste (a.hd, supprimer (x, a.tl));
}
On peut faire une version destructive.
static Liste supprimer (int x, Liste a) {
if (a != null)
if (a.hd == x) a = a.tl;
else a.tl = supprimer (x, a.tl);
return a;
}
On doit utiliser la première autant qu'on peut. La deuxième peut finir
dans des problèmes compliqués de partage de listes modifiables. Penser
au GC (garbage collection) qui récupère automatiquement la
mémoire.
Planche 20
Destruction dans les listes en Ocaml
La librairie standard Ocaml ne fournit que des listes non modifiables.
Il faut se définir un nouveau type pour les listes modifiables.
type 'a liste = Nil | Cons of 'a cellule
and 'a cellule = { hd : 'a; mutable tl : 'a liste };;
let x = Cons ({hd = 2; tl= Cons ({hd = 4; tl = Nil})});;
let rec supprimer v a = match a with
Nil -> a
| Cons ({hd = v1; tl = a1} as cellule) -> if v1 = v then a1
else begin cellule.tl <- supprimer v a1; a end;;
Après (par exemple) la suppression de 4 dans x, la valeur de
x est modifiée et 4 n'y figure plus.
Remarquer l'utilisation du mot-clé as permettant de faire 2
filtrages simultanément.
Planche 21
Grands nombres et cryptographie
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, posons B=10.
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, PPC). Nous prenons petit endien.
On fait facilement l'addition et la multiplication, la lecture et
l'impression. Comment faire la division et le test de primalité, utiles
pour faire de la cryptographie?
Planche 22
Cryptographie à clé publique
Un problème 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 les cours Demazure/Morain en majeure Math et Info,
ou ``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
ed º 1 mod (p-1)(q-1)
On suppose les messages m coupés en morceaux mi < n, et on
fait
ci = mie mod n
On décode par
mi = cid mod n
On vérifie que
cid º mi 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.
Planche 23
Grands nombres premiers
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).
Planche 24
Méthode 2 (Rabin-Miller, 1980)
Soit b la plus grande puissance de 2 telle que p=1+m2b
1- Choisir un nombre aléatoire a tel que a < p
2- Poser j=0 et z= am 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=z2 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/251.
Planche 25
Exercices en TD
- faire Merge Sort sur les listes.
- faire la lecture, l'impression, et les opérations sur les grands
nombres. Pour rentrer les grands nombres, on pourra soit les tirer au
hasard, soit les lire comme arguments sur la ligne d'input (au niveau
du shell Unix). Il faudra alors comprendre comme accéder aux éléments
d'une chaîne de caractères:
En Java, s.charAt(i) donne le i+1ème caractère de s
En Ocaml, s.[i]
et transformer un caractère en entier, on fait
En Java, int c = Character.digit(s.charAt(i), 10);
En Ocaml, let c = Char.code s.[i] - Char.code '0'
Remarque: les chaînes de caractères sont modifiables en Ocaml, mais
non modifiables en Java. La classe StringBuffer est la classe
des chaînes modifiables.
This document was translated from LATEX by HEVEA.