APPROCHE ALGORITHMIQUE PAR ERIC CREPIN

Mise à jour du 23 mai 2003

Accueil
GENIE LOGICIEL et ALGORITHMIQUE

La DEMARCHE de PROGRAMMATION

ANALYSE et CONCEPTION

Présentation

La décomposition fonctionnelle

La méthode JACKSON.

LA PROGRAMMATION STRUCTUREE

Introduction

La séquence

La sélection

La répétition

La METHODE RETENUE

Les étapes

Illustration

GENIE LOGICIEL et ALGORITHMIQUE

L’objectif des traitements informatiques est de résoudre des problèmes de

façon automatique, fiable, et rapide. Cependant le niveau de complexité
de l’ensemble des problèmes qu’il est envisageable d’informatiser est très
variable.

Voyons quelques exemples de problèmes

Il est évident qu’un enfant sera capable de résoudre le problème faire une
opération, et d’en fournir un algorithme (la suite des étapes permettant de
résoudre le problème).

Alors que l’ensemble des chercheurs du monde sera incapable de créer un

logiciel imitant complètement le comportement humain.

 Plus le problème est complexe, plus il est abstrait donc difficile

à formaliser.

Il est évident qu’il est impossible d’envisager de tout informatiser,

toutefois l’objectif doit être de résoudre le maximum de problèmes sans
les déformer.

Pour cela il faut mettre en application les règles de conception des

logiciels (le Génie Logiciel).

 Au niveau du développement d’un algorithme (de base), et de son

programme associé, les étapes qui nous intéressent sont :

la conception
 la codification
les tests unitaires

La démarche de programmation

L'écriture d'un programme nécessite différentes phases d'élaboration, qui

vont du problème brut posé au départ, jusqu'à l'obtention de résultats
suite à l'exécution de l’application (un ou plusieurs programmes).

On note donc trois étapes distinctes :

 l'Analyse : étape de réflexion et de modélisation du problème.

Conception théorique de l'application.

 la Programmation : étape d’élaboration d'un outil informatique: le

programme.

Codification en langage de programmation, et maintenance du

programme.

 l'Exécution : étape d'utilisation du programme en traitement de

l'information (les données) en vue d'obtenir des résultats.

Jeux d'essai (tests de validités) et utilisation normale.

Schématiquement

Schéma détaillé de la conception d'une application

Remarques importantes :

Une application n'est définitivement finie qu'au moment où les jeux

d'essai sont concluants

 les résultats du programme correspondent à l’énoncé du cahier

des charges.

Si une anomalie est détectée lors des tests de validation, il faut remonter
à la formulation du problème (conception), et ne surtout pas procéder à
un bricolage de programme.

ANALYSE et CONCEPTION

Présentation

Il existe un grand nombre de méthodes visant à la réalisation de

programmes et d’applications informatiques ; ceci prouve qu’il n’y a pas
une solution unique aux problèmes de conception de logiciels.

Présentons quelques règles qui font forces de LOIS dans la

démarche de conception :

La démarche "Informatique" n'a rien de "Magique"

On ne peut programmer que ce qu'on est capable de

comprendre.

Aucune méthode de conception d'analyses, ou d'algorithmes ne peut se

substituer à la réflexion humaine face à un problème à résoudre.
En aucun cas la réalisation d'un système informatique ne doit trahir
la réalité du problème posé à la base.

Le but étant d’atteindre les objectifs suivants (rappel Génie Logiciel)

fiabilité

performance

maintenance facile

temps de production raisonnable

diminution des coûts

Quelques exemples de méthodes ou de langage de formalisation

la décomposition fonctionnelle

la conception dirigée par les données

JACKSON

MERISE

U.M.L.
 X.P.

SADT

l’algorithme par les types abstraits

la conception par objets

La décomposition fonctionnelle

Cette méthode a pour objectif la décomposition d’un problème conséquent

en un certain nombre de sous problèmes plus simples, et de reproduire ce
traitement sur les sous problèmes, jusqu’à en obtenir des fonctions
élémentaires.

exemple : Je suis dans la rue, et je veux rentrer chez moi.

Problème : Rentrer chez moi.

 Sous Problème :
 Ouvrir la porte de l’immeuble

 Sous Problème 

1. Prendre la clé
2. Mettre la clé dans la serrure
3. Tourner la clé dans la serrure
4. Pousser la porte

 Prendre l’ascenseur

 Sous Problème 

1. Appuyer sur le bouton d’appel

2. Monter dans l’ascenseur

 Sous Problème  

1. Ouvrir la porte de l’ascenseur

2. Entrer dans l’ascenseur
3. Attendre la fermeture de la porte

3. Appuyer sur le bouton de l’étage

4. Descendre de l’ascenseur

 Ouvrir la porte de l’appartement

 Sous Problème 

1. Prendre la clé
2. Mettre la clé dans la serrure
3. Tourner la clé dans la serrure
4. Pousser la porte

Remarques

La décomposition fonctionnelle fait intervenir des critères d’expérience,

et de  bon sens de la part du concepteur du logiciel.
La méthode est très intuitive, et ne fait pas apparaître les structures des
données à manipuler; celles ci étant des éléments terminaux.
La méthode est un guide, c’est le concepteur qui crée ; ce qui veut dire
que pour deux concepteurs différents on pourra obtenir deux solutions
différentes, cela peut poser des problèmes d’organisation, et de
maintenance.

La méthode JACKSON.

L’objectif de ce paragraphe n’est pas de développer dans le détail la

méthodologie JACKSON, mais d’en présenter les éléments qui vont nous
permettre de résoudre les quelques problèmes rencontrés précédemment
lors de la conception par décomposition fonctionnelle.

La méthode JACKSON est établie sur le fait que la structure d’un logiciel
repose sur la structure des données que celui ci manipule.

Le fonctionnement du logiciel correspondant aux traitements que l’on va

appliquer aux structures de données (fonctionnalité du logiciel 
fonction sur les données).

On voit apparaître les notions :

de structures de données représentations de l’information

de fonctions appliquées aux données actions sur l’information

de modules logiques fonctionnalités générales

exemple : Je suis dans la rue, et je veux rentrer chez moi.

structure des données

PORTE (comporte

BATTANT
 SERRURE

CLE)

ASCENSEUR (comporte

PORTE

BOUTON d’APPEL

BOUTONs d’ETAGE)

modularité de conception

Fonctions appliquées aux structures de données

Module : Entrer dans l’immeuble.

début module

Prendre (CLE d’immeuble)

Ouvrir (PORTE d’immeuble)

Pousser (PORTE d’immeuble)

fin module

description de la fonction Ouvrir (PORTE)

début fonction

Mettre (CLE,SERRURE)

Tourner (CLE,SERRURE)

fin fonction

LA PROGRAMMATION STRUCTUREE

Introduction

La programmation structurée repose sur le concept que tout programme

peut être développé uniquement à partir de trois constructeurs :

la séquence
la sélection
la répétition

 fin de la programmation  spaghetti

 l’instruction  GOTO est par le fait interdite

Théorème : Tout programme contenant des  GOTO peut être

transformé en un programme structuré équivalent. BOHM et JACOPINI

La séquence

Cette opération consiste à exécuter les instructions en séquence.

Schéma d’une séquence

exemple : Problème  additionner deux nombres.

Cet algorithme comporte 4 séquences (actions élémentaires) qui vont

permettre de résoudre notre problème.

La sélection

Une sélection consiste à effectuer un choix (de traitement à faire) en

fonction d’une condition plus ou moins complexe.

Schéma d’une sélection

exemple : Problème  S’il fait beau j’irai faire du vélo, sinon je lirai un
livre.

écriture pré-algorithmique

Si le temps est beau (condition)

alors j’irai faire du vélo (traitement 1 condition vérifiée)

sinon je lirai un livre (traitement 2 condition non vérifiée)

Problème  Si j’ai la clé ou si la porte est ouverte j’entrerai dans la salle

écriture pré-algorithmique

Si j’ai la clé ou la porte est ouverte (condition complexe)

alors j’entrerai dans la salle (traitement 1 condition vérifiée)

sinon rien à faire (traitement 2 condition non vérifiée)

La répétition

A quoi pourrait bien servir l’informatique si l’ordinateur n’était pas capable

de répéter des traitements ?

 exemple un logiciel de paye qui ne calculerait qu’une fiche de paye ???

La répétition va permettre d’utiliser un traitement plusieurs fois pour gérer
un ensemble de données de mêmes types dans le but d’obtenir une série
de résultats construits sur le même schéma.

Schéma d’une répétition

exemple : Problème  Additionner 4 nombres.

écriture pré-algorithmique

Compteur = résultat = 0 initialisation du traitement itératif

répéter

lire(Nombre) action  traitement itératif

cumuler (résultat avec nombre) action  traitement itératif

incrémenter (Compteur) action  traitement itératif

jusqu’à Compteur = 4 condition de répétition

écrire (résultat)

ou

Compteur = résultat = 0 initialisation du traitement itératif

tant que Compteur  4 condition de répétition

lire(Nombre) action  traitement itératif

cumuler (résultat avec nombre) action  traitement itératif

incrémenter (Compteur) action  traitement itératif

fin de tant que

écrire (résultat)

La METHODE RETENUE

Les Etapes

La méthode que nous allons adopter sera la décomposition

fonctionnelle,

en décrivant les structures de données,

et en y appliquant un traitement modulaire.

Les outils utilisés seront ceux de la programmation structurée soit

la séquence,
la sélection,
la répétition.

La conception d’un programme sera décomposée en quatre étapes

1. étape de réflexion

définir les données du problème

définir les résultats du problème
décomposer les résultats pour retrouver les données
ou
construire le résultat à partir des données

2. conception de l’algorithme et de son lexique

ordonnancer les actions à effectuer

définir la forme des structures de données

3. traduction en langage de programmation

programmer l’algorithme et le lexique

vérifier que la syntaxe du programme est correcte

4. validation du programme par des jeux d’essai

 sélection d’échantillon de données caractéristiques
exécuter le programme à partir des échantillons sélectionnés

Illustration

Enoncé : additionner deux nombres

Etape de réflexion

Données du
le nombre 1 et le nombre 2
problème
Résultats du
somme des deux nombres
problème
Schéma de
somme = nombre 1 + nombre 2
calcul

Algorithme et lexique

lexique nom de variable type informatique définition

Variabl
type définition
e
NOMBR
(réel) le nombre 1
1
NOMBR
(réel) le nombre 2
2
SOM (réel) somme des deux nombres

algorithme ordonnancement des instructions explications

Instructions
commentaire
ordonnées
demande de saisie clavier du nombre
lire (NOMBR1)
1
lire (NOMBR2)
demande de saisie clavier du nombre
SOM = NOMBR1 +
2
NOMBR2
somme des deux nombres
écrire (SOM)
affichage à l’écran du résultat

Programme

en Turbo PASCAL

Program EXEMPLE_UN;

(* déclaration des variables  traduction du lexique *)

var NOMBR1, NOMBR2, SOM : real;

BEGIN (* début du programme  traduction algorithme *)

(* saisie des données du problème *)

readln(NOMBR1);

readln(NOMBR2);

(* calcul du résultat *)

SOM := NOMBR1 + NOMBR2;

(* affichage du résultat *)

writeln(SOM);

END. (* fin du programme  algorithme *)

Tests de validité

sur ce programme un seul test sera suffisant, il n’y a qu’un calcul

variable sens de l’information valeur

NOMBR1 Unité Centrale  clavier 1.75

NOMBR2 Unité Centrale  clavier 6.3

SOM Unité Centrale  écran 8.05

simulation machine

avant exécution du programme

lancement du programme

après la saisie des données

après l’exécution du calcul

Attention : en fin de programme