Algorithme

Page 1

Algorithmique et Structures de Données

Page 2

C’est quoi un algorithme ?

oUn algorithme est un ensemble de règles logiques et chronologiques qu’on doit suivre pour aboutir à la résolution d’un problème particulier.

oCes règles sont constituées d’un nombre fini d’opérations élémentaires.

oCes opérations seront exécutées dans un ordre bien déterminé.

oUn algorithme peut être assimilé à un raisonnement que l’on peut traduire avec un langage que toute personne peut comprendre :

LDA : Langage de Description d’Algorithme

oLe langage de description d’algorithme (LDA) ne doit pas être confondu avec le programme proprement dit.

oLe programme correspond en fait à la traduction du LDA à un autre langage compréhensible pour la machine (Pascal, Visual Basic, C, C++, C#, Java…)

Page 3

Chemin de la traduction de la pensée

Raisonnement logique et

chronologique LDA………………

ProgrammeC, C++,…

Langage traduisant la pensée de manière compréhensible pour toute personne :

Algorithme

Langage traduisant le LDA de manière compréhensible pour l’ordinateur : Programme

Page 4

o Le LDA utilise un ensemble de mots clés et de structures permettant de décrire de manière complète, précise et claire, l’ensemble des opérations à effectuer pour aboutir au résultat recherché.

o Il est vivement conseillé d’agrémenter le LDA de nombreux commentaires pour faciliter sa lecture.

o Ces règles sont constituées d’un nombre fini d’opérations élémentaires.

o Ces opérations seront exécutées dans un ordre bien déterminé.

o Un algorithme peut être assimilé à un raisonnement cohérent que l’on peut traduire avec un langage que toute personne peut comprendre :

LDA : Langage de Description d’Algorithme

o Le langage de description d’algorithme (LDA) ne doit pas être confondu avec le programme proprement dit.

o Le programme correspond en fait à la traduction du LDA à un autre langage compréhensible pour la machine (Pascal, Visual Basic, C, C++, C#, Java…)

Page 5

Structure d’un Algorithmealgorithme nom de l’algorithme

constliste des constantes

varliste des variables

structliste des structures

début algorithmeaction 1 // commentaire 1action 2 // commentaire 2

.

.

.action n // commentaire n

fin algorithme

Déclaration du nom de l’algorithme

Déclaration des constantes, des variableset des structures

Le corps de l’algorithme

Page 6

Nom de l’algorithme :

Il permet tout simplement d’identifier un algorithme parmi d’autres.

Les déclarations :

C’est une liste exhaustive de variables utilisées et manipulées dans le corps de l ’ algorithme.

Le corps de l’algorithme :

Dans cette partie de l’algorithme, sont placées les tâches à exécuter (instructions, opérations, …).

Les commentaires :

Pour permettre une lecture plus aisée et plus compréhensive de l’algorithme

Structure d’un Algorithme

Page 7

Les Déclarations

Les Constantes :

Elles représentent des chiffres, des nombres, des caractères, des chaînes de caractères, … dont la valeur ne peut pas être modifiée au cours de l’exécution de l’algorithme.

Les Variables :

Elles peuvent stocker des chiffres des nombres, des caractères, des chaînes de caractères,… dont la valeur peut être modifiée au cours de l’exécution de l’algorithme.

Les Structures :

Elles permettent de rassembler plusieurs variables ou constantes sous unmême identificateur, on parle également d’entités ou d’objets.

Page 8

Les constantes et les variables sont définies dans la partie déclarative par deux caractéristiques essentielles, à savoir :

L’ identificateur :

Il représente le nom de la variable, de la constante ou de la structure. Il est composé généralement de lettres mais peut également contenir et de chiffres.Il ne doit pas commencer par des chiffresIl ne doit pas contenir d’espaces, de caractères de ponctuation ou de caractères accentués (il existe des langages qui acceptent des caractères accentués au niveau de l’identificateur).

Le type :

Il représente la nature de la variable ou de la constante (entier, réel, booléen, chaîne de caractères…)

Exemples :var age : réel ;var sexe, adresse, ville : chaine ;var nbr_enfants , etage : entier ;

Les Déclarations

Page 9

Les types de baseDe façon générale, pour toute objet censé contenir une ou plusieurs informations devant êtres traités par le processeur, l’ordinateur doit lui réserver de la mémoire volatile (RAM). La taille mémoire nécessaire pour stocker cet objet dépend de la nature de l’information en question.

Exemple d’informations de base :

Les nombres entiers : 0, -1, 45, 36, -10 en décimal 45H, 0FBH, 64H en hexadécimal 10101111, 1011 en binaire

Le caractère : ‘a’ , ‘A’ , ’*’ , ’7’ , ’z’ , ’!’ , ….

Les nombres réels : -3.67, 4.2569, –564.0, 18.36 10e-6

La chaîne de caractères ‘électronique’ , ’cd ROM de 80mn’ , …

Le booléen : Il ne peut prendre que deux états possibles : VRAI ou FAUX (True ou False)

Page 10

Les opérateursArithmétique

+ Addition

- Soustraction

* Multiplication

/ Division

DIV Division entière

↑ Puissance

Comparaison

> Supérieur stricte

< Inférieur stricte

≥ Supérieur ou égal

≤ Inférieur ou égal

= Egal

≠ Différent

Logique

ET Fonction ET

OU Fonction OU

OUX Fonction OU Exclusif

NON Fonction NON

NON ET Fonction NON ET

NON OU Fonction NON OU

Page 11

Les opérateurs : Quelques remarqueso Opérateur de concaténation Alpha-Alphanumérique ( + )

o Les différents opérateurs cités précédemment peuvent avoir des notations différentes selon les langages de programmation que vous allez utiliser.

Par exemple : pour la concaténation des chaines de caractères on utilise • un + en JavaScript (‘Bonjour ‘ + ‘ tout ‘ + ‘le monde ‘ + 17)• un & en VB ("Bonjour" & " tout " & "le monde " & 17)

o Les opérateurs de comparaison pour les booléens : ( = , ≠ )

o Les opérateurs de comparaison pour les chaînes de caractères : ( = , ≠ , < , > )

o Le signe = est utilisé dans certains langages à la fois comme étant opérateur de comparaison mais aussi comme opérateur d’affectationPar exemple : a = 10 , b = 20 ;

Si (a = b) alors c = "a est égal à b" ;

Sinon c = "a est différent de b" ;

Fin si

Page 12

Priorité des opérateurs usuels

Priorité croissante de bas vers le haut

* Opérateur de multiplication

/ Opérateur de division

+ Opérateur d'addition

- Opérateur de soustraction

< Opérateur d'infériorité stricte

> Opérateur de supériorité stricte

<= Opérateur d'infériorité ou d'égalité

>= Opérateur de supériorité ou d'égalité

== Opérateur d'égalité (lang c,c++, javascript), (= VB)

!= Opérateur d'inégalité (lang c,c++, javascript), (<> VB)

&& Opérateur et logique ET (lang c,c++, javascript), (AND VB)

|| Opérateur ou logique OU (lang c,c++, javascript), (OR VB)

= Opérateur d'affectation

Page 13

Les tables de vérité : opérateurs logiques

ET Logique

ET 0 1

0 0 0

1 0 1

OU Logique : inclusif

OU 0 1

0 0 1

1 1 1

XOR Logique : ou exclusif

XOR 0 1

0 0 1

1 1 0

NOT Logique : négation

Val Val

0 1

1 0

Page 14

Les structures fondamentales

Les opérations élémentaires relatives à la résolution d’un problème peuvent, en fonction de leur nature être organisées suivant quatre familles de structures :

• les structures linéaires• les structures alternatives• les structures de choix• les structures itératives ou répétitives

Important : NE PAS CONFONDRE

-structure comme étant un nouveau type de données constitué à partir de types de données élémentaires.

ET-structure comme étant un regroupent d’instructions devant être exécuté après vérification d’un certain nombre de conditions.

Page 15

Les structures linéaires

La structure linéaire se caractérise par une suite d’actions à exécuter dans l’ordre où elles sont énoncées.

Traitement 1

Traitement 2

Traitement 3

Traitement 4

Page 16

Les structures Alternatives Une structure alternative offre la possibilité de donner des issues différentes à la

poursuite d’un algorithme.

Ces issues s’excluent mutuellement.

On peut rencontrer plusieurs formes de structures alternatives :

Forme alternative complète : dans cette structure, l’exécution de l’un des deux traitements distincts possibles T2

et T3 ne dépend que la réalisation de la condition qui les précède :

ConditionSi Vrai Si Faux

Traitement 2 Traitement 3

Traitement 4

Traitement 1si la condition est vérifiée les traitements se font dans cet ordre : (T1 T2 T4).

si la condition n’est pas vérifiée les traitements se font dans cet ordre : (T1 T3 T4).

Page 17

Les structures Alternatives

Forme alternative réduite :dans cette structure, l’exécution du traitement T2 ne dépend que la réalisation de la condition qui le précède :

ConditionSi Vrai

Si FauxTraitement 2

Traitement 3

Traitement 1si la condition est vérifiée les traitements se font dans cet ordre : (T1 T2 T3). si la condition n’est pas

vérifiée les traitements se font dans cet ordre : (T1 T3).

Page 18

Forme alternative linéaire

var A, B, C : EntierA = 10 ;B = 20 ;C = A + B ;

Forme alternative complète

var A, B : EntierSaisir A ;Si A > 5 Alors

B = A + 10Sinon

B = A + 2Fin SiAfficher B ;

Les structures Alternatives : ExemplesForme alternative réduite

var A, B : EntierSaisir A ;B = A ;Si A > 5 Alors

B = A + 10Fin SiAfficher B ;

Page 19

Les structures Alternatives

Forme alternative multiple :dans cette structure, l’exécution des traitement Ti ne dépend que la réalisation de la condition qui les précède. Ces conditions doivent être disjointes.

Si Cond 1

FauxTA

Si Cond 2

Si Cond n

TB

Vrai

T1

Vrai

T2

Vrai

Tn

Aucune Cond

T n+1

Faux

Faux

TAT1TB

TAT2TB

TATnTB

TATn+1TB

Page 20

Forme alternative multiple

var A, B : EntierSaisir A ;Si A < 0 Alors

B = 0 ;Sinon Si A >= 0 ET A < 5 Alors

B = A + 1 ;Sinon Si A >= 5 ET A < 10 Alors

B = A + 2 ;Sinon Si A >= 10 ET A < 14 Alors

B = A + 3 ;Sinon

B = 20 ;Fin SiAfficher B ;

Les structures Alternatives : Exemples

Page 21

ALGOAlgorithme EleverAuCarre

//Cet algorithme calcule le carré du nombre que lui fournit l'utilisateurVariables UnNombre, SonCarre : entiers ;

Débutafficher("Quel nombre voulez-vous élever au carré ? ") ;saisir(UnNombre) ;SonCarre ← UnNombre×UnNombre ;afficher("Le carré de ", UnNombre) ;afficher("c'est : ", SonCarré) ;

Fin

Page 22

Lang VBSub EleverAuCarre()

Dim UnNombre as integer, SonCarre as integerUnNombre = InputBox("Quel nombre voulez-vous élever au carré ? ") SonCarre = UnNombre×UnNombre MsgBox("Le carré de " & UnNombre & " est " & SonCarre )

End Sub

Lang Cvoid EleverAuCarre(){

int UnNombre, SonCarre ;printf("Quel nombre voulez-vous élever au carré ? ") ;scanf("%d" , &UnNombre) ;SonCarre = UnNombre×UnNombre ;printf("Le carre de %d est %d" , UnNombre, SonCarre ) ;

}

Page 23

Algorithme CalculMontantTTC // Saisit un prix HT et affiche le prix TTC correspondantConstantes

TVA ← 20.0 : réel ,Titre ← "Résultat " : chaine ;

Variables prixHT, prixTTC : reels

Début afficher("Donnez-moi le prix hors taxe :")saisir(prixHT)prixTTC ← prixHT* (1+TVA/100) // calcul du prix TTCafficher(Titre) ;afficher(prixHT, " DH H.T. devient ", prixTTC, "Dh T.T.C.")

Fin

Page 24

Algorithme CaFaitQuoiVariables valA, valB : réels ;Debut

afficher("Donnez-moi deux valeurs : ") ;saisir (valA, valB) ;afficher("Vous m'avez donné ", valA, " et ", valB) ;valA←valB ;valB←valA ;afficher("Maintenant , mes données sont : ", valA, " et ", valB) ;

Fin

Page 25

Les structures itérativesLes structures itératives permettent de répéter l’exécution d’un ensemble d’instructions une ou plusieurs fois. Ces structures sont regroupées sous deux grandes familles selon si le nombre de répétitions est connu ou pas.

Cas ou le nombre de répétition est connu :

POUR … ALLANT DE … À … FAIRE …

Dans cette structure, la sortie de la boucle d’itération s’effectue lorsque lenombre souhaité de répétition est atteint.

On utilise donc une variable d’itérations caractérisée par :• sa valeur initiale,• sa valeur finale,• son pas de variation.

Si la valeur finale de l’indice est inférieure à sa valeur initiale le pas devariation est négatif, la structure est dite « pour décroissant », dans le cas contraire, le pas est positif et la structure est dite « pour croissant »

Page 26

Les structures itératives

Page 27

Les structures itératives : ForAlgo

POUR i ALLANT DE ValeurInitiale À ValeurFinale Variation = PasVariation FAIRE

Bloc d’instructionsFIN POUR

VB FOR i = ValeurInitiale TO ValeurFinale STEP PasVariation

Bloc d’instructions

Next

C

for(i = ValeurInitiale ; i <= ValeurFinale ; i = i + 1){

Bloc d’instructions}

Page 28

Les structures itératives : whileCas ou le nombre de répétition est inconnu :

Algo

TantQue (TestsLogiques)Bloc d’instructions

FIN TantQue

VB While(TestsLogiques)

Bloc d’instructionsWEnd

C

While(TestsLogiques){

Bloc d’instructions}

Page 29

Ecrire un algorithme permettant de calculer le total ht, le total tva et le total ttc d’une facture.

Page 30

Algorithme CalculFacture( )Const tva = 0.2 : reel ;Var mht = 0, mtva = 0, mttc = 0, puht, qt : reel ;Var Nbr_Produits = 0 : entier ;Var Reponse char ;

DEBUTAfficher (« Voulez vous effectuer un achat ? : ») ;Saisir(Reponse) ;

TANT QUE (Reponse == ‘O’) FAIRE Nbr_Produits = Nbr_Produits + 1 ;Afficher(« Saisir le PUHT : ») ;Saisir(puht) ;Afficher(« Saisir la quantité : ») ;Saisir(qt) ;mht = mht + qt*puht ;mtva = mht*tva ;mttc = mht*(1+tva) ;Afficher(« mht : » mht) ;Afficher(« mtva: » mtva) ;Afficher(« mttc : » mttc) ;Afficher (« Voulez vous effectuer un autre achat ? : ») ;Saisir(Reponse) ;

FIN TANT QUESI (Nbr_Produits == 0) ALORS

Afficher(« mht : » mht) ;Afficher(« mtva: » mtva) ;Afficher(« mttc : » mttc) ;

FIN SIFIN

Page 31

Algèbre de Boole (Suite)

Page 32

Algèbre de Boole (Suite)

Page 33

Algèbre de Boole et Circuits Logiques

Page 34


Page 35


Page 36

Algèbre de Boole et Circuits LogiquesLe AND

Page 37


Page 38


Page 39


Page 40

Algèbre de Boole et Tests Logiques

Page 41


Page 42


Page 43

LES MEMOIRES

Page 44

LES MEMOIRES

Page 45

LES MEMOIRES

Page 46

LES MEMOIRES

Page 47

LES MEMOIRES

Business

Algorithme