Accueil > Cours > Algorithmes

Algorithmes

Sommaire

Création d’un algorithme

Principe de résolution d’un problème informatique

Le cahier des charges

analyse

Algorithme
Traduction
Exécution
Tests/validation

Variable

Intro

Identificateur
Le type
La valeur

Exemple de calcul de moyenne

Outils

Opérations logiques et mathématiques

Entrées/sorties

écriture
Lecture

Algèbre de Boole

Fonctions booléennes

Fonctions pour 1 variable
Fonctions de 2 variables

Opérateur modulo

Structure de contrôle

Structures conditionnelles

Branchement simple
Branchement multiple

Structures répétitives

tableau

structure

sous programme

 

 

Création d’un algorithme

Principe de résolution d’un problème informatique

Cahier des charges

Analyse

Algorithme

Traduction

Execution

Test/validation

Le cahier des charges

Il contient :

  • l’énoncé du problème
  • la spécification des données
  • les conditions de fonctionnement

analyse

Elle permet d’avoir une idée claire des étapes à réaliser pour la résolution du problème donné, elle est rédigée en français.

Algorithme

On détaille à l’aide d’un langage adapté les différents traitements (ou étapes)

Traduction

Il s’agit de traduire les étapes précédentes en langage de programmation (C ou C++, voir JAVA)

Exécution

Elle doit permettre de vérifier que le programme fonctionne correctement

Tests/validation

Il s’agit de valider le respect du cahier des charges. Les tests permettent de valider le programme dans les conditions limites

Variable

Intro

Dans nos programmes informatiques, les instructions manipulent des objets ou des informations. Chaque objet possède trois qualificatifs.

Identificateur

C’est le nom de l’objet.
 Ex : a, b, z, étudiant, nombre, ...

♠ Toujours donner un identificateur en rapport avec l’objet manipulé.

Le type

Il détermine l’ensemble de définitions dans lequel l’objet prend ses valeurs.
 Ex : entier, réel, caractère, ...

La valeur

C’est un élément quelconque de l’ensemble de définition ou de l’objet.
 Ex : 5, 12, (entiers...)
 Ex : 3.8, 5.6, (réels...)
 Ex : a, r, (caractère...)

Cet objet est appelé variable quand sa valeur n’est pas constante.
Les variables peuvent être multidimensionnelles, elles sont alors déclarées sous forme de tableau.

ê Un tableau est un ensemble de variables du même type.

 Ex : 1 dimension
V(N)=(v(0), v(1), v(2), ..., v(n-1))

 Ex : 2 dimensions
Matrice [M][N] :
Mat(0)(0)......................................... Mat(n-1)(0)
.
.
Mat(0)(m-1)..................................... Mat(n-1)(m-1)

Exemple de calcul de moyenne

1ère étape : Cahier des charges. Réaliser un programme qui calcule la moyenne de 3 notes de partiels d’un étudiant. Les notes seront saisies au clavier. Le résultat sera affiché à l’écran.

2ème étape :
/*initialisation*/
saisie des trois notes
/*traitement*/
calcul de la moyenne des trois notes
moyenne=(note1+note2+note3)/3
/*résultat*/
afficher la moyenne à écran

3ème étape : algorithme

  • définition des variables utilisées données :
    note1 : type réel
    note2 : type réel
    note3 : type réel
    résultat : moyenne : type réel
  • algorithme et métalangage

Début{
/*initialisation*/
écrire (’donner la 1ère note’)
Lire (note1)
écrire (’donner la 2ème note’)
Lire (note2)
écrire (’donner la 3ème note’)
Lire (note3)
/*traitement*/
moyenne(note1+note2+note3)/3
/*résultat*/
écrire (’la moyenne de l’élève est :’, moyenne)
Fin }

Outils

Opérations logiques et mathématiques

Addition +
Soustraction -
Multiplication *
Division / (ab a prend la valeur de b)
Affectation ← (a3 a prend la valeur de 3)
égalité = (a=b vrai si a=b, faux si a¹b)
Différent ¹ != (même principe que pour le =)
Supérieur >
Supérieur ou égal >=
Inférieur <
Inférieur ou égal <=
Et logique ET &
Ou logique OU

Entrées/sorties

écriture :

écrire (’...’) affiche à l’écran
écrire (’...’, variable)

Lecture

Lire (variable) (saisie au clavier, valeur mise dans ’variable’)

Algèbre de Boole

Conventions :
Soit a un interrupteur. Il peut être ouvert ou fermé
Par convention :

  • a ouvert =>a=0, FAUX
  • a fermé =>a=1, VRAI

a est une variable booléenne
Soit l une lampe. Elle peut être allumée ou éteinte.

  • l allumée l=1 =>VRAI
  • l éteinte l=0 =>FAUX

Soit a, b, et l. la lampe est allumée si a et b sont fermés. Table de vérité :

aF0F1F2F3
00011
10101
 Cste â a Cste

Donc on en déduit que l=a.b

Fonctions booléennes

Fonctions pour 1 variable

aF0F1F2F3
00011
10101
 Cste â a Cste

Fonctions de 2 variables

abF0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15
010101010101000011
010011001100110011
100000111100001111
110000000011111111
 Cste|Nor â ^b|Xor|Nand|ET|Xor| b a OU Cste

^(a.b)=â+^b
^(a+b)=â.^b
a++b=âb+a^b

avec ^b= b barre, â= a barre...
++= ou exclusif

Opérateur modulo

Noté %, l’opérateur modulo représente le reste de la division euclidienne.
 Ex : 4%2=0  4/2=2R0
 Ex : 5%2=1  5/2=2R1

Utilisation : si l’on veut tester si un nombre est pair, on utilisera le modulo 2. si n%2=0, alors le nombre n est pair.
♠Ne s’applique que sur les nombres entiers.
Si l’on veut tester un nombre divisible par n, on testera Y%n

Structure de contrôle

Structures conditionnelles

Appelées aussi structures alternatives,, elles permettent un choix d l’action à exécuter suivant qu’une condition soit remplie ou non.

Branchement simple

Si (condition) alors
 Début
(réalisé si la condition est vraie)
 [...]
 Fin
Sinon
 Début
(réalisé si la condition est faux (optionnel))
 [...]
 Fin

Branchement multiple

Suivant (variable)
Si valeur1 faire (réalisé si variable=Valeur1)
 Début
 [...]
 Fin
Si
valeur2 faire
 Début

 [...]
 Fin
Si
valeurn faire
 Début

 [...]
 Fin
Par défaut faire
(optionnel)
 Début
 [...]
 Fin

Structures répétitives

Aussi appelée structure interactive, elles permettent d’exécuter une suite d’instructions ou d’actions un certains nombre de fois (boucle). Nous distinguons 3 types :

  • tant que (condition de maintient) faire
  • répéter tant que (condition de maintient)
  • pour (variable) variation de Vini à Vfinal

métalangage :

  1. Tant que (condition de maintient) faire
    début
     [...]
    fin
  2. Répéter
    début
     [...]
    fin
    tant que
    (condition de maintient)
  3. Pour variable allant de Vi à Vf avec un pas de Ic faire
    début
     [...]
    fin

Nb : ces trois structures sont très proches et interchangeables.

Les tableaux

Ils peuvent être à une dimension, sous la forme d’une colonne ou d’une ligne, et s’écrivent comme suit :

Nom_du_tableau[X]
X représente le nombre de cases du tableau.
Pour entrer des nombre dans un tableau, il faut définir sur quelle case on veut écrire. On utilise pour cela un FOR :
For (i=0 ; i<X ; I++)
{scanf("%d", &tab[I]),}
cela signifie que pour toutes les cases du tableau allant de 0 à I, la valeur rentrée sera affectée a la case i.
pour un tableau à deux dimensions, la déclaration se fait nom_du_tableau[X][Y]. compter deux FOR, avec un saut de ligne entre les deux :
For(i=0 ; i<X ; i++)
{printf(« \n ») ,
for (j=0 ; j<Y ; j++)
{scanf (« %d », &tab[i][j]),}}
cela affichera un tableau standard avec X colonnes, et Y lignes.

Les structures

Elles permettent de regrouper plusieurs éléments dans une mémoire. Exemple : une structure qui retiens le jour, la date et le mois d’anniversaire pour plusieurs personnes. Elle a un peu la même fonction qu’un tableau mais en plus simplifiée.

Le sous programme (ou fonction)

Il permet de faire appel à une partie de programme que l’on va réutiliser plusieurs fois, ou alors pour éviter de surcharger le programme principal. Par exemple : on fait un programme qui demande la date, puis qui la réutilise plusieurs fois après. La fonction peut retourner une information au programme principal (comme pour la date), ou ne rien renvoyer (affichage)