008_Schéma fonctionnel

Dans la méthode de construction des algorithmes, nous partons de l’objectif final, le plus souvent une valeur à calculer ; ainsi, nous faisons apparaître une variable pour laquelle il faut expliciter le mode de calcul. Ce calcul présuppose lui-même le calcul d’autres variables. On comprend intuitivement que la valeur finale est calculée en fonction des variables dont elle dépend. Chaque calcul peut faire l’objet d’un algorithme et on peut utiliser, dans une définition d’un algorithme, une valeur résultant de l’exécution d’un autre algorithme.

Soit par exemple à fabriquer une série d’appareils dont chaque exemplaire sera équipé d’un quartz et de deux diviseurs de fréquence correspondant à la demande de chaque client. À la commande, le client précisera les 2 fréquences dont il a besoin. Nous allons écrire le programme qui détermine la valeur du quartz et les valeurs des deux diviseurs de fréquence, sachant que toutes ces valeurs sont des nombres entiers.

ActionsOrdre

FREQ : /* Calcul d'une fréquence et de deux diviseurs */
Lexique
✔︎ F_q : Fréquence du quartz
✔︎ F_1 et F_2 : Fréquences client
✔︎ div_1 : diviseur pour F_1
✔︎ div_2 : diviseur pour F_2
Afficher (F_q, dvi_1, dvi_2) ;
F_q = PPCM (F_1, F_2) ;
div_1 = \nicefrac{F_q}{F_1} ;
div_2 = \nicefrac{F_q}{F_2} ;
saisir(F_1, F_2) ;
5
2
3
4
1

La valeur F_q sera renvoyée par le calcul du PPCM de F_1 et F_2.

PPCM (a,b) /* Calcul du plus petit commun multiple */
 PPCM = \dfrac{a\times b}{\tt PGCD (a,b)}

La valeur du PPCM sera renvoyée par le calcul du PGCD de F_1 et F_2.

PGCD (x, y) /* Calcul du plus grand diviseur commun de 2 nombres */
✔︎ m : : variable temporaire while (x != 0)
{
if  (x < y) y = y – x ;
else        x = x – y ;
}
return y ;

On voit donc que l’on est conduit à écrire 2 nouvelles fonctions (qui ne sont pas natives) le PPCM et le PGCD pour réaliser ce programme.

Relation de précédente

On définit une relation de précédente sur les variables d’un algorithme. Nous dirons que la variable x précède la variable y si x a au moins une occurrence dans la définition de y. À cause de cela, la valeur de y dépend de la valeur de x, et le calcul de y n’est possible que si x a déjà été calculé. La relation « x précède y » peut donc être lue comme « le calcul de x doit précéder le calcul de y ».

Cette relation définit un ordre partiel sur les variables de l’algorithme.

Un calendrier perpétuel

Définition du problème :

On se propose de déterminer le jour de la semaine d’une date donnée. Sachant que le 1^{er} janvier 1900 était un lundi ; on appellera décalage la position d’un jour dans la semaine \mid décalage \in [0-6], 0 \equiv dimanche.
Pour cela, on va chercher le décalage entre le 1^{er} janvier de l’année 1900 et la date considérée. On se donne une table du nombre de jours écoulés depuis le début de l’année jusqu’au début du mois mois.

Calper (quantieme, mois, an)
✔︎jour \in [0-6] 
✔︎ decalage \in \mathbb{N}
✔︎ decalAA \in \mathbb{N}
✔︎ decalAA \in \mathbb{N}
afficher (jour) ;
jour     = decalage modulo 7 ; 
decalage = quantieme + decalAA + decalMM
decalAA  = ecoulesan (an ) ;
decalMM  = ecoulesmm (an, mois) ;
5
4
3
1
2
 Ecoulean (a)
✔︎ DecAn \in \mathbb{N}
✔︎ AnsApres1900\in \mathbb{N}
✔︎ AnsBissextiles \in \mathbb{N}
/* 1 jour de decalage par an + 1 par annee bissextile */
return DecAn ;
DecAn = AnsApres1900 + AnsBissextiles ;
AnsApres1900 = a modulo 100 ;
/* on ne compte pas l’annee courante parmi les bissextiles */
AnsBissextiles = (a -1) / 4 ;
4
3
12
 EcouleMM(a, m)
✔︎ DecMois \in \mathbb{N}
✔︎ Biss \in [0, 1]
✔︎ SommeMois \in \mathbb{N}
 /* Decalage de jours entre 1.1.a et 1.M.a */
return DecMois ;
DecMois = SommeMois[m] + Biss ;
Biss = 0
if (a modulo 4)
   if (m > 2)
      Biss = 1 ;
SommeMois [] = { 0, 0, 31, 59, 90, 120, 151,
               
181, 212, 243, 273, 304, 334} ;
5
4
2
31

Rendered by QuickLaTeX.com

Graphe de dépendance des variables

On vérifie sur le graphe de dépendance des variables de la figure ci-dessus que l’objectif (Jour) présuppose le calcul des variables dont il dépend, et que chacune d’elles est explicitée, soit par un calcul simple, soit par l’appel d’une fonction, jusqu’à remonter aux valeurs fournies à l’algorithme.