Développement

Introduction

Un ensemble est une collection d’objets (éléments) distincts , non ordonnés. Contrairement aux structures séquentielles ( listes , piles , files ) vues précédemment , les ensembles n’ont pas la notion d’ordre sur les places des éléments .

Seules la présence ou l’absence de l’élément importe .

La structure la plus élémentaire de représentation de donnée est l’ensemble dont les opérations fondamentales sont l’appartenance , l’adjonction et la suppression .

Une des organisation de données la plus commune aux différents langages de programmation est " la liste linéaire": on organise en liste linéaire des données qui doivent traitées séquentiellement.

En plus une liste est évolutive, c'est à dire qu'on peut ajouter et supprimer des données. Deux cas particuliers des listes jouent un rôle important en informatique: les piles et les files.

La conception d’un algorithme un peu compliqué s’effectue toujours en plusieurs étapes qui correspondent à des raffinements successifs. La 1ère version de l’algorithme est autant que possible indépendante d’une implémentation particulière. La représentation des données n’est pas fixée. A ce premier niveau les données sont considérées de manière abstraite: on se donne une notation pour les décrire ainsi l’ensemble des opérations qu'on peut leur appliquer et les propriétés de ces opérations ; on parle alors de type abstrait de données.

La récursivité est un outil extrêmement puissant pour la description des algorithmes, elle permet de les exprimer facilement, de manière concise, de prouver leur validité et de les évaluer.

Définition:

Un objet est dit récursif s’il est réutilisé directement ou indirectement dans sa définition : on définit aussi bien une structure de données récursive (structure de liste, d’arbre, … ) qu’une action paramétrée récursive.

Généralement la solution d'un problème concret est complexe et longue. La tentative de le résoudre en une seule phase peut conduire à un échec. Pour résoudre facilement et sûrement tel problème on le décompose en sous problèmes plus simples, plus ou moins indépendants. La solution complète du problème sera alors composée des solutions partielles des différents sous problèmes.