Cours d'algorithmique - Notions et instructions de base

Qu'est-ce qu'un algorithme ?

Le terme algorithme vient du nom du mathématicien arabe Al Khawarizmi (820 après J.C.)
Un algorithme est une description complète et détaillée des actions à effectuer et de leur séquencent pour arriver à un résultat donné

• Intérêt: séparation analyse/codage (pas de préoccupation de syntaxe) 

• Qualités: exact (fournit le résultat souhaité), efficace (temps d’exécution, mémoire occupée), clair (compréhensible), général (traite le plus grand nombre de cas possibles), …

L’algorithmique désigne aussi la discipline qui étudie les algorithmes et leurs applications en Informatique
Une bonne connaissance de l’algorithmique permet d’écrire des algorithmes exacts et efficaces

Représentation d’un algorithme

Historiquement, deux façons pour représenter un algorithme:
L’Organigramme : représentation graphique avec des symboles (carrés, losanges, etc.)

• offre une vue d’ensemble de l’algorithme
• représentation quasiment abandonnée aujourd'hui

Exemple L’Organigramme 1 : 

Exemple L’Organigramme 2 : 

Le pseudo-code : représentation textuelle avec une série de conventions ressemblant à un langage de programmation (sans les problèmes de syntaxe)

• plus pratique pour écrire un algorithme
• représentation largement utilisée

Notion de variable 

• Dans les langages de programmation une variable  sert à stocker la valeur d’une donnée 

• Une variable désigne en fait un emplacement mémoire dont le contenu peut changer au cours d’un programme (d’où le nom variable)

• Règle : Les variables doivent être déclarées avant d’être utilisées, elle doivent être caractérisées par :

• un nom (Identificateur) 

• un type (entier, réel, caractère, chaîne de caractères, …)

Choix des identificateurs 

Le choix des noms de variables est soumis à quelques règles qui varient selon le langage, mais en général:

• Un nom doit commencer par une lettre alphabétique                       

exemple valide : A1 exemple invalide: 1A

• doit être constitué uniquement de lettres, de chiffres et du soulignement _ (Éviter les caractères de ponctuation et les espaces)            

valides: SMIP2007, SMP_2007
invalides: SMP 2005,SMI-2007,SMP;2007

• doit être différent des mots réservés du langage (par exemple en Java: int, float, else, switch, case, default, for, main, return, …) 
• La longueur du nom doit être inférieure à la taille maximale spécifiée par le langage utilisé

Conseil : pour la lisibilité du code choisir des noms significatifs qui décrivent les données manipulées          

   exemples : TotalVentes2004, Prix_TTC, Prix_HT

Remarque: en pseudo-code algorithmique, on va respecter les règles citées, même si on est libre dans la  syntaxe

Types des variables 

Le type d’une variable détermine l’ensemble des valeurs quelle peut prendre, les types offerts par la plus part des langages sont:

• Type numérique (entier ou réel)
• Byte (codé sur 1 octet): de 0 à 255
• Entier court (codé sur 2 octets) : -32 768 à 32 767
• Entier long (codé sur 4 ou 8 octets) 
• Réel simple précision (codé sur 4 octets) 
• Réel double précision (codé sur 8 octets)
• Type logique ou booléen: deux valeurs VRAI ou FAUX 

Type caractère: lettres majuscules, minuscules, chiffres, symboles, …

exemples: ’A’, ’a’, ’1’, ’?’, …

Type chaîne de caractère: toute suite de caractères,             

                        exemples: " Nom, Prénom", "code postale: 1000", …

Déclaration des variables

Rappel: toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable
En pseudo-code, on va adopter la forme suivante pour la déclaration de variables

Syntaxe Générale : 

Variables    liste d'identificateurs : type

Exemple: 

Variables    i, j,k : entier
            x, y : réel
           OK: booléen
           ch1, ch2 : chaîne de caractères

Remarque: pour le type numérique on va se limiter aux entiers et réels sans considérer les sous types

L’instruction d’affectation 

l’affectation consiste  à attribuer une valeur à une variable (ça consiste en fait à remplir où à modifier le contenu d'une zone mémoire)
En pseudo-code, l'affectation se note avec le signe   ←
Syntaxe Générale : 

Var← e : attribue la valeur de e à la variable Var 

• e peut être une valeur, une autre variable ou une expression
• Var et e doivent être de même type ou de types compatibles
• l’affectation ne modifie que ce qui est à gauche de la flèche 

Exemples valides: 

                          i ←1                     j ←i                           k ←i+j
                       x ←10.3              OK ←FAUX             ch1 ←"SMI"
                       ch2 ←ch1            x ←4                        x ←j

      (voir la déclaration des variables dans le transparent précédent)
Exemple non valides: 

                             i ←10.3   OK ←"SMI" j ←x

Quelques remarques

Beaucoup de langages de programmation (C/C++, Java, …) utilisent le signe égal = pour l’affectation ←.

 Attention aux confusions: 

l'affectation n'est pas commutative : A=B est différente de B=A
l'affectation est différente d'une équation mathématique :

• A=A+1 a un sens en langages de programmation 

• A+1=2 n'est pas possible en langages de programmation et n'est pas équivalente à A=1 

Certains langages donnent des valeurs par défaut aux variables déclarées. Pour éviter tout problème il est préférable d'initialiser les variables déclarées

Exercices 

Exercice 1

Donnez les valeurs des variables A, B et C après exécution des instructions suivantes ?

Variables A, B, C: Entier
Début
A ← 3
B ← 7
A ← B
B ← A+5
C ← A + B
C ← B – A
Fin

Exercice 2

Donnez les valeurs des variables A et B après exécution des instructions suivantes ?

Variables A, B : Entier
Début
A ← 1
B ← 2
A ← B
B ← A
Fin

Les deux dernières instructions permettent-elles d’échanger les valeurs de A et B ?

Exercice 3

Écrire un algorithme permettant d’échanger les valeurs de deux variables A et B

Expressions et opérateurs

Une expression peut être une valeur, une variable ou une opération constituée de variables reliées par des opérateurs
Exemples : 

1, b, a*2, a+ 3*b-c, … 

L'évaluation de l'expression fournit une valeur unique qui est le résultat de l'opération.
Les opérateurs dépendent du type de l'opération, ils peuvent être :

des opérateurs arithmétiques :  +, -, *, /, % (modulo), ^ (puissance)
des opérateurs logiques :  NON, OU, ET
des opérateurs relationnels :  =,     , <, >, <=, >=
des opérateurs sur les chaînes :  & (concaténation) 

Une expression est évaluée de gauche à droite mais en tenant compte de priorités  

Priorité des opérateurs

Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est le suivant (du plus prioritaire au moins prioritaire) :

^          (élévation à la puissance)
* , /      (multiplication, division)
%         (modulo)
+ , -     (addition, soustraction)

Exemple: 

2 + 3 * 7     vaut  23

En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer les opérations à effectuer en priorité   
Exemple: 

(2 + 3) * 7  vaut  35

Les instructions d'entrées-sorties:  lecture et écriture

Les instructions de lecture et d'écriture permettent à la machine de communiquer avec l'utilisateur

La lecture

La lecture permet d'entrer des donnés à partir du clavier

En pseudo-code, on note : lire (var)
la machine met la valeur entrée au clavier dans la zone mémoire nommée var

Remarque: Le programme s'arrête lorsqu'il rencontre une instruction Lire et ne se poursuit qu'après la frappe d’une valeur au clavier et de la touche Entrée

L'écriture

L'écriture permet d'afficher des résultats à l'écran (ou de les écrire dans un fichier)

En pseudo-code, on note: écrire (var) 
la machine affiche le contenu de la zone mémoire var

Conseil: Avant de lire une variable, il est fortement conseillé d’écrire des messages à l’écran, afin de prévenir l’utilisateur de ce quille doit frapper

Exemples

Exemple 1

Écrire un algorithme qui demande un nombre entier à l'utilisateur, puis qui calcule et affiche le double de ce nombre

Algorithme Calcul_double
variables A, B : entier
Début
écrire("entrer le nombre ")
lire(A)
B ← 2*A
écrire("le double de ", A, "est :", B)
Fin

Exemple 2

Écrire un algorithme qui vous demande de saisir votre nom puis votre prénom et qui affiche ensuite votre nom complet

Algorithme AffichageNomComplet
variables Nom, Prenom, Nom_Complet : chaîne de caractères
Début
écrire("entrez votre nom")
lire(Nom)
écrire("entrez votre prénom")
lire(Prenom)
Nom_Complet ← Nom & Prenom
écrire("Votre nom complet est : ", Nom_Complet)
Fin