Upload
marcelon-cheron
View
112
Download
3
Embed Size (px)
Citation preview
Algorithmes et structures de données
9ème cours
Patrick Reutermaître de conférences
http://www.labri.fr/~preuter
• La dernière fois :
– Règles de complexité– Pointeurs
Théorie de la complexitéClasses de Grand-O• O(1) complexité constante
• O(log n) complexité logarithmique
• O(n) complexité linéaire
• O(n log n) complexité quasi-linéaire
• O(na) complexité polynomiale– O(n2) complexité quadratique
– O(n3) complexité cubique
• O(an) complexité exponentielle
O(log n) O(n) O(n log n) O(n2) O(n3) O(2n)
Théorie de la complexité
• Règles de constantes
• Règles des sommes
• Règles des produits
• Transitivité
• Pointeurs
Définitions
• Déclaration d’un pointeur vers un byte
var p_a : ^byte;
• Déréférencement d’un pointeur :
p_a^
• Connaître l’adresse d’une variable a
Addr(a); {ou bien }@a;
Organisation de la mémoire
var a : byte; ( 1 octet (byte) )
#0#1#2#3#4#5
...
#536.870.910#536.870.911
#1.000
...
Organisation de la mémoire
var a : byte;
#0#1#2#3
a #4#5
...
#536.870.910#536.870.911
#1.000
...
Organisation de la mémoirevar a : byte;a := 97;
#0#1#2#3
a #4#5
...
#536.870.910#536.870.911
#1.000
...
97
Organisation de la mémoirevar a : byte;a := 97;
#0#1#2#3
a #4#5
...
#536.870.910#536.870.911
#1.000
...
97
Comment connaître l’adresse de a ? Addr(a)
Organisation de la mémoirevar a : byte;a := 97;p_a := Addr(a); { Sauvegarder l’adresse }
#0#1#2#3
a #4#5
...
#536.870.910#536.870.911
#1.000
...
97
Comment connaître l’adresse de a ? Addr(a)
var a : byte;var p_a : ^byte; {4 octets, lire : pointeur vers a}a := 97;p_a := Addr(a); { Sauvegarder l’adresse }
#0#1#2#3
a #4#5
...
#536.870.910#536.870.911
p_a #1.0000
97
Comment connaître l’adresse de a ? Addr(a)
p_a #1.001p_a #1.002p_a #1.003
4
00
« p_a pointe vers a »
var a : byte;
var p_a : pointer to byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
{ p_a est 4, p_a^ est 97)
p_a^ := 10; { Déréférencement }
{ p_a est 4, p_a^ est 10)
#0#1#2#3
p_a^ a #4#5
...
#536.870.910#536.870.911
p_a #1.0000
10
Comment connaître l’adresse de a ? Addr(a)
p_a #1.001p_a #1.002p_a #1.003
4
00
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { affectation par déréférencement }
a := 10; { affectation }
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { affectation par déréférencement }
a := 10; { affectation }
C’est équivalent !!
Définitions
• Déclaration d’un pointeur vers un byte
var p_a : ^byte;
• Déréférencement d’un pointeur :
p_a^
• Connaître l’adresse d’une variable a
Addr(a); {ou bien }@a;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
begin
p_a^ := 10; { affectation par déréférencement}
end.
ERREUR !!
var p_a : ^byte; {4 octets, lire : pointeur vers a}
p_a^ := 10; { affectation par déréférencement }
ERREUR !!
#0#1#2#3
#4#5
...
#536.870.910#536.870.911
p_a #1.000p_a #1.001p_a #1.002p_a #1.003
Solution
var p_a : ^byte; {4 octets, lire : pointeur vers a}
...
#0#1#2#3
#4#5
...
#536.870.910#536.870.911
p_a #1.000p_a #1.001p_a #1.002p_a #1.003
...
00
00
Solution
var p_a : ^byte; {4 octets, lire : pointeur vers a}
...
New(p_a);
#0#1#2#3
#4#5
...
#536.870.910#536.870.911
p_a #1.000p_a #1.001p_a #1.002p_a #1.003
...
00
00
p_a^
Solution
var p_a : ^byte; {4 octets, lire : pointeur vers a}
...
New(p_a);
p_a^ := 10; { affectation par déréférencement }
#1#2#3
#4#5
...
#536.870.910#536.870.911
p_a #1.000p_a #1.001p_a #1.002p_a #1.003
...
00
00
10p_a^ #0
« p_a pointe vers p_a^ »
Solution
var p_a : ^byte; {4 octets, lire : pointeur vers a}
...
New(p_a);
p_a^ := 10; { affectation par déréférencement }
...
Dispose(p_a); { Libérer la mémoire }
#0#1#2#3
#4#5
...
#536.870.910#536.870.911
p_a #1.000p_a #1.001p_a #1.002p_a #1.003
...
00
00
Aujourd’hui
• Tableaux dynamiques
• Portée
Type : tableau statique(angl. static ARRAY)
Déclaration d’une variable de type tableau
Défintion :
var nom_du_tableau : Array[MinDim..MaxDim] of type ;
Exemple :
var points : array[1..10] of byte;
…
- structure de données la plus connu- structure homogène, chaque élément est du même type de base
- La taille du tableau est fixe
Type : tableau statique(angl. static ARRAY)
Déclaration d’une variable de type tableau statique
var points : array[1..10] of byte;
Affectation :
nom_du_tableau[index] := valeur ;
• Exemples :points[1] := 130;points[2] := 25;…points[10] := 90;
points[11] ----- Erreur !!!points[12] ----- Erreur !!!
…
Organisation de la mémoire
var points : array[1..10] of byte; {10 octets}
#0
points[1] #2000
...
#536.870.910#536.870.911
...
points[3] #2002
points[10] #2009
...
points[2] #2001
...
Organisation de la mémoire
points[1]:=130; points[2]:=25; …
#0
points[1] #2000
...
#536.870.910#536.870.911
...
points[3] #2002
points[10] #2009
...
points[2] #20011302531
90
Organisation de la mémoire
var points : array[1..10] of byte; {10 octets}
#0
...
#536.870.910#536.870.911
...
Occupe de la place successivedans la mémoire
points[1] #2000
...
...
points[3] #2002
points[10] #2009
points[2] #20011302531
90
Organisation de la mémoire
var points : array[1..10] of byte; {10 octets}
#0
...
#536.870.910#536.870.911
points[index] #(2000+index-1)
...
Occupe de la place successivedans la mémoire
points[1] #2000
...
points[3] #2002
points[10] #2009
points[2] #20011302531
90
Organisation de la mémoire
var points : array[1..10] of byte; {10 octets}
...
#536.870.910#536.870.911
...
#0
points[index] #(2000+index-1)
points[1] #2000
...
points[3] #2002
points[10] #2009
points[2] #20011302531
90
Type : tableau statique(angl. static ARRAY)
- structure de données la plus connu
- structure homogène, chaque élément est du même type de base
- occupe de la place successive dans la mémoire
- « random access » = accès aux différentes éléments se fait au coût égal
var points : array[1..10] of byte; {12 octets}
var i : byte;
i := 0;
points = points[1] #2000
...
#536.870.910#536.870.911
points[3] #2002
points[10] #2009
...
points[2] #200131
#0
points[index] #(2000+index-1)
i #2010 0
...
1302531
90
• Un onzième joueur veut se connecter ..
• points[11] ????
Tableaux
• Que faire si on veut agrandir la taille du tableau ?
Solution : Tableaux dynamiques
var points : array of byte; {Tableau dynamique}
SetLength(points, 10); { Allocation de [0..9] ... }SetLength(points, 50); { Allocation de [0..49] ... }...SetLength(points, 0); { Désallocation !!! }
Tableaux
• Que faire si on veut agrandir la taille du tableau ?
Solution : Tableaux dynamiques
var points : array of byte; {Tableau dynamique}
SetLength(points, 10); { Allocation de [0..9] ... }SetLength(points, 50); { Allocation de [0..49] ... }...SetLength(points, 0); { Désallocation !!! }Commence toujours à 0 !!
var points : array of byte; {pointeur 4 octets}
var i : byte;
i := 10;
points[0] := 2;
{ ERREUR !!!! }
...
...
#0
10i #104
points #100points #101points #102points #103
Pointeur : 4 octets
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
...
...
#0
jours[index] #(120+index)
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
120000
• Un onzième jouer ? Un douzième joueur ?
points[10] ? points [11] ?
• Solution :
SetLength(nom_du_tableau_dynamique, taille);
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
jours[index] #(120+index)
...
...
#0
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
120000
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
points[0] := 130;
points[1] := 25;
…
...
...
#0
jours[index] #(120+index)
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
120000
130
25
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
...
SetLength(points, 12);
...
...
#0
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
200000
points[0] #200
points[2] #202
points[11] #211
points[1] #201
...
... ...
Réserver la mémoire 130
25
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
...
SetLength(points, 12);
...
...
#0
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
200000
points[0] #200
points[2] #202
points[11] #211
points[1] #201
...
... ...
Copier la mémoire
130
25
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
...
SetLength(points, 12);
...
...
#0
points[0] #120
points[2] #122
points[9] #129
points[1] #121
10i #104
points #100points #101points #102points #103
200000
points[0] #200
points[2] #202
points[11] #211
points[1] #201
...
... ...
Libérer la mémoire
130
25
SetLength(nom_du_tableau_dynamique, taille);
Complexité : O(n) avec n = taille
SetLength(points, 12);
1. Chercher un endroit dans la mémoire pour 12 octets consécutives
2. Copier toute la mémoire dans le nouvel endroit … O(n) !
3. Libérer la place occupé avant
Type : tableau dynamiques(angl. dynamic ARRAY)
SetLength(nom_du_tableau_dynamique, 0);
1. Libère la place pour la suite du programme
Désallocation
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
...
SetLength(points, 12);
SetLength(points, 0);
...
...
#0
10i #104
points #100points #101points #102points #103
200000
points[0] #200
points[2] #202
points[11] #211
points[1] #201
... ...
Libérer la mémoire
130
25
• La portée :
program portee;
var i : byte;
function somme(n : byte) : byte;var i : byte;begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
program portee;
var i : byte;
function somme(n : byte) : byte;var i : byte;begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
...
...
...
#0
i #100
program portee;
var i : byte;
function somme(n : byte) : byte;var i : byte;begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
...
...
3
...
#0
i #100
n #200i #201
5
program portee;
var i : byte;
function somme(n : byte) : byte;var i : byte;begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
...
...
3
...
#0
i #100
n #200i #201
program portee;
var i : byte;
function somme(n : byte) : byte;var i : byte;begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
...
...
3
...
#0
i #100
n #200i #201 1
program portee;
var i : byte; { Variable globale }
function somme(n : byte) : byte;var i : byte; { Variable locale }begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
program portee;
var i : byte; { Variable globale }
function somme(n : byte) : byte;var i : byte; { Variable locale }begin result := 0; for i := 1 to n do begin result := result + i; end;end;
begin i:=3; WriteLn(somme(5)); WriteLn('i : ', i);
readln;
end.
Appel des fonctions
• Appel par valeur
• Appel par référence
var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
Appel par valeur
var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
Appel par valeur
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
#220#221
...
...
#222
#223...
...
4
var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin #0
a #200 #201
#202
#536.870.910#536.870.911
#203
parametre #220#221
...
...
#222
#223...
...
4
4
Appel par valeur
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
parametre #220#221
...
...
#222
#223...
...
6
4
Appel par valeur var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
#220#221
...
...
#222
#223...
...
4
Appel par valeur var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
#0
#200 #201
#202
#536.870.910#536.870.911
#203
#220#221
...
...
#222
#223...
...Appel par valeur
var a : byte;
procedure ajouter (parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
4
Appel par référencevar a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin
var a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin
Appel par référence
Parametre est un pointeur
Appel par référence
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
...
...
...
...
4
Appel par référencevar a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin
var a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin #0
a #200 #201
#202
#536.870.910#536.870.911
#203
parametre #240parametre #241
...
...
parametre #242
parametre #243
...
...
4
200000
Appel par référence
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
parametre #240parametre #241
...
...
parametre #242
parametre #243
...
...
6
200000
Appel par référencevar a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin
#0
a #200 #201
#202
#536.870.910#536.870.911
#203
#240#241
...
...
#242
#243
...
...
6
Appel par référencevar a : byte;
type t_p_a = ^byte;
procedure ajouter (parametre : t_p_a);begin
WriteLn('parametre^', parametre^);
parametre^ := parametre^ + 2;
WriteLn('parametre^', parametre^);end;
débuta := 4;
WriteLn('a', a);
ajouter(Addr(a));
WriteLn('a', a);fin
Appel par référence (2)var a : byte;
procedure ajouter (var parametre : byte)début
WriteLn(‘parametre’, parametre);
parametre := parametre + 2;
WriteLn(‘parametre’, parametre);fin
débuta := 4;
WriteLn(‘a’, a);
ajouter(a);
WriteLn(‘a’, a);fin
Une autre façon d’appeler une fonctionpar référence qui est moins explicite