Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre I -II Support de cours ALORITHMIQUE II Contenu du support − Etapes de

Chapitre I -II Support de cours ALORITHMIQUE II Contenu du support − Etapes de conception d’un algorithme − Identification/Spécification d’un problème − Analyse descendante d’un problème − Algorithme et programme − Le Langage Algorithmique − Structure d’un Algorithme − Quelques structures de données élémentaires − Les actions élémentaires − Les structures de contrôle − Procédures et fonctions − Compléments sur les structures de données 2 3 Etapes de conception d’un programme Description informelle du Problème Description précise du Problème Identification du problème Analyse Programme Résultats Codage Test Langage de programmation Données Langage algorithmique Algorithme 4 L'identification d’un problème Objectif : passer d'une description non formelle du problème à traiter, à une description plus précise qui comprend : • une reformulation plus explicite et plus précise du problème comprenant le choix d'hypothèses de travail pour lever les éventuelles ambiguïtés de l'énoncé, et la liste des services que doit offrir l’application envisagée ; • la liste des données nécessaires à la résolution du problème et la réponse aux questions suivantes : Qui doit les fournir ? Faut-il les contrôler pour vérifier qu'elles sont conformes à ce qui avait été prévu ? Quel type de contrôle faut-il faire ? • la liste des résultats à fournir, ce qui suppose la réponse à la question suivante : Quelles sont les résultats pertinents à communiquer à l'utilisateur ? • l'interface avec l'utilisateur du programme (ensemble des informations visibles à l'écran) ce qui suppose la réponse aux questions suivantes : Quelles sont les informations que doit fournir l'utilisateur ? Sous quelle forme ? Quelle sont les informations qu'on doit lui communiquer ? Sous quelle forme ? Quelle est l'évolution de l'interface ? 5 Analyse descendante d'un problème Définition : « L’analyse descendante d'un problème est une démarche systématique qui part d'une expression assez générale du problème à résoudre et le décompose en taches plus simples. Chaque tâche peut faire à son tour l'objet d'une telle décomposition. Ce travail d'affinage peut être répété jusqu'à ce que tout ait été exprimé en terme d'actions assez élémentaires pour être traduit directement dans un langage de programmation. » [Meyer]. Exemple : dessiner une villa peut être envisagé progressivement comme le montre ce dessin : Cette analyse aboutit à la proposition d'une solution sous forme d'algorithmes. Villa Maison Piscine Jardin Quatre murs toit Ovale Remplir Arbres Fleurs 6 Algorithme − Définition : Un algorithme est la description d'une action complexe au moyen d'actions élémentaires et de règles de composition de ces actions. − Définition : Une action est une opération qui produit un effet prévu en un temps fini. − Exemple : Une recette de cuisine est un algorithme où les actions élémentaires sont des opérations que le cuisinier est censé savoir exécuter ("éplucher les carottes", "mettre le plat au four", etc) et les règles de composition servent à combiner entre elles ces actions élémentaires (exécuter telle action après telle autre, attendre un certain temps avant telle action, répéter telle action un certain temps, etc). − Remarque : En général, il existe plusieurs algorithmes pour résoudre un même problème. Nous privilégierons ici les solutions simples, facile à comprendre. − Un algorithme destiné à devenir un programme, c’est à dire à être traité par un ordinateur doit être formulé dans un langage précis, i.e défini par : un lexique, une syntaxe et une sémanti- que. − Définition : Un programme est un algorithme exprimé dans un langage de programmation i.e. compréhensible par une machine. 7 Le Langage algorithmique Un langage algorithmique se définit en précisant : • le type d'objets que peut manipuler l'algorithme : les structures de données. • la manière de décrire ces objets : déclarations. • l'ensemble des actions élémentaires en indiquant leur syntaxe et leur sémantique. • l'ensemble des règles de composition (ou structure de contrôle) en indiquant leur syntaxe et leur sémantique. Structure d’un algorithme (I) Structure d'un algorithme Algorithme <nom de l'algorithme> Déclarations constantes <identificateur de constante 1> = <constante 1>{<rôle de la cste 1>} .... <identificateur de constante n> = <constante n>{<rôle de la cste n>} types <identificateur du type 1 > = <définition du type 1>{<rôle du type 1>} … <identificateur du type o>=<définition du type o>{<rôle du type o>} variables <identificateur de variable 1> : <type 1> {<rôle de la variable 1>} ... <identificateur de variable p> : <type n > {<rôle de la variable p>} Debut <Action complexe : composition d’actions élémentaires> Fin 8 Structure d’un algorithme (II) Algorithme calcul_salaire { cet algorithme calcule le salaire brut à partir du salaire de base et de la prime} Déclarations variables salaire_de_base : reel prime : reel salaire_brut : reel Debut {Préparation du traitement : saisie des données} écrire ("donnez le salaire de base") lire (salaire_de_base) écrire ("donnez la prime") lire (prime) {calcul du salaire brut} salaire_brut<-salaire_de_base + prime {affichage des résultats} écrire ("Le salaire de base étant de", salaire_de_base, "et la prime de", prime, "le salaire brut est donc de ", salaire_brut) Fin Mémoire Salaire_de_base prime Salaire_brut 9 10 Quelques structures de données élémentaires − Etapes de conception d’un algorithme − Identification/Spécification d’un problème − Analyse descendante d’un problème − Algorithme et Programme − Le Langage Algorithmique - Structure d’un algorithme - Quelques structures de données élémentaires - Les actions élémentaires - Les structures de contrôle - Procédures et fonctions 11 Quelques structures de données élémentaires (I) Les types Un type est défini par : 1) un ensemble de valeur, et 2) un ensemble d'opérations applicables aux éléments de cet ensemble. Exemple : Le type entier sera défini par : • un sous-ensemble fini de Z • et notamment les opérations suivantes : addition, soustraction, division, reste, etc. Les constantes Une constante est un objet non modifiable par l'algorithme. Une constante est définie lorsqu'on a précisé son nom et sa valeur constante. Exemple : Au lieu de manipuler dans un algorithme la valeur 0.055 correspondant à un taux TVA, il est plus clair d'employer un identifiant pour le désigner, par exemple CodeTva. Cela va permettre : 1) de modifier plus facilement l'algorithme 2) d'indiquer le rôle de cette valeur puisque l'identifiant est plus explicite. Les variables Une variable est une objet modifiable par l'algorithme. Elle est définie lorsqu'on a précisé : son nom(ou identificateur), son type, son rôle. Par définition, une variable peut prendre plusieurs valeurs au cours de l'exécution d'un algorithme. Mais à un instant donné elle ne peut avoir qu'une valeur. 12 Quelques structures de données élémentaires (II) Identificateur : Il faut s'efforcer de choisir des identificateurs explicites c'est à dire en rapport avec ce qu'il représente ( on préférera "age" à X si on doit représenter l'age d'un individu). Syntaxiquement, un identificateur peut être décrit par une suite non vide de caractères respectant les conditions suivantes : 1) il ne doit pas contenir de caractères délimiteurs : espaces, parenthèses, guillemets, ... 2) il ne doit pas appartenir au mot réservé du langage ; 3) il doit commencer par une lettre. Remarques : • En cours d'exécution, une variable ne peut recevoir que les valeurs associées à son type. • Le rôle d'une variable est un commentaire facultatif (mais que nous conseillons) qui explicite l'utilisation qui est faite de la variable. 13 Quelques structures de données élémentaires (III) - La partie déclaration d'un algorithme Tout algorithme commence par la définition des objets qu'il manipule. Comme dans une recette on met toujours les ingrédients nécessaires en tête de la recette : 1 livre de farine, 1kg de belles tomates, ... Dans un algorithme la déclaration se fait selon la syntaxe suivante : Déclarations constante <identificateur de constante 1> = <constante 1>{<rôle de la constante 1>} .... <identificateur de constante n> = <constante n>{<rôle de la constante n>} types <identificateur du type 1 > = <définition du type 1>{<rôle du type 1>} … <identificateur du type o>=<définition du type o>{<rôle du type o>} variable <identificateur de variable 1> : <type 1> {<rôle de la variable 1>} ... <identificateur de variable p> : <type n > {<rôle de la variable p>} Exemple : Déclarations constante Taux_Tva = 0.055 {représente le taux tva utilisé dans le contexte du problème posé} variable Quantité : entier {indique le nombre d'articles commandés} Prix_HT: réel {indique le prix unitaire hors taxes de chaque article} 14 Quelques structures de données élémentaires (IV) - Les types prédéfinis élémentaires Ce sont des types que l'on retrouve dans la plupart des langages. La machine sait les représenter et offre des fonctions pour les manipuler. Entier : C'est un sous-ensemble fini de Z (par exemple de [-32768, 32767]). Les opérations possibles sur les entiers sont définies par : +, -, *, div(division entière), ^(puissance), mod(RESTE), abs(valeur absolue), sqr(carré) … Réel : ensemble des valeurs numériques non forcément entières que la machine sait représenter. Les opérations possibles sur les réels sont définies par : +, -, *, /, ^, abs (valeur absolue), int (partie entière), sqr (carré), sqrt (racine carrée). Chaîne de Caractères : ensemble des caractères que la machine reconnaît (jeu de caractères fait de lettres, de chiffre, ....). On convient de distinguer les uploads/s3/ support-ch1-2.pdf