Algo

division management des systèmes d’information Cours Programmation

Algorithmique et structures de données

Edition 2001

1. INTRODUCTION La programmation (but final) a souvent été une activité menée sans méthodes strictes, à grand renfort d'astuces et de recettes personnelles. Cette situation est issue des balbutiements de l'informatique quand les conditions permettaient (ou favorisaient) cet état de choses. Pour tenter de mettre un terme à ce type de situations, un certain nombre de chercheurs (E.W. Dijkstra, N. Wirth, Hoare ...), dès les années 70, se sont efforcés de développer et de propager des méthodes pour discipliner l'analyse, la programmation et l'organisation de projets informatiques. C'est cette méthodologie que l'on désigne sous le terme de programmation structurée. La programmation structurée définit deux types de préoccupations: Disciplines d'analyse et de programmation Définitions d'un nombre restreint de structures dites fondamentales à partir desquelles on peut écrire tout algorithme. Analyse TOP-DOWN : résolution des problèmes par affinages successifs de l'énoncé global jusqu'aux détails. Méthodes systématiques dans l'utilisation des langages traditionnels et de préférence, emploi de langages appropriés. Disciplines d'organisation Définition stricte des rôles des membres d'une équipe de programmation et hiérarchie des équipes. Grand soin apporté à l'écriture et à la mise à jour de la documentation. Modularisation du produit et définitions précises des interfaces. Normes de programmation et normes de présentation des programmes respectées par l'ensemble de l'équipe.

Algorithmique et Structures de Données

Page 1 /43

2. INTRODUCTION A L’ALGORITHMIQUE L’algorithmique est une science très ancienne. Son nom vient d’un mathématicien arabe du IXème siècle EL KHOWRISMI. Des mathématiciens grecs comme Euclide ou Archimède en ont été les précurseurs (calcul du PGCD de 2 nombres, calcul du nombre π). 2.1. Qu’est-ce qu’un algorithme ? Plusieurs définitions possibles : "spécification d'un schéma de calcul, sous forme d'une suite finie d'opérations élémentaires obéissant à un enchaînement déterminé". "ensemble de règles opératoires dont l'application permet de résoudre un problème donné au moyen d'un nombre fini d'opérations". 2.2. Propriétés d'un algorithme Un algorithme - décrit un traitement sur un nombre fini de données - est la composition d'un nombre fini d'étapes, chaque étape étant formée d'un nombre fini d'opérations dont chacune est définie de façon rigoureuse et non ambiguë, effective, c'est-à-dire pouvant être effectivement réalisée par une machine Quelque soit la donnée sur laquelle il travaille, un algorithme doit toujours se terminer et fournir un résultat. Un algorithme est déterministe; étant donné un algorithme, toute exécution de celui-ci sur les mêmes données donne lieu à la même suite d'opérations et aboutit au même résultat. Il existe une relation étroite entre la notion de programme informatique et celle d'algorithme. Un programme informatique est écrit dans un langage de programmation et s'exécute sur un ordinateur (processeur, mémoire et organes d'Entrées-Sorties). En résumé, un algorithme doit être PRECIS: Il doit indiquer: - l'ordre des étapes qui le constituent - à quel moment il faut cesser une action - à quel moment il faut en commencer une autre - comment choisir entre différentes possibilités DETERMINISTE - Une suite d'exécutions à partir des mêmes données doit produire des résultats identiques. FINI DANS LE TEMPS - c'est-à-dire s'arrêter au bout d'un temps fini.

Algorithmique et Structures de Données

Page 2 /43

2.3. Place de l'algorithme dans la résolution d'un problème informatique La résolution d'un problème informatique se décompose en quatre phases: - Phase d'étude Inventorier les paramètres connus ou observables et définir les objectifs à réaliser. - Phase de réalisation du modèle Déterminer l'enchaînement des opérations. Cette phase aboutit à l'élaboration d'un schéma de résolution. - Phase de spécification Exprimer le schéma de résolution de manière plus précise en utilisant éventuellement un pseudo-langage. Cette phase débouche sur des algorithmes. - Phase de traduction Mettre en œuvre les algorithmes en les traduisant en un langage de programmation adapté à la machine utilisée.

2.4. Notion de pseudo-langage Aujourd'hui, on dispose d'une grande variété de langages de programmation. Certains langages très connus du grand public sont largement utilisés dans des domaines très divers (PASCAL, C, LISP, ADA, COBOL etc...). On distingue généralement les langages de bas niveau (proches de la machine : Assembleur) et les langages évolués (dits de haut niveau). De tout temps, les chercheurs ont essayé de mettre au point des langages permettant de se détacher le plus possible de la machine sur laquelle les programmes seront exécutés. Certains algorithmes très anciens (Crible d'Erathostène par exemple) ont été décrits en utilisant un langage peu formalisé (proche du langage naturel). D'un autre côté, un algorithme n'a d'intérêt que s'il peut être compris et utilisé par un grand nombre de programmeurs. Il a donc fallu élaborer un langage de description suffisamment formel, pour permettre des implantations dans différents langages de programmation peu fastidieuses, et d'un niveau suffisant pour qu'il soit un outil de communication efficace. Un tel langage s'appelle pseudo-langage. En résumé, l'avantage du pseudo-langage est qu'il permet d'écrire tout algorithme de façon formelle, c'est-à-dire suffisamment précise, tout en restant compréhensible pour l'ensemble des informaticiens. La phase de programmation se trouvera nécessairement allégée, puisqu'elle se résumera à adapter l'ensemble des opérations décrites aux spécificités du langage utilisé. 2.5. Elaboration d'un algorithme. Quatre phases principales: - Analyse du problème - Expression d'une solution en langage courant - Expression d'une solution en pseudo-langage - Tests et Vérification de l'adéquation de la solution Analyse du problème:

Algorithmique et Structures de Données

Page 3 /43

Bien comprendre l'énoncé du problème: Il est inutile et dangereux de passer à la phase suivante si vous n'avez pas bien discerné le problème. Expression du raisonnement Bien souvent, quelques lignes écrites en langage courant suffisent pour décrire succinctement l'essentiel du problème. L'intérêt de cette étape est qu'elle permet de vérifier rapidement que l'on se trouve sur la bonne voie. De plus, ces quelques lignes seront un support efficace lors de l'écriture de l'algorithme. Expression d'une solution en pseudo-langage Il peut arriver que plusieurs solutions répondent à un problème donné. Il faudra choisir la solution la plus judicieuse et rester cohérent jusqu'au bout. Tests et Vérification de l'adéquation de la solution Vérifier l'exactitude du comportement de l'algorithme, son bon déroulement. Si l'algorithme ne répond pas parfaitement à toutes les requêtes exprimées dans l'énoncé du problème, retournez à la phase n°1.

Algorithmique et Structures de Données

Page 4 /43

3. OBJETS SIMPLES, TYPES ET ACTIONS ELEMENTAIRES Un algorithme va manipuler des objets au sens informatique. Ces objets pourront être des données qui seront fournies en entrée, des résultats produits par l'algorithme ou des outils nécessaires au bon déroulement de l'algorithme. 3.1. Type d'un objet En mathématiques, lorsque l'on utilise des objets, on précise leur type. Exemples: x∈ R i∈Z

x et i appartiennent à des types dont on connaît les propriétés

En informatique, les objets manipulés par un algorithme doivent appartenir à un type connu au moment de leur utilisation. Intérêt: documentation vérifications possibles dans les langages de haut niveau lors de certaines opérations Tout objet peut être caractérisé par un type qui indique: les ensembles de valeurs que peut prendre l'objet. les actions autorisées sur cet objet. Les objets simples sont: des nombres (par exemple 3 , 7 , 3.141592 , 1996). des caractères ou des chaînes de caractères (par exemple : 'A' , '45' , 'BONJOUR'). des valeurs booléennes (VRAI , FAUX) On distingue généralement: - les types scalaires qui sont par définition totalement ordonnés - les types structurés qui regroupent sous un même nom une collection d'objets élémentaires qui peuvent être de même type (type homogène) ou de type différents (type hétérogène). Ces types structurés seront vus ultérieurement. En résumé, objet ⇒ donnée ou algorithme algorithme ⇒ procédure ou fonction donnée ⇒ constante ou variable constante ou variable ⇒ type scalaire ou type structuré type structuré ⇒ type homogène ou hétérogène

Algorithmique et Structures de Données

Page 5 /43

3.2. Les objets. Pour désigner ces différents objets, on utilisera des chaînes de caractères qui seront appelées les identificateurs des objets. Pour différentier un identificateur d'un nombre, un identificateur commence par une lettre et ne comporte pas d'espace. De plus, on essaiera toujours de choisir des noms explicites afin de faciliter la relecture et l'éventuelle maintenance de l'algorithme par un tiers. Un objet peut être : une constante ou une variable s'il s'agit d'une donnée au sens large, une fonction (ou une procédure) s'il s'agit d'un algorithme 3.3. Actions élémentaires Les actions élémentaires sur une donnée dépendent évidemment du type de cette donnée et de sa catégorie (variable ou constante). Type entier: prend ses valeurs dans un sous-ensemble des entiers relatifs. C'est un ensemble fini dans lequel chaque élément possède un successeur et un prédécesseur. Type réel prend ses valeurs dans un sous-ensemble de réels décimaux signés. Dans la plupart des langages, cet ensemble n'est pas un ensemble fini. On ne peut trouver de successeur ou de prédécesseur à un réel donné. Type caractère prend ses valeurs dans l'ensemble des caractères de la table ASCII. Type chaîne de caractère se compose d'une suite de symboles de type caractère Type booléen type logique qui peut prendre les valeurs VRAI ou FAUX.

Algorithmique et Structures de Données

Page 6 /43

3.3.1. Opérateurs sur les types simples Opérateur + et – unaires négation logique Elévation à la puissance Multiplication Division entière Division reste(modulo) Addition Soustraction Comparaison et logique ou logique

notation +NON ↑ * DIV / MOD + < <= >= = ≠ ET OU

type des opérandes entier ou réel booléen entier ou réel entier ou réel entier réel entier entier ou réel entier ou réel entier ou réel tout type booléen booléen

type du résultat celui de l'opérande booléen entier ou réel entier ou réel entier réel entier entier ou réel entier ou réel entier ou réel booléen booléen booléen

Dans ce tableau, les opérateurs sont classés par ordre de priorité décroissante mais prudence! dans l'utilisation des priorités car il existe souvent des différences d'un langage de programmation à l'autre. En absence de parenthésage, l'évaluation se fait de gauche à droite. 3.3.2. Affectation L'affectation a pour rôle d'attribuer une valeur, résultat d'une évaluation, à un objet. La valeur doit être compatible avec le type de la valeur à gauche de l'affectation. Le symbole utilisé pour l'affectation est <-. Exemple: prix_total <- nb_kg * prix_du_kg Si nb_kg est de type entier et prix_du_kg est de type réel alors prix_total doit être de type réel.

Algorithmique et Structures de Données

Page 7 /43

3.3.3. Lecture et écriture Ces actions permettent d'assurer l'interface entre l'environnement externe (l'utilisateur) et l'algorithme. LIRE(Valeur1, Valeur2 ...) ECRIRE(Valeur3, Valeur4 ...) ECRIRE('Le résultat du calcul est : ',prix_total) Exemple d'algorithme ALGORITHME EPICIER VAR prix_total , prix_du_kg : REEL; nb_kg : ENTIER; DEBUT ECRIRE('Entrez le prix d'un kilogramme de choux : '); LIRE(prix_du_kg); ECRIRE('Entrez le nombre de kilogramme de choux : '); LIRE(nb_kg); prix_total <- prix_du_kg * nb_kg; ECRIRE('Le prix total de l''achat est :',prix_total); FIN 3.3.4. Commentaires Afin d'améliorer la lisibilité d'un algorithme, on peut utiliser des commentaires. Un commentaire est une suite de caractères quelconques encadrée par les symboles CO et FCO. Exemple: CO ceci est un commentaire FCO

Algorithmique et Structures de Données

Page 8 /43

4. LES STRUCTURES FONDAMENTALES 4.1. Notion de programme propre On appelle programme propre un traitement qui possède une seule entrée et une seule sortie. Avantage: si l'on doit apporter des modifications dans ce programme propre, il est beaucoup plus facile de déterminer l'impact de ces modifications . e

T T1 s

Les structures fondamentales utilisées pour écrire les algorithmes sont au nombre de 3. 4.2. Enchaînement des actions On utilisera cette structure lorsqu'une action doit succéder à une autre e1

T1, T2 : traitements ou algorithmes (programmes propres) T1 T

Exemples: DEBUT CO traitement 1 FCO s1 e2

T2 T

FIN

CO fin du traitement 1 FCO

DEBUT

CO traitement 2 FCO

FIN

CO fin du traitement 2 FCO

s2

Le résultat obtenu est aussi un programme propre

Algorithmique et Structures de Données

Page 9 /43

4.3. Structure alternative ou conditionnelle

e

SI Condition ALORS T1; SINON T2; FSI

Condition

T1

T2

s

Condition désigne une expression booléenne dont la valeur est VRAI ou FAUX. T1 et T2 désignent une suite d'instructions (pouvant elles mêmes être des structures alternatives). La structure alternative est une structure parenthésée, chaque partie étant délimitée par les symboles SI, ALORS, SINON et FSI. Le traitement T2 est facultatif. Exemple : ALGORITHME MAXIMUM_DE_DEUX_NOMBRES VAR A, B : ENTIER; CO les deux nombres à comparer FCO MAX: ENTIER; CO le plus grand FCO DEBUT ECRIRE('Entrez le premier nombre :'); LIRE(A); ECRIRE('Entrez le deuxième nombre :'); LIRE(B); SI A >= B ALORS MAX <- a; SINON MAX <- b; FSI ECRIRE('le maximum de ', A,' et de ',B,' est : ',MAX); FIN On pourrait remplacer la conditionnelle de cet exemple par MAX <- B; SI A > B ALORS MAX <- A FSI On remarque que cette alternative ne comporte pas de clause SINON.

Algorithmique et Structures de Données

Page 10 /43

4.4. Structure itérative La notion d'itération est l'une des notions fondamentales de l'algorithmique. Elle est utilisée lorsque l'on doit exercer plusieurs fois le même traitement sur un même objet. Si le nombre de répétitions est grand, il serait fastidieux de réécrire n fois le même algorithme et même impossible si n était inconnu.

Lorsque la condition a pour valeur VRAI, on exécute le traitement T1 puis on revient tester la condition. Il est donc nécessaire que l'action T1 modifie la condition sinon l'itération ne s'arrêtera pas. Lorsque la condition a pour valeur FAUX, le traitement séquentiel continue. L'itération est terminée.

e V RA I C o n d itio n FA U X T1

s

En pseudo-langage, on écrira la structure itérative de la façon suivante: TANT QUE Condition FAIRE DEBUT T1; FIN Il existe bien d'autres méthodes pour représenter une itération. Théorème : structures.

Tout programme propre peut être ramené à l'un de ces trois types de

Algorithmique et Structures de Données

Page 11 /43

5. EXERCICES Ex1 : Marchand de vin Un marchand de vin expédie une quantité Q de bouteilles de prix unitaire P. Si le total de la commande HT est au moins égal à 500 F, le port est gratuit sinon il est facturé 10% de la commande HT avec un minimum de 10 F. Ecrire l'algorithme qui donne le détail et la somme à payer pour des valeurs entrées P et Q. La TVA (taux en cours) ne s'applique pas sur les frais de port. Ex2 : Facture EDF On veut établir la facture d'un abonné EDF, connaissant le dernier et l'avant-dernier relevé du compteur. Les règles de tarification sont les suivantes: Consommation inférieure à 100 kwh : prix du kwh = 0.5 F Consommation comprise entre 100 kwh et 500 kwh : prix du kwh = 0.4 F Consommation supérieure à 500 kwh : prix du kwh = 0.35 F Coût de l'abonnement 250 F Ecrire l'algorithme qui donne la montant de la facture à acquitter toutes taxes comprises. Ex3 : Transformation en heures Soient x et y, deux nombres représentant deux temps exprimés en secondes. Ecrire un algorithme qui transforme ces deux nombres en heures, minutes et secondes, qui calcule et affiche leur somme à partir de la transformation effectuée. On vérifiera que la somme obtenue est égale à la somme de x et y en secondes. Ex4 : Equation Ecrire l'algorithme de résolution d'une équation du second degré. Ex5 : Moyenne Ecrire un algorithme qui lit une suite de nombres non nuls terminée par le marqueur 0 et affiche la moyenne des nombres lus. Ex6 : Jeu de l'oie. Un joueur est caractérisé par un nombre PLACE compris entre 0 et 66 qui situe sa position sur le jeu de l'oie. Donner l'algorithme permettant de déterminer la nouvelle place du joueur après un jet de 2 dés DE1 et DE2, sachant qu'il applique les règles suivantes: - il faut arriver juste à 66 sinon on recule d’autant de cases que l’on dépasse 66. - une oie toutes les 9 cases sauf au 63 double le déplacement (9, 18, 27, ...) - une tête de mort au 58 renvoie au départ (position 0). Ex7 : Suite Soit S une suite de nombres entiers positifs ordonnés par ordre croissant. Ecrire un algorithme permettant de déterminer la longueur L de la plus longue sous-suite extraite de S et ne comportant que des éléments identiques. Ex8: Série Ecrire un algorithme qui calcule la somme de la série 1 - 1/3 + 1/5 - 1/7 + ... avec une précision de l'ordre de Epsilon lu.

Algorithmique et Structures de Données

Page 12 /43

6. LES STRUCTURES COMPLEMENTAIRES 6.1. L'alternative généralisée

e

Expression

T1

T2

T3

T4

s

Suivant la valeur de l'expression, un des traitements T1, T2, T3 ou T4 est exécuté. Ce traitement pourrait être obtenu à l'aide de SI imbriqués. SI valeur = valeur1 ALORS T1; SINON SI valeur = valeur2 ALORS T2; SINON SI valeur = valeur3 ALORS T3; SINON SI valeur = valeur4 ALORS T4; FSI FSI FSI FSI Beaucoup de langages proposent en outre un traitement pour les autres cas.

Algorithmique et Structures de Données

Page 13 /43

En pseudo-langage, on écrira CAS expression valeur1 T1; valeur2 DEBUT T21; T22; FIN valeur3 T3; valeur4 T4; AUTRE T_autre; FIN 6.2. La répétition

e

On effectue le traitement T Si la condition est VRAI, on recommence le traitement T L'itération se terminera lorsque la condition sera FAUX

T

Condition VRAI s

Algorithmique et Structures de Données

FAUX

Page 14 /43

A l'aide des structures fondamentales, on aurait le schéma suivant: e T

VRAI

Condition

FAUX

T

DEBUT T TANT QUE Condition FAIRE DEBUT T FIN FIN Bien noter que dans le cas présent, la condition est une condition de continuation

s

Traduction de la répétition en pseudo-langage REPETER DEBUT T1; T2; FIN JUSQU'A condition (Ici, la condition est une condition de terminaison) Théorème : il faut toujours se ramener à une des structures (fondamentales ou complémentaires). Exercice : Traduire le schéma suivant: e T1

V RA I

T2

C o n d itio n

FA U X s

Algorithmique et Structures de Données

Page 15 /43

7. METHODE D'ANALYSE 7.1. Les buts: - Obtenir une analyse et une programmation de haut en bas selon une décomposition arborescente qui autorise le fractionnement des programmes en modules de taille facilement lisible (par exemple de la taille d'une page de listing). -

Supprimer, grâce à cette analyse descendante, la phase d'intégration (partie très délicate lors de projets importants).

-

Rendre possible la lecture des modules de haut niveau par des non-spécialistes.

-

Faciliter la maintenance et l'extensibilité en donnant la possibilité de modifier une arborescence, sans affecter ce qui est au niveau supérieur.

-

Diminuer les risques d'erreurs de programmation.

-

Fournir aux programmeurs un mode commun de décomposition des problèmes.

7.2. Analyse descendante C'est une méthode de décomposition des problèmes. Soit le problème A à résoudre Problème A AI1

AI2 AE2 AE21

AE11

AE12

AE22

AE13

1111 On a tout d'abord décomposé le problème A en 2 actions intermédiaires (AI1 et AI2) et 1 action élémentaire AE2 AI1 est ensuite décomposé en 3 actions élémentaires AE11, AE12 et AE13 AI2 est ensuite décomposé en 2 actions élémentaires AE21 et AE22 Exemple : Problème de la crevaison d'une roue de voiture. Une telle situation peut sembler idyllique, mais il y a une contrepartie: l'analyse descendante ne permettra que rarement de définir des sous-programmes identiques appelés de points différents. L'analyse Top-Down doit être le guide général, mais il peut être profitable, dans le cas de traitements complexes, d'osciller quelque peu entre analyse descendante et montante.

Algorithmique et Structures de Données

Page 16 /43

7.3. Analyse ascendante Elle consiste à identifier dès le début les actions élémentaires qu'il faudra savoir résoudre. Avec la méthode descendante appliquée de façon rigide, il est possible de rencontrer ou de résoudre plusieurs fois le même problème ou des problèmes voisins. La méthode ascendante consiste à déterminer les objets (ou classes d'objets) de l'application, une classe d'objets étant caractérisée: - par un ensemble de valeurs ou d'états (on parle aussi d'attributs ou de propriétés), - et par un ensemble d'actions ou d'opérations sur ces objets d'autre part. 7.4. Les méthodes dirigées par les données Dans la méthode descendante, l'accent est mis sur la décomposition en actions. Les données manipulées et nécessaires sont affinées au fur et à mesure mais ne jouent pas un rôle stratégique dans la décomposition. Dans un système de gestion de base de données (SGBD), le programmeur commence par décrire les données de l'application (parce que les données jouent le rôle central). Il utilise pour cela un langage de description de données (LDD) qui permet de décrire les objets ou les classes d'objets qu'il utilise ainsi que les associations entre classes d'objets et les contraintes d'intégrité éventuelles. On construit ainsi le modèle conceptuel des données. On écrite ensuite les programmes qui permettront la création, la mise à jour de la base de données en utilisant un langage de manipulation de données (LMD). 7.5. Evolution de la programmation impérative vers la programmation objet 7.5.1. 1ère étape: la programmation procédurale Langages Algol, Pascal, C Notions de types Structures de contrôles 7.5.2. 2ème étape: la programmation modulaire A un module correspond un sous-système, ce sous-système rend au reste de l'application un service. Pour l'utilisateur, il suffit de savoir ce que fait le module et comment on y accède. C'est le premier pas vers le composant logiciel réutilisable. 7.5.3. 3ème étape: la programmation par type générique (ou abstraction) Une abstraction fait ressortir les caractéristiques essentielles d'un objet (qui le distinguent de tous les autres genres d'objets) et donc procure des frontières conceptuelles rigoureusement définies par rapport au point de vue de l'observateur. (Ex : le chat vu par la mémère et par le vétérinaire). 7.5.4. 4ème étape: les objets L'accent est mis sur la réutilisation et l'adaptation en utilisant les mécanismes d'héritage (ou de sous-typage) et la programmation par interfaces. On décrit le monde comme étant formé d'objets ainsi que les relations existant entre les objets.

Algorithmique et Structures de Données

Page 17 /43

8. LES SOUS-PROGRAMMES Ce nouvel objet (au sens algorithmique) permet au programmeur de traiter un problème sans s'embarrasser des détails des sous-problèmes. En effet, à l'intérieur du programme (principal) en question, le traitement relatif à un sous-problème est simplement désigné par un identificateur (appel de sous-programme). Le détail de ce sous-programme est décrit par ailleurs dans la partie déclaration de sousprogramme. Jusqu'à présent, un identificateur était associé à une valeur (donnée), il est ici associé à une suite d'instructions. Un sous-programme peut comporter des données (types, variables etc...) qui lui sont propres. On parle alors de variables locales au sous-programme. On peut noter dès à présent que ces variables existeront uniquement pendant l'exécution du sous-programme. 8.1. Procédures sans paramètres Traduction de la procédure sans paramètre en pseudo-langage PROCEDURE id_procedure; VAR I : ENTIER; DEBUT T; FIN Dans le programme principal, l'appel à ce sous-programme se fera de la façon suivante: DEBUT ... id_procedure; ... FIN

Algorithmique et Structures de Données

Page 18 /43

8.2. Procédures avec paramètres fixes Bien souvent, une procédure utilise des données fournies par le programme principal (ou par une autre procédure). La procédure sera écrite avec des arguments fictifs appelés paramètres formels auxquels on fera correspondre lors de l'appel les données réelles appelées paramètres effectifs ou réels. Traduction de la procédure avec paramètre fixe en pseudo-langage PROCEDURE id_procedure ( parametre_formel : type du paramètre) VAR I : ENTIER; DEBUT T; FIN Dans le programme principal, l'appel à ce sous-programme se fera de la façon suivante: VAR I, J, K : ENTIER; DEBUT ... id_procedure(J); ... id_procedure(5); ... FIN

Algorithmique et Structures de Données

Page 19 /43

8.3. Procédures-Fonctions Lorsqu'une procédure doit rendre un résultat unique de type simple, il est commode de définir cette procédure comme une fonction dont l'utilisation est analogue à celui des fonctions mathématiques usuelles (SIN(x), TANG(x), COS(x) etc...). Traduction de la procédure-fonction en pseudo-langage PROCEDURE id_proc (parametre_formel : type du paramètre) : resultat : type_resultat ou FONCTION id_fonction(parametre_formel : type du paramètre) : type_resultat VAR I : ENTIER; DEBUT T; FIN Dans le programme principal, l'appel à ce sous-programme se fera de la façon suivante: VAR I, J, K : ENTIER; DEBUT ... I <- id_proc(J); ... FIN

Algorithmique et Structures de Données

Page 20 /43

8.4. Procédures avec paramètres modifiables Alors qu'une procédure-fonction ne rend qu'un seul résultat, il est quelquefois intéressant d'utiliser des procédures qui rendent plusieurs résultats. Ceci se réalise à l'aide de procédures à paramètres modifiables. Traduction de la procédure à paramètres modifiables en pseudo-langage PROCEDURE id_procedure ( VAR parametre1_formel : type du paramètre1 , VAR parametre2_formel : type du paramètre2 etc...) VAR ENT I; DEBUT T; FIN Dans le programme principal, l'appel à ce sous-programme se fera de la façon suivante: VAR I, J, K : ENT; DEBUT ... id_procedure(I,J); ... FIN A la fin (ou au cours) de l'exécution du sous-programme, les valeurs de I et J auront pu être changées.

Algorithmique et Structures de Données

Page 21 /43

9. LA RECURSIVITE La récursivité, c'est la possibilité de faire figurer dans la définition d'un objet une référence à ce même objet. Beaucoup de langages autorisent la récursivité simple et la récursivité croisée. Il y a récursivité simple lorsqu'une procédure (ou fonction) en cours d'exécution s'appelle elle-même. Il y a récursivité croisée lorsqu'une procédure A appelle une procédure B qui elle-même appelle la procédure A. A chaque appel du sous-programme récursif, les variables locales, les paramètres et l'adresse de retour sont empilés dans une zone mémoire appelée pile. A la fin de chaque exécution du sous-programme, les éléments empilés sont dépilés. Exemple : calcul de la factorielle d'un nombre n n! = n(n-1)(n-2) ... 2*1 si n > 0 n! = 1 On peut bien entendu résoudre ce problème de manière itérative classique. Méthode si on désire le résoudre par un algorithme récursif: - paramétrage du problème : on détermine les éléments dont dépend la solution et qui caractérisent la taille du problème. - recherche du cas trivial qui donne la solution (condition d'arrêt) ici lorsque n = 1 on connaît le résultat - décomposition du cas général en cas plus simples : tant que le cas trivial n'est pas atteint, il y a modification de la valeur du paramètre et nouvel appel de la fonction. D'où l'algorithme FONCTION FACT(N : ENTIER) : ENTIER DEBUT SI N=1 RETOURNER(1); SINON RETOURNER(N*FACT(N-1)); FSI FIN En langage C, int fact(int n)

/* fonction fact retournant un entier et acceptant un paramètre de type entier */

{ if (n == 1) return(1); else return(n*fact(n-1)); } Autre exemple : Tours de Hanoi

Algorithmique et Structures de Données

Page 22 /43

10.LES STRUCTURES DE DONNEES STATIQUES Une structure de données est un ensemble organisé d'informations reliées logiquement, ces données pouvant être traitées collectivement ou individuellement. L'exemple le plus simple est un tableau mono-dimensionnel ou vecteur. Une structure de données est caractérisée par ses composantes mais aussi par son mode d'utilisation. On verra par la suite que des structures semblables sont considérées différentes car leurs modes d'exploitation sont fondamentalement différents (Exemple : les piles et les listes). 10.1.

Les tableaux

Il est fréquent d'utiliser dans un problème des objets réunis par des caractéristiques communes. Par exemple les jours de la semaine, les élèves d'une classe etc... Il est alors pratique de donner à cet ensemble d'éléments un même nom. Chaque élément est désigné par ce nom et un indice donnant le rang de cet élément. Un tel regroupement de données, toutes de même type est un tableau. Déclaration VAR Tab : ENTIER[inf:sup]; Tab est une variable de type tableau d'entiers dont l'indice peut prendre les valeurs comprises entre inf et sup (inf<sup). Le nombre d'éléments du tableau est sup-inf+1. Le type du tableau est un type simple (entier, réel, booléen, caractère ou chaîne). Pour sélectionner un élément du tableau, il faut préciser son indice de la façon suivante: Tab[I] où I est une expression de type scalaire à résultat de type scalaire dont la valeur est dans l'intervalle de définition des bornes du tableau.

Algorithmique et Structures de Données

Page 23 /43

Exemple: VAR Tab : ENTIER[0:10]; I : ENTIER; DEBUT POUR I=0,10 FAIRE LIRE(Tab[I]); FIN POUR I=0,10 FAIRE ECRIRE(Tab[I]); FIN FIN L'itération de type boucle POUR est très souvent utilisée pour le parcours d'un tableau. Le type TABLEAU peut être multidimensionnel. Chaque élément est alors repéré par plusieurs indices. La déclaration d'un tel tableau est la suivante: VAR RUBIK : ENTIER[1:3,1:3,1:3]; Ce tableau peut être considéré comme un tableau de tableau de tableau.

1

1

1

2

2

2

3

3

3

5

Exemple : RUBIK[2,1,3] contient la valeur 5. On peut constater que chaque case du tableau de gauche sur le schéma ci-dessus contient un tableau dont chaque élément contient un tableau de 3 entiers.

Algorithmique et Structures de Données

Page 24 /43

10.2.

Les enregistrements

Un enregistrement (ou record ou structure) est une structure constituée d'un nombre fixe de composants appelés champs. Les champs peuvent être de différents types et chaque champ comporte un identificateur de champ permettant de le sélectionner. Exemple: TYPE T_ABONNE = ENREG NOM PRENOM AGE SALAIRE FIN

: CHAINE; : CHAINE; : ENTIER; : REEL;

Une variable du type T_ABONNE sera déclarée et utilisée de la façon suivante: VAR ABONNE1: T_ABONNE; Dans le programme utilisant cette variable, ABONNE1.NOM identifie le champ NOM de l'enregistrement ABONNE1 de type T_ABONNE. Les opérations permises sur le type chaîne seront possibles sur ABONNE1.NOM (lecture, écriture, affectation, comparaison, etc...). Si on déclare une autre variable ABONNE2 du type T_ABONNE, les opérations d'affectation seront possibles entre ABONNE1 et ABONNE2.

Algorithmique et Structures de Données

Page 25 /43

11.LE TYPE POINTEUR 11.1.

Généralités

Un pointeur est un objet (au sens informatique) qui permet d’accéder à un autre objet, l’objet pointé. Un objet pointeur peut changer de valeur en cours d’exécution, il peut donc pointer sur des objets différents (mais de même type). TYPE T_POINTEUR = ^CHAINE ; VAR POINTEUR : T_POINTEUR ; POINTEUR, variable du type T_POINTEUR, pourra pointer , c'est-à-dire pourra accéder à une variable de type CHAINE; La variable pointée (ici de type CHAINE) n'existe pas lors de l'exécution. Il faudra la créer en fonction des besoins. La variable pointée est une variable dynamique contrairement aux variables statiques utilisées jusqu'à présent. Les deux variables mises en jeu seront notées: - POINTEUR: le pointeur, l'adresse - POINTEUR^ qui sera la variable pointée par POINTEUR La variable POINTEUR^ pourra être manipulée exactement comme une variable de type CHAINE. On pourra lui affecter une valeur, tester la valeur etc. Exemples : POINTEUR^ <- 'MARIE' TANT QUE POINTEUR^ <> 'ZORRO' FAIRE DEBUT …; FIN

Algorithmique et Structures de Données

Page 26 /43

12.LES STRUCTURES DE DONNEES DYNAMIQUES 12.1. Présentation d'une liste simple Si nous souhaitons créer une liste de noms dont le nombre est inconnu au moment de la conception, il faut pouvoir relier plusieurs pointeurs (variables pointées) entre eux. DEBUT

MARIE

SUIVANT

Où DEBUT est un pointeur sur un enregistrement contenant un champ Nom de type CHAINE et un champ Suivant de type T_POINTEUR. Pour construire une liste, il suffira donc de raccrocher plusieurs cellules de ce type les unes derrière les autres. TYPE T_POINTEUR = ^CELLULE; CELLULE = ENREG NOM : CHAINE; SUIVANT : T_POINTEUR; FIN VAR DEBUT : T_POINTEUR; On a alors - DEBUT pointe sur DEBUT^ qui est la première cellule - DEBUT^ est un enregistrement qui contient : - DEBUT^.NOM qui est de type CHAINE - DEBUT^.SUIVANT qui peut pointer vers une nouvelle cellule 12.2. La valeur spéciale NIL Pour tester la fin des structures pointées, ou pour indiquer qu'un pointeur ne pointe sur rien, on utilise la valeur spéciale NIL qui : - Correspond à un pointeur qui ne pointe sur rien - Est compatible avec tous les pointeurs. POINTEUR <- NIL ; SI DEBUT = NIL ALORS …

Algorithmique et Structures de Données

Page 27 /43

12.3.

Structure de liste

12.3.1. La pile Une pile est une structure linéaire dont seul le dernier élément peut être ajouté ou enlevé. Une image en est donnée par une pile d'assiettes.

Dépiler Empiler 12.3.2. La queue (file) A l'inverse de la pile, une queue est une structure où le premier arrivé est le premier parti. Une image de la queue est la file d'attente. Pour placer une cellule à la fin de la queue, il faut pouvoir accéder facilement au pointeur suivant de la dernière cellule: - pour la première cellule, il s'agit de DEBUT^.SUIVANT, - pour la deuxième, c'est DEBUT^.SUIVANT^.SUIVANT, etc… Dans la pratique, on préfère utiliser un pointeur particulier qui pointera en permanence sur la dernière cellule. Ce pointeur particulier (FIN) sera mis à jour à chaque ajout d'une cellule. DEBUT

JOE

LUC

ZORRO

NIL

FIN

Algorithmique et Structures de Données

Page 28 /43

12.4.

Structures non linéaires

12.4.1. Les graphes Lorsqu'un élément pointe vers ou est pointé par plusieurs éléments, nous avons affaire à une structure de graphe. Par exemple, on fait correspondre à un client plusieurs factures et ces factures peuvent avoir plusieurs articles. TYPE P_ARTICLE = ^ARTICLE; ARTICLE = ENREG NUMERO : ENTIER; LIBELLE : CHAINE; QUANTITE : ENTIER; PRIX : REEL; P_SUIVANT : P_ARTICLE; FIN P_FACTURE = ^FACTURE; FACTURE = ENREG NUMERO_FACT : ENTIER; DATE : CHAINE; P_ART : P_ARTICLE; FACT_SUIVANTE : P_FACTURE; FIN P_CLIENT = ^CLIENT; CLIENT = ENREG NOM : CHAINE; P_FACT : P_FACTURE; CLI_SUIVANT : P_CLIENT; FIN DUPONT

DURAND

525

02/04/97

2

Colle

100

15

21

Vis

10

1,25

26

Clous

100

0,25

526

Algorithmique et Structures de Données

05/04/97

NIL

Page 29 /43

12.4.2. Les arbres Un arbre est une structure non linéaire, dont chaque élément n'est pointé que par un seul élément. - Les éléments sont appelés des nœuds. - Le premier élément qui n'est pointé par rien est appelé la racine. - Les éléments qui ne pointent sur rien sont appelés les feuilles.

Un arbre binaire est un arbre dont les éléments pointent au plus vers deux autres éléments.

Ces arbres binaires peuvent être utilisés pour effectuer des tris ou des recherches rapides. La propriété fondamentale est que chaque cellule comporte: - Une valeur simple ou complexe (type simple ou structuré) - A gauche un sous-arbre contenant des valeurs plus petites - A droite un sous-arbre contenant des valeurs plus grandes TYPE P_CELLULE = ^CELLULE; CELLULE = ENREG VALEUR : CHAINE; PTG : P_CELLULE; PTD : P_CELLULE; FIN

Algorithmique et Structures de Données

Page 30 /43

13.LES FICHIERS 13.1.

Généralités sur l'organisation des informations.

On a souvent besoin de stocker différentes informations sur des supports physiques pour une utilisation éventuelle ultérieure. La notion d'accès à une information rangée devient fondamentale. Les différentes primitives sur les supports d'information sont: - accès à un élément. - recherche d'un élément. - insertion d'un nouvel élément. - suppression d'un élément. - copie d'une partie des informations. - éclatement de l'ensemble en plusieurs sous-ensemble. - fusion de plusieurs sous-ensembles en un seul. - tri d'un ensemble. 13.2. Notion de fichier Les différentes informations que l'on aura à traiter seront donc stockées sur un support physique. Il va donc falloir organiser les différents transferts entre la mémoire et ce support physique grâce à différentes primitives d'accès. L'organisation d'un fichier est la structure logique permanente établie au moment où le fichier est crée. 13.2.1. Définition Un fichier est un ensemble organisé d'informations (articles ou enregistrements) de même nature susceptibles de faire l'objet de traitements divers.

Algorithmique et Structures de Données

Page 31 /43

13.2.2. Les accès aux fichiers On accède généralement aux fichiers par deux méthodes principales: -accès séquentiel. -accès direct. 13.2.2.1. Accès séquentiel Soit F un fichier: ce fichier est dit à accès séquentiel si l'on ne peut accéder à un élément quelconque de rang n qu'après avoir accédé aux n-1 éléments qui le précèdent. On se déplace dans ce type de fichier en passant d'un élément à son suivant. Il existe deux éléments particuliers: le premier qui nous permet d'accéder au fichier et le dernier qui nous signale qu'il n'a pas de suivant. 1

2

3

4

13.2.2.2. Accès direct Soit F un fichier: ce fichier est dit à accès direct lorsqu'il suffit de connaître le rang n de l'élément recherché pour y accéder, sans parcourir le reste du fichier. Cette méthode est en général plus intéressante en temps et en efficacité. 1

2

3

4

C o u lo ir

13.3.

Les fichiers en algorithmique

13.3.1. Déclaration d'une variable de type fichier VAR fic : FICHIER; où fic est l'identificateur (= nom logique).

Algorithmique et Structures de Données

Page 32 /43

13.3.2. Assignation d'un nom de fichier logique ASSIGNER (nom_de_fichier_logique, nom_de_fichier_physique) où nom_de_fichier_physique est soit une constante chaîne soit une variable chaîne. Le nom du fichier physique correspond au nom du fichier sur le support physique (en général disque magnétique, bande, etc...). Ce nom peut comprendre le chemin (absolu ou relatif) du fichier. L'opération d'assignation est obligatoire, tous les accès au fichier se feront à l'aide du nom de fichier logique. 13.3.3. Actions et opérations sur les fichiers Ouverture. - en écriture : OUVREECR(nom_de_fichier_logique); - en lecture : OUVRELEC(nom_de_fichier_logique); Fermeture. FERMER(nom_de_fichier_logique); Ecriture dans un fichier. ECRIRE(nom_de_fichier_logique,expression); ECRIRE(fic,expression) écrit à partir de la position courante de la tête d'écriture sur le fichier fic la valeur de l'expression. La tête d'écriture est ensuite positionnée sur l'élément suivant. Lecture dans un fichier. LIRE(nom_de_fichier_logique, variable); LIRE(fic,variable) Comme pour une lecture clavier, le type de la variable doit être le même que celui de l'élément lu. La tête de lecture est ensuite déplacée sur l'élément suivant à la fin de l'opération.

Algorithmique et Structures de Données

Page 33 /43

14.SCHEMAS DE TRADUCTION EN LANGAGE C Langage de description 1-Commentaires CO FCO 2-Opérateurs arithmétiques +-*/ DIV MOD 3-Opérateurs logiques OU ET NON 4-Opérateurs relationnels = (égal) <> > < >= <= 5-Affectation <6-Opérateur de séquentialité ; 7-Déclarations de variables VAR i,j : ENTIER; x,y : REEL; b : BOOLEEN; ch : CHAINE; 8-Instruction alternative SI condition ALORS T1 SINON T2 FSI SI condition ALORS DEBUT T11; T12; FIN SINON DEBUT T21; T22; FIN FSI

Algorithmique et Structures de Données

Langage C /*

*/

+-*/ / entre 2 entiers % || && ! == != > < >= <= = ; (pour séparer deux instructions) int i,j; float x,y; Pas de type booléen en langage C char ch[10]; if(condition) T1; else T2; if(condition) { T11; T12; } else { }

T21; T22;

Page 34 /43

9-Itérations TANT QUE condition FAIRE DEBUT T1; T2; FIN REPETER DEBUT T1; T2; FIN JUSQU'A condition 10-Sous-programmes Procédure sans paramètre PROCEDURE P1; Appel P1;

while(condition) { T1; T2; } do {

T1; T2;

} while( !condition) ; /* Attention NON CONDITION */

void p1(void) Appel p1();

Procédure avec paramètre PROCEDURE P2(I,J:ENTIER); Appel P2(K,L); Appel P2(3,6);

void p2(int i, int j) Appel p2(k,l); Appel p2(3,6);

Fonction renvoyant une valeur FONCTION F1 : ENTIER; Appel J = F1;

int f1(void); Appel lvalue = f1();

Passage de paramètres

En C, tous les paramètres sont passés par valeur.

Paramètres non modifiables (par valeur) PROCEDURE P3(I,J : ENTIER); Appel P3(k,8);

void p3(int i, int j) Appel p3(k,8);

Paramètres modifiables PROCEDURE P4(VAR I : ENTIER); Appel P4(K); K pourra être modifié par la procédure P4

void p4(int *i) Appel p4(&j);

11-Enregistrement TYPE T_ABONNE = ENREG NOM : CHAINE; PRENOM : CHAINE; AGE : ENTIER; FIN VAR ABONNE : T_ABONNE;

struct t_abonne { char nom[15]; char prenom[10]; int age; } struct t_abonne abonne;

12-Pointeurs TYPE T_POINTEUR = ^CHAINE ;

typedef char * t_pointeur;

VAR POINTEUR : T_POINTEUR ;

t_pointeur pointeur;

Algorithmique et Structures de Données

Page 35 /43

13-Fichiers VAR FIC : FICHIER; NOMFIC : CHAINE; ABONNE : T_ABONNE;

FILE *fic; char nomfic[10]; struct t_abonne abonne;

ASSIGNER(FIC, NOMFIC); OUVREECR(FIC); OUVRELEC(FIC); FERMER(FIC); LIRE(FIC,ABONNE); ECRIRE(FIC,ABONNE);

fic = fopen(nomfic,"w"); fic = fopen(nomfic,"r"); fclose(fic); fread(&abonne,sizeof(abonne),1,fic); fwrite(&abonne,sizeof(abonne),1,fic);

Algorithmique et Structures de Données

Page 36 /43

15.SCHEMAS DE TRADUCTION EN LANGAGE PASCAL Langage de description

Langage Pascal

1-Commentaires CO FCO 2-Opérateurs arithmétiques +-*/ DIV MOD 3-Opérateurs logiques OU ET NON 4-Opérateurs relationnels = (égal) <> > < >= <= 5-Affectation <6-Opérateur de séquentialité ; 7-Déclarations de variables VAR i,j : ENTIER; x,y : REEL; b : BOOLEEN; ch : CHAINE; 8-Instruction alternative SI condition ALORS T1 SINON T2 FSI SI condition ALORS DEBUT T11; T12; FIN SINON DEBUT T21; T22; FIN FSI

{ } ou (*

*)

+-*/ DIV entre 2 entiers MOD OR AND NOT = <> > < >= <= := ; {n’est pas considéré comme un opérateur} VAR

i,j : INTEGER; x,y : REAL; b : BOOLEAN ch : String[10];

IF condition THEN T1 ELSE T2; IF condition THEN BEGIN T11; T12; END ELSE BEGIN T21; T22; END;

9-Itérations TANT QUE condition FAIRE DEBUT T1; T2; FIN REPETER DEBUT T1; T2; FIN JUSQU'A condition

WHILE condition DO BEGIN T1; T2; END; REPEAT T1; T2; UNTIL condition

10-Sous-programmes Procédure sans paramètre PROCEDURE P1; Appel P1;

Procedure P1; Appel P1;

Procédure avec paramètre PROCEDURE P2(I,J:ENTIER); Appel P2(K,L); Appel P2(3,6);

Procedure p2(i, j : INTEGER) Appel p2(k,l); Appel p2(3,6);

Fonction renvoyant une valeur FONCTION F1 : ENTIER; Appel J = F1;

Function f1 : INTEGER; Appel lvalue := f1;

Passage de paramètres Paramètres non modifiables (par valeur) PROCEDURE P3(I,J : ENTIER); Appel P3(k,8);

Procedure P3(i,j : INTEGER) Appel p3(k,8);

Paramètres modifiables PROCEDURE P4(VAR I : ENTIER); Appel P4(K); K pourra être modifié par la procédure P4

Procedure P4(VAR I : INTEGER) Appel p4(k);

11-Enregistrement TYPE T_ABONNE = ENREG NOM : CHAINE; PRENOM : CHAINE; AGE : ENTIER; FIN VAR ABONNE : T_ABONNE;

TYPE T_abonne = RECORD nom : String[15]; prenom : String[10]; age : INTEGER; End; VAR Abonne : T_abonne;

12-Pointeurs TYPE T_POINTEUR = ^CHAINE ;

TYPE T_pointeur = ^STRING;

VAR POINTEUR : T_POINTEUR ;

VAR

Pointeur T_pointeur;

13-Fichiers VAR FIC : FICHIER; NOMFIC : CHAINE; ABONNE : T_ABONNE; ASSIGNER(FIC, NOMFIC); OUVREECR(FIC); OUVRELEC(FIC); FERMER(FIC); LIRE(FIC,ABONNE); ECRIRE(FIC,ABONNE);

VAR

fic : file of T_abonne; NomFic : String[10]; Abonne : T_abonne;

ASSIGN(fic, NomFic); Rewrite(Fic); { en écriture } Reset(Fic); {lecture ou lecture/écriture } Close(fic); Read(Fic, Abonne); Write(Fic, Abonne);

TABLE DES MATIERES 1. INTRODUCTION...............................................................................................................................................1 2. INTRODUCTION A L’ALGORITHMIQUE.................................................................................................2 2.1. QU’EST-CE QU’UN ALGORITHME ?.....................................................................................................................2 2.2. PROPRIÉTÉS D'UN ALGORITHME.........................................................................................................................2 2.3. PLACE DE L'ALGORITHME DANS LA RÉSOLUTION D'UN PROBLÈME INFORMATIQUE..........................................................3 2.4. NOTION DE PSEUDO-LANGAGE...........................................................................................................................3 2.5. ELABORATION D'UN ALGORITHME......................................................................................................................3 3. OBJETS SIMPLES, TYPES ET ACTIONS ELEMENTAIRES..................................................................5 3.1. TYPE D'UN OBJET...........................................................................................................................................5 3.2. LES OBJETS ...................................................................................................................................................6 3.3. ACTIONS ÉLÉMENTAIRES ..................................................................................................................................6 3.3.1. Opérateurs sur les types simples...............................................................................................................7 3.3.2. Affectation.................................................................................................................................................7 3.3.3. Lecture et écriture.....................................................................................................................................8 3.3.4. Commentaires............................................................................................................................................8 4. LES STRUCTURES FONDAMENTALES ....................................................................................................9 4.1. NOTION DE PROGRAMME PROPRE.......................................................................................................................9 4.2. ENCHAÎNEMENT DES ACTIONS...........................................................................................................................9 4.3. STRUCTURE ALTERNATIVE OU CONDITIONNELLE...................................................................................................10 4.4. STRUCTURE ITÉRATIVE..................................................................................................................................11 5. EXERCICES.....................................................................................................................................................12 6. LES STRUCTURES COMPLEMENTAIRES .............................................................................................13 6.1. L'ALTERNATIVE GÉNÉRALISÉE.........................................................................................................................13 6.2. LA RÉPÉTITION............................................................................................................................................14 7. METHODE D'ANALYSE...............................................................................................................................16 7.1. LES BUTS :..................................................................................................................................................16 7.2. ANALYSE DESCENDANTE................................................................................................................................16 7.3. ANALYSE ASCENDANTE.................................................................................................................................17 7.4. LES MÉTHODES DIRIGÉES PAR LES DONNÉES.......................................................................................................17 7.5. EVOLUTION DE LA PROGRAMMATION IMPÉRATIVE VERS LA PROGRAMMATION OBJET....................................................17 7.5.1. 1ère étape: la programmation procédurale............................................................................................17 7.5.2. 2ème étape: la programmation modulaire.............................................................................................17 7.5.3. 3ème étape: la programmation par type générique (ou abstraction)....................................................17 7.5.4. 4ème étape: les objets.............................................................................................................................17 8. LES SOUS-PROGRAMMES..........................................................................................................................18 8.1. PROCÉDURES SANS PARAMÈTRES .....................................................................................................................18 8.2. PROCÉDURES AVEC PARAMÈTRES FIXES.............................................................................................................19 8.3. PROCÉDURES -FONCTIONS...............................................................................................................................20 8.4. PROCÉDURES AVEC PARAMÈTRES MODIFIABLES...................................................................................................21 9. LA RECURSIVITE..........................................................................................................................................22 10. LES STRUCTURES DE DONNEES STATIQUES....................................................................................23 10.1. LES TABLEAUX..........................................................................................................................................23 10.2. LES ENREGISTREMENTS................................................................................................................................25 11. LE TYPE POINTEUR...................................................................................................................................26 11.1. GÉNÉRALITÉS............................................................................................................................................26 12. LES STRUCTURES DE DONNEES DYNAMIQUES...............................................................................27 12.1. PRÉSENTATION D'UNE LISTE SIMPLE................................................................................................................27 12.2. LA VALEUR SPÉCIALE NIL...........................................................................................................................27 12.3. STRUCTURE DE LISTE..................................................................................................................................28 12.3.1. La pile....................................................................................................................................................28 12.3.2. La queue (file).......................................................................................................................................28

12.4. STRUCTURES NON LINÉAIRES.........................................................................................................................29 12.4.1. Les graphes............................................................................................................................................29 12.4.2. Les arbres..............................................................................................................................................30 13. LES FICHIERS...............................................................................................................................................31 13.1. GÉNÉRALITÉS SUR L'ORGANISATION DES INFORMATIONS ......................................................................................31 13.2. NOTION DE FICHIER....................................................................................................................................31 13.2.1. Définition...............................................................................................................................................31 13.2.2. Les accès aux fichiers............................................................................................................................32 13.3. LES FICHIERS EN ALGORITHMIQUE..................................................................................................................32 13.3.1. Déclaration d'une variable de type fichier...........................................................................................32 13.3.2. Assignation d'un nom de fichier logique...............................................................................................33 13.3.3. Actions et opérations sur les fichiers....................................................................................................33 14. SCHEMAS DE TRADUCTION EN LANGAGE C....................................................................................34 15. SCHEMAS DE TRADUCTION EN LANGAGE PASCAL.......................................................................37