Analyse et programmation 1
Techniques algorithmiques
Thmes abords
Comment concevoir un algorithme Quelques Q l techniques t h i algorithmiques l ith i usuelles ll
Analyse et programmation 1 - Techniques algorithmiques
Comment concevoir un algorithme
Mthodologies Quelques Q l techniques t h i d de conception ti
Les organigrammes Les structogrammes Le pseudo code
Analyse et programmation 1 - Techniques algorithmiques
Mthodologies
Nature du problme
Les acteurs de la ralisation dun programme
Lutilisateur L utilisateur : connat le besoin, besoin de faon informelle informelle. Le programmeur : connat (plus ou moins) la programmation. Besoin dun outil de communication entre les deux.
Les cahiers des charges
Sont en gnral de haut niveau. Exemple : piloter une machine de production.
Les instructions disposition
Sont de trs bas niveau. Exemple : if, for, i++
Problme du programmeur dapplication
Comment passer du cahier des charges aux instructions en C.
Analyse et programmation 1 - Techniques algorithmiques
Mthodologies
Prsentation
Solution : utiliser une mthodologie
Dfinir des notations
Si possible comprhensibles par le programmeur et lutilisateur.
Proposer une dmarche
Cheminement pour la rsolution des problmes.
Constat
Il existe des dizaines de mthodologies. Les mthodologies ne savent pas programmer notre place. La programmation reste un art difficile. difficile
Ncessite de la pratique.
Une mthodologie
Peut vous proposer un cadre formel. Ne peut pas rflchir votre place.
Analyse et programmation 1 - Techniques algorithmiques
Comment trouver un algorithme ?
Pour analyser un problme
Commencer par le rsoudre rso dre la main main.
Papier, crayon.
Une fois quune dmarche est trouve, analyser tape par tape ce que vous faites. Identifier ensuite les structures de contrle. Et noter les grandes lignes de lalgorithme.
Est Est-ce ce efficace de perdre du temps rflchir ?
Une fois que le bon algorithme est trouv, la programmation devient un simple problme de traduction. Une fois les bases du langage assimiles, la programmation prend peu de temps.
Analyse et programmation 1 - Techniques algorithmiques 5
Les organigrammes
Prsentation
dbut dbut
Reprsentation graphique dun d un algorithme
Rectangle : instruction. Losange : dcision. Flches : saut
Mot
Gauche := 1 ; Droite := N ;
vrai Gauche >Droite? faux Milieu := (Gauche + Droite) / 2 "PAS TROUVE" fin
vrai Dico (Milieu) = Mot? faux Dico (Milieu) < Mot? faux Droite:= Milieu - 1 Milieu fin
vrai Gauche:= Milieu + 1
Analyse et programmation 1 - Techniques algorithmiques
Les organigrammes
Symboles
squence action 1 action 2 action 3
alternatives condition vrai action 1 action 2 faux
itrations action 2
condition
Analyse et programmation 1 - Techniques algorithmiques
Les organigrammes
Analyse
Permettent de reprsenter des algorithmes simples
Exemple E emple : reprsenter le fonctionnement dune d ne instr instruction. ction Devient vite difficile lire sur des problmes rels.
Encore utiliss en assembleur
Traduit bien les instructions machine
Traduisent mal la programmation structure
Les branchements traduisent goto Pas de symbole reprsentant for, while, do while
Pratique industrielle en langage volu
Peu rencontr sur des projets professionnels.
Donc
Analyse et programmation 1 - Techniques algorithmiques 8
Les structogrammes
Nassi Shneiderman Diagram (NSD) - Prsentation Reprsentation graphique des structures de contrle, invente en 1972.
L Limbrication imbrication graphique traduit limbrication l imbrication logique. logique Diffrents symboles pour les structures de contrle habituelles.
squence
1er bloc structurel oui 2me bloc structurel 3me bloc structurel THEN - bloc ELSE - bloc
Alternative
Condition non
itration
DO WHILE (condition)
imbrication
1er bloc structurel 2me bloc structurel 3me bloc structurel
Bloc rptitif
Analyse et programmation 1 - Techniques algorithmiques
Les structogrammes
Illustration
DO WHILE ( (condition) )
Condition oui non
1er bloc structurel
1er bloc structurel
2me bloc structurel
2me bloc structurel
3me bloc structurel
3me bloc structurel
Analyse et programmation 1 - Techniques algorithmiques
10
Les structogrammes
Analyse
Permettent de reprsenter des algorithmes structurs Traduisent T d i t bien bi l la programmation ti structure t t
Montrent la dcomposition hirarchique. Bonne faon de rflchir.
Limitations
Des niveaux dimbrication multiples deviennent peu lisibles. Un outil ddition est indispensable (ou alors une bonne gomme).
Pratique industrielle en langage volu
Peu rencontr sur des projets professionnels.
Donc
Analyse et programmation 1 - Techniques algorithmiques
11
Le pseudo code
Prsentation Principe du pseudo code
Pseudos instructions traduisant les structures de contrle.
SI . . . ALORS . . . SINON . . . SELECTION SUR I . . . 1 => . . . 2=> FAIRE . . . TANT QUE . . . TANT QUE . . . FAIRE
Indpendance par rapport la syntaxe relle du langage cible. On laisse de ct laspect dclaration des variables. Moyen rapide et simple de structurer ses ides.
Exemple
FAIRE Saisir X SI X < 0 ALORS Afficher un message derreur TANT QUE X < 0
Analyse et programmation 1 - Techniques algorithmiques
12
Le pseudo code
Table de symboles
Variables utilises dans le pseudo code
Dans les cas simples simples, le type et le rle dune d une variable sont vidents. vidents Dans les autres cas, il faut crire une table de symboles.
Table de symboles
Elle prcde le pseudo code Elle prcise
Le nom de lobjet : X Sa nature (variable, constante) : Son type de donnes : rel, rel entier entier, Un descriptif quand le nom nest pas assez explicite.
Correspond aux dclarations de variable
Exemple
Somme : rel, accumulateur pour la somme des rels saisis
Analyse et programmation 1 - Techniques algorithmiques 13
Le pseudo code
Analyse
Avantages
Trs similaire a au code final Donc, pas deffort de traduction particulier. Trs efficace, on ignore les exigences syntaxiques du langage cible. Structur. Documente lalgorithme pour les volutions futures. Ne ncessite aucun outil particulier.
Inconvnients
Laisse beaucoup (trop) de libert. Textuel : permet certaines ambiguts.
Analyse et programmation 1 - Techniques algorithmiques
14
Mthodologie
Quelle approche choisir
Lorsque le problme est compliqu
Prfrer lapproche base sur s r le pseudo pse do code code. Utiliser dautres formalismes
Lorsquils contribuent vraiment la comprhension. Ou comme outil de communication.
Lorsque le problme est assez simple
Lalgorithme peut tre conu directement au niveau du code. Pratique industrielle : cest c est le cas courant. courant
Un algorithme doit tre clair avant dtre programm.
La programmation directe dun algorithme devient possible avec la pratique.
Analyse et programmation 1 - Techniques algorithmiques
15
Mthogologie
Comment choisir la structure de contrle adapte
Squence
Solution gnrale Dans une expression Conditions boolennes
Liste dinstructions Oprateur , if switch Oprateur ? : for while do while
Enchaner des traitements
Algorithme
Choisir un traitement
Slection
Valeur dun entier Evaluation selon condition Nombre connu de fois
Rpter un traitement
Itration
Selon condition Au moins une fois, puis selon condition
Analyse et programmation 1 - Techniques algorithmiques
16
Quelques techniques algorithmiques usuelles
Le comptage L Laccumulation l ti La recherche dextremum Les rptitions imbriques
Analyse et programmation 1 - Techniques algorithmiques
17
Techniques algorithmiques usuelles
Lchange de variables
Contexte
2 variables ariables contiennent des valeurs ale rs diffrentes diffrentes. On veut changer leurs valeurs.
But
Utile pour de nombreux algorithmes. Exemples
Ordonner 2 nombres. Rtablir les bornes d dun un intervalle. intervalle
Analyse et programmation 1 - Techniques algorithmiques
18
Techniques algorithmiques usuelles
Lchange de variables Implmentation nave
int main() { int i, j; printf("Saisir 2 entier :"); scanf("%d%d", &i, &j); if (i > j) { i et j contiennent finalement la mme valeur. i = j; La valeur initiale de i est perdue !!! j = i i; } printf("Dans lordre croissant : %d, %d\n", i, j); _getch(); return 0; }
Analyse et programmation 1 - Techniques algorithmiques 19
10
Techniques algorithmiques usuelles
Lchange de variables
Implmentation fonctionnelle
int main() { int i, j, tmp; printf("Saisir 2 entier :"); scanf("%d%d", &i, &j); if (i > j) { tmp = i; 1. On conserve la valeur initiale de i dans tmp. i = j; 2 2. On copie la valeur de j dans i i. 3. On copie la valeur initiale de i dans j. j = tmp; } printf("Dans l'ordre croissant : %d, %d\n", i, j); _getch(); return 0; }
Analyse et programmation 1 - Techniques algorithmiques 20
Techniques algorithmiques usuelles
Le comptage
But : compter un nombre dlments par programme. Exemples E l
Protocole de communication :
le nombre de caractres dun message. le nombre de messages reus.
Caisse enregistreuse : nombre darticles.
Le comptage peut tre
Systmatique : prend en compte tous les objets. objets Slectif : teste une condition sur lobjet avant de le comptabiliser.
Analyse et programmation 1 - Techniques algorithmiques
21
11
Techniques algorithmiques usuelles
Le comptage - illustration int nombre_e; char c a c; printf("Saisissez une ligne de texte:\n"); nombre_e = 0; do { scanf("%c", &c); if ((c == 'e') || (c == 'E')) nombre e++; nombre_e++; } while (c != '\n'); printf("Cette ligne contient %d caracteres e ou E.\n", nombre_e);
Analyse et programmation 1 - Techniques algorithmiques
22
Techniques algorithmiques usuelles
Laccumulation
But : faire la somme dlments par programme. Exemples E l
Caisse de parking :
somme des pices de monnaie introduites par un client. somme des pices de monnaie dans la caisse.
Machine dassemblage
Quantit totale de colle dj utilise
Calcul de moyenne
En combinaison avec un comptage
Laccumulation peut tre
Systmatique : prend en compte tous les objets. Slective : teste une condition sur lobjet avant de le comptabiliser.
Analyse et programmation 1 - Techniques algorithmiques 23
12
Techniques algorithmiques usuelles
Laccumulation - illustration
int valeur_piece; int i; int somme; const int PRIX_PLACE = 200; // 2 Francs somme = 0; while (somme < PRIX_PLACE) { printf("Valeur de la piece de monnaie en centimes :"); scanf("%d", &valeur_piece); if (valeur_piece (valeur piece >= 10) somme += valeur_piece; else printf("piece refusee\n"); } printf("Prenez votre ticket\n");
Analyse et programmation 1 - Techniques algorithmiques 24
Techniques algorithmiques usuelles
Recherche dextremum
But : rechercher le plus petit ou le plus grand lment dune d une collection par programme. programme Exemples
Station mto, thermomtre lectronique de conglateur :
Mmoriser les tempratures minimales et maximales.
Systme dinformation de lcole
Trouver ltudiant le plus mritant
Analyse et programmation 1 - Techniques algorithmiques
25
13
Techniques algorithmiques usuelles
Recherche dextremum - illustration
int int int for { valeur; i; minim m ma minimum, maximum; im m (i = 1; i <= 10; i++) printf("Mesure de temperature n %d :", i); scanf("%d", &valeur); if (i == 1) { minimum = valeur; maximum = valeur; } else if (valeur < minimum) minimum = valeur; else if (valeur > maximum) maximum = valeur; } printf("Temperature minimum: %d\n", minimum); printf("Temperature maximum: %d\n", maximum);
Analyse et programmation 1 - Techniques algorithmiques 26
Techniques algorithmiques usuelles
Rptitions imbriques
But :
Rpter plusieurs pl sie rs fois un n traitement traitement, l lui i mme constit constitu d dune ne rptition.
Exemples
Machine de soudage :
Produire 100 pices Pour chaque pice, effectuer 15 points de soudure.
Afficher les tables de multiplication p
10 tables de multiplication Pour chaque table, 10 multiplications.
Analyse et programmation 1 - Techniques algorithmiques
27
14
Techniques algorithmiques usuelles
Rptitions imbriques - illustration int i, j; for (i = 1; i <= 10; { printf("Table de for (j = 1; j <= printf("%d x printf("\n"); }
i++) %d\n", i); 10; j++) %d = %d\n", i, j, i * j);
Analyse et programmation 1 - Techniques algorithmiques
28
Techniques algorithmiques usuelles
Rptitions imbriques pige classique Utilisation de la mme variable pour 2 boucles imbriques
for (i ( = 1; ; i <= 10; ; i++) ) for (i = 1; i <= 5; i++) // Probleme ! { . . . . }
Ne pas confondre avec deux boucles conscutives
for (i = { . } for (i = { . } 1; i <= 5; i++) // pas de probleme . . . 1; i <= 5; i++) // pas de probleme . . .
Analyse et programmation 1 - Techniques algorithmiques
29
15
Quavons-nous appris ?
Comment formaliser un algorithme
Graphiq Graphiquement ement : organigramme organigramme, str structogramme. ctogramme Textuellement : pseudo code
Technique algorithmiques courantes
Comptage Accumulation Recherche dextremum Rptitions imbriques
Analyse et programmation 1 - Techniques algorithmiques
30
Vos questions
Analyse et programmation 1 - Techniques algorithmiques
31
16
Analyse et programmation 1 - Techniques algorithmiques
32
17
