Algorithmique

I-Gnralit : 1) Dfinition : - Algorithme = suite de raisonnements ou doprations qui fournit la solution certains problmes. - Algorithmique = mthodologie de conception de traitements indpendamment de la machine qui leffectuera (indpendant dun langage de programmation, dun systme, du processeur utilis). Langage algorithmique : franais structur (adapt) 2) Chane de production de programmes : programmation

nonc du problme, donnes

Analyse

Algorithme

Programme source

algorithmique

Langage machine objet

compilation

Module excutable

excution

Rsultats

nonc du problme : - ce que lon veut faire - le rsultat final obtenir Analyse : - avec quoi obtenir ce rsultat ? - comment lobtenir ? - hypothses pour raliser lnonc Algorithme : - obtention dun traitement qui partir des hypothses rsout le problme Principales tapes : a) prparation du traitement : . indiquer et acqurir les donnes . vrifier leur cohrence b) traitement : . rsolution du problme pas pas aprs dcomposition en sous problme si ncessaire

c) dition des rsultats : . affichage des rsultats programmation : - choix dun langage - codage de lalgorithme dans ce langage en suivant la chane dexcution du programme remarque : 2 principales sortes dalgorithmique - non numrique, les rsultats ne sont pas des calculs - numrique, les rsultats sont des calculs II-Algorithmique : 1) Structures algorithmique (structure de contrle), squence (slection) rptition. 3 structures de base qui dfinissent tous les enchanements possibles excuter. a) Squence : Suite ordonne dactions excutes les unes la suite des autres. Ex : algorithmique pour planter un arbre. 4 actions lmentaires : creuser un trou, placer larbre dans le trou, reboucher le trou, arroser larbre. Syntaxe algorithmique : DEBUT Creuser un trou Placer larbre dans le trou Reboucher le trou Arroser larbre FIN

Remarque : ordre des actions trs important

b) Slection (structure alternative) : Sert exprimer un choix dexcution entre 2 sries dactions suivant une condition. Syntaxe : SI <condition> ALORS <action1> SINON <action2> FSI Si la condition est vraie, laction 1 est excute, pas la 2 Si la condition est fausse, laction 2 est excute, pas la 1 Ex : SI le sol est dur, ALORS Je prends une pioche SINON Je prends une bche FSI Je creuse un trou Syntaxe : Si <condition> alors <action1> FSI Remarque : -action 1 et/ou 2 peuvent se voir remplacer par une squence -il existe une structure de slection qui ne comporte pas de partie sinon. Dans ce cas, seule laction 1 est excute, sinon on passe directement la suite. Ex : Si je nai pas doutils, alors jen prends un. FSI Jutilise loutil

c) Rptition : Rpter un certain nombre de fois une action (ou une squence dactions). BOUCLE TANT QUE : Syntaxe : TANT QUE <condition> FAIRE <action> FTQ On rpte laction jusqu ce que la condition actuelle soit contraire la condition du problme. Ex : TANT QUE il reste un arbre planter FAIRE Planter un arbre Remarque : viter les boucles infinies, il faut que la partie FTQ <action> ait une influence et modifie <condition> BOUCLE POUR : Rpte un nombre de fois dtermin priori une action. Syntaxe : POUR <compteur> DE <valeur 1> A<valeur 2> FAIRE <action> FPOUR Ex : POUR un nombre darbre de 1 10 FAIRE Planter un arbre FPOUR Remarque : chaque tape, la valeur du compteur est => on plante 10 arbres incrmente de 1. BOUCLE RPTER JUSQU : Syntaxe : REPETER <action> JUSQUA <condition> . on rpte laction jusqu ce que la condition soit vraie . la diffrence avec TANT QUE est que la condition est teste aprs excution de laction => laction est toujours excute au moins une fois. Ex : REPETER planter un arbre JUSQUA plus darbre planter Remarque : laction doit influencer la condition pour viter une boucle infinie.

Imbrication et mlange de toutes les structures de base pour concevoir tout algorithme. d) Exemple d algorithme : 10 fleurs bleues et 10 fleurs jaunes : algorithme pour planter les fleurs. Fleurs bleues : bac 1 Fleurs jaunes : bac 2 4 actions lmentaires : prendre une fleur, planter une fleur bleue dans le bac 1, planter une fleur jaune dans le bac 2, arroser les fleurs. Syntaxe : MODULE planter 20 fleurs * planter des fleurs jaunes et bleues * DEBUT POUR nombre de fleurs de 1 20 FAIRE Prendre une fleur * choisir le bac * SI la fleur est bleue ALORS la planter dans le bac 1 SINON la fleur est jaune ALORS la planter dans le bac 2 FSI Arroser les fleurs FPOUR FIN 2) Mthode de conception (mthode des raffinages successifs) : On crit un premier algorithme grossier cest dire dans lequel certaines parties ne sont pas dtailles. Ex : 1er niveau DEBUT Faire un caf FIN Dans les algorithmes successifs on dtaille les instructions grossires jusqu tomber sur les instructions lmentaires. Ex : 2me niveau de raffinage DEBUT * faire un caf * Prendre une tasse

3me niveau de raffinage * lancer la machine * SI la machine est teinte ALORS Allumer la machine FSI Vrifier le niveau deau Vrifier le niveau de caf

La mettre dans la machine Lancer la machine Rcuprer la tasse FIN

III- Algorithme numrique : 1) Variable : Un algorithme est amen oprer sur des flux dinformations. . Il produit des rsultats (infos de sortie) ) partir de donnes (infos en entre). . Un algorithme doit pouvoir oprer sur tous les jeux de donnes pour lequel il est construit. Les infos traites sont reprsentes par des variables. Une variable recoupe la notion de contenant et de contenu. Contenant => identificateur Contenu => information Chaque variable possde 3 qualificatifs : . identificateur = nom de la variable, explicite et unique . type des valeurs = notion voisine de celle des ensembles mathmatiques. Ensemble des valeurs que peut prendre la variable. Ex : module de traitement. . valeur = lment du type qui donne la valeur courante de la variable. La dfinition des algorithmes doit tre faite en dbut dalgorithme sous forme de glossaire. Ex : MODULE traitement GLOSSAIRE Un entier : variable de type entier Var rel : variable de type rel DEBUT <instructions> FIN 2) Instructions sur les variables : a) Affectation : Donne une valeur la valeur considre Oprateur <= Ex : MODULE calcul GLOSSAIRE n : variable de type entier z : variable de type entier

t : variable de type entier DEBUT n<=3 z<=n t<=n+z-6 n<=n+z FIN * n reoit la valeur 3 * * z prend la valeur de n * * t rsultat dun calcul * * n reoit lancienne valeur de n+z *

Toute variable cre possde une valeur indtermine => ncessit de lui affecter une premire valeur avant tout calcul.

b) Opration dentre (de lecture) : LIRE CLAVIER n Affecte une valeur n depuis le clavier. c) Opration de sortie (dcriture) : ECRIRE ECRAN les valeurs de n et z sont , n, z Affiche lcran le message entre apostrophes et les valeurs de n et de z. 3) Structures de contrle : Comme pour le non-numrique. BOUCLE ET TRACE : Ex : * affichage des 3 premiers nombre pars * MODULE nombres pairs n, i : variables de type entier DEBUT N <= 3 I <= 1 TANT QUE i<=n (infrieur ou gal) FAIRE AFFICHER ECRAN 2*i I <= i + 1 FTQ FIN

On met une sonde ici (on regarde les valeurs courantes des variables)

. La condition de la boucle contient des variables. chaque itration de boucle, certaines Passage dans Valeur de i Valeur de n valeurs peuvent tre modifies. la boucle . But : on veut vrifier que la boucle s'arrte un certain moment. 1 3 Avant le 1er passage 1er passage 2me passage 3me passage 4me passage 3 4 1 3 3 3 3

Autre algorithme valide avec une boucle POUR : MODULE nombres pairs 2 GLOSSAIRE n, i : variable de type entier DEBUT n <= 3 POUR i de 1 n FAIRE AFFICHER 2*i FPOUR FIN IV-Gnralits : fonctions et procdures : 1) Gnralits : fonctions et procdures. Un sous-programme est un ensemble d'instructions regroupes qui ralisent un traitement spcifique. But : viter la rptition de calculs identiques ou compltement identique, de certaines variables. Certaines expressions changent mais la structure squentielle du sous- programme reste la mme. Avantage : rend possible la mise au point de parties indpendantes sparment => dcomposer un problme complexe en une somme de problmes simples. Il y a 2 types de sous- programmes : procdures et fonctions. 2) Procdures : a) Notion de bote noire qui communique avec l'extrieur . recevoir des informations . fournir des informations

Ex : procdure SOMME de 2 nombres a et b a b SOMME a+b

Communication avec l'extrieur grce une interface de communication. b) Dfinition (dclaration) d'une procdure : PROCEDURE somme (a, b, rsultat) GLOSSAIRE a, b : paramtres par valeur (entre) de type entier rsultat : paramtre par rfrence (sortie) aux : variable interne de type entier DEBUT aux <= a + b rsultat <= aux FIN Somme : nom de la procdure (<entre parenthses>) liste de paramtres pour la communication sous-programme <=> extrieur. GLOSSAIRE : description des paramtres et des variables de la procdure. paramtres : ils font partis de l'interface de communication. variables internes : elle font uniquement parties du sous- programme pour les calculs internes. Paramtres : ensemble des objets par lequel le sous- programme peut communiquer avec l'extrieur. . par valeur (entre) : ces paramtres reoivent une valeur depuis l'extrieur qui leur sert lorsque le sous- programme est activ. . par rfrence (sortie) : fournissent les valeurs vers l'extrieur de la procdure (ces paramtres peuvent parfois recevoir une information de l'extrieur). DEBUT...FIN : liste des instructions du sous- programme. c) Appel (utilisation) du sous- programme par le programme : Correspond l'endroit o le programme se sert du sous- programme pour faire des calculs. Ex : MODULE calcul GLOSSAIRE X, z : variables de type entier DEBUT ECRIRE ECRAN "entrez la valeur de x" LIRE CLAVIER x * on demande au sous- programme SOMME d'ajouter 4 x et de le mettre le rsultat dans z * SOMME (x, 4, z) ECRIRE ECRAN "z =", z

FIN Fonctionnement de l'appel de la procdure : (1)droulement de la procdure (2)appel de la procdure (3)lien dynamique entre les variables du programme les paramtres du sous- programme (4)droulement des instructions de la procdure (5)retour au programme principal (6)continuation du programme et
(2)appel de somme (x, 4, z) (6) (5) (3) (a, b, rsultat) dbut sousprogramme (4) fin sousprogramme

Programme
dbut (1)

Sous-programme

2) Lien entre les variables du programme et les paramtres : SOMME (x, 4, z) Variables + lments du programme va donner sa valeur x va donner sa valeur 4 va donner sa valeur z paramtres du sous- programme a
entre entre sortie

b rsultat

Lien d'entre : le sous-programme acquiert des informations depuis l'extrieur. Lien de sortie : le sous- programme transmet des informations vers l'extrieur, ainsi toute modification de la valeur du paramtre rsultat modifiera la valeur de la variable z du programme. Remarque : . passage par valeur : les paramtres a et b ont acquis une valeur. Si elles sont modifies par le sous- programme, alors ces changements n'affectent pas les variables extrieures qui sont lies. Ex : Programme x 12 Sous-programme a 12 A <= 128 128 48 Programme z Sous-programme rsultat rsultat <= 48 48 rsultat <= 312 312

12

312

. la correspondance lments du programme <=> paramtres se fait suivant leur ordre de dclaration. Ici : x <=> a a <=> b z <=> rsultat . une procdure peut ne retourner aucun rsultat (affichage) ou bien n'avoir aucun paramtres d'entre (lecture d'une variable complexe). 3) Fonctions : a) Dfinitions : Fonction : sous- programme qui retourne toujours un rsultat (paramtre par rfrence) que l'on a particularis et qui fait partie de la df. de la fonction. Avantage : ce rsultat particulier est Type du paramtre par rfrenceles la fonction directement utilisable dans li calculs (fonctions mathmatiques). b) Dclaration : FONCTION somme2 (a, b) : de type entier GLOSSAIRE A, b : paramtres par valeur entier DEBUT Retourne (a + b) FIN
Donne un rsultat au paramtre particulier et termine la fonction

c) Utilisation/appel : MODULE calcul2 GLOSSAIRE x : variable de type entier DEBUT x <= somme2 (3, 4)*12 FIN
Le rsultat particulier est utilis directement

V-Types et variables compos : 1) Tableaux : a) Tableau une dimension (vecteur) :

Suite contigu d'lments de mme type. Ex : tableau d'entier tableau de caractres

Reprsentation : ensemble de cases dont chacun contient une valeur. Toutes ces valeurs sont de mme type. mon_tableau : -2.3 #0 -0.8 #1 0.0 #2 0.1 #3 8.1 #4 9.6 #5 18 #6

Dclaration d'une variable de type tableau : mon_tableau : variable de type tableau 7 cases rels.
identification type nombre de cases Type de chaque case

Chaque case est repre par un indice entier. La 1re case a pour indice #0. La dernire case a pour indice #nombre de cases 1. Accs au contenu d'une case : oprateur [ ] Ex : mon_tableau [3] <= 3.3 : changer la valeur de la case 3 par 3.3 mon_tableau [2] : afficher la valeur qui se trouve l'indice #2. b) Tableaux 2 dimensions (matrices) . Extension des tableaux une dimension . 2 indices commenant chacun 0 reprent une case. Ex : ma_matrice : variable de type tableaux de rels, de 3 lignes et de 4 colonnes. #0 #0 #1 #2 i, j : variables de type entier -2.3 18 1.3 #1 -0.8 17 -9.8 #2 0.0 9.6 0.9 #3 0.1 8.1 0.5
indice

i <= 1 j <= 2 Afficher cran ma_matrice [i] [j]

(=> affiche 9.6)

Remarque : il existe des tableaux 3, 4, N dimensions. 2) Structures ou enregistrements : Regroupement dans une mme variable d'un ensemble d'objets qui peuvent tre de types diffrents. Chaque lment (ou champ) est dclar avec son type. TYPE personne_type : structure compose de Nom : tableau de 100 caractres Age : entier Num. scu : entier Adresse : tableau de 200 caractres FIN

Cration d'un nouveau type qui se comportera comme les types prdfinis (entiers, rels, caractres, ...) Dclaration d'une variable dont le type a t dfini auparavant. Personne_1 : variable de type personne_type (type cr par l'utilisateur) Nom : ... Age : ... Num. scu : ... Adresse : ... Personne_2 : variable de type personne_type Nom : ... Age : ... Num. scu : ... Adresse : ... Remarque : personne_1 (comme personne_2) regroupe un ensemble de champs manipuls de faon in dissocie. Accs un champ d'une variable de type structure : Utilisation de l'oprateur "." <nom_variable>.<nom_champ> Ex :

Personne_1.Age <= 21 * Personne_2 a 2 ans de plus que Personne_1 * Personne_2.Age <= Personne_1.Age +2 Personne_1.Nom <= "Dupont" n : variable entire n <= Personne_2.Age Remarque : tableaux et renseignements sont appels constructeurs de types car ils permettent de dfinir des types nouveaux (non dfinis dans le langage) utilisables par la suite pour dfinir des variables dans l'algorithme dcrit. Une fois dfinies, les variables de ces nouveaux types s'utilisent comme des variables classiques => elles peuvent intervenir comme paramtre et pour le passage de paramtres aux sousprogrammes. Il est possible de crer des tableaux dont chaque case a un type de structure. Ex : tableau de 50 personnes Une structure peut avoir des champs qui sont des tableaux.