Par: Melle Najlae KORIKACHE

Algorithmique et structure de données

Syllabus du cours ...Objectif : se familiariser avec les méthodes de résolution de

problèmes avec l'outil informatique ; apprendre les principes de l'algorithmique ; acquérir un début de maîtrise des techniques et langages

de programmation.

Bibliographie : Introduction a l'algorithmique, Thomas H. Cormen, Charles

E. Leiserson, Ronald L. Rivest et Cliord Stein, Dunod, Paris, 2004.

Algorithmique Application en C, Jean-Michel Lery, Pearson Education, 2005.

Algorithmique et programmation en Java, Vincent Granet, Dunod, Paris, 2000.

Débuter en programmation, Greg Perry, CampusPress, 2003.

Plan du cours1. Introduction à l'algorithmique2. Environnement algorithmique3. Structure de données4. Structures de contrôle5. Structures itératives6. Sous-programmes7. Mode de passage de paramètres8. Tableaux

Structures de contrôleExemple introductifIndiquer le chemin de l’hôtel à un touriste

égaré :1. Allez tout droit jusqu’au prochain carrefour,2. puis prenez à droite3. ensuite prenez la deuxième à gauche et vous y

êtesEst-ce que la rue est autorisée à la circulation?1. Allez tout droit jusqu’au prochain carrefour et là

regardez à droite.2. Si la rue est autorisée à la circulation, alors :

1. prenez la,2. puis, prenez la deuxième à gauche.

3. Si en revanche elle est en sens interdit, alors :1. continuez jusqu’à la prochaine à droite,2. prenez celle-là,3. ensuite, prenez la première à droite.

Structures de contrôleLa structure d’un testEn algorithmique, il y a deux formes

possibles pour un test :Structure simple

Si Booléen AlorsInstructions

Fin SiStructure complète

Si Booléen AlorsInstructions 1

SinonInstructions 2

Fin Si

Structures de contrôleLa structure d’un test

Un booléen est une expression dont la valeur est VRAI ou FAUX. Elle peut-être:

1.une variable de type booléen ;2.une condition.

Structures de contrôleLa structure d’un testDescription de la structure simple :

Arrivé à la première ligne (Si . . . Alors), la machine examine la valeur du booléen :Si le booléen a pour valeur VRAI, alors la

machine exécute la série d’instructions.Si le booléen a pour valeur FAUX, alors la

machine saute directement aux instructions situées après le Fin Si.

Si Booléen AlorsInstructions

Fin Si

Structures de contrôleLa structure d’un testDescription de la structure complète :

Arrivé à la première ligne (Si . . . Alors), la machine examine la valeur du booléen :Si le booléen a pour valeur VRAI, alors la machine

exécute la série d’instructions 1.Au moment ou la machine arrive au mot Sinon, elle

saute directement à la première instruction située après le Fin Si.

Si le booléen a pour valeur FAUX, alors la machine saute directement aux instructions situées après le Sinon.

La machine exécute la série d’instructions 2.

Si Booléen AlorsInstructions 1

SinonInstructions 2

Fin Si

Structures de contrôleLa structure d’un testExemple :Allez tout droit jusqu’au prochain carrefour

Si la rue à droite est autorisée à la circulation Alors

Tournez à droiteAvancezPrenez la deuxième à gauche

SinonContinuez jusqu’à la prochaine rue à

droitePrenez cette ruePrenez la première à droite

Fin Si

Structures de contrôleQu’est-ce qu’une condition ?

Une condition est donc composée de trois éléments :1. une valeur ;2. un opérateur de comparaison ;3. une autre valeur.

DéfinitionUne condition est une comparaison qui, à un moment donné, est vraie ou fausse.

ImportantLes valeurs peuvent être a priori de n’importe quel type (numériques, caractères, etc.) Mais si l’on veut que la comparaison ait un sens, il faut que les deux valeurs de la comparaison soient du même type !

Structures de contrôleQu’est-ce qu’une condition ?

Les opérateurs de comparaison sont : = : égal à . . . ≠: différent de . . . < : strictement plus petit que . . . > : strictement plus grand que . . . ≤: plus petit ou égal à . . . ≥: plus grand ou égal à . . .

Exemples de conditions : X ≤ 50 Fifi = “Loulou” (à ne pas confondre avec

l’affectation) Y ≠24,5

Structures de contrôleQu’est-ce qu’une condition ?

Exemples de conditions sur des caractères :“p” > “m” “papa” < “maman”“Toto” = “toto”“T” < “t”“Papa” < “maman”“Totu” > “Tota”

ImportantLes opérateurs de comparaison peuvent s’employer avec des caractères.Ceux-ci sont codés par la machine dans l’ordre alphabétique. De plus, les majuscules sont systématiquement placées avant les minuscules.

VRAIFAUXFAUXVRAIVRAI VRAI

Structures de contrôleLes conditions composées

Comment exprimer la condition “Toto est inclus entre 5 et 8”?

Cette phrase cache deux conditions :1. “Toto est supérieur à 5” (Toto > 5)2. “Toto est inférieur à 8” (Toto < 8)

Le deux conditions sont reliées par l’opérateur logique “ET”.

La condition s’exprime :(Toto > 5) ET (Toto < 8)

Les opérateurs logiques : ET : la conjonction ; OU : la disjonction ; NON : la négation.

Structures de contrôleLes conditions composées

La conjonction : Le ET a les mêmes sens en informatique que

dans le langage courant. Pour que (Condition 1) ET (Condition 2) soit : VRAI, il faut impérativement que Condition 1

soit VRAI et que Condition 2 soit VRAI. Dans tous les autres cas, (Condition 1) ET

(Condition 2) sera FAUX. La table de vérité :(Condition 1) ET (Condition 2)

Condition 1 VRAI

Condition 1 FAUX

Condition 2 VRAI VRAI FAUX

Condition 2 FAUX FAUX FAUX

Structures de contrôleLes conditions composées

La disjonction : Pour que (Condition 1) OU (Condition 2)

soit : VRAI, il suffit que Condition 1 soit VRAI ou que

Condition 2 soit VRAI. FAUX, il faut que Condition 1 soit FAUX et

que Condition2 soit FAUX aussi. La table de vérité :(Condition 1) OU (Condition 2)

Condition 1 VRAI

Condition 1 FAUX

Condition 2 VRAI VRAI VRAI

Condition 2 FAUX VRAI FAUX

Structures de contrôleLes conditions composées

La négation : le NON inverse une condition. NON

(Condition 1) est : VRAI si Condition 1 est FAUX. FAUX si Condition 1 est VRAI.

La table de vérité :NON (Condition 1)

Condition 1 VRAI

FAUX

Condition 1 FAUX

VRAI

Structures de contrôle Les tests imbriqués

Il y a beaucoup de situations ou deux voies ne suffisent pas!

Si Booléen Alors

Instructions 1Sinon

Instructions 2Fin Si

Graphiquement, on peut facilementreprésenter la structure d’un testcomme un aiguillage de chemin de fer.Un SI ouvre deux voies, correspondantà deux traitements différents.

Structures de contrôle Les tests imbriqués

Structures de contrôle Les tests imbriqués

Algorithme Temperature_Eau_1Var : Temp : réelDébut

Lire (“Entrez la température de l’eau :” ; Temp)Si (Temp ≤ 0) Alors

Ecrire (“C’est de la glace”)Fin SiSi (Temp > 0) ET (Temp < 100) Alors

Ecrire (“C’est du liquide”)Fin SiSi (Temp ≥ 100) Alors

Ecrire (“C’est de la vapeur”)Fin Si

Fin

Exemple : Un algorithme qui donne l’état de l’eau selon sa température. Il doit pouvoir fournir trois réponses possibles : (1) solide ; (2) liquide ou (3) gazeuse.

Structures de contrôle Les tests imbriqués

Algorithme Temperature_Eau_2Var : Temp : réelDébut

Lire (“Entrez la température de l’eau :” ; Temp)Si (Temp ≤ 0) Alors

Ecrire (“C’est de la glace”)Sinon

Si (Temp < 100) AlorsEcrire (“C’est du liquide”)

SinonEcrire (“C’est de la vapeur”)

Fin Si Fin Si

Fin

Exemple : Un algorithme qui donne l’état de l’eau selon sa température. Il doit pouvoir fournir trois réponses possibles : (1) solide ; (2) liquide ou (3) gazeuse.

Structures de contrôle Les tests imbriquésSi Booléen 1 Alors Instructions 1Sinon Si Booléen 2 Alors Instructions 2 Sinon Instructions 3 Fin SiFin Si

Si Booléen 1 Alors Instructions 1Sinon Si Booléen 2 Alors Instructions 2 Sinon Instructions 3 Fin SiFin Si

Si Booléen 1 Alors Instructions 1Sinon Si Booléen 2 Alors Instructions 2Sinon Instructions 3Fin Si

Si Booléen 1 Alors Instructions 1Sinon Si Booléen 2 Alors Instructions 2Sinon Instructions 3Fin Si

De manière plus simplifiée :

ImportantDans le cas de tests imbriqués, le Sinon et le Si peuvent être fusionnés en un Sinon Si. On considère alors qu’il s’agit d’un seul bloc de test, conclu par un seul Fin Si.

ImportantDans le cas de tests imbriqués, le Sinon et le Si peuvent être fusionnés en un Sinon Si. On considère alors qu’il s’agit d’un seul bloc de test, conclu par un seul Fin Si.

Plan du cours1. Introduction à l'algorithmique2. Environnement algorithmique3. Structure de données4. Structures de contrôle5. Structures itératives6. Sous-programmes7. Mode de passage de paramètres8. Tableaux