Concepts en algorithmique

Implémentés en Pascal

Philippe Quet

Les méthodes de conception des structures de données permettent de résoudre des problèmes particuliers comme l'élaboration d'un questionnaire arborescent pour un système de classification (faune, flore, etc.), ou d'une structure de base pour la représentation des solides dans un système de C.A.O.

Les méthodes utilisées conduisent à s'interroger sur les « objets » fondamentaux qui interviennent dans le problème. Elles peuvent être très rigoureuses, fondées par exemple sur la logique, ou sur l'algèbre comme les « types abstraits algébriques ».

Dans les chapitres 1 et 2 , nous verrons comment spécifier des structures de données, et comment les implémenter dans un langage de programmation particulier comme Pascal. Nous étudierons en même temps le comportement des structures de données modélisé par des opérations abstraites. L'écriture des programmes se rapproche des manières humaines de poser et résoudre les problèmes, par l'élaboration de fonctionnalités de plus en plus abstraites, qui garantissent leur indépendance vis-à-vis de la mise en œuvre de fonctionnalités plus « primitives ».

Dans le chapitre 3, nous étudierons la technique de preuve de programme. Prouver un programme consiste à prouver que la spécification est conforme à l'algorithme.

Commentez

- Titre : Concepts en algorithmique

- Auteur : Philippe Quet

- Parution : 10 septembre 2015

- Mise à jour : 22 octobre 2015

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2015 Philippe Quet. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Implémentation et manipulation de structures algébriques isomorphes à l'ensemble des entiers naturels N muni de lois

- I-A. Propriétés des entiers naturels

- I-B. Conception des primitives

- I-C. Opérations complexes sur les entiers basées sur les primitives

- I-D. Écriture du module de fonctionnalités non primitives sur les entiers

- I-E. Implémentation et manipulation de l'ensemble des mots

- I-E-1. Module de primitives

- I-E-2. Module de fonctionnalités non primitives

- I-F. Implémentation et manipulation de l'ensemble des entiers écrits en base n

- I-F-1. Module de primitives

- I-F-2. Fonctionnalités élaborées

- II. Listes récursives

- II-A. Définition

- II-B. Primitives

- II-C. Implémentation par des pointeurs

- II-D. Fonctionnalités non primitives

- II-E. Chapitres I et II : Conclusion

- III. Preuve de programme

- III-A. Notation

- III-B. Procédure

- III-C. Spécification

- III-D. Algorithme

- III-E. Exemples

- III-F. Égalité de procédures

- III-G. Équivalence des procédures

- III-H. Calculabilité d'un algorithme

- III-I. Prouver une procédure

- III-I-1. Exemple 1 : montrer que Aff est bien spécifiée

- III-I-2. Exemple 2 : montrer que Rang est bien spécifiée

- IV. Remerciements

I - Implémentation et manipulation de structures algébriques isomorphes à l'ensemble des entiers naturels N muni de lois

On souhaite écrire un programme qui effectue des opérations sur les éléments d'un ensemble E ayant les mêmes propriétés que l'ensemble des entiers naturels N. Nous allons démontrer qu'écrire un tel programme revient à implémenter le type des entiers naturels N et à concevoir les opérations qui manipulent ce type. La conception du programme sera facile, car l'ensemble des entiers naturels nous est familier.

C'est l'ensemble « de base », nous connaissons bien ses propriétés. Rappelons que N est l'ensemble des nombres entiers supérieurs ou égal à 0.

I-A - Propriétés des entiers naturels

Nous allons dans un premier temps énoncer les propriétés de N ; c'est ce qui nous servira à créer les primitives opérant sur le type N.

1. Il existe un élément qui est le plus petit élément de N. Nous appellerons cet élément Zéro.
Zéro ϵ N - Zéro est une fonction constante.

2. Il existe une fonction successeur dont la signature est N > N. Successeur(n) est appelé « le successeur de n » :

3. Il existe une fonction booléenne notée Égal qui teste l'égalité de deux entiers.
Sa signature est N x N > booléen.
Égal(n1,n2) a la valeur vrai si n1 et n2 sont égaux.

- a - Successeur(n) <> n (Successeur(n) est différent de n) ;

- b - Zéro n'est le successeur d'aucun nombre.

En résumé : propriétés de N

1. Zéro ϵ N ;

2. il existe une fonction successeur telle que :

- a - Successeur(n) < > n ;

- b - Zéro n'est le successeur d'aucun nombre.

Ces deux axiomes suffisent pour définir l'ensemble N.

Connaissant l'ensemble N et ses propriétés, l'écriture des primitives sera facile.

I-B - Conception des primitives

Le type des entiers naturels TEntier sera implémenté par le type integer (ou longint).

On écrira un module MEntierPrim comportant le type TEntier et les primitives Zéro, Successeur et Égal.

unit MEntier_Prim ;

interface

type TEntier = integer ;
function Zero : TEntier ;
function Successeur( n : TEntier ) : TEntier ;
function Egal ( n1 , n2 : TEntier ) : boolean ;

implementation

function Zero : TEntier ;
begin
Zero : = 0 ;
end ;

function Successeur ( n : TEntier ) : TEntier ;
begin
Successeur : = n + 1 ;
end ;

function Egal  ( n1 , n2 : TEntier ) : boolean ;
begin
Egal : = ( n1 = n2 ) ;
end;

end.

I-C - Opérations complexes sur les entiers basées sur les primitives

Pour effectuer des calculs sur les entiers, nous aurons besoin d'opérations telles que la somme, la soustraction (différence), le produit, la division (s'il s'agit d'entiers, on écrira une procédure qui renverra le quotient et le reste) et pourquoi pas d'opérations comme le PGCD, le PPCM…

Pour écrire ces fonctions et procédures, on utilisera uniquement le type TEntier et les primitives Zéro, Successeur et Égal.

En ce qui concerne les entiers, pourquoi procéder ainsi, alors que n'importe quel langage de programmation comporte déjà les fonctions usuelles : + - * / sinus logarithme…

Imaginons que l'on veuille manipuler les éléments d'un ensemble qui possède les mêmes propriétés que l'ensemble des entiers naturels : par exemple, les mots d'un dictionnaire. Les mots sont mis dans un certain ordre dans le dictionnaire. L'ensemble des mots susceptibles d'appartenir au dictionnaire est totalement ordonné par une relation d'ordre R. Soit ordre(m) le rang d'un mot m dans le dictionnaire (le mot est à la n-ième place) : ordre(m1) < ordre(m2)  m1 R m2.

Le « plus petit élément » est le mot « a » (le mot de rang 1).

Chaque mot a un successeur dans le dictionnaire. Le successeur d'un mot m est différent de m.

Le mot « a » n'est le successeur d'aucun mot.

On mettra en œuvre la même conception. On se servira du même module de primitives ; il suffira de redéfinir le type des éléments de l'ensemble ( par exemple un type de mots ou d'une autre entité mathématique) et de réécrire le corps des primitives : Zéro (plus petit élément), Successeur et Égal.

Puis on concevra un module de fonctionnalités utilisant le module des primitives (dans le cas des entiers, il s'agissait des opérations somme, soustraction…). Les fonctionnalités non primitives sont des fonctionnalités qui utilisent uniquement les primitives et le type des éléments de l'ensemble.

Dans ce sens, leur description algorithmique est indépendante de la description algorithmique des primitives. Nous n'avons pas besoin de savoir comment sont conçues les primitives pour écrire l'algorithme des fonctionnalités non primitives.

Et pourquoi ne pas concevoir un deuxième module de fonctionnalités non primitives qui utilise le premier ?

Par exemple, avec les entiers, on peut créer un module de fonctions calculant le PGCD, le PPCM, le modulo… Ces fonctionnalités se serviront uniquement des fonctionnalités somme, soustraction… du premier module de fonctionnalités non primitives. Ainsi on peut créer des modules comportant des fonctionnalités de plus en plus élaborées.

I-D - Écriture du module de fonctionnalités non primitives sur les entiers

Le module de fonctionnalités non primitives MEntier comprend les fonctions prédécesseur, somme, différence, produit, le prédicat EstAvant (n1 est avant n2) et la procédure division qui retourne le quotient et le reste de la division euclidienne de a (dividende) par b (diviseur).

unit MEntier ;

interface

uses MEntier_Prim ;

function Entier_Predecesseur ( n : TEntier ) : TEntier ;
{ le prédécesseur de n différent de Zéro ou }
{ l'entier dont le successeur est n }
{ TEntier > TEntier }
{ n < > Zero }

function  Entier_EstAvant ( n,m : TEntier ) : boolean ;
{ est égale à vrai si n est avant m, }
{ est égale à faux si m est avant n }
{ TEntier x TEntier > booléen }

function Entier_Somme( n,m : TEntier ) : TEntier ;
{ le m-ième successeur de n }
{ TEntier x TEntier > TEntier }

function Entier_Difference ( n,m : TEntier ) : TEntier ;
{ le m-ième prédécesseur de n, }
{ est égal à Zero si m est après n }
{ TEntier x TEntier > TEntier }

function Entier_Produit ( n,m : TEntier ) : TEntier ;
{ le produit de n par m }
{ TEntier x TEntier > TEntier }

procedure Entier_Division ( a,b : TEntier ; var quotient,reste : TEntier ) ;
{ retourne le quotient et le reste de la division }
{ euclidienne de a par b }
{ TEntier x TEntier > TEntier x TEntier }

implementation

function Entier_Predecesseur ( n : TEntier ) : TEntier ;
var i : TEntier ;
begin
i : = Zero ;
while not ( Egal ( Successeur ( i ) , n ) ) do
i : = Successeur ( i ) ;
Entier_Predecesseur : = i ;
end;

function  Entier_EstAvant ( n,m : TEntier ) : boolean ;
begin
if  Egal ( n,m ) then
Entier_EstAvant : = false
else
if  Egal ( n , Zero ) then
Entier_EstAvant : = true
else if  Egal ( m , Zero ) then
Entier_EstAvant : = false
else
Entier_EstAvant : = Entier_EstAvant ( Entier_Predecesseur ( n ) ,  Entier_Predecesseur( m ) ) ;
end ;

function  Entier_Somme ( n,m : TEntier ) : TEntier ;
begin
if Egal ( n , Zero ) then
Entier_Somme : = m
else
Entier_Somme : =  Entier_Somme ( Entier_Predecesseur ( n ) , Successeur ( m ) ) ;
end;

function Entier_Difference ( n,m : TEntier ) : TEntier ;
var  i,d : Tentier;
begin
if Entier_EstAvant ( n,m ) then
Entier_Difference : = Zero
else
begin
i : = Zero ;
d : = n ;
while  not ( Egal ( i , m ) do
begin
d : = Entier_Predecesseur ( d ) ;
i : = Successeur ( i ) ;
end ;
Entier_Difference : = d ;
end ;
end;

function  Entier_Produit ( n,m : TEntier ) : TEntier ;
var i,p : TEntier ;
begin
i : = Zero ;
p : = Zero ;
while not ( Egal ( i , m ) ) do
begin
p : = Entier_Somme ( p , n ) ;
i : = Successeur ( i ) ;
end ;
Entier_Produit : = p ;
end ;

procedure Entier_Division ( a,b : TEntier ; var quotient,reste : TEntier ) ;
begin
quotient : = Zero ;
while Entier_EstAvant ( Entier_Produit ( b , quotient ) , a ) do
quotient : = Successeur ( quotient ) ;
quotient : = Entier_Predecesseur ( quotient ) ;
reste : = Entier_Difference ( a , Entier_Produit ( b , quotient ) ) ;
end ;

end.

I-E - Implémentation et manipulation de l'ensemble des mots

I-E-1 - Module de primitives

unit MMot_Prim ;

interface

type  TMot : String ;

function  PremierMot : TMot ;

function  Successeur ( m : TMot ) : TMot ;

function  Egal ( m1 , m2 : TMot ) : boolean ;

implementation

function  PremierMot : TMot ;
begin
PremierMot : = ‘a' ;
end ;

function  Successeur ( m : TMot ) : TMot ;

function  Succ_Lettre ( c : string ) : string;
begin
if  c = ‘z'  then
Succ_Lettre : = ‘a'
else
Succ_Lettre : = chr ( ord ( c ) + 1 ) ;
end ;

function  Rang ( l , i : integer ) : integer ;
{ l  est la longueur  du  mot }
begin
Rang : = l - i + 1 ;
end ;

function  Mot_Jusqua ( m : TMot;  r : integer ) : TMot ;
begin
Mot_Jusqua : = substring ( m , 1 , r ) ;
end ;

var i , r , l : integer ;  mt : TMot ;
begin
i : = 1 ;
l : = length ( m ) ;
r : = Rang ( l , i ) ;
if  l = 25  then
begin
if  m[r] = ‘z'  then
begin
while  m[r] = ‘z' do
begin
i : = i + 1 ;
r : = Rang ( l , i ) ;
end ;
mt : = Mot_Jusqua ( m , r ) ;
mt[r] : = Succ_Lettre ( mt[r] ) ;
Successeur : = mt ;
end ;
else
begin
m[r] : = Succ_Lettre ( m[r] ) ;
Successeur : = m ;
end    ;
end ;
else
Successeur : = m + ‘a' ;
end ;

function  Egal ( m1 , m2 : TMot ) : boolean ;
begin
Egal : = ( m1 = m2 ) ;
end ;

end.

Commentaire : le plus petit élément est le mot « a », pour la fonction successeur : le plus long mot est « anticonstitutionnellement », qui a 25 lettres ; on conviendra que les mots ont au plus 25 lettres ; si le mot se termine par ‘ zzz …. ‘ : exemple : si m = ‘ abzzz…z' (mot de 25 lettres), le successeur est ‘ ac ' sinon si m = ‘ abc ‘ le successeur est ‘ abca '. Pour la fonction Égal : l'opérateur ‘ = ‘ du Pascal permet de déterminer si deux mots sont égaux.

I-E-2 - Module de fonctionnalités non primitives

L'ensemble des entiers naturels et l'ensemble des mots ont les mêmes propriétés : il existe un « plus petit mot » qui n'est le successeur d'aucun mot et chaque mot m a un successeur différent de m.

On peut donc effectuer des opérations sur les mots avec les fonctionnalités non primitives que nous avons conçues pour l'ensemble des entiers. Nous pouvons nous servir du module MEntier (fonctionnalités non primitives des entiers), car ces fonctionnalités garantissent leur indépendance vis-à-vis de la mise en œuvre des primitives.

unit MMot ;

interface

uses MMot_Prim ;

function Mot_Predecesseur ( n : TMot ) : TMot ;
{ le prédécesseur de n différent de PremierMot ou }
{ le mot dont le successeur est n }
{ TMot > TMot }
{ n < > PremierMot }

function  Mot_EstAvant ( n,m : TMot ) : boolean ;
{ est égale à vrai si n est avant m, }
{ est égale à faux si m est avant n }
{ TMot x TMot > booléen }

function Mot_Somme( n,m : TMot ) : TMot ;
{ le m-ième successeur de n }
{ TMot x TMot > TMot }

function Mot_Difference ( n,m : TMot ) : TMot ;
{ le m-ième prédécesseur de n , }
{ est égal à PremierMot si m est après n }
{ TMot x TMot > TMot }

function Mot_Produit ( n,m : TMot ) : TMot ;
{ le produit de n par m }
{ TMot x TMot > TMot }

procedure Mot_Division ( a,b : TMot ; var quotient,reste : TMot ) ;
{ retourne le quotient et le reste de la division }
{ euclidienne de a par b }
{ TMot x TMot > TMot x TMot }

implementation

function Mot_Predecesseur ( n : TMot ) : TMot ;var i : TMot ;
begin
i : = PremierMot ;
while not ( Egal ( Successeur ( i ) , n ) ) do
i : = Successeur ( i ) ;
Mot_Predecesseur : = i ;
end;

function  Mot_EstAvant ( n,m : TMot ) : boolean ;
begin
if  Egal ( n,m ) then
Mot_EstAvant : = false
else
if  Egal ( n , PremierMot ) then
Mot_EstAvant : = true
else
if  Egal ( m , PremierMot ) then
Mot_EstAvant : = false
else
Mot_EstAvant : = Mot_EstAvant ( Mot_Predecesseur ( n ) ,  Mot_Predecesseur( m ) ) ;
end ;

function  Mot_Somme ( n,m : TMot ) : TMot ;
begin
if  Egal ( n , PremierMot ) then
Mot_Somme : = m
else
Mot_Somme : =  Mot_Somme ( Mot_Predecesseur ( n ) , Successeur ( m ) ) ;
end;

function Mot_Difference ( n,m : TMot ) : TMot ;
var  i,d : Tmot;
begin
if Mot_EstAvant ( n,m ) then
Mot_Difference : = PremierMot
else
begin
i : = PremierMot ;
d : = n ;
while  not ( Egal ( i , m ) do
begin
d : = Mot_Predecesseur ( d ) ;
i : = Successeur ( i ) ;
end ;
Mot_Difference : = d ;
end ;
end;

function  Mot_Produit ( n,m : TMot ) : TMot ;
var i,p : TMot ;
begin
i : = PremierMot ;
p : = PremierMot ;
while not ( Egal ( i , m ) ) do
begin
p : = Mot_Somme ( p , n ) ;
i : = Successeur ( i ) ;
end ;
Mot_Produit : = p ;
end ;

procedure Mot_Division ( a, b : TMot ; var quotient,reste : TMot ) ;
begin
quotient : = PremierMot ;
while Mot_EstAvant ( Mot_Produit ( b , quotient ) , a ) do
quotient : = Successeur ( quotient ) ;
quotient : = Mot_Predecesseur ( quotient ) ;
reste : = Mot_Difference ( a , Mot_Produit ( b , quotient ) ) ;
end ;

end.

Commentaire : la structure algébrique des mots munie des lois « somme, différence, produit, division » est isomorphe à la structure des entiers naturels munie des mêmes lois, car l'ensemble des entiers naturels et l'ensemble des mots ont les mêmes propriétés : « plus petit élément » et « successeur ». Ainsi on peut effectuer une division euclidienne avec les mots, qui retournera les deux mots quotient et reste.

Les primitives « Zéro » et « Successeur » servent à construire une structure d'entiers, c'est-à-dire une structure dont les éléments sont totalement ordonnés par une relation d'ordre. Dès que l'on connaîtra un ensemble ayant la structure d'entiers, on pourra lui associer des fonctionnalités élaborées conçues uniquement à partir du type des éléments de l'ensemble et des primitives « Zéro », « Successeur » et « Égal ». Ces calculs seront fondés sur la structure construite par les primitives, en l'occurrence une relation d'ordre.

Calculer un produit ou une division de mots n'a pas beaucoup de sens, mais nous pouvons par exemple implémenter un type de nombres écrits en base 2 , 5 ou hexadécimal, les trois primitives et manipuler cet ensemble avec les fonctionnalités élaborées.

I-F - Implémentation et manipulation de l'ensemble des entiers écrits en base n

I-F-1 - Module de primitives

unit MEntier_Base_n_Prim ;

interface

type    TEntier_Base_n = record
base_n : integer ;
entier : string ;
end ;

function Zero ( base : integer ) :  TEntier_Base_n ;

function Successeur ( x : TEntier_Base_n ) : TEntier_Base_n ;

function Egal ( x1 , x2 :  TEntier_Base_n ) : boolean ;

implementation

function Zero ( base : integer ) :  TEntier_Base_n ;
var d :  TEntier_Base_n ;
begin
d . base_n : = base ;
d . entier : = ' 0 ' ;
Zero : = d ;
end ;

function Successeur ( x : TEntier_Base_n ) : TEntier_Base_n ;
var   r , base : integer ;  fini : boolean ;  d :  TEntier_Base_n ;
begin
r : = length ( x . entier )  ;
base : = x . base_n - 1 ;
fini : = false ;
while not fini do
begin
if x . entier [ r ] = base then
if r = 1 then
begin
x . entier [ r ] : = ' 0 ' ;
x . entier : = '1' + x . entier ;
fini : = true ;
end
else
begin
x . entier [ r ] : = ' 0 ' ;
r  : = r - 1  ;
fini : = false ;
end
else
begin
x . entier [ r ] : = chr ( ord ( x . entier [ r ] ) + 1 ) ;
fini : = true ;
end ;
end ;
d . base_n : = x . base_n ;
d . entier : = x . entier ;
Successeur : = d ;
end ;

function Egal ( x1 , x2 : TEntier_Base_n ) : boolean ;
begin
Egal : = (  ( x1 . base_n = x2 . base_n ) and ( x1 . entier = x2 . entier ) ) ;
end ;

Après avoir implémenté un ensemble d'entiers représentés en base n, nous pouvons manipuler les éléments de cet ensemble avec le même module de fonctionnalités élaborées (opérations d'arithmétique).

_Predecesseur
_EstAvant
_Somme
_Difference
_Produit
_Division

I-F-2 - Fonctionnalités élaborées

Ajoutons maintenant de nouvelles fonctions à ce module ; voyons comment les primitives permettent la conversion des bases, en d'autres termes la conversion d'un entier représenté en base n en un entier représenté en base m.

function Entier_Base_n_Converti ( x : TEntier_Base_n ; base : integer ) : TEntier_Base_n ;
{ entier  x  converti en une nouvelle base }
{ TEntier_Base_n X integer > TEntier_Base_n }

var    base_de_x : integer ;
i , x_converti :  TEntier_Base_n ;

begin
base_de_x : = x . base_n ;
i  : = Zero ( base_de_x ) ;
x_converti  : = Zero ( base )  ;
while not ( Egal ( i , x ) ) do
begin
x_converti : = Successeur (  x_converti ) ;
i : = Successeur ( i ) ;
end ;
Entier_Base_n_Converti : = x_converti ;
end ;

Là aussi, cette fonction utilise uniquement le type TEntier_Base_n et les trois primitives.

Nous allons maintenant créer les fonctions Modulo, PGCD, PPCM.

function Entier_Modulo ( a , m : TEntier ) : TEntier ;
{ a modulo m ou bien :  le reste de la division euclidienne de a par m }
{ TEntier X TEntier > TEntier }
{ m est inférieur ou égal à a }

{ L'algorithme est évident : nous avons déjà écrit la procédure de division euclidienne }

function Entier_Modulo ( a , m : TEntier ) : TEntier ;
var quotient , reste : TEntier ;
begin
Entier_Division ( a , m , quotient , reste ) ;
Entier_Modulo : = reste ;
end ;

function Entier_PGCD ( a , b : TEntier ) : TEntier ;
{ le PGCD ( plus grand commun diviseur ) de a et b }
{ TEntier X TEntier > TEntier }

Nous allons nous servir de la fonction Entier_Modulo : a est divisible par b si Entier_Modulo (a, b) = 0.

Cherchons lequel de a et b est le plus grand. Si a est avant b, par exemple, il suffit de chercher le plus grand entier inférieur ou égal à a qui soit un diviseur de a et de b.

var d : TEntier ;
begin
if  Entier_EstAvant ( a , b ) then
d : = a
else
d : = b ;
while not (  ( Entier_Modulo ( a , d ) = 0 ) and ( Entier_Modulo ( b , d ) = 0 )  )   do
d : = Entier_Predecesseur ( d ) ;
Entier_PGCD : = d ;
end ;

Remarque : le PGCD de a et b est 1 si a et b sont premiers entre eux.

function Entier_PPCM ( a , b : TEntier ) : TEntier ;
{ le PPCM ( plus petit commun multiple ) de a et b }
{ TEntier X TEntier > TEntier }

Cherchons lequel de a et b est le plus grand. Si a est avant b, par exemple, il suffit de chercher le plus petit entier supérieur ou égal à b qui soit un multiple de a et de b.

var d : TEntier ;
begin
if  Entier_EstAvant ( a , b ) then
d : = b
else
d : = a ;
while not (  ( Entier_Modulo ( a , d ) = 0 ) and ( Entier_Modulo ( b , d ) = 0 )  ) do
d : = Successeur ( d ) ;
Entier_PPCM : = d ;
end ;

II - Listes récursives

II-A - Définition

Une liste récursive est :

- soit une liste vide notée < > ;

- soit un doublet formé d'un objet et d'une liste récursive, qu'on notera < e lr >.

Dans ce dernier cas, l'objet e est appelé le premier élément de la liste, et la liste lr la liste restante, ou le reste, ou la suite de la liste.

On simplifiera les notations en remplaçant < e1 < e2 < e3 < > > > > par < e1 e2 e3 >.

Le reste de la liste < e1 e2 e3 > est donc la liste < e2 e3 >, abréviation de < e2 < e3 < > > >.

On conviendra que les éléments de la liste sont des valeurs du type TData quelconque de données, et on notera TListeRec le type des listes récursives de données.

II-B - Primitives

Pour manipuler des listes, on a besoin de deux constructeurs : un pour la liste vide, et un pour un doublet :

function ListeRec_Vide : TListeRec
{ la liste vide (de données) < > }
{ => TListeRec : => < > }

function ListeRec_Construire(e :TData; lr :TListeRec) : TListeRec
{ la liste non vide - le doublet <e lr > - dont le premier élément est e et le reste lr }
{ TData X TListeRec => TListeRec : e , lr => < e lr > }

On a également besoin d'un prédicat qui permet de reconnaître une liste vide :

function ListeRec_EstVide(l :TListeRec) : boolean
{ l est la liste vide }
{TListeRec => boolean }

Il faut également disposer de « sélecteurs » permettant de déterminer les deux composants d'une liste non vide :

function ListeRec_Premier(l:TListeRec) : TData
{ le premier élément d'une liste non vide l }
{ TListeRec => TData : < e lr > => e }
{ domaine : l est non vide }

function ListeRec_Reste(l :TListeRec) : TListeRec
{ le reste d'une liste non vide l }
{ TListeRec => TListeRec : < e lr > => lr }
{ domaine : l est non vide }

Enfin, il faut disposer de transformations qui permettent de modifier une liste :

procedure ListeRec_PremierA(d :TData ; var l :TListeRec) ;
{ affecter d comme premier élément d'une liste non vide l }
{ TData X TListeRec => TListeRec : d , < e lr  > => < d lr > }
{ domaine : l est non vide }

Procedure ListeRec_ResteA(lr :TListeRec ; var l :TListeRec) ;
{ affecter lr comme reste d'une liste non vide l }
{ TListeRec X TListeRec => TListeRec : lr , < e r > => < e lr > }
{ domaine : l est non vide }

II-C - Implémentation par des pointeurs

L'implémentation « naturelle » serait de définir le type TListeRec comme une réunion :

TListeRec = record case vide : boolean of
true : ( ) ;
false : ( element : TData; reste : TListeRec );
end;

Malheureusement cette définition n'est pas « calculable » : en effet, le calcul de la taille t du type TlisteRec donnerait l'équation suivante : t = 1 + tailleDe TData + t, qui n'admet pas de solution.

Le moyen de résoudre cette difficulté est d'identifier une liste à un pointeur sur (une référence à) un doublet.

Dans ces conditions, une liste vide serait identifiée à l'adresse Nil, et la taille de TListeRec devient calculable.

Autrement dit : une liste vide est identifiée à Nil et une liste non vide à l'adresse du doublet qu'elle définit.

Soit TPtrDoublet=TListeRec le type pointeur sur TDoublet, où TDoublet est le type :

Record premier : TData ; reste : TListeRec end

Dans ces conditions, la taille du type TListeRec est égale à la taille d'un pointeur (en général quatre octets), et la taille d'un doublet est égale à TailleDe TData + TailleDe TListeRec

Type    TPtrDoublet = ^ TDoublet ;
TListeRec = TPtrDoublet;
TDoublet = Record
premier : TData ;
reste : TListeRec ;
end ;

function  ListeRec_Vide : TListeRec ;
begin
ListeRec_Vide : = nil
end ;

function ListeRec_EstVide( l : TListeRec) : boolean ;
begin
ListeRec_EstVide : = ( l = nil ) ;
end;

function  ListeRec_Construire ( elt : TData; lr : TListeRec ) : TListeRec;
var    PtrDoublet : TPtrDoublet;
begin
new(PtrDoublet);
PtrDoublet^.premier : = elt ;
PtrDoublet^.reste : = lr ;
ListeRec_Construire : = PtrDoublet ;
end;

function ListeRec_Premier ( l : TListeRec ) : TData;
begin
ListeRec_Premier : = l^.premier;
end;

function ListeRec_Reste ( l : TListeRec ) : TListeRec;
begin
ListeRec_Reste : = l^.reste;
end;

procedure ListeRec_PremierA ( d : TData ; var l : TListeRec ) ;
begin
l^.premier : = d ;
end;

procedure ListeRec_ResteA ( lr : TListeRec; var l : TListeRec ) ;
begin
l^.reste : = lr;
end;

II-D - Fonctionnalités non primitives

Les fonctionnalités non primitives sont des fonctionnalités qui utilisent uniquement les primitives et le type TListeRec. Dans ce sens, leur description algorithmique est indépendante de la description algorithmique des primitives.

Avec les listes récursives, on cherche toujours à trouver une description récursive de l'algorithme d'une procédure Proc non primitive, en terme de liste vide, de premier élément, de reste et de la procédure Proc elle-même. En général, c'est sur le reste de la liste que la procédure Proc sera appelée dans l'algorithme.

Voyons deux exemples simples avant de construire les fonctionnalités d'ajout et de suppression :

function  ListeRec_LeNeme ( n : integer ; l : TListeRec ) : TData;
{ le nème élément d'une liste l }
{ Integer X TListeRec => TData }
{ domaine : 1<=n<=longueur de l }
begin
if n=1 then
ListeRec_LeNeme := ListeRec_Premier(l)
else
ListeRec_LeNeme :=  ListeRec_LeNeme ( n-1, ListeRec_Reste(l))
end;

Commentaire : l'algorithme est clair : ou bien n = 1 (et par hypothèse l contient au moins un élément) et c'est le premier élément, ou bien n > 1 (et <= à longueur de l) et alors le n‑ième élément de l est le (n-1)ième du reste.

function ListeRec_Longueur(l : TListeRec) : Integer ;
{ la longueur de l }
{ TListeRec => Integer }

function longueurIter( n :Integer ; l :TListeRec):Integer;
{ ajouter à n la longueur de l }
begin
if ListeRec_EstVide(l) then
longueurIter :=n
else
longueurIter := longueurIter(n+1, ListeRec_Reste(l))
end ;
begin
ListeRec_Longueur := longueurIter(0,l)
end ;

Commentaire : on aurait pu écrire l'algorithme plus simplement : si l est vide c'est 0, sinon c'est 1 + la longueur du reste. Avec l'algorithme décrit dans l'exemple, la fonction ListeRec_Longueur n'est pas elle-même récursive. Elle fait appel à une fonction récursive et de ce fait l'est indirectement. Cependant la fonction longueurIter est « terminalement » récursive, et donc décrit un processus itératif.

procedure ListeRec_InsererAvant(d :TData ; n :Integer ; var l : TListeRec  );
{ inserer d avant le nème élément de l }
{ TData X Integer X TListeRec => TListeRec   }
{ 1<=n<=longueur(l)+1 }
var lt: TListeRec  ;
begin
if ListeRec_EstVide(l) or (n=1)
then l :=ListeRec_Construire(d,l)
else begin
lt :=ListeRec_Reste(l) ;
ListeRec_InsererAvant(d, n-1, lt) ;
ListeRec_ResteA(lt,l)
end ;
end ;

Commentaire : si la liste est vide ou s'il faut insérer en tête, l est un doublet dont l'élément est d et le reste l.

Sinon on insère d avant le (n-1)ième élément du reste de l.

On utilise lt puisque ListeRec_InsererAvant(d, n-1, ListeRec_Reste(l)) n'est syntaxiquement pas correct.

procedure  ListeRec_SuppPrem ( d :TData ; var l : TListeRec ) ;
{ supprimer de l la première occurrence de d  }
{ TData X TListeRec => TListeRec }
var lt : TListeRec ;
begin
if not ListeRec_EstVide( l ) then
begin
if Data_Identique ( d, ListeRec_Premier ( l )) then
begin
lt := l;
l := ListeRec_Reste ( l );
dispose ( lt) ;
end
else
begin
lt :=  ListeRec_Reste ( l );
ListeRec_SuppPrem( d, lt);
ListeRec_ResteA( lt , l );
end;
end;
end;

Commentaire : le prédicat Data_Identique est une fonctionnalité du type TData qui permet de comparer deux données.

On remarque l'utilisation d'une liste « de travail » pour dans un cas permettre de rendre le premier Doublet au manager de la mémoire (avec la procédure Dispose), et dans le deuxième cas de pouvoir appeler récursivement la procédure en passant, comme il faut, un identificateur comme paramètre : l'instruction ListeRec_SuppPrem( d, ListeRec_Reste( l )) n'est en effet pas valide.

II-E - Chapitres I et II : Conclusion

Le terme structure de donnéesdésigne une composition de données unies par une même sémantique.

Nous avons implémenté une structure de données en définissant le type des données.

Dans le cas des entiers, il s'agissait d'un type simple (integer) ; les listes ont été implémentées par des pointeurs de manière récursive : « une liste est un doublet formé d'un objet et d'une liste ».

Puis, nous avons spécifié et créé des primitives pour opérer sur la structure de données.

La mise en œuvre des primitives se fait conformément aux propriétés de la structure de données.

Enfin nous avons conçu un module de fonctionnalités élaborées qui utilisent uniquement les primitives, pour effectuer la résolution de problèmes d'arithmétique en ce qui concerne les entiers ; pour les listes, des opérations de calcul de la longueur d'une liste, de recherche d'un élément, d'ajout et de suppression d'un élément…

Les fonctionnalités élaborées doivent garantir leur indépendance vis-à-vis de la mise en œuvre des primitives. Leur description algorithmique est indépendante de la description algorithmique des primitives.

Supposons que deux structures A et B aient strictement les mêmes propriétés (on peut les définir par les mêmes axiomes). On peut concevoir pour l'une et l'autre exactement les mêmes modules de fonctionnalités élaborées (non primitives), après avoir implémenté A et B et écrit le programme complet pour la structure A, afin d'écrire le programme travaillant sur la structure B, il suffira de concevoir convenablement l'algorithme des primitives qui opèrent sur la structure B. C'est ce que nous avons démontré en concevant le programme qui traite l'ensemble des mots (isomorphe à l'ensemble des entiers).

En procédant comme nous l'avons fait, on passe par différentes étapes, du langage informatique au langage humain (le français).

Utilisateur

Français, spécification du problème

^

Cogniticien

Mathématiques, Logique

Logicien

Domaine de l'intelligence artificielle

Informaticien

Mise en équation du problème

Conception des structures de données

Informaticien

Algorithmique : description ordonnée du procédé de résolution

Informaticien

Programmation : codage de l' algorithme dans un langage de programmation

Ordinateur

Programme codé dans le langage de l'ordinateur (langage machine) et chargé en mémoire

III - Preuve de programme

III-A - Notation

Si T est un type, ValeurDe (T) est l'ensemble de toutes les données de type T implémentables par la machine utilisée. On confondra souvent, dans la suite, T avec ValeurDe (T).

III-B - Procédure

Une procédure P sera représentée par le quadruplet (S, D, T, A) où :

- S la spécification (voir plus loin) ;

- D est le domaine, c'est-à-dire l'ensemble des valeurs du domaine de la signature T, pour lesquelles la procédure est applicable. Le domaine de P est toujours inclus dans le domaine de T, mais pas toujours identique ;

- T (comme type) la signature, et A l'algorithme.

On conviendra que l'identificateur de la procédure est également P.

On note que D, S et T font partie de l'interface (déclaration publique) alors que A fait partie de l'implémentation (à partir de fonctionnalités « plus primitives »).

III-C - Spécification

La spécification S est un énoncé paramétré par D : elle contient un paramètre d dont les valeurs sont les éléments de D.

On conviendra que :

- si P est un prédicat, S est une proposition ;

- si P est une fonction, S spécifie un objet ;

- si P est une commande (par définition, l'application de P modifie l'état de la machine ou provoque un « effet de bord » (affichage à l'écran, impression, exportation de données…), ou bien les deux) S décrit sans ambiguïté une modification de l'état de la machine, et/ou un effet de bord.

C'est le point délicat de la preuve de programme : « sans ambiguïté une modification de l'état de la machine, et/ou un effet de bord » n'a malheureusement pas toujours un sens très précis, dans le modèle des machines que nous utilisons implicitement.

III-D - Algorithme

Appliquer une procédure P à un élément de son domaine D consiste à appliquer la suite des instructions de A à d ; on note A(d) ou quelquefois, par abus de langage, P(d), le résultat de l'application de A à d :

- si P est un prédicat, A(d) est un booléen ;

- si P est une fonction, A(d) est un élément du codomaine de T ;

- si P est une commande, A(d) est une modification ou un effet de bord.

III-E - Exemples

Aff = (« Afficher à l'écran tous les éléments d'une liste l »,

TListe ,

l : TListe => ,

« si l est vide

ne rien faire

sinonChoseAfficher ( ListePremier ( l ) )

Aff ( ListeReste ( l ) ) »)

où ChoseAfficher = ( « Afficher à l'écran la chose ch »,

ch : TChose ,

TChose => ,

… )

ListePremier = (« Le premier élément de la liste non vide l »,

l : l est une liste de TListe non vide ,

TListe => TChose ,

… )

ListeReste = (« Le reste de la liste non vide l » ;

l : l est une liste de TListe non vide ,

TListe => TListe ,

… )

Rang = («  Le rang de la première occurrence de la chose ch dans la liste l,
ou -1 si ch n'est pas dans la liste »,

l , ch : TListe x TChose

TListe x TChose => Entier ,

« au cas ou

: ( l est vide ) retourner -1

: ( ChoseEgale ( ch , ListePremier ( l ))) retourner 1

sinon n <= Rang ( ListeReste ( l ) , ch )

si n = -1 retourner -1

sinon retourner n+1

fin de cas »)

III-F - Égalité de procédures

C'est l'égalité des quadruplets : P = (S, D, T, A) est égale à P' = (S', D', T', A') - on note P = P' - ssi S = S' , D = D' , T = T' et A = A'.

III-G - Équivalence des procédures

C'est « l'équivalence des algorithmes » : P = (S, D, T, A) est équivalent à P' = (S', D', T', A') - on note P ≈ P' - ssi S ≈ S' , D ≈ D' , T ≈ T' et l'application de P à tout élément d de D produit le même résultat que celle de P' à d.

Encore une fois, si P est une commande, l'expression « produit le même résultat que » n'a pas toujours un sens très précis.

III-H - Calculabilité d'un algorithme

Un algorithme est calculable si chacune de ses procédures est appliquée à un argument de son domaine.

On pourrait imposer une condition supplémentaire : que l'exécution de l'algorithme se termine après un nombre fini d'instructions.

III-I - Prouver une procédure

Définition : la procédure P est prouvée ssi :

- ( p ) toutes les procédures de A, autres que P sont prouvées (P est prouvable) ;

- ( c ) pour tout d de D, A est calculable (P est calculable) ;

- ( s ) pour tout d de D, P(d) est décrit par S(d) (P est bien spécifié) :

- si P est un prédicat, S(d) est vrai si et seulement si P(d) est vrai ;

- si P est une fonction, l'objet P(d) est spécifié par S(d) ;

- si P est une commande à effet de bord, S(d) doit décrire l'effet de bord obtenu par application de P à d ;

- si P est une commande qui modifie l'état du système, S(d) doit décrire la modification apportée au système après application de P à d.

Dire que « P est bien spécifié » signifie que la spécification est conforme à l'algorithme.

Prouver une procédure consiste à démontrer que P est prouvé.

Il n'y a pas de difficultés particulières à montrer qu'un algorithme est prouvable quand les procédures qui le composent sont elles-mêmes prouvables.

La preuve qu'une procédure est bien spécifiée est généralement beaucoup plus difficile, en particulier quand il s'agit de commandes.

Cependant, lorsque la procédure est rédigée récursivement, on dispose d'un outil qui généralement fait bien l'affaire : les techniques de preuve par récurrence.

La récursion est en effet implicitement associée à une partition de D : Di, Di+1, …

Si on note Pn la restriction de P à DiU…UDn (Pn = (S, DiU…UDn, T, A)) , montrer que P est bien spécifié pour tout d de D est équivalent à montrer que Pn est bien spécifiée pour tout n ≥ i.

Ce qu'on peut faire par récurrence :

1. (Valeur initiale) On vérifie que Pi est bien spécifiée ;

2. (Induction) On démontre que si Pk est bien spécifiée pour i ≤ k ≤ n alors Pn+1 est bien spécifiée.

III-I-1 - Exemple 1 : montrer que Aff est bien spécifiée

( h ) Nous supposerons ( p ) et ( c )

D = TListe. On partitionne D selon la relation d'équivalence Lg : Lg ( l , l' ) ssi l et l' ont même longueur. Dk est l'ensemble des listes de TListe de longueur k ; D_0 , D_1, … Dk…

forment une partition de D.

Par définition , Affn est la restriction de Aff aux listes de longueur ≤ n.

1. Vérifions que Aff_0 est bien spécifiée ; il faut montrer que si on applique A à une liste l de longueur 0 , le résultat est bien décrit par S(l) :
S(l) est l'énoncé « Afficher à l'écran tous les éléments d'une liste vide l »
Appliquons A à l : comme la liste est vide aucune instruction n'est exécutée : A(l) ne fait rien. Si on considère que « Afficher à l'écran tous les éléments d'une liste vide l »
( S(l) ) c'est ne rien faire ( A(l) ) , Aff_0 est bien spécifiée.

2. En faisant l'hypothèse que Affk est bien spécifiée revient à montrer que pour toute liste l de longueur n+1, A(l) est décrit par S(l).

S(l) est l'énoncé « Afficher tous les éléments de la liste l »

Appliquons A à l : puisque l n'est pas vide, ChoseAfficher(ListePremier(l)) est d'abord exécutée. Comme ChoseAfficher et ListePremier sont bien spécifiées (car prouvées par hypothèse ( h ) )

ChoseAfficher(ListePremier(l)) est décrit par l'énoncé  « Afficher à l'écran le premier élément de l ».

Puis Aff(ListeReste(l)) est exécutée. Comme ListeReste(l) est une liste de longueur n (ListeReste est prouvée) , Aff(ListeReste(l)) est équivalent à Affn(ListeReste(l)).

Comme par hypothèse de récurrence Affn est bien spécifiée, Aff(ListeRest(l)) est décrit par l'énoncé « Afficher à l'écran le premier élément de l , puis afficher à l'écran tous les éléments du reste de la liste ».

A(l) est donc finalement décrit par l'énoncé  « Afficher à l'écran le premier de l , puis afficher à l'écran tous les éléments du reste de la liste » , qui est une forme équivalente de S(l).

III-I-2 - Exemple 2 : montrer que Rang est bien spécifiée

( h ) : Nous supposerons ( p ) et ( c )

On partitionne TListe de la même façon : Dk est maintenant Lk x TChose , où Lk est l'ensemble des listes de TListe de longueur k.

1. Vérifions que Rang_0 est bien spécifiée :
S( l , ch ) est l'objet -1. Appliquons A à ( l , ch ) : comme la liste est vide A retourne -1 : C.Q.F.D.

2. Montrons Rangn+1
Pour une liste de longueur n+1 S( l , ch ) est l'énoncé « Le rang de la première occurrence de la chose ch dans la liste l , ou -1 si ch n'est pas dans la liste ».
Appliquons A à ( l , ch ). De trois choses l'une :

1. Ou bien le premier élément de l est égal à ch ;

2. Ou bien ch n'est pas dans l ;

3. Ou bien ch est dans le reste de l.

Dans le premier cas, A retourne 1 : c'est bien « le rang de la première occurrence de la chose ch dans la liste l ».

Dans le second cas (ch n'est pas dans l) n est affectée de la valeur Rang(ListeReste(l) , ch ). Comme ListeReste est bien spécifiée ( hypothèse ( h ) ) c'est le reste de la liste l, donc une liste de longueur n ; Rang(ListeReste(l) , ch) étant alors équivalent à Rangn (ListeReste(l) , ch ) qui est prouvée par hypothèse de récurrence , n est affectée de la valeur -1 (ch n'est pas dans l !). A retourne -1 , ce qui est conforme à la spécification.

Dans le troisième cas (ch est dans le reste de l), on peut affirmer, par un raisonnement analogue, que n est affectée du rang de ch dans le reste de l ; A retourne ce rang plus 1 qui est effectivement « le rang de la première occurrence de la chose ch dans la liste l » : en effet, si ch a le rang r dans le reste de l, il a le rang r+1 dans l.

Remarque  : si P = ( S , D , T , A ) est prouvé ainsi que P' = ( S , D , T , A' ), alors P ≈ P'.

IV - Remerciements

Merci à Claude Leloup et Pierre RUEL pour leur relecture.