Belahmidi (2008) 1

ALGORITHMIQUES

Cours d’informatique2ème année Economie

Belahmidi (2008) 2

Section 1 - Notions d’algorithmique

1. Pourquoi utiliser un algorithme ?

2. Qu’est-ce qu’un algorithme ?

3. Caractéristiques d’un algorithme

4. La structure d’un algorithmeA. Les objets utilisés dans l’algo :

constantes, variables

B. Les règles de mises en forme

Belahmidi (2008) 3

Pourquoi utiliser des algorithmes ?

Problèmes de communication entre le gestionnaire et l’informaticien :

Difficultés pour décrire des travaux à informatiser (oublis, ambiguïtés…)

Vision différente entre concepteur et utilisateur

Diversité des langages de programmation…

Voir schéma des niveaux de langages en infoDonc, nécessité d’acquérir une méthode d’analyse des problèmes communes à

tous !

Belahmidi (2008) 4

Qu’est-ce qu’un algorithme ?

Un algorithme décrit une succession d’opérations à exécuter dans un certain ordre et sous certaines

conditions, pour passer des données de base aux

résultats

Belahmidi (2008) 5

Qu’est-ce qu’un algorithme ?

L’algorithmique est la technique des algorithmesUn algorithme décrit un traitement selon une logique et un formalisme rigoureux. L’algo prépare la programmation

L’algo est une étape préalable indispensable à la réalisation d’un bon programme

C’est une méthode de découpage d’un traitement en instructions élémentaires

Belahmidi (2008) 6

Caractéristiques d’un algorithme

Il contient plusieurs séquences à exécuter Ensemble d’actions élémentaires

les séquences (étapes) se succèdent dans un certain ordre Il peut éventuellement exister une répétition (itération) ou une condition d’exécution ou non de certaines séquencesIl est caractérisé par un début et une fin

Belahmidi (2008) 7

Exemple d’algo – niveau 1Algo : FactBout (d’après sujet Bac IG Désaltère)Constantes:

TXTVA : 0,196Variables

Ref, Nb : EntierPu, BrutHT, : Réel

Début * Entrée des données élémentaires

SAISIR «  référence de la bouteille ?  », RefSAISIR «  Prix HT d’une bouteille ?  », Pu

SAISIR « Combien de bouteilles achetées ?, Nb * Calcul du montant dû par le client

BrutHT Pu * Nb * Sortie des résultats Afficher "Montant dû par le client:", BrutHTFin

Belahmidi (2008) 8

La structure d’un algorithme

En général, un algo comprend 4 parties :

1. Avant le début de l’algo, la déclaration des variables nécessaires aux traitements

2. Au début de l’algo, l’initialisation des variables : affectation de valeurs initiales aux variables déclarées

Belahmidi (2008) 9

La structure d’un algorithme

3. Le traitement des différentes séquences ordonnées de l’algo :

Réalisation d’actions élémentaires ou structurées Appel de procédures ou de fonctions externes : « sous-traitement » de portée générale qui sont réutilisés dans plusieurs algorithmes différents

4. À la fin de l’algo, la sortie des résultats et l’arrêt de l’algo

Belahmidi (2008) 10

Les objets utilisés dans l’algo Un algo utilise des objets qui peuvent être des variables, des

constantes, des littéraux.Chaque objet à un rôle qui consiste à mémoriser une valeur particulière significative :

La variable qui contient une valeur appelée à être modifiée au cours de l'algorithme.

La constante qui retient une valeur qui ne change pas au cours de l'algorithme Le littéral qui est une valeur de type numérique ou alphanumérique (« SARL

MONPC » ; 19.6)

Un objet est parfaitement défini s’il est parfaitement identifié, typé et renseigné

Belahmidi (2008) 11

a) caractéristiques d’une variable

Une variable est un dispositif de mémorisation d’une valeur à laquelle on accède à tout moment. Elle est caractérisée par :

Un rôle : signification attribuée à la variable Un nom (identificateur) : « contenant » permettant

d’accéder directement à son contenu. Il doit être le plus parlant et le plus évocateur du rôle de la variable

Une valeur : contenu de la variable à un moment donné : 1 seule valeur ou plusieurs valeurs

Un type : c’est la définition du domaine dans lequel une variable peut puiser sa valeur(voir tableau de déclaration de variables)

Belahmidi (2008) 12

b) Tableau de déclaration de variables

N°

Nom Statut

(Entrée ou Sortie)

Rôle Type (Entier,

réel, texte, date,

booléen)

Format

1 Codecli E Code du client

entier 111

2 datfact E Date de la facture

date jj/mm/aaaa

3 anciencli E Ancien client Booléen Oui / non4 Nomcli E Nom du

clientTexte 40 car

…

Belahmidi (2008) 13

Section 2 - La construction d’un

algorithme

1. Les actions élémentaires

2. Les actions structuréesA. La structure alternative

B. La structure itérative

3. Les actions nommées

Belahmidi (2008) 14

Les règles de mise en forme de l’algorithme

Nom de l’algorithme

Déclaration des variables et constantes

Début

*commentaires

Instructions1

Instructions 2

*commentaires

Fin

Belahmidi (2008) 15

Les actions élémentaires

1. L’instruction d’affectation L'opération consiste à affecter une valeur à une variable. Elle est représentée par une flèche orientée à gauche

NomVariable expression ; constante ; variable

Exemple : Nomcli « DUPONT »

A 100

B A * 0.196

A A + B

Belahmidi (2008) 16

Les instructions élémentaires

2.L’instruction d’entrée : SAISIR ou ENTRERA l’exécution de cet ordre, l’ordinateur demande à l’utilisateur de lui communiquer par l’intermédiaire du clavier ou de la souris, une valeur. L’info saisie doit être cohérente avec le type de la variable.Remarque : lors de la saisie d’une donnée, celle-ci est automatiquement affichée à l’écran.SAISIR « nom de l’élève : », NOMELEV

3.L’instruction de sortie : AFFICHERA l’exécution de cet ordre, l’information est restituée à l’écran.AFFICHER « La note obtenue par : », NOMELEV, « est de : », NOTE

Belahmidi (2008) 17

Les actions structuréesLes instructions structurées sont des structures algorithmiques de base. C’est l’ordonnancement logique des actions, tenant compte des décisions à prendre, qui structure l’algo

1. La structure alternative2. La structure itérative

Belahmidi (2008) 18

La structure alternativeCette structure permet de mener deux actions différentes selon une condition. La condition peut être simple ou combinée (avec les opérateurs logiques ET, OU). Les alternatives peuvent s’imbriquer.

Alternative complète :Si « condition »

Alors « Action 1 »Sinon « Action 2 »

Fin Si

Alternative appauvrie :Si « condition »

Alors « Action 1 »Fin Si

Belahmidi (2008) 19

Exemple d’algo – niveau 2Algo : FactBout (d’après sujet Bac IG Désaltère)

Constantes:TXTVA : 0,196

VariablesRef, Nb : EntierPu, BrutHT, Rem, NetHT, netTTC : Réel

Début * Entrée des données élémentaire

SAISIR «  référence de la bouteille ?  », RefSAISIR «  Prix HT d’une bouteille ?  », Pu

SAISIR « Combien de bouteilles achetées de cette référence ?, Nb

* Calcul du montant dû par le client…..

* Sortie des résultats Afficher "Montant dû par le client:", NetTTCFin

Belahmidi (2008) 20

Exemple d’algo – niveau 2

* Calcul du montant dû par le client* *Calcul du montant de la remise (5% si le Nb de bouteilles > 24)

BrutHT Pu * NbSi Nb >= 24

Alors Rem BrutHT * 0,05 Sinon Rem 0

Fin Si* *Calcul du montant net HT

NetHT BrutHT – Rem

** Calcul du montant net TTC (réduction 10% sup si netHT) Si NetHT > 2000

Alors NetTTC NetHT * 0,9 * (1+TxTVA) Sinon NetTTC NetHT * (1+TxTVA)

Fin Si

Belahmidi (2008) 21

La structure itérativeL’itération (ou boucle) est une structure qui permet de faire répéter un ensemble d’actions, un certain nombre de fois dans un ordre préalablement défini.

Il existe trois types de structures itératives :1. la structure « TANT QUE… FAIRE » :

Le nombre de répétitions n’est pas connu et peut être nul : 0 à n répétitions

2. la structure « REPETER… JUSQU’À » :Le nombre de répétitions n’est pas connu mais ne peut pas être nul : 1 à n répétitions

3. la structure « POUR… FIN POUR » :Le nombre de répétitions est connu (i= 1 à 20)

Belahmidi (2008) 22

Algo : FactBout (d’après sujet Bac IG Désaltère)Variables :… TOTALTTC : réelDébut * Initialisation de la variable TOTAL TOTALTTC 0 SAISIR « Quelle est la référence des bouteilles achetées ? », Ref * répétition du calcul du montant dû pour

TANT QUE Ref <> 0 FAIRE * Entrée des autres données élémentaires Pu, Nb

* * Calcul du montant de la remise * * Calcul du montant net HT * * Calcul du montant net TTC TOTALTTC TOTALTTC + NETTTCSaisir « Autre référence de bouteille :», ref

FIN TANT QUEAFFICHER «montant total TTC facturé et dû par le client »,

TOTALTTCFin

La structure «TANT QUE… FIN TANT QUE»

Belahmidi (2008) 23

La structure «REPETER… JUSQU’A»Algo : FactBout (d’après sujet Bac IG Désaltère)Variables :… TOTALTTC : réel

Réponse : booléenDébut * Initialisation de la variable TOTAL TOTALTTC 0 * répétition du calcul du montant dû pour

REPETER * Entrée des autres données élémentaires Ref, Pu, Nb

* * Calcul du montant de la remise * * Calcul du montant net HT * * Calcul du montant net TTC TOTALTTC TOTALTTC + NETTTCSaisir «Y-a-t-il une autre référence de bouteille :», réponse

JUSQU’À réponse NONAFFICHER «montant total TTC facturé et dû par le client »,

TOTALTTCFin

Belahmidi (2008) 24

La structure «POUR… FIN POUR»Algo : FactBout (d’après sujet Bac IG Désaltère)Variables :… TOTALTTC : réel

NBREF : entier i : entier

Début * Initialisation de la variable TOTAL TOTALTTC 0 SAISIR « nombre de références différentes des bouteilles achetées : », NBREF * répétition du calcul du montant dû pour

POUR i = 1 à NBREF * Entrée des autres données élémentaires Ref, Pu, Nb

* * Calcul du montant de la remise * * Calcul du montant net HT * * Calcul du montant net TTC TOTALTTC TOTALTTC + NETTTC

FIN POURAFFICHER «montant total TTC facturé et dû par le client », TOTALTTC

Fin

Belahmidi (2008) 25

Les actions nommées : procédures et fonctionsDans le principe, un bon algorithme ne devrait pas dépasser une page !Pour respecter ce principe, il convient de NOMMER certaines séquences d’actions qui correspondront à des procédures ou à des fonctions

Ainsi, ces actions nommées seront décrites dans des algorithmes auxiliaires et seront utilisées dans un algorithme principal.

Belahmidi (2008) 26

L’utilisation des procédures - Exemple

Algo principal : Lasagnes à la BolognaiseVariables :

500g lasagnes précuites –150 g parmesan – 50 gbeurre plat à gratin NBpers

DEBUT Saisir « Plat pour combien de personnes ? », nbpers Préparer la sauce bolognaise (nbpers) Préparer la sauce béchamel (nbpers)1. Disposer vos ingrédients dans le plat

Préchauffer four thermostat 6 et beurrer un plat à gratin Disposer une couche de lasagne au fond du plat Étaler généreusement de la sauce bolognaise Puis recouvrir de sauce béchamel

Renouveler l’opération 1 ou 2 fois selon la hauteur du platParsemer de parmesan et de beurreFaire gratiner 35 min au four à chaleur tournante

FIN

Belahmidi (2008) 27

Algo auxiliaire :

Procédure Bolognaise (quantité)Variables locales (pour 8 personnes) : 600g de bœuf et porc haché - 100 g de dés de lard fumé - 500 g oignons _300 g champignons – 2 carottes – 2 côtes de céleri – 60 cl vin blanc – 70 cl bouillon - 60 cl purée de tomates – huile d’olive – poivre – 100 g beurre

DEBUT procédure Pelez et coupez les oignons, carottes, céleri Faire revenir ces légumes 5 min dans huile d’olive et 50g de

beurre Faire dorer les champignons puis la viande et le lard dans

une poêle avec 25 g de beurre et un peu d’huile d’olive Regrouper la viande avec les légumes .Verser le vin et

laisser mijoter 20 min à feu doux. Délayer le bouillon et la purée de tomate et ajouter à la

préparation Poivrer et laisser mijoter 1 h 30

FIN Procédure

Belahmidi (2008) 28

Algo auxiliaire :

Procédure Béchamel (quantité)Variables locales (pour 8 personnes) : 80g de farine – 1,25 l de lait - 100 g beurre – noix de muscade – sel - poivreDEBUT procédure

Faire fondre le beurre dans une casserole Ajouter la farine et mélanger pendant 2 min à feu doux Verser peu à peu le lait en remuant régulièrement Porter à ébullition pendant 5 min en toujours en remuant Poudrer de noix de muscade. Saler. Poivrer Retirer du feu et couvrer.

FIN Procédure

Belahmidi (2008) 29

Les procéduresUne procédure est un algo auxiliaire qui contient une séquence d’actions :La procédure est désignée par un nomLa procédure est appelée, une ou plusieurs fois, dans un ou plusieurs algos principaux. La procédure a besoin de variables élémentaires déclarées dans l’algo principalLa procédure renvoie, dans l’algorithme principal, un ou plusieurs résultats contenus dans des variables déclarées dans l’algo principal

Belahmidi (2008) 30

L’utilisation des procédures - Exemple

L’algorithme appelant (lasagnes) est celui qui contient l’appel aux procédures (bolognaise et béchamel ).L’algorithme appelé (bolognaise ou béchamel) utilise des variables déclarées dans l’appelant : il s’agit donc de variables globales (Nbpers)

L’algo appelé peut déclarer ses propres variables qu’il est seul à utiliser. Il s’agit de variables locales (liste ingrédients)

Belahmidi (2008) 31

L’intérêt d’utiliser des procédures est de permettre une plus grande lisibilité de l’algo principal (appelant) :

Gain de temps car cela évite d’écrire plusieurs fois la même chose. l’algo auxiliaire peut être appelé dans plusieurs algos principaux : Appelant : pizza à la bolognaise – Appelé : Bolognaise Appelant : choux fleur Sauce Mornay –Appelé : Béchamel

Mise à jour plus aisée de l’algo principal : Réduction du risque d’erreur car seul l’algo appelant est modifié

Belahmidi (2008) 32

Les fonctionsUne fonction est une procédure particulière qui ne renvoie, dans l’algorithme principal, qu’un et un seul résultat. La fonction est appelée dans l’algorithme principal, directement dans une instruction :

en général, elle apparaît dans la partie droite d’une affectation

Lors de son appel, la fonction est évaluée à partir d’arguments qui lui sont fournis

le résultat vient se substituer au nom de la fonction dans l’expression appelante

Belahmidi (2008) 33

Les fonctionsToute utilisation de la fonction

nécessite donc deux spécifications :1. Un nom2. Un ou plusieurs paramètres

Exemple : place ---- rang( pointspil ; total ;

décroissant)

Belahmidi (2008) 34

Les fonctionsIl existe deux catégories de fonctions :

1. Les fonctions standards : fonctions de base offertes par le langage utilisé

2. Les fonctions utilisateurs : Tôt ou tard, l’utilisateur devra développer ses propres fonctions à partir du langage utilisé. En effet, elles doivent répondre à un besoin précis et elles ne seront pas disponibles dans la bibliothèque du langage de programmation utilisé…

Belahmidi (2008) 35

FIN du cours d’algo

N’oubliez pas : Un bon

programme, c’est d’abord un bon

algo !