[PDF] Algorithmique Structures de données





Previous PDF Next PDF



Algorithmique Structures de données

1 de 87. Algorithmique. Structures de données. Florent Hivert. Mél : Florent. La plupart des bons algorithmes fonctionnent grâce à une méthode.



COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

12 mar. 2013 1. MAP@UNICE.FR. COURS ALGORITHMIQUE. ET PROGRAMMATION. INFORMATIQUE. DUT INFORMATIQUE ... Un algorithme prend des données en entrée.



Algorithmes et langage C

1- Le processeur extrait les données à traiter à partir de la source Le terme algorithme est employé en informatique pour décrire une méthode de ...



Informatique et Algorithmique avec le langage Python

I - Algorithmes instructions et langages informatiques des ordinateurs travaillent sur des données binaires 0/1



Cours dAlgorithmique - Florent Hivert

Retenir. Un programme est une suite d'instructions permettant à une système informatique d'exécuter une tâche donnée écrit dans un langage de programmation 



CONCOURS DINFORMATICIEN SUJETS DONNÉS AU

25 août 1992 1. Qui est actuellement le président du Sénat ? A. Gérard Larcher ... Concevez un algorithme et les structures de données nécessaires ...



Première partie : Algorithmique avancée pour les graphes

la première partie les algorithmes pourront être introduits avec un niveau de détail moins fin





livre-algorithmes EXo7.pdf

Une fonction en informatique est similaire à une fonction mathématique En déduire un algorithme qui pour une configuration donnée de la rampe



Algorithmique & programmation en langage C - vol.1 - Archive

1 fév. 2019 informatique sont exprimés en utilisant des langages formels5. ... est structurée et comment on peut y stocker des données

1 de 87

Algorithmique

Structures de données

Florent Hivert

Mél :Florent.Hivert@lri.fr

Page personnelle :http://www.lri.fr/˜hivert

2 de 87

Types de données

Retenir

Avoir choisi les bons types de données permet d"avoir un programmeplus lisible car auto documenté plus facile à maintenir souvent plus rapide, en tout cas plus facile à optimiser " I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. " - Linus Torvalds (creator of Linux)

3 de 87

Algorithmes et structures de données

La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Nous allons étudier quatre

grandes classes de structures de données :Les structures de données séquentielles (tableaux);

Les structures de données linéaires (liste chaînées);

Les arbres;

Les graphes.

Structures séquentielles : les tableaux

4 de 87Structures

séquentielles : les tableaux

Structures séquentielles : les tableaux

5 de 87Structure de donnée séquentielle (tableau)

En anglais : array, vector.Définition

Untableauest une structure de donnéeTqui permet de stocker un certain nombre d"élémentsT[i]repérés par un indexi. Les

tableaux vérifient généralement les propriétés suivantes :tous les éléments ont le même type de base;

le nombre d"éléments stockés est fixé; l"accès et la modification de l"élément numéroiest en temps constant(1), indépendant deiet du nombre d"éléments, le tableau.

Structures séquentielles : les tableaux

6 de 87Un tableau en mémoire

Définition

Dans le tableau, tous les éléments ont la même taille mémoire. Nombre d"élément :n, taille d"un élémentt:T[0]T[1]T[2]...T[n-1]

On suppose que le tableau commence à l"adressedT[0]occupe les casesdàd+t1;T[1]occupe les casesd+tàd+2t1;T[i]occupe les casesd+itàd+ (i+1)t1;Le tableau entier occupe les casesdàd+nt1.

Note : indirection (pointeur) possible si taille variable (par exemple classe virtuelle).

Structures séquentielles : les tableaux

6 de 87Un tableau en mémoire

Définition

Dans le tableau, tous les éléments ont la même taille mémoire. Nombre d"élément :n, taille d"un élémentt:T[0]T[1]T[2]...T[n-1]

On suppose que le tableau commence à l"adressedT[0]occupe les casesdàd+t1;T[1]occupe les casesd+tàd+2t1;T[i]occupe les casesd+itàd+ (i+1)t1;Le tableau entier occupe les casesdàd+nt1.Note : indirection (pointeur) possible si taille variable (par exemple

classe virtuelle).

Structures séquentielles : les tableaux

7 de 87Structure de donnée séquentielle (tableau)

On encapsule souvent le tableau dans une structure qui permet de

faire varier la taille :Java : tableauint[](taille fixe),ArrayList(taille variable)C : tableauint[](taille fixe), pointeur (taille variable)C++ :std::array(taille fixe),std::vector(taille variable)Python :list(taille variable,6=liste chaînée)

Structures séquentielles : les tableaux

8 de 87Exemple : Tableau en C (bas niveau)

On suppose déclaré un typeelempour les éléments.Espace mémoire nécessaire au stockage d"un élément exprimé

en mots mémoire (octets en général) :sizeof(elem).définitionstatique:elem t[taille];définitiondynamiqueen deux temps (déclaration, allocation) :

#include elem *t; t = (elem*) malloc(taille*sizeof(elem));L"adresse det[i]est notét + i. Calculée par

Addr(t[i]) = Addr(t[0]) +sizeof(elem)i

Structures séquentielles : les tableaux

8 de 87Exemple : Tableau en C (bas niveau)

On suppose déclaré un typeelempour les éléments.Espace mémoire nécessaire au stockage d"un élément exprimé

en mots mémoire (octets en général) :sizeof(elem).définitionstatique:elem t[taille];définitiondynamiqueen deux temps (déclaration, allocation) :

#include elem *t; t = (elem*) malloc(taille*sizeof(elem));L"adresse det[i]est notét + i. Calculée par

Addr(t[i]) = Addr(t[0]) +sizeof(elem)i

Structures séquentielles : les tableaux

8 de 87Exemple : Tableau en C (bas niveau)

On suppose déclaré un typeelempour les éléments.Espace mémoire nécessaire au stockage d"un élément exprimé

en mots mémoire (octets en général) :sizeof(elem).définitionstatique:elem t[taille];définitiondynamiqueen deux temps (déclaration, allocation) :

#include elem *t; t = (elem*) malloc(taille*sizeof(elem));L"adresse det[i]est notét + i. Calculée par

Addr(t[i]) = Addr(t[0]) +sizeof(elem)i

Structures séquentielles : les tableaux

9 de 87Tableau en Java

On suppose déclaré un typeelempour les éléments.définitiondynamiqueen deux temps (déclaration, allocation) :

elem[] t; t = new elem[taille];

Structures séquentielles : les tableaux

10 de 87Tableau partiellement remplis

Retenir

Pour simuler un tableau de taille variable, on peut

réserver une certaine quantité de mémoire appeléecapacite,et ranger les valeursau début du tableau .

Organisation des données (structure, classe) :

tableau de taillecapaciteallouééléments d"indiceipour 0i0 ...taille1 ...capacite1utilisélibre

Structures séquentielles : les tableaux

11 de 87Opérations de base

Hypothèses :tableau de taillecapaciteallouééléments 0i

accès au premier élément :(1)accès à l"élément numéroi:(1)accès au dernier élément :(1)insertion/suppression d"un élément au début :(taille)insert./suppr. d"un élt en positioni:(taillei)O(taille)insert./suppr. d"un élt à la fin :(1)À faire : écrire les méthodes correspondantes

Structures séquentielles : les tableaux

12 de 87Problème de la taille maximum

0 ...taille1 ...capacite1utilisélibre

On essaye d"insérer un élément dans un tableau oùtaille = capacite

Il n"y a plus de place disponible.

0 ...taille1= capacite1u t i l i s é

Comportements possibles :Erreur (arrêt du programme, exception) Ré-allocation du tableau avec recopie, coût :(taille)

Structures séquentielles : les tableaux

12 de 87Problème de la taille maximum

0 ...taille1 ...capacite1utilisélibre

On essaye d"insérer un élément dans un tableau oùtaille = capacite

Il n"y a plus de place disponible.

0 ...taille1= capacite1u t i l i s é

Comportements possibles :Erreur (arrêt du programme, exception) Ré-allocation du tableau avec recopie, coût :(taille)

Structures séquentielles : les tableaux

13 de 87Ré-allocation

En C :realloc

void *realloc(void *ptr, size_t size);modifie la taille du bloc de mémoire pointé par ptr pour l"amener à une taille desizeoctets.realloc()conserve le contenu de la zone mémoire minimum entre la nouvelle et l"ancienne taille. [...] Si la zone pointée était déplacée, unfree(ptr)est effectué.En Java, copy systématique :

E[] newData = (E[]) new Object[...];

System.arraycopy(data, 0, newData, 0, size);

data = newData;

Structures séquentielles : les tableaux

14 de 87Ré-allocation : coût

Problème

Quel est le coût des réallocations?

On se place dans le scénario suivant :Au début, le tableau ne contient rien;

On ajoute, 1 par 1,néléments à la fin.

méthodeappenden Python et Java,push_backen C++

On veut calculer la complexité de l"ajoutExemple : enregistrement d"un signal audio venant d"un micros

44000 échantillons par seconde.

Structures séquentielles : les tableaux

14 de 87Ré-allocation : coût

Problème

Quel est le coût des réallocations?

On se place dans le scénario suivant :Au début, le tableau ne contient rien;

On ajoute, 1 par 1,néléments à la fin.

méthodeappenden Python et Java,push_backen C++

On veut calculer la complexité de l"ajoutExemple : enregistrement d"un signal audio venant d"un micros

44000 échantillons par seconde.

Structures séquentielles : les tableaux

15 de 87Rappels suites arithmétiques et géométriques

Suite arithmétique :un+1=un+r,un=u0+nr.

u

0+u1++un= (n+1)u0+un2

= (n+1)2u0+nr2

0+r+2r+:::nr= (n+1)nr2

Suite géométrique :un+1=qun,un=u0qn.

u

0+u1++un=u01qn+11qsiq6=1

1+q+q2++qn=1qn+11q

Structures séquentielles : les tableaux

16 de 87Ré-allocation par ajout d"une case

On ajoute, 1 par 1,néléments à la fin.ÉtapeAllocationsCopiesStockage#écritures

11T[0]1

22T[0]T[1]2

33T[0:::1]T[2]3

..nnT[0:::n2]T[n1]n

Bilan :

nX i=1i=n(n+1)2

écritures.

Structures séquentielles : les tableaux

16 de 87Ré-allocation par ajout d"une case

On ajoute, 1 par 1,néléments à la fin.ÉtapeAllocationsCopiesStockage#écritures

11T[0]1

22T[0]T[1]2

33T[0:::1]T[2]3

..nnT[0:::n2]T[n1]n

Bilan :

nX i=1i=n(n+1)2

écritures.

Structures séquentielles : les tableaux

17 de 87Ré-allocation par ajout d"une taille fixeb

Nombre d"étapes :k=dnb

e. Hypothèse simplificatrice :nest un multiple de la taillebdes blocs :n=kb. À chaque étape, on écritbvaleurs.ÉtapeAlloc.CopiesStockage#écritures

1b0:::b1b

22b0:::b1b:::2b12b

33b0:::2b12b:::3b13b

..kkb0:::(k1)b1(k1)b:::kb1kb

Bilan :

kX i=1bi=bkX i=1i=bk(k+1)2n22bécritures.

Structures séquentielles : les tableaux

17 de 87Ré-allocation par ajout d"une taille fixeb

Nombre d"étapes :k=dnb

e. Hypothèse simplificatrice :nest un multiple de la taillebdes blocs :n=kb. À chaque étape, on écritbvaleurs.ÉtapeAlloc.CopiesStockage#écritures

1b0:::b1b

22b0:::b1b:::2b12b

33b0:::2b12b:::3b13b

..kkb0:::(k1)b1(k1)b:::kb1kb

Bilan :

kX i=1bi=bkX i=1i=bk(k+1)2n22bécritures.

Structures séquentielles : les tableaux

18 de 87Ré-allocation par ajout d"une taille fixe : Bilan

Retenir

On suppose que l"on réalloueune case supplémentaireà chaque débordement. Coût (nombre de copies d"éléments) : n X i=1i=n(n+1)2 2(n2)

Si on alloue des blocs de tailleb, en notantk=dnb

ele nombre de blocs :kX i=1bin22b2(n2) La vitesse est divisée parbmais lacomplexité reste la même.

Structures séquentielles : les tableaux

18 de 87Ré-allocation par ajout d"une taille fixe : Bilan

Retenir

On suppose que l"on réalloueune case supplémentaireà chaque débordement. Coût (nombre de copies d"éléments) : n X i=1i=n(n+1)2

2(n2)Si on alloue des blocs de tailleb, en notantk=dnb

ele nombre de blocs :kX i=1bin22b2(n2) La vitesse est divisée parbmais lacomplexité reste la même.

Structures séquentielles : les tableaux

19 de 87Ré-allocation par doublement de taille

Bilan : Il faut allouer de plus en plus d"éléments.Question Que ce passe-t-il si l"on double la taille à chaque fois?

Structures séquentielles : les tableaux

20 de 87Ré-allocation par doublement de taille

Nombre d"étapes :k=dlog2ne. Hypothèse simplificatrice :nest une puissance de 2 :n=2k.ÉtapeAlloc.CopiesStockage#écritures 0101
12012

240:::12:::34

380:::34:::78

4160:::78:::1516

..k2 k0:::2k112 k1:::2k12 kBilan : kX i=02quotesdbs_dbs18.pdfusesText_24
[PDF] Algorithme ; Fonction ; f(x) 2nde Mathématiques

[PDF] Algorithme ? faire Terminale Mathématiques

[PDF] Algorithme ? programmer Terminale Mathématiques

[PDF] algorithme ? réaliser 2nde Mathématiques

[PDF] Algorithme ? trouver 1ère Mathématiques

[PDF] Algorithme Abonnement DVD 2nde Mathématiques

[PDF] algorithme algobox exemple PDF Cours,Exercices ,Examens

[PDF] algorithme algobox seconde PDF Cours,Exercices ,Examens

[PDF] algorithme algobox suite PDF Cours,Exercices ,Examens

[PDF] Algorithme angle orienté 1ère Mathématiques

[PDF] algorithme avancé et complexité exercices corrigés PDF Cours,Exercices ,Examens

[PDF] algorithme avec algobox PDF Cours,Exercices ,Examens

[PDF] Algorithme avec des congruences Terminale Mathématiques

[PDF] Algorithme avec exemples 2nde Mathématiques

[PDF] Algorithme avec un triangle isocèle 2nde Mathématiques