12006818
Les bases de l'algorithmique
Description
No tags specified
Slide Set by Jean-Pierre Léturgie, updated more than 1 year ago
More
Less
|
Created by Jean-Pierre Léturgie
almost 7 years ago
|
|
|
|
Copied by Jean-Pierre Léturgie
almost 7 years ago
|
|
Resource summary
Slide 1
L'algorithmique
L'algorithmique est la science des algorithmes.
Elle permet de résoudre
différents problèmes
en décrivant
les étapes de résolution.
Slide 2
Algorithme
Un algorithme est
le découpage d'une tâche
en une suite ordonnée
d'instructions élémentaires.
Slide 3
Exemple d'algorithme
Une recette de cuisine peut être considérée comme un algorithme.
La formulation est bien sûr assez libre mais elle décompose la tâche en plusieurs étapes. Chaque étape est une instruction donnée au cuisinier.
Un programme informatique est un algorithme écrit dans un langage compréhensible par l'homme et la machine.
Slide 4
Une instruction est un ordre simple.
Pour la recette de cuisine la formulation est assez libre, mais techniquement, elle se formule par un verbe à l'infinitif suivi, éventuellement, de compléments et de paramètres.
Par exemple :
TOURNER A DROITE DE 90°
STOPPER
Instruction
Slide 5
Langage
La notion de langage est très vaste : http://www.larousse.fr/dictionnaires/francais/langage/46165
Ici il n'est question que des langages informatiques qui sont très nombreux.
Il existe plusieurs types de langage permettant de faire un algorithme, certains sont textuels d'autres graphiques.
Une liste des langages informatiques est disponible sur Wikipedia.
Le format que nous avons vu précédemment se nomme PSEUDO-CODE, car il ne s'agit pas d'un langage informatique précis, les règles sont relativement libres. Nous pourrions dire que c'est du "code-like".
Il convient toutefois de respecter certaines règles d'écriture pour que l'algorithme soit compréhensible par le plus grand nombre de personnes.
A noter que La plupart des langages informatiques sont en anglais
Slide 6
Les bases algorithmique : le pseudo-code
Un algorithme peut se créer grâce à des langages textuels ou graphiques.
Certains langages sont plus proches de la machine, d'autres de l'homme, mais en fin de compte il faudra produire des instructions que comprend l'ordinateur.
Il faut donc traduire ce qu'écrit l'homme en instructions compréhensibles par l'ordinateur, des applications font cette traduction : les compilateurs et les interpréteurs. Ces applications ne peuvent fonctionner que si tout est écrit selon des règles strictes.
Le pseudo-code peut être assimilé à ces langages, même s'il n'y a pas vraiment de compilateurs ou d'interpréteurs (il existe Algobox qui a été développé dans un but pédagogique).
Nous allons voir les bases de l'algorithmique en pseudo-code.
Il vous sera facile ensuite de transposer vers d'autres langages, notamment les langages graphiques sous forme d'organigramme ou par blocs
Slide 7
Syntaxe
La syntaxe est une partie de la grammaire.
Retenons que pour un langage informatique c'est la façon d'écrire une instruction.
Par exemple en langage C (comme dans beaucoup d'autres langages), la plupart des instructions doivent se terminer par un point-virgule (;).
Les programmeurs qui utilisent ce langage sont habitués. Mais il suffit d'oublier un seul point virgule pour que le programme ne fonctionne pas.
Ne fonctionne pas ne veut pas dire qu'il donne des résultats faux mais qu'il est impossible de le traduire en langage machine, donc de l'exécuter.
Slide 8
Syntaxe d'une instruction
Le format d'une instruction est :
Verbe à l'infinitif + [complément(s)] + [paramètre(s)]
Les crochets [ ] indiquent que certains éléments sont facultatifs.
Attention ! Ceci ne veut pas dire que l'on peut toujours s'en affranchir mais que pour certaines instructions ils ne sont pas nécessaires.
Exemples :
TOURNER : il est obligatoire de dire dans quel sens,
STOPPER : peut s'utiliser seul.
Slide 9
Exemple en Pseudo-code : tracer un carré
Sujet : faire l'algorithme qui permet de tracer un carré de 4 unités de côté.
Il faut considérer que nous nous adressons à une machine. Cette dernière ne sait pas extrapoler.
Il faut donc tout lui indiquer.
Nous allons considérer qu'elle comprend certaines choses, les ordres de base, donc les instructions élémentaires que nous lui donnons.
Slide 10
Dans cet algorithme nous considérons que la machine que nous programmons comprend les ordres PRENDRE, POSER, TOURNER, DEPLACER, POSITIONNER, LEVER.
Nous considérons aussi qu'elle comprend ce que veut dire REGLE, CRAYON, FEUILLE QUADRILLEE, LIGNE et aussi qu'elle sait prendre compte certains paramètres chiffrés.
Mais l'algorithme ainsi écrit fait apparaître des séquences de lignes identiques. Nous allons considérer que la machine comprends une autre instruction REPETER x FOIS.
Tracé d'un carré : version 1
Slide 11
Tracé d'un carré : V2
Bien que nous tracions 4 côtés identiques les opérations pour tracé le premier côté sont différentes, il faut donc les effecteur à part.
Il y a ici deux exemples d'indentation (retrait des lignes) qui permettent de bien comprendre le code.
La diapositive suivante vous présente le code non indenté.
Slide 12
Tracé d'un carré v2 indentation
Caption: : L'algorithme non indenté : il est très difficile de le comprendre au premier coup d’œil !
Caption: : L'algorithme indenté permet de voir sa structure et de le comprendre plus rapidement.
Slide 13
Tracé d'un carré
Même en réduisant le code grâce à l'instruction REPETER, nous voyons qu'il y a 2 endroits où nous indiquons la longueur d'un côté. Nous ne sommes pas à l'abri d'une erreur lors de l'écriture de l'instruction.
Si nous nous trompons et mettons un mauvais chiffre dans une des instructions de déplacement il y aura alors un tracé incorrect.
Sur cet algorithme simple ceci est à 2 endroits mais parfois ce peut être à plusieurs endroits.
Imaginons aussi que nous souhaitions changer la longueur du côté de notre carré il faut penser à la changer à tous les endroits où cette valeur est utilisée, ce qui est fastidieux sur un long algorithme.
Le mieux est donc d'indiquer cette valeur en début d'algorithme..
Pour cela il faut créer une variable.
Slide 14
Variable
Une variable est une case qui contient une valeur.
A un instant T elle ne peut contenir qu'une seule valeur.
Cette valeur peut être du texte, des nombres, ...
Quand on met une nouvelle valeur elle remplace la valeur qui est présente et l'efface. Il n'y a pas d'historique.
Mettre une valeur dans une variable se nomme l'affectation. On affecte une valeur à une variable.
L'opérateur d'affectation est une flèche vers la gauche
Pour utiliser une variable il faut la déclarer (cela crée la case). La variable porte un nom.
Quand ce nom est utilisé dans l'algorithme c'est la valeur que contient la variable qui est prise en compte.
Caption: : la syntaxe que nous employons maintenant est d'écrire les noms des variables en minuscule afin de ne pas les confondre avec les instructions et leurs paramètres.
Slide 15
Variable
Caption: : Ici si nous souhaitons modifier la longueur du côté il faut modifier les 2 lignes DEPLACER. Imaginez un code de 1000 lignes avec un grand nombre de lignes utilisant la même valeur.
Caption: : Ici le seul fait de changer la valeur dans la deuxième ligne (longueur ← 4) permet que cette valeur soit prise en compte à chaque fois que l'on fait référence à la variable. Par exemple si on veut un carré de 5 de côté on remplace par longueur ← 5)
Slide 16
Les variables : connaître le contenu
Nous allons faire ce que l'on appelle faire tourner un algorithme à la main.
Nous allons construire un tableau et noter la valeur de la variable au début et à la fin chaque ligne.
Pour cela nous allons numéroter nos lignes.
Nous allons faire changer la valeur de la variable. dans l'algorithme.
Pour voir ce que cela donne nous allons "tracer" l'algorithme
Slide 17
Le point sur la syntaxe
Il est question ici de la syntaxe que nous employons dans ce cours, il n'y a pas de syntaxe officielle pour le pseudo-code. Toutefois quand on écrit un algorithme il faut respecter une syntaxe dans tout cet algorithme et ceux associés.
Les instructions et leurs paramètres sont écrits en lettres capitales,
Il n'y a qu'une instruction par ligne
le code doit être indenté
Une variable doit être déclarée grâce à l'instruction VARIABLE
Le nom des variables est écrit en minuscule
Il est possible de commenter les lignes de code :
on ajoute le signe ' devant le commentaire (ce qui suit n'est donc pas lu pour l'exécution)
Slide 18
Interactions avec l'utilisateur
Pour l'instant nous avons créé un algorithme qui trace un carré avec une longueur de côté indiquée directement dans l'algorithme.
On dit que la valeur est mise en dur dans l'algorithme.
Si l'on veut changer cette longueur nous devons modifier l'algorithme. Ce qui ne sera pas très pratique si l'utilisateur de la machine ne sait pas modifier l'algorithme.
Il faut donc que l'utilisateur et la machine puissent discuter.
Pour cela nous ajoutons 2 instructions :
AFFICHER pour que la machine envoie un message à l'utilisateur (via l'écran)
SAISIR pour que l'utilisateur envoie son message à la machine (via le clavier)
Slide 19
La syntaxe de l'instruction AFFICHER est simple.
Il faut mettre à la suite le message à afficher. Ce message peut être littéral ou être une variable ou une combinaison des 2.
Quand on affiche une variable c'est son contenu qui est affiché.
Quand un message comprends plusieurs éléments, on les sépare par une virgule.
Quand on met un texte il faut l'entourer de guillemets afin qu'il ne soit pas confondu avec une instruction ou une variable : voir la différence entre la seconde instruction et la troisième instruction ci-contre
Syntaxe AFFICHER
Slide 20
Interaction
La syntaxe de l'instruction SAISIR est très simple.
Le paramètre est le nom de la variable dans laquelle sera affecté ce qui est saisi.
L'affectation de la saisie à la variable se fait quand l'utilisateur appuie sur la touche entrée.
Vous pouvez maintenant écrire l'algorithme qui permet de demander à l'utilisateur la longueur du côté.
La solution se trouve page suivante.
Slide 21
Tracé avec interaction
Caption: : On suppose ici que l'utilisateur ne fait pas d'erreur de saisie.
Slide 22
Structure de contrôle : SI.
Nous allons maintenant considérer que nous pouvons tracer un carré seulement si la valeur saisie est supérieure à 3.
Il faut donc tester le contenu de la variable longueur.
L'instruction vérifie une condition et exécute les instructions si elle est vérifiée.
La solution se trouve page suivante.
Caption: : Syntaxe de l'instruction SI. Attention à bien respecter l'indentation.
Slide 23
Tracé du carré avec un côté > 3
Caption: :
Les instructions du tracé ne seront effectuées que si la valeur de la variable longueur est supérieure à 3.
Maintenant nous allons rajouter une condition, il faut que la longueur soit supérieure à 3 mais inférieure à 9.
Astuce : il faut imbriquer les instructions SI
Slide 24
Carré avec côté ]3.9[
L'algorithme teste en premier si le nombre saisi pour la longueur est plus grand que 3.
Si cette condition est avérée, et seulement dans ce cas, alors il teste si la longueur est inférieure à 9 et si cette seconde condition est avérée alors il trace le carré.
Nous voulons maintenant afficher un message quand le tracé ne peut être effectuer. Il faut dans ce cas utiliser une autre syntaxe de l'instruction SI, baptisée SI... ALORS...SINON....FINSI.
La solution est sur la diapositive suivante.
Slide 25
Algorithme complet du tracé d'un carré
Caption: :
Cet algorithme demandent à l'utilisateur de saisir la longueur du côté du carré.
Si la longueur saisie est supérieure à 3 et si elle est inférieure à 9 alors il trace le carré.
Si elle est inférieure ou égale à 3 il affiche le message "tracé impossible avec une longueur x qui est trop petite".
Si elle est supérieure ou égale à 9 il affiche le message "tracé impossible avec une longueur x qui est trop grande".
La façon de l'exprimer en langage courant est différente que celle utilisée dans l'algorithme
Slide 26
Plusieurs variables
Nous allons maintenant faire l'algorithme qui permet de tracer le rectangle après avoir demandé la longueur et la largeur à l'utilisateur.
Nous allons considérer que la machine possède 2 nouvelles instructions :
LIGNE qui lui permet de tracer une ligne de manière autonome (donc nous n'avons plus besoin de lui indiquer de poser la règle, de poser et de le ver me crayon,...) Cette instruction prend pour paramètre la longueur de la ligne.
Syntaxe : LIGNE [longueur de la ligne]
POSITIONNER qui permet de se positionner à un point précis grâce à ses coordonnées.
Syntaxe : POSITIONNER [abscisse],[ordonnée]
La solution se trouve sur la diapositive suivante.
Slide 27
Algorithme de tracé d'un rectangle
On commence par déclarer les variables pour réserver les cases mémoire.
Ensuite on initialise les variables pour ne pas risquer d'avoir des informations résiduelles dans la mémoire
On effectue le dialogue avec l'utilisateur
On se positionne sur le point d'origine coordonnées (0,0)
On trace les lignes.
On considère qu'en l'absence d'indication d'orientation le mouvement de tracé se fait vers la droite.
Caption: : On considère que l'utilisateur ne fait pas d'erreur de saisie.
Slide 28
Calculs
Il est bien sûr possible de faire des calculs.
Les opérateurs de calcul que nous avons à notre disposition sont
l'opérateur d'addition : +
l'opérateur de soustraction : -
l'opérateur de multiplication : *
l'opérateur de division : /
Par exemple pour additionner le chiffre 3 et le chiffre 4 on note 3 + 4, attention si on veut multiplier on note 3 * 4
On peut le faire avec des variables, supposons les variables prix et paiement, pour calculer le rendu de monnaie : paiement - prix.
Mais où va le résultat ? Il faut le mettre dans une variable : monnaie <- paiement - prix.
Faîtes l'algorithme qui trace le rectangle puis qui affiche le périmètre et l'aire du rectangle..
Slide 29
Algorithme avec calculs
Nous avons besoin de 4 variables que nous déclarons.
Nous initialisons les 4 variables.
Nous effectuons le dialogue avec l'utilisateur et enregistrons la saisie.
Nous traçons le rectangle.
Nous effectuons les calculs.
Nous affichons les résultats.
Caption: : Il est possible de mélanger des valeurs en dur et des variables dans les calculs. Les parenthèses sont utilisées avec les mêmes règles qu'en algèbre.
Slide 30
Contrôle de la saisie
On suppose que l'utilisateur ne peut saisir que des nombres.
Nous ajoutons une condition : les rectangles que nous traçons ne doivent pas être des carrés.
Nous avons vu l"instruction REPETER x fois.... FINREPETER.
Nous allons nous servir d'une instruction qui au lieu de répéter un nombre de fois défini répète jusqu'à ce qu'une condition soit remplie.
Syntaxe REPETER jusqu'à [condition]
FINREPETER
Nous avons vu les opérateurs de comparaison =, <, >.
Mais quel est l'opérateur qui permet de constater une différence, le = barré n'existe pas sur le clavier.
Les opérateur "plus petit ou égale", "plus grand ou égale" et "différent de" sont composés de 2 signes et sont respectivement <=, >= et <> (si un nombre plus grand ou plus petit il est différent)
Faîtes l'algorithme en prenant en compte la condition ci-dessus
Slide 31
Contrôle de la saisie
Dans cet algorithme on répète la demande de saisie des valeurs de la longueur et de la hauteur jusqu'à ce qu'elle soient différentes.
On indique à l'utilisateur que l'on ne veut pas qu'elles soient égales (ce manière détournée en lui disant que l'on ne veut pas saisir un carré)
Pour terminer nous allons calculer la longueur des diagonales du du rectangle.
L'opérateur qui permet d'élever un nombre à une puissance est ^
exemple : 3 au carré : 3 ^ 2
Pour obtenir la racine carrée d'un nombre on utilise la fonction
RACINECARREE(nombre)
Exemple : √ 9 : RACINECARREE(9)
Astuce, il faut utiliser le théorème de Pythagore.
Slide 32
Caption: : L'algorithme est complet. Une explication sur le calcul est donné sur la diapositive suivante.
Algorithme complet du rectangle
Slide 33
Explication du calcul
Caption: : .
Exemple avec largeur = 3 et hauteur=4
Dans la première ligne on fait le calcul de la somme des carrés de chaque côté.
Nous affectons le résultat à la variable diagonale. Donc après la première ligne diagonale vaut : 3^2 + 4^2 = 9 + 16 =25
Ensuite nous utilisons cette valeur pour calculer le résultat final puis nous affectons le résultat à la variable diagonale.
Rappel : quand on met une nouvelle valeur dans une variable cette nouvelle valeur remplace la valeur contenue dans la variable.
Le calcul est donc √ 25 = 5
Quand le calcul est fait le résultat de ce calcul est donc mis dans la case nommée diagonale donc 5 remplace 25.
Après la deuxième ligne de ce calcul la case mémoire dont le nom est diagonale contient la dernière valeur qui la été affectée soit le nombre 5.
Slide 34
Tracer un algorithme
Quand on veut savoir ce que produit un algorithme comme résultat il est intéressant de le "tracer".
Le tracer va permettre aussi de le mettre au point donc de déceler et de corriger d'éventuels dysfonctionnements (connu sous le nom de bug).
Pour tracer l'algorithme il est faut que les lignes soient repérables nous allons donc les numérotées.
Il existe pour les langages de programmation des outils que l'on nomme "débogueurs" mais là on le fait soit même on dit souvent que l'on fait tourner l'algorithme à la main.
Nous allons prendre l'algorithme du rectangle et regarder le contenu des variables après l'exécution de chaque ligne.
Caption: : L'algorithme du simple tracé d'un rectangle comprend 40 lignes.
Slide 35
Tracer un algorithme.
Dans le tableau ci-contre nous avons tracé uniquement le contenu des variables.
Quand la case est barrée d'une croix ceci veut dire que la variable n'existe pas. Quand il est marqué "vide" ceci veut dire que la variable n'a pas de contenu, donc qu'aucune valeur ne lui a été affectée.
Le lignes de commentaires ne sont pas exécuter, donc il est inutile de les tracer, pour la machine ces lignes n'existent pas.
Les répétitions, n'ont pas été marquées pour simplifier et rendre le tableau lisible mais les lignes 27, 28 et 9 devraient se trouver en double.
Pour tracer il a fallu considérer un cas pour donner des valeurs correspondantes à la saisie. Ici on considère que l'utilisateur saisi 3 pour la longueur et 4 pour la hauteur. Pour être sur de l'algorithme il aurait fallu prendre plusieurs cas de figure.
On considère que l'algorithme détruit les variables à la fin.
Caption: : Le tableau avec le contenu des variables
Slide 36
Trace de l'algorithme du rectangle
Slide 37
Trace d'un algorithme
Tracer un algorithme permet de vérifier son comportement et donc les résultats.
Il faut numéroter les lignes afin d'avoir des repères
Il faut choisir un cas de figure puis faire la trace de l'algorithme, ce qui signifie qu'il faut faire un scénario des saisies.
Il faut normalement regarder l'action de chaque ligne, Donc il se peut que l'on retrouve plusieurs fois le même numéro de ligne dans le tableau.
Un exemple est donné sur la diapositive suivante. Quand il y a des répétitions liées au scénario choisi il faut aussi trace ces répétition.s
Slide 38
Dans cet extrait du tableau correctement écrit nous voyons que les lignes 27, 28 et 29 sont répétées 2 fois.
Essayer de faire la trace de l'algorithme pour le scénario suivant :
L'utilisateur saisi 3 pour la longueur puis 3 pour la hauteur, ensuite il saisi 20 pour la longueur et 15 pour la hauteur.
Trace d'un algorithme
Slide 39
Trace d'un algorithme
Caption: : Nous voyons que les lignes 16 à 21 sont répétées car la condition longueur <> hauteur n'est pas respectée au premier passage.
Caption: : Les lignes 27, 28, 29 sont répétées 2 fois.
Slide 40
Les structures algorithmiques
A travers le pseudo-code nous avons vu les structures algorithmique.s.
Quand on traduit l'algorithme dans un langage on parle de programmation structurée.
Il y a plusieurs structures ; elles sont décrites dans les diapositives suivantes.
Pour un algorithme les structures sont souvent imbriquées les unes dans les autres.
Pour repérer les structures et leurs imbrications on utilise l'indentation.
Slide 41
Structure conditionnelle
Caption: : .
Cette structure est utilisée quand on doit effectuer certaines instructions sous condition.
Si la condition est avérée alors on exécute les instructions.
Si la condition n'est pas avérée on saute les instructions pour passer à la suite de l'algorithme., donc on passe directement après le FINSI
Slide 42
Structure alternative
Caption: : La structure alternative prévoit ce qu'il faut faire si la condition n'est pas avérée.
Elle ressemble à la structure conditionnelle, mais propose une alternative dans le cas ou la condition n'est pas avérée..
Si la condition est avérée on exécute le premier groupe d'instructions,
si elle est infirmée on exécute le tive d'instructions.
Slide 43
Structures répétitives
La première de ces structures va répéter les instruction jusqu'à ce qu'une condition soit remplie.
Attention si la condition est remplie dès le début les lignes ne seront jamais exécutées.
La seconde structure répète x fois les lignes
La dernière structutre répète les lignes indéfiniment. Elle est surtout utilisée pour les automatismes.
On appelle aussi ces structures des boucles
Caption: : Les structures répétitives sont aussi nommées des boucles.
Slide 44
Synthèse
Les algorithmes permettent de programmer des machines.
On parle de langage de programmation et de programmation structurée. :
structure conditionnelle,
structure alternative,
structure répétitive.
Les langages on des règles stricte notamment sur la syntaxe.
Les informations peuvent être contenu dans des cases mémoire appelées variables.
Chaque variable est repérée par un nom.
Une variable ne peut contenir qu'une seule valeur à un instant T
Quand on met une valeur dans une variable on dit que l'on affecte la valeur à la variable.
L'opérateur d'affectation est ←.
Les opérateurs de comparaison sont <, >, =, <=, >=, <> soit respectivement : inférieur à, supérieur à, égale à, inférieur ou égale à, supérieur ou égale à, différent de.
Les opérateurs de calcul sont +, -, *, / respectivement addition, soustraction, multiplication et division.
L'opérateur de puissance est ^
L'indentation permet de faciliter la lecture d'un algorithme et de bien distinguer les structure
Pour déboguer un algorithme on le fait tourner à la main et on trace le contenu des variables.
Want to create your own Slides for free with GoConqr? Learn more.