Concepts en algorithmique

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.

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.

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.

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.

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-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.

I-E-2. Module de fonctionnalités non 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.

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 ;

 _Predecesseur
 _EstAvant
 _Somme
 _Difference
 _Produit
 _Division

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

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 ;

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 }

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 ;

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

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 ;

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.

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 }

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;

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.

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).

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).

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 »).

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.

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.

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 »)

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'.

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.

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.

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 : D_i, D_i+1, …

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

Ce qu'on peut faire par récurrence :

1. (Valeur initiale) On vérifie que P_i est bien spécifiée ;
2. (Induction) On démontre que si P_k est bien spécifiée pour i ≤ k ≤ n alors P_n+1 est bien spécifiée.

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▲