Notion d’algorithme1

8/3/2019 Notion d’algorithme1

http://slidepdf.com/reader/full/notion-dalgorithme1 1/39

BTS DSI ALGORITHMIQUE 1

BTS DSIPr. Salwa Baqqali

Algorithmique

module 13




Notion d·algorithme




Structure générale d·un système

informatique :

Un ordinateur comprend cinq éléments

fon

damen

taux : l¶unité d¶entrée.

l¶unité de sortie.

l¶unité de mémoire.

l¶unité de contrôle.

l¶unité arithmétique.







Les unités d¶entrée sortie sont des éléments qui permettent àl¶ordinateur de recevoir ou d¶émettrede l¶information (clavier, imprimante, CD-Rom, clé USB,«).

Les trois autres unités (L¶unité de mémoire, l¶unité de contrôle etl¶unité arithmétique) constituent l¶unité centrale (UC).

L¶unité de mémoire est l¶élément où sont stockées les donnéeset les résultats, elle est constituée de très nombreuses cases(cases mémoires).

L¶unité de contrôle coordonne toutes les activités des diverséléments de l¶ordinateur. Elle émet des commandes, contrôle lessignaux et détermine les séquences des diverses instructions.

L¶unité arithmétique est constituée de circuits électriques qui

exécutent les diverses opérations arithmétiques et logiques.




M

éthodologie de programmation

Les différentes étapes du processus de

programmation







L¶analyse d¶un problème posé consiste à définir les différentes étapes de sa résolution.L¶ensemble de ces spécifications représentel¶algorithme.

La phase suivante consiste à traduire l¶algorithmedans un langage de programmation donné.

Dans le cas d¶erreur, le programme produit des

faux résultats : les retours vers l¶analyse(algorithme) sont alors nécessaires.




Algorithme :définition :

Un

algorithme c¶est un

e suite ordonn

ée d¶ordre ou detache à exécuter par la machine pour obtenir un résultat définie par le cahier de charge.

Algorithme = méthode de résolution

Algorithme vient du nom du célèbre mathématicien arabe Al Khawarizmi (Abu Jaafar Mohammed Ben Mussa Al-Khawarizmi).






La conception d¶un algorithme passe par

plusieurs étapes : Analyse: définition du problème en termes de

séquences d¶opérations de calcul de stockagede données, etc.

Conception: définition précise des données,des traitements et de leur séquencement.

Implantation: traduction et réalisation del¶algorithme dans un langage précis.

Test: Vérification du bon fonctionnement del¶algorithme.




Structure d¶un algorithme :

Début

Instruction 1 Les instructions sont exécutées

en ordre de 1 à N. les limites d¶algorithmes sont

définis par début etfin.

.

.Instruction N




Organisation d·un algorithme

Exemple d¶un programme : Algor ithme monAlg

/* Constantes: initialisation obligatoir e */

CONST const1 : entier

const2 : chaîne // Les var iables

VAR var Reel1, var Reel2 : réels

varChaine : chaîne

DEBUT

Instruction1

Instruction2

«

FIN




Les données :

Données = ensemble des informationsmanipulées par un programme

Les données d'un programme sontmémorisées en mémoire centrale dans desvariables (sortes de cases)

Donnée : valeur stockée variable ou constante

Type




Traitement : opérations sur les données

instructions

Données initiales Traitements résultats




Analyse du problème

Décomposer la tâche

Exemple simple : moyenne de 10 notes




Variables

Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement

des valeurs. Il peut s¶agir de données issues du

disque dur, four nies par l¶utilisateur (frappées auclavier). Ces données peuvent être de plusieurstypes : elles peuvent être des nombres, du texte,

etc. Dès que l¶on a besoin de stocker une

information au cours d¶un programme, on utilise unevariable.




Notion de variable :

Une variable possède : une valeur contenue par la case mémoire.

un identificateur : nom unique par lequel on peutaccéder à son contenu.

un type qui définit la taille de la place occupée.

Ne pas confondre la variable et son contenu Une variable est un contenant (case ou boîte).

Le contenu d'une variable est une valeur numérique, alphanumérique«




On utilisera différents types de variables (pour le moment):

Par exemple,définit 2 variables de type entières n'ayantaucune valeur (pour l'instant).




T ypes numériques classiques

Entier : une variable est dite entière si elle prend ses valeurs dansZ et quelle peut supporter les opérations suivantes :

Addition, soustraction, multiplication, division.

Division entièr e notée div :

N div p=q : la division entière de n par p donne la partie entièredu quotient q.

Division modulo notée mod :

N mod p=r : la division modulo de n par p donne le reste r.

Exemples :

12 div 3=4 13 div 3=4

12 mod 3=0

13 mod 3=1




R éel :

Si la variable prend ses valeurs dans IR(ensemble des nombres réels).

Il existe deux représentations des réels : la forme usuelle avec les points : 0.426 , 342.78 , -12.5

la notation scientifique ayant la forme suivante : aE+bou :

Exemple : 247=2.4 E2=0.247 E3= 2470 E-1

Les opérations définies sur les réels : Addition, soustraction, multiplication, division.







A utres types numériques

Certains langages autorisent d¶autres typesnumériques, notamment :

le type monétaire (avec strictement deux chiffres aprèsla virgule)

le type date (jour/mois/année).




Type alphanumér ique

Le type alphanumérique caractérise les valeurs caractères (notées Car) ou chaî ne decaractères (notées chaî ne).

Caractère : peut appartenir au domaine des chiffres de µ0¶ à µ9¶, des lettres de A à Z(majuscules ou minuscules) et des caractères spéciaux (µ+¶, µ-µ, 4,¶, µ, µ ;¶, .¶, µ(µ, µ)¶, µ}¶, µ]¶, %,$,«

Uncaractère sera toujours

noté e

ntre des apostrophes.

Chaine : est une suite finie des caractères quelconques. Exemple : µbon jour¶ µtelevision¶ Var A : chaine Debut A ¶bon jour¶ Ecrire(A)

Fin Dans une variable de ce type, on stocke des caractères, qu¶il s¶agisse de lettres, de

signes de ponctuation, d¶espaces, ou même de chiffres. Le nombre maximal de caractèrespouvant être stockés dans une seule variable string dépend du langage utilisé.

Un groupe de caractères (y compris un groupe de un, ou de zéro caractères), qu¶il soit ou non stocké dans une variable est donc souvent appelé chaî ne de caractères.




T ype booléen

Le der nier type de variables est le type booléen :on y stocke uniquement les valeurs logiques VRAIet FAUX.

On peut représenter ces notions abstraitesde VRAI et de FAUX par tout ce qu'on veut :de l'anglais (TRUE et FALSE) ou desnombres (0 et 1).




A ffectation, expression et opérateurs

L¶affectation est l¶action élémentaire dontl¶effet est de donner une valeur à unevariable (ranger une valeur à une place).

L'affectation est réalisée au moyen del'opérateur

(ou = en C et := en Pascal)

Exemple: A 4




O pérateurs :

Un opérateur est un signe qui relie deuxvaleurs, pour produire un résultat.

Opérateurs numériques :

Ce sont les quatre opérations arithmétiques :

+ Addition

- soustraction

* multiplication

/ Division




Lire et écrire

Soit le programme suivant :

Variable A : entière

Début

A 12^2

Fin

Ce programme nous donne le carré de 12 soit144.

On remarque que :




Si on veut connaître le résultat d¶un calcul ou le contenu d¶unevariable X, l¶algorithme doit contenir l¶instruction qui commande àla machine de four nir ce résultat. Cette instruction est

écrire(X)

qui signifie : mettre sur l¶écran (organe de sortie de la machine)le contenu de la case X. Cette action ne modifie pas le contenude X. Exemple : soit le morceau d¶algorithme suivant :

A étant une donnée, X un résultat

lire (A)X A^2

écrire (X)










Structure sélective

Si condition alor s inst1

Si la con

dition

est vrai l¶ordin

ateur exécutel¶inst1.

Si elle est fausse l¶ordinateur exécutel¶inst2.

Si«alors«sinon

Fin si







Solution




Structure sélective

choix multiple Choisir expression parmi Exp1 : inst1 Exp2 : inst2 . . ExpN : instN Fch Optionnellement Choisir exp parmi V1 : exp 1 V2 : exp 2 .

. VN : exp N Sinon exp N+1 Fch




autre forme de l·action sélective

le choix multiple Syntaxe : Selon variable Début Val1 : action 1 Val2 : action 2 « Val N : action Fin Si variable est égale à val i, on exécute action i, et

on passe à la suite de l¶algorithme, sinon on exécuteaction et on passe à la suite de l¶algorithme.




L·action itérative

la forme répétitive :

Il y a trois sortes de formes répétitives permettant de répéter l¶exécution d¶un bloc d¶instruction, le nombre de répétition estdéfini dans l¶instruction.

1ér e f or me répétitive :

Tant que condition faire Inst 1

Inst 2

« Bloc des instructions à répéter

Inst N

Fin Tq Tant que la condition est vérifiée on exécutera le corps de la

boucle, on s¶arrêtera dés que la condition n¶est plus vérifiée.




2ére forme répétitive

La boucle répéter

La boucle Répéter permet de rentrer dans la bouclequelque soit la condition et réitère l¶exécution

jusqu¶à ce que la condition soit vérifiée. Répéter

«

Action

«

Jusqu¶à condition




3ére forme répétitive :

La boucle Pour

Syntaxe

Pour compteur allant de valeur i

nitiale pas de i

ncréme

nt faire

...

Traitement

...

Fin Pour La boucle pour permet de répéter une instruction un nombre connu de fois.

Documents

Notion d’algorithme1