Partie 3 : Un peu d'algorithmique


L’algorithmique naît des premiers efforts menés par des scientifiques comme Knuth (inventeur de TEX), E.W. Dijkstra, C.A.R. Hoare, N. Wirth pour rationaliser l’inginiérie du logiciel.

Elle vise à trouver les techniques qui assurent la fiabilité des programmes (c’est l’objet de la recherche sur la « preuve » des programmes), leur efficacité (par exemple les études sur la récursivité), la facilité de leur mise au point et de leur correction (la programmation structurée), et enfin la mise à disposition d’unités standardisées aisément réutilisables.

C’est dans ce dernier cadre que l’on voit se développer les méthodes sur les tris (shaker, shell, heapsort, quicksort), les arbres, le hachage, les graphismes (modes vectoriel ou matriciel) etc.

La grille

La question d’algorithmique est relative à une grille telle que celle qui est représentée ci-dessous. Certaine cases sont blanches ; chacune est destinée à y inscrire un caractère. D’autres sont grisées, et en nombre suffisant pour limiter plusieurs îlots blancs ; la convention de continuité est la suivante : deux carrés grisés sont contigus s’ils ont au moins un point en commun (sommet ou côté) ; deux carrés blancs le sont s’ils ont un côté en commun ! (C’est la convention habituelle dans la gestion d’un écran, décrit comme un tableau de pixels, quand on y définit des lignes limitant des surfaces). Noter que le tour est entièrement grisé, ce qui revient à dire qu’un îlot est limité par une ligne grisée.

 

Dans une réalisation logicielle comportant une grille de ce type, on a défini l’équivalent de la séquence algorithmique qui suit :


001

002

003

004

005

006

007

008

009

010

011

012

013


variables

  Pile : tableau de nombres entiers ; premier indice : 0

  Pointeur_De_Pile : entier

  Grille : tableau de caractères à deux dimensions

  indices de la première dimension : entiers de xmin à xmax

  indices de la seconde dimension : entiers de ymin à ymax

  x_depart, y_depart : entiers

  xdroit, xgauche : entiers

  cptc : entier

variables initalisées

  CC : caractère ; CC ß "A"

  fond : caractère ; fond ß " "

  bord : caractère ; bord ß "."


014

015

016

017

018

019

020

021


procédure
Empiler

paramètres par valeur : u et v : entiers

corps_de_procédure

  Pile [Pointeur_de_Pile] ß u

  incrémenter Pointeur_de_Pile

  Pile [Pointeur_de_Pile] ß v

  incrémenter Pointeur_de_Pile

fin_de_procédure Empiler


022

023

024

025

026

027

028

029


procédure
Dépiler

paramètres par référence : u et v : entiers

corps_de_procédure

  décrémenter Pointeur_de_Pile

  v ß Pile[Pointeur_de_Pile]

  décrémenter Pointeur_de_Pile

  u ß Pile[Pointeur_de_Pile]

fin_de_procédure Dépiler


030

031

032

033

034

035

036

037

038

039

040

041


procédure
A_droite

variable locale

  x_local : entier

corps_de_procédure

  x_local ß x_depart

  Tant_Que(Grille[x_local,y_depart]=fond) Faire

    grille[x_local,y_depart] ß  CC

    incrémenter x_local

    incrémenter cptc

  fin_de_Tant_Que_Faire

  xdroit ß (x_local-1)

fin_de_procédure A_droite


042

043

044

045

046

047

048

049

050

051

052

053

054


procédure
A_gauche

variable locale

  x_local : entier

corps_de_procédure

  x_local ß x_depart

  décrémenter x_local

  Tant_Que(Grille[x_local,y_depart]=fond) Faire

    grille[x_local, y_depart]ß CC

    décrémenter x_local

    incrémenter cptc

  fin_de_Tant_Que_Faire

  xgauche ß (x_local+1)

fin_de_procédure A_gauche


055

056

057

058

059

060

061

062

063

064

065

066

067

068
 

069

070

071

072

073

074


procédure
Au_dessus

  variables locales

  x_local, y_local : entiers

corps_de_procédure

  x_local ß xgauche

  y_local ß (y_depart-1)

  Si(y_local > ymin) Alors

    Tant_Que(x_local=<x_droit) Faire

      Tant_Que((Grille[x_local,y_local]<>fond) EtÃ
              (x_local=<x_droit)) Faire

          incrémenter x_local

      Fin_de_Tant_Que_Faire

      Si(x_local=<x_droit) Alors

        Empiler x_local, y_local

        Tant_Que((Grille[x_local, y_local]= fond) Ã
               Et (x_local=<x_droit)) Faire

          incrémenter x_local

        Fin_de_Tant_Que_Faire

      fin_de_Si_Alors

    Fin_de_Tant_Que_Faire

  Fin_de_Si_Alors

fin_de_procédure Au_dessus


075

076

077

078

079

080

081

082

083
 

084

085

086

087

088
 

089

090

091

092

093

094


procédure
En_dessous

variables locales

  x_local, y_local : entiers

corps_de_procédure

  x_local ß xgauche

  y_local ß (y_depart+1)

  Si(y_local < ymax) Alors

    Tant_Que(x_local =< x_droit)Faire

      Tant_Que((Grille[x_local,y_local]<>fond) EtÃ
         (x_local=<x_droit))Faire

        incrémenter x_local

      fin_de_Tant_Que_Faire

      Si(x_local=<x_droit) Alors

        Empiler x_local, y_local

        Tant_Que((Grille[x_local,y_local]=fond) EtÃ
            (x_local=<x_droit))Faire

          incrémenter x_local

        fin_de_Tant_Que_Faire

      fin_de_Si_Alors

    fin_de_Tant_Que_Faire

  fin_de_Si_Alors

fin_de_procédure En_dessous


095

096

097

098

099

100

101

102

103

104

105

106

107


procédure
Tache

corps de procédure

  Empiler x_depart, y_depart

  Tant_Que(Pointeur_de_Pile>0) Faire

    Dépiler x_depart, y_depart

    Si(grille[x_depart,y_depart]=fond) Alors

      A_droite

      A_gauche

      En_dessous

      Au_dessus    

    fin_de_Si_Alors

  fin_de_Tant_Que_Faire

fin_de_procédure Tache


108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123


procédure
Remplir

variables locales

  i,j : entiers

corps_de_procédure

  Pointeur_De_Pile ß 0

  Pour i Allant_de xmin Jusque xmax Faire

    Pour j Allant_de ymin Jusque ymax Faire

      Si(grille[i,j] = fond) Alors

        x_départ ß i

        y_départ ß j

        Tache

        CC ß (suivant CC)

      fin_de_Si_Alors

    fin_de_Pour j

  fin_de_Pour i

fin_de_procedure Remplir

 

questions

3.1. La procédure REMPLIR.

Quel est l’effet de l’appel de cette procédure ? En quoi cette procédure permet-elle de déterminer le nombre d’îlots ? Un carré blanc peut-il être « affecté » plusieurs fois lors de l’exécuton de la procédure ?

3.2. La procédure TACHE.

On suppose que l'on réalise l'appel séquentiel suivant :

      x_depart ß (xmin+3)
      y_depart ß (ymin+2)
      TACHE

On demande d'indiquer sur la grille les carrés dont les coordonnées sont empilées à un moment ou un autre, en les numérotant à partir de 0 (carré de l'appel) dans l'ordre où se font les appels d'empilage.

3.3. Sans cadre.

Quelles difficultés apparaissent si on veut se libérer de la condition : le tour est entièrement grisé (un îlot est limité localement soit par un contour grisé, soit par les bords de la grille) ?

 

illustration du livre de Niklaus Wirth