Algorithme

omment faire un travail sans la moindre ambiguïté

- langage simple : des instructions (pas élémentaires) - suite finie d'actions à entreprendre en respectant une chronologie imposée

• L’écriture algorithmique : un travail de programmation à visée «universelle»

un algorithme ne dépend pas - du langage dans lequel il est implanté, - ni de la machine qui exécutera le programme correspondant.

Algorithmique 1 : Introduction 6

Les problèmes fondamentaux en algorithmique

• Complexité

- En combien de temps un algorithme va -t-il atteindre le résultat escompté? - De quel espace a-t-il besoin?

• Calculabilité :

- Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ? - Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?

• Correction

- Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu?

Algorithmique 1 : Introduction 7

Les instructions de base

Algorithmique 1 : Instructions de base

8

Un premier algorithme

Algorithme ElèveAuCarré {Cet algorithme calcule le carré du nombre que lui fournit l'utilisateur} variables unNombre, sonCarré: entiers début {préparation du traitement} afficher("Quel nombre voulez-vous élever au carré?") saisir(unNombre) {traitement : calcul du carré} sonCarré ← unNombre × unNombre {présentation du résultat} afficher("Le carré de ", unNombre) afficher("c'est ", sonCarré) fin

Algorithmique 1 : Instructions de base 9

{déclarations: réservation d'espace-mémoire}

Les trois étapes d’un algorithme

• Préparation du traitement

- données nécessaires à la résolution du problème

• Traitement

- résolution pas à pas, après décomposition en sousproblèmes si nécessaire

• Edition des résultats

- impression à l’écran, dans un fichier, etc.

Algorithmique 1 : Instructions de base

10

Déclarer une variable

variable : type

• Fonction :

Instruction permettant de réserver de l’espace mémoire pour stocker des données (dépend du type de ces données : entiers, réels, caractères, etc.)

• Exemples :

variables val, unNombre : entiers nom, prénom : chaînes de caractères

Algorithmique 1 : Instructions de base 11

Saisir une donnée

saisir()

• Fonction :

Instruction permettant de placer en mémoire les informations fournies par l'utilisateur.

• Exemples:

saisir(unNombre) saisir(nom, prénom) saisir(val)

Algorithmique 1 : Instructions de base 12

Afficher une donnée, un résultat

afficher()

• Fonction :

Instruction permettant de visualiser les informations placées en mémoire.

• Exemples:

afficher(unNombre, "est différent de 0") afficher("La somme de", unNombre, "et" , val , "est", unNombre + val)

Algorithmique 1 : Instructions de base 13

Déclarer une constante

constante ( : type) ←

• Fonction :

Instruction permettant de réserver de l’espace mémoire pour stocker des données dont la valeur est fixée pour tout l’algorithme

• Exemples :

constantes (MAX : entier) ← 100 (DOUBLEMAX : entier) ← MAX × 2

Algorithmique 1 : Instructions de base 14

Saisies et affichages : exemples

Algorithme ParExemple {Saisit un prix HT et affiche le prix TTC correspondant} constantes (TVA : réel) ← 20.6 (Titre : chaîne) ← "Résultat" variables prixHT, prixTTC : réels {déclarations} début afficher("Donnez-moi le prix hors taxe :") saisir(prixHT) prixTTC ← prixHT * (1+TVA/100) {préparation du traitement}

{calcul du prix TTC}

afficher(Titre) {présentation du résultat} afficher(prixHT, « euros H.T. devient ", prixTTC, « euros T.T.C.") Fin Affichage :

Algorithmique 1 : Instructions de base 15

Affecter une valeur à une variable

← ou ou

• Fonction :

Instruction permettant d’attribuer à la variable identifiée par l'élément placé à gauche du symbole ← la valeur de l'élément placé à droite de ce symbole.

• Exemple:

nom ← "Venus" val ← 50 val ← val × 2

Algorithmique 1 : Instructions de base 16

Affectation : exemples

constante variables (SEUIL : réel) ← 13.25 valA, valB : réels compteur : entier mot , tom : chaînes

tableau de simulation :

valA valB compteur mot tom

valA ← 0.56 valB ← valA valA ← valA × (10.5 + SEUIL) compteur ← 1 compteur ← compteur + 10 mot ← " Bonjour " tom ← "Au revoir ! "

Algorithmique 1 : Instructions de base

17

Affectation : exemples (suite)

afficher(mot) afficher(" valA = ", valA) afficher(" valB = ", valB) afficher(" compteur =", compteur ) afficher(tom) Affichage :

Algorithmique 1 : Instructions de base

18

Simulation d'un algorithme

Algorithme CaFaitQuoi? {Cet algorithme .........................................} variables valA, valB : réels {déclarations}

début {préparation du traitement} afficher("Donnez-moi deux valeurs :") saisir (valA, valB) afficher("Vous m'avez donné ", valA, " et ", valB) {traitement mystère} valA ← valB valB ← valA {présentation du résultat} afficher("Maintenant , mes données sont : ", valA, " et ", valB) Fin Affichage :

Algorithmique 1 : Instructions de base 19

Ce qu’il fallait faire …

• Déclarer une variable supplémentaire

variables valA, valB, valTemp : entiers

• Utiliser cette variable pour stocker provisoirement une des valeurs

saisir(valA, valB) valTemp ← valA valA ← valB valB ← valTemp

Algorithmique 1 : Instructions de base

20

Traitement à faire si …

Algorithme SimpleOuDouble {Cet algorithme saisit une valeur entière et affiche son double si cette donnée est inférieure à un seuil donné.) constante (SEUIL : entier) ← 10 variable val : entier début afficher("Donnez-moi un entier : ") { saisie de la valeur entière} saisir(val) si val < SEUIL { comparaison avec le seuil} alors afficher ("Voici son double :" , val × 2) sinon afficher ("Voici la valeur inchangée :" , val) fsi fin

Algorithmique 1 : Instructions de base 21

L’instruction conditionnelle

si alors instructions [sinon instructions] fsi

Si l’expression logique (la condition) prend la valeur vrai, le premier bloc d’instructions est exécuté; si elle prend la valeur faux, le second bloc est exécuté (s’il est présent, sinon, rien).

Algorithmique