[PDF] Algorthmique luc.brun@greyc.ensicaen.fr.





Previous PDF Next PDF



Algorithmique

Les tableaux. Nicolas Delestre et Michel Mainguenaud. {Nicolas.DelestreMichel.Mainguenaud}@insa-rouen.fr. Adapté pour l'ENSICAEN par. Luc Brun.



Les algorithmes de tri

luc.brun@ensicaen.fr. Tableaux – p.1/23 Les tableaux permettent de stocker plusieurs éléments de même type au sein d'une seule entité.



Les tableaux

Les tableaux. Nicolas Delestre et Michel Mainguenaud. {Nicolas.DelestreMichel.Mainguenaud}@insa-rouen.fr Adapté pour l'ENSICAEN par. Luc Brun.



Création de pages Web Dynamiques

head : Définitions générales sur le document : Informations non affichées body : corps du document. textes



Pyramides irrégulières descendantes pour la segmentation de

7 jan. 2012 Je tiens avant-tout à remercier Luc Brun et Guillaume Damiand pour ... les cellules du complexe à l'aide d'un tableau de dimension 2n + 1 ...



Variables (locales et globales) fonctions et procédures

luc.brun@greyc.ensicaen.fr Remplir un tableau de naturels avec des notes saisies par l'utilisateur ... Trouver le plus petit naturel d'un tableau.



Traitement dimages Couleur

Si l'on doit calculer les tableaux c1c2 et c3 au début de l'algorithme



Algorthmique

luc.brun@greyc.ensicaen.fr. Sources: Habib Abdulrab (INSA Rouen) Un tableau de taille MAX





20-21 Mai 2011

Coordination : Jean-Luc Brun dans le tableau 1 ne concernaient ... Tableau 1 : Influence de la brèche endométriale sur les résultats de la FIV après ...

Algorthmique

Types abstraits de donnés

Luc Brun

luc.brun@greyc.ensicaen.fr Sources: Habib Abdulrab (INSA Rouen), Christine Porquet(ENSICAEN)

Types abstraits de donn

´ees - p.1/90

PlanDéfinition d'un type abstraitDéfinition des enregistrementsBestiaire des types abstraitsLes ensembles,Les listes,Les files,Les piles,Les arbres,Les arbres binaires,- Les arbres binaires de recherche,- Les arbres parfaits et les tas

Types abstraits de donn

´ees - p.2/90

Pourquoi les types abstraitsUn Type abstrait de données (TAD) est :1. un ensemble de données organisé et2. d'opérations sur ces données.Il est défini d'une manière indépendante de la représentation des données enmémoire. On étudie donc le concept en termes de fonctionnalités.Cette notion permet l'élaboration des algorithmes :

1. en faisant appel aux données et aux opérations abstraites du TAD (couche

supérieure),

2. suivi d'un choix de représentation du TAD en mémoire (couche

inférieure).

Types abstraits de donn

´ees - p.3/90

Décomposition en couchesLe codage de la couche supérieure donne des programmes abstraits,compréhensibles et réutilisables.Le codage de la couche inférieure implante un choix de la représentation duTAD en mémoire.???

La couche supérieure reste inchangée si on change cette couche inférieure.

Types abstraits de donn

´ees - p.4/90

Les Enregistrements

Le codage de types abstraits dans la couche inférieure nécessite souvent des

types complexes.En plus des types élémentaires : Entiers, Réels, Caractères..., on peut définirdes nouveaux types (des types composites) grâce à la notion d'enregistrement.Remarque :La notion de Classe (beaucoup plus riche)dans les langages à Objets remplace avantageusement la notiond'enregistrement.

Types abstraits de donn

´ees - p.5/90

Définition d'un enregistrementUn enregistrement est défini par n attributs munis de leurs types, n 0. Unattribut peut être de type élémentaire ou de type enregistrement.Syntaxe (en pseudo langage algorithmique) :Type= Enregistrement

début :;...:; fin

Types abstraits de donn

´ees - p.6/90

Exemple

On peut créer le type Personne, défini par un nom, un prénom, et un age.

TypePersonne= Enregistrement

début nom : ChaîneDeCharactères; prénom : Chaîne; age : Entier; fin

Types abstraits de donn

´ees - p.7/90

Enregistrements ImbriquésIl est possible d'imbriquer sans limitation des enregistrements les uns dansles

autres.Exemple : On peut définir l'adresse (par un numéro, une rue, une ville et uncode postal) comme un nouvel enregistrement, et l'ajouter comme un attributsupplémentaire à l'enregistrement Personne.

Types abstraits de donn

´ees - p.8/90

Exemple

TypeAdresse= Enregistrement

début numero : Entier; codePostal : Entier; rue,ville : ChaîneDeCharactères; fin

TypePersonne= Enregistrement

début nom,prenom : ChaîneDeCharactères; age : Entier;adresse : Adresse; fin

Types abstraits de donn

´ees - p.9/90

Accès aux attributsL'accès aux attributs d'un enregistrement se fait, attribut par attribut,

à l'aide

la notation "."

Exemple :

Var p , p1 : personne;

p.nom :=`Dupont'; p.prenom :=`Jean'; p.adresse.rue :=`Place Colbert';

Types abstraits de donn

´ees - p.10/90

Les principaux types abstraits de donnéesClassification suivant :

1. La présence d'un ordre parmis les éléments du TAD,

2. L'existence d'une méthode spécifique d'insertion/suppression.

On distingue notamment :Les ensembles : Pas de notion d'ordre.Les listes : Ensemble ordonné, sans notion de priorité d'entrée et de sortie.Les piles (FILO : First in Last Out).Les files (FIFO : First in First out)

Types abstraits de donn

´ees - p.11/90

Les ensembles

Opérations :creer() : Ensemble.vide(e : Ensemble) : Booléenajouter(x : Élement,e : Ensemble) : Booléensupprimer(x : Élément,e : Ensemble) : Booléenappartient(x,Élément, e : Ensemble) : Booléen

Plus en option :tête(e : Ensemble).Positionne un index sur un élément de l'ensemble,suivant(e : Ensemble) : Booléen.Choisi aléatoirement un élément non préalablement parcouru.courant(e : Ensemble) : Élément.Renvoi l'élément courant.

Types abstraits de donn

´ees - p.12/90

Différence

Calcule la différence de deux ensembles. Le paramètre de sortie diff est supposé vide. procéduredifference(E e1,e2 : Ensemble, S diff : Ensemble)

Déclarationx : Element

début sivide(e1)alors retournerdiff finsi tête(e1) répéter x←courant(e1) sinon appartient(x,e2)alors ajouter(x,diff) finsi jusqu'à ce que non suivant(e1) finTypes abstraits de donn´ees - p.13/90

Un exemple de codage d'ensembleUn tableau de taille MAX,un index sur l'élément courant,un index sur le dernier élément.

TypeEnsemble= Enregistrement

début courant : Naturel; dernier : Entier;

élément : Tableau[0..MAX] d'Éléments;

fin

Types abstraits de donn

´ees - p.14/90

Un début de codage (1)

fonctioncréer() :Ensemble

Déclarationens : Ensemble

début ens.courant←0 ens.dernier←-1 retournerens fin fonctionvide(e : Ensemble) :Booléen

Déclaration-

début retournere.dernier=-1 fin

Types abstraits de donn

´ees - p.15/90

Un début de codage (2)

fonctionajouter(x : Élément,e : Ensemble) :Booléen

Déclaration-

début sie.dernier = MAXalors retournerfaux finsi e.dernier←e.dernier+1

élément[e.dernier]←x

retournervrai fin

Types abstraits de donn

´ees - p.16/90

Un début de codage (3)

fonctionsupprimer(x : Élément, e : Ensemble) :Booléen

Déclarationi : Naturel

début sivide(e)alors retournerfaux finsi i←0 tant quei < e.dernierfaire sie.élément[i]=xalors sii?=e.dernieralors finsi e.dernier←e.dernier-1 sinon i←i+1 finsi fintantqueTypes abstraits de donn

´ees - p.17/90

Les listes

Un ensemble ordonné d'éléments (notion de premier, second...).

Opérations :créer() : Liste,vide(l : Liste) : Booléen,ajouter(x : Élément, l : Liste) : Booléen (à préciser).supprimer(x : Élément, l : liste) : Booléen

Opérations de parcourt :tête(l : Liste)courant(l : Liste) : Élémentsuivant(l : Liste) : Booléen (faux si vide)ajouterCourant(x : Élément, l : Liste)pré conditions :tête(l), courant(l), suivant(l) définis ssi vide(l)=faux.

Types abstraits de donn

´ees - p.18/90

Exemple

fonctionappartient(x : Élément, l : Liste) :Booléen

Déclarationcurrent : Élément

début sivide(l)alors retournerfaux finsi tête(l) répéter current←courant(l)sicurrent=xalors retournervrai finsi jusqu'à ce quenon suivant(l) retournerfaux fin

Types abstraits de donn

´ees - p.19/90

Représentation par tableau

Identique à celle vue pour les ensembles.

TypeEnsemble= Enregistrement

début courant : Naturel; dernier : Entier;

élément : Tableau[0..MAX] d'Éléments;

fin La différence apparaît dans les opérations qui doivent maintenir l'ordre des élé- ments dans la liste.

Types abstraits de donn

´ees - p.20/90

Représentation par tableauAvantages :Parcours et accès faciles au ieélément (accès direct).Possibilité de recherche efficace si la liste est triée (par exemple, recherchedichotomique).Inconvénients :Réservation, lors de la compilation de la taille maximale.Manque de souplesse et d'économie.Inefficacité de la suppression et de l'insertion pour les listes

Obligation de décaler tous les éléments entre l'élément inséré ou supprimé et le dernier élément.

Types abstraits de donn

´ees - p.21/90

Les PointeursUne variable de type pointeur est une variable qui contient une adresse.Syntaxe (en pseudo langage algorithmique) :nom :?;

nom ici est une variable de type

Exemple :

x : ?Entiernom?désigne la valeur (de type ) sur laquelle pointe la variable nom.NIL est le pointeur vide : une variable x de type pointeur initialisée à NIL

signifie que x ne pointe sur rien.allouer(nom, )permet d'allouer dynamiquement de l'espace mémoire (de type ) etfait pointer nom sur elle.libérer(nom)permet de libérer l'espace mémoire alloué ci-dessus.

Types abstraits de donn

´ees - p.22/90

Illustration

x : ?Entier allouer(x,Entier); x ?←1 1 x→ 2 4 3 x?→ 4 1

Types abstraits de donn´ees - p.23/90

Pointeurs sur Enregistrements

Soit l'enregistrement :

TypePersonne= Enregistrement

début nom : ChaîneDeCharactères; prénom : Chaîne; age : Entier;

finUn pointeur sur enregistrement se défini par :x :?PersonneOn accède à un attribut comme suit :x?.age←10

Types abstraits de donn

´ees - p.24/90

Représentation de listes par cellules

NILa2a3s1s2sisnai+1

a 1aiT

ˆete´el´ement courantqueue

t

ˆetecourant

Types abstraits de donn´ees - p.25/90

Codage par cellulesTypePointeurCellule=?CelluleTypeCellule= Enregistrement début contenu : Élément; suivant : PointeurCellule fin

TypeListe= Enregistrement

début tête : PointeurCellule; courant : PointeurCellule fin

´El´ementadresse dusuccesseur

Types abstraits de donn´ees - p.26/90

Liste vide, Ajout d'une cellule

procédureajouter(E : x Élément, E/S l : Liste)

Déclarationcel : PointeurCellule

début allouer(cel,cellule) cel ?.contenu←x sinon vide(l)alors cel?.suivant←l.courant?.suivant l.courant ?.suivant←cell sinon cel ?.suivant←NIL l.courant←cell l.tete←cell finsi fin cel x s i+1ai+2ai+1si xcel s i+1ai+2a?si fonctionvide(l : Liste) :

Booléen

Déclaration-

début retournerl.tete=NIL fin

Types abstraits de donn

´ees - p.27/90

Suppression d'une cellule

procéduresupprimer(E/S l : Liste)

Déclarationcell : PointeurCellule

début sivide(l)alors retourner sil.courant=l.têtealors libérer(l.tete) l.tete←NIL l.courant←NIL finsi sinon l.courant.suivant←cell.suivant libérer(cell) finsi couranta i+1siai+3ai+2si+1si+2 ai+2ai+3 couranta i+1sisi+1si+2

Types abstraits de donn´ees - p.28/90

Représentation des listes par cellulesAvantages :La quantité de mémoireutilisée est exactement ajustée aux besoins.Insertion et suppressionplus aisées et efficaces que dans le cas de la représentation par des tableaux.Inconvénients :Accès uniquement séquentiel.

Types abstraits de donn

´ees - p.29/90

Différents types de listesLes listes doublement chaînées.TypeCellule= Enregistrement début contenu : Élément; suivant : PointeurCellule précédent : PointeurCellule fin

Tˆete´el´ement courantqueueNIL

a2a3ai+1s

1s2sisn

t

ˆetecouranta

1aia i-1a1NILai

Types abstraits de donn´ees - p.30/90

Différents types de listesLes listes circulaires :Le pointeur de queue pointe sur la tête.Avantages : Gestion plus aisée des suppressions, insertions.

NILa2a3s1s2sisnai+1

T

ˆete´el´ement courantqueue

a ia1 courant tˆete

Types abstraits de donn´ees - p.31/90

Différents types de listesListe doublements chaînées circulaires.

Tˆete´el´ement courantqueuea

2a3ai+1s

1s2sisn

courant a ia i-1a1ai a 1 t

ˆetea

1an

Types abstraits de donn´ees - p.32/90

Les piles et les filesCorrespondent comme les liste à une suite d'éléments ordonnés.Différences :La notion d'élément courant n'existe pas.On ajoute et enlève les éléments de la structure dans un ordre précis.

Types abstraits de donn

´ees - p.33/90

Les FilesStructure de type FIFO (files d'attentes).On utilise généralement la notion de file lorsque l'on à un mécanismed'attente où le premier arrivé est le plus prioritaire (supermarché,imprimante...)←10 20 30←

Types abstraits de donn´ees - p.34/90

Files : OpérationsOpérations :créer() : File,vide(f : file) : Booléen,enfiler(x : Élément,f : File),défiler(f :File),tête(f : File) : Élément,Pré conditions :défiler(f) est défini ssi vide(f)=fauxtête(f) est défini ssi vide(f)=faux

Types abstraits de donn

´ees - p.35/90

Files : Implémentation par tableau

TypeFile= Enregistrement

début début : Naturel; nbÉléments :Naturel; tab : Tableau[1..MAX] d'Éléments fin fonctioncréer() :File

Déclarationf : File

début f.debut←0 nbÉléments←0 fin

Types abstraits de donn

´ees - p.36/90

Plein, Enfiler

fonctionplein(f : File) :Booléen

Déclaration-

début retourner nbÉléments=MAX fin procédureenfiler(x : Élément, f : File)

Déclarationfin : Naturel

début siplein(f)alors erreur("File pleine") finsi fin←(f.début+nbÉléments) mod MAX f.tab[fin]←x nbÉléments←nbÉléments+1 fin

Types abstraits de donn

´ees - p.37/90

Vide, défiler

fonctionvide(f : File) :Booléen

Déclaration-

début retournernbÉléments=0 fin procéduredéfiler(f : File)

Déclaration-

début sivide(d)alors erreur("File Vide") finsi f.debut← (f.debut+1) mod MAX nbÉléments←nbÉléments-1 fin

Types abstraits de donn

´ees - p.38/90

Exemple

-créer() début : 0 nbÉlt : 00 1 2 3 4-enfiler(10,20,30,40,50)début : 0 nbÉlt : 5 fin : 0

0 1 2 3 410

20 30
40
50
-défiler()début : 1 nbÉlt : 4 fin : 0

0 1 2 3 4

20 30
40
50
-enfiler(60)début : 1 fin : 1

0 1 2 3 460

20 30
40
50

Types abstraits de donn´ees - p.39/90

File Implémentation par liste

TypeFile= Enregistrement

début début :PointeurCellule; fin : PointeurCellule; fin fonctioncréer() :File

Déclarationf : File

début f.début←NIL f.fin←NIL fin

Types abstraits de donn

´ees - p.40/90

Enfiler

procédureenfiler(x : Élément, f : File)

Déclarationcell : PointeurCellule

début allouer(cell,Cellule) cell ?.contenu←x cell ?.suivant←NIL sivide(f)alors f.debut←cell sinon f.fin.suivant←cell finsi f.fin←cell fin

Types abstraits de donn

´ees - p.41/90

Vide, défiler

procéduredéfiler(f : File)

Déclarationcell : PointeurCellule

début sivide(f)alors erreur("File Vide") finsi sif.debut=f.finalors libérer(f.debut) f.debut←NIL f.fin←NILquotesdbs_dbs22.pdfusesText_28
[PDF] Les tableaux 1 Exercice 1 - Lipn

[PDF] Terminale S Exercices sur les suites Exercice 1 On consid`ere la

[PDF] Cours d algorithmique BTS SIO première année - Bienvenue sur le

[PDF] Algorithmique et programmation, un levier pour développer des

[PDF] Algorithmique et Structures de Données

[PDF] ORME 212 : Algorithmique en seconde avec Python

[PDF] Ali baba et les quarante voleurs - Gomme Gribouillages

[PDF] Commentaire de l 'article 26 du code de droit international privé

[PDF] 1 Biliographie générale : Droit international privé - Droit du

[PDF] Les différences de retraite entre salariés du privé et fonctionnaires

[PDF] 2 Le rôle des aliments - Académie de Nancy-Metz

[PDF] Usines complètes de production d aliments pour - Amandus Kahl

[PDF] La nutrition active pour prévenir et traiter l 'anémie par déficience en fer

[PDF] Ces aliments qui favorisent le bon cholestérol - Mutualp

[PDF] le ba ba de la vitamine c - RTS