Download Algorithmique 1 - Ensiwiki

Transcript
Ensimag 1ère année — Algorithmique 1
Examen 1ère session — Janvier 2009
package FilePrio i s
subtype Elt i s Integer range ...;
f u n c t i o n EstVide return Boolean ;
-- retourne True ssi la file ne contient aucun élément .
procedure Vider ;
-- garantit EstVide = True
procedure Inserer ( X : i n Elt );
-- garantit une nouvelle occurrence de X est insérée dans la file .
procedure DetruireMax ( Max : out Elt );
-- requiert EstVide = False
-- garantit une occurrence de Max est retirée de la file ,
-et Max est >= à tous les éléments restants dans la file .
end FilePrio ;
Figure 2 – Interface de FilePrio
En supposant Elt’First<=3 et 10<=Elt’Last,
on considère la séquence ci-contre.
A l’issue de cette séquence, la variable X vaut
10. La file de priorités contient ici les éléments
suivants : “3” en deux exemplaires, “5” en
quatre exemplaires, et “10” en un exemplaire.
Si
on
fait
ensuite un nouvel appel à
DetruireMax (X), la variable X vaut encore 10,
mais la file ne contient plus l’élément 10. Le
maximum de la file est donc 5 (en quatre exemplaires).
X : Elt ;
begin
...
Vider ;
Inserer (3);
Inserer (10);
Inserer (5);
Inserer (5);
Inserer (10);
Inserer (5);
Inserer (3);
Inserer (5);
DetruireMax ( X );
Figure 3 – Exemple d’utilisation de FilePrio
L’implémentation par tableau utilise les deux variables globales :
NbOcc : array ( Elt ) o f Natural ;
MaxFile : Elt ;
L’invariant satisfait par ces deux variables du paquetage est la conjonction des deux propriétés :
1. si NbOcc = (others => 0) alors MaxFile = Elt’First ;
2. si NbOcc /= (others => 0) alors NbOcc (MaxFile) /= 0 et pour tout I : Elt tel que
NbOcc (I) /= 0, on a I <= MaxFile.
Figure 4 – Variables globales de FilePrio dans implém. par tableau
2008-2009
page : 2/5