Discussion :

[l1informatique]

Bonjour,

Quelqu'un peut m'aider pour comprendre cette question:

lisez la section OVERVIEW OF DATA STRUCTURES, table 1.1, à la p. 14 de DATA STRUCTURES AND
ALGORITHMS IN
24 HOURS77 (Robert Lafore) et caractérisez la performance des algorithmes
qui manipulent ces structures dans le pire des cas.


merci

[foetus]

Analyse de la complexité des algorithmes

[l1informatique]

BONJOUR,

Merci pour le lien, si j'ai bien compris comme c'est un tableau je dois utilisé

complexité quadratique (polynomiale). mais ce qui me bloque c'est comment utiliser ça ??

voici le tableau :

Employee number: Social security number: Last name: First name: Street address: City: State: Zip code: Phone number: Date of birth: Date of first employment: Salary:

merci

[foetus]

mais ce qui me bloque c'est comment utiliser ça ??

Simple

Si c'est une complexité N², donc cela veut dire que ton algo est tout lent et qu'il faut réfléchir à l'améliorer (en O(N), en O(log N) et petit frère, ou en O(1) (mais il ne faut pas trop espérer))

[l1informatique]

Simple

Si c'est une complexité N², donc cela veut dire que ton algo est tout lent et qu'il faut réfléchir à l'améliorer (en O(N), en O(log N) et petit frère, ou en O(1) (mais il ne faut pas trop espérer))

J'essaye de comprendre :s, je sais que c'est lent :s.

pour ce tableau qui contient des 12 lignes d'information de n emplyeurs.

pour caractérisez la performance des algorithmes qui manipulent ces structures dans le pire des cas.

comme c'est un tableau de une liste d'employeur on calculera avec O(n)

Le tableau est constitué d’un nombre fini de lignes. Appelons-les 1(1) `a l(k) .
Soit n1 ... nk le nombre de fois qu’elles sont effectu ́ees. La complexit ́e de l’algo
est n(j) l’une des lignes qui est effectuée le plus souvent. Si toutes les lignes s’effectuent en
temps O(1), la complexit ́e de l’algorithme est majorée par knj O(1) soit O(nj ).

C'est ça la réponses ?

merci

[picodev]

Bonjour,

Quelqu'un peut m'aider pour comprendre cette question:

lisez la section OVERVIEW OF DATA STRUCTURES, table 1.1, à la p. 14 de DATA STRUCTURES AND
ALGORITHMS IN
24 HOURS77 (Robert Lafore) et caractérisez la performance des algorithmes
qui manipulent ces structures dans le pire des cas.


merci

BONJOUR,

Merci pour le lien, si j'ai bien compris comme c'est un tableau je dois utilisé

complexité quadratique (polynomiale). mais ce qui me bloque c'est comment utiliser ça ??

voici le tableau :

Employee number: Social security number: Last name: First name: Street address: City: State: Zip code: Phone number: Date of birth: Date of first employment: Salary:

merci

Bonjour,
je ne comprends rien car la référence que tu donnes est ce tableau que tu aurais dû fournir →


Explique toi un peu mieux car je ne vois pas du tout à quoi ton deuxième message fait référence !

Sinon le tableau du livre liste des sdd avec des remarques sur l'accès, l'insertion, la suppression et la recherche.
J;imagine que les réponses attendues sont par exemple :

	accès	insertion	suppression	recherche
tableau	O(1)	O(n)	O(n)	O(n)
tableau trié	...	...	...	...

[sambia39]

Bonjour

BONJOUR,

Merci pour le lien, si j'ai bien compris comme c'est un tableau je dois utilisé

complexité quadratique (polynomiale). mais ce qui me bloque c'est comment utiliser ça ??

voici le tableau :

Employee number: Social security number: Last name: First name: Street address: City: State: Zip code: Phone number: Date of birth: Date of first employment: Salary:

merci

Il y a un truc que je ne comprends pas ou j’ai dû peut-être zapper. Par quelle conclusion arrivez-vous à une complexité quadratique, je ne vois pas en quoi un simple tableau peut avoir cette complexité.

De plus, vous nous citez les noms de tableaux, mais en réalité cela correspond à des membres d’une structure. Au final, votre évaluation de complexité se base sur quoi en réalité ?
S’agit-il d’une évaluation de complexité en temps ou en nombre d’opérations ?

Personnellement, je dirais en nombre d’opérations car il s’agit de structure de donnée.

La liste des tableaux donnée par @picodev est déjà un bon point de départ, mais s’il faut aller plus loin dans ce que vous appeler « l’évaluation des structures dans le pire des cas » alors, il faut procéder autrement en utilisant par exemple une analyse dite amortie qui vous permettra d’évaluer la complexité temporelle de l’ensemble des opérations ou une opération sur votre structure de données, ce qui vous permettra de connaitre le cas le plus défavorable (pire des cas) et de savoir si elle impacte ou pas de façon globale l’ensemble des opérations sur la structure.

à bientôt.

[l1informatique]

Bonjour,

Je vous remercie pour les réponses, j'ai téléchargé un autres pdf que je croyais le bon :s.

avec ce tableau , qui ce que je dois faire au début pour commencer de caractériser la performance des algorithmes qui manipulent ces structures dans le pire des cas.

Je n'ai pas de notion dans sa. J'ai lu le cours sur la notion de complexité mais je ne vois pas comment répondre.

Merci

[picodev]

Bonjour,

Je vous remercie pour les réponses, j'ai téléchargé un autres pdf que je croyais le bon :s.

avec ce tableau , qui ce que je dois faire au début pour commencer de caractériser la performance des algorithmes qui manipulent ces structures dans le pire des cas.

Je n'ai pas de notion dans sa. J'ai lu le cours sur la notion de complexité mais je ne vois pas comment répondre.

Merci

D'abord il faut trouver les algorithmes. Ici ce ne sont que des algos hyper classiques (en gros ceux que tout informaticien devrait connaître sur le bout des doigts). Ensuite il faut les comprendre et en calculer la complexité. Comme c'est hyper classique tu trouves une méga tonne d'info sur le net.
Par exemple l'insertion d'un élément dans un tableau → pour insérer un élément dans un tableau tu dois d'abord créer une place vide en décalant les éléments de la position d'insertion à la fin du tableau, ensuite tu insères la valeur. La complexité est mesurée en «opération élémentaires». L'algo pourrait être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
procédure insérer( tableau, position, valeur)
début
  pour i de position à tableau.longueur faire
    tableau[i+1]=tableau[i]
  tableau[position]=valeur
fin.

Il y a tableau.longueur-position opérations de décalages et une opération d'affectation. Donc pour un tableau donné de longueur n insérer un élément en position p «coûte» (n-p)*2+1. Ici je compte 2 pour l'opération de décalage pour un accès en lecture plus un accès en écriture, mais on pourrait compter 3,4 ou 42 ça ne changera pas beaucoup.
Dans le pire des cas on insère en tête (p=0), et il faudra 2*n+1 opérations, c'est donc un algo en O(n).
Dans le meilleur des cas on insère en fin (p=n), et il faudra 1 opération.
En moyenne, si on suppose que p peut prendre équiprobablement n'importe quelle valeur entre 1 et n on trouve 2*(n/2)+1=n+1.

Cet algorithme a donc une complexité en moyenne et au pire des cas en O(n), sachant qu'une insertion en fin est en O(1).

Tu as beaucoup de lecture en perspective

[l1informatique]

D'abord il faut trouver les algorithmes. Ici ce ne sont que des algos hyper classiques (en gros ceux que tout informaticien devrait connaître sur le bout des doigts). Ensuite il faut les comprendre et en calculer la complexité. Comme c'est hyper classique tu trouves une méga tonne d'info sur le net.
Par exemple l'insertion d'un élément dans un tableau → pour insérer un élément dans un tableau tu dois d'abord créer une place vide en décalant les éléments de la position d'insertion à la fin du tableau, ensuite tu insères la valeur. La complexité est mesurée en «opération élémentaires». L'algo pourrait être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
procédure insérer( tableau, position, valeur)
début
  pour i de position à tableau.longueur faire
    tableau[i+1]=tableau[i]
  tableau[position]=valeur
fin.

Il y a tableau.longueur-position opérations de décalages et une opération d'affectation. Donc pour un tableau donné de longueur n insérer un élément en position p «coûte» (n-p)*2+1. Ici je compte 2 pour l'opération de décalage pour un accès en lecture plus un accès en écriture, mais on pourrait compter 3,4 ou 42 ça ne changera pas beaucoup.
Dans le pire des cas on insère en tête (p=0), et il faudra 2*n+1 opérations, c'est donc un algo en O(n).
Dans le meilleur des cas on insère en fin (p=n), et il faudra 1 opération.
En moyenne, si on suppose que p peut prendre équiprobablement n'importe quelle valeur entre 1 et n on trouve 2*(n/2)+1=n+1.

Cet algorithme a donc une complexité en moyenne et au pire des cas en O(n), sachant qu'une insertion en fin est en O(1).

Tu as beaucoup de lecture en perspective

Woow, donc sa c'est une études pour la première collonne du tableau 1.1 (tableu), je dois faire meme choses pour tous le reste :s.

Je croyais pas que c'était aussi compliquer

[sambia39]

Bonsoir,
Je vais essayer d’éclaircir un peu ce qui a été dit. Tout d'abord, il faut comprendre que la notion de complexité est une notion qui permet d’évaluer ce que l’on appelle le coût d’exécution d’un algorithme et ces coûts peuvent être temporels (complexité temporelle qui est une fonction de « n » qui mesure le temps de calcul pour une donnée de taille « n ») ou spatial( complexité en mémoire ou taille mémoire qui est une fonction de « n » qui mesure la place mémoire utilisée pour le calcul sur une donnée de taille « n »)
Pour mesurer un coût, il faut prendre en compte:

• La taille des données.
• Le comportement asymptotique de l’algorithme, c'est-à-dire son comportement à l’infini donc de « n »
• Le cas le plus défavorable dit «le pire des cas » (est lorsque l’on donne une borne supérieure sur le temps de calcul pour toutes les données de taille « n »), en clair, on cherche le cas où l’algorithme se déroule pendant un temps assez long (qui tend vers l’infini) et l’on dit moyenne , le temps de calculs pour toutes les données de taille « n »

Exemple:
Soit l'algorithme suivant (tiré du cours de complexité d'algorithme de Mr Laurent Moreau enseignant au CNAM): nous allons calculé la complexité de celle-ci a titre pédagogique et nous nous limiterons au comportement asymptotique.
La formule a été édité sur se site. Car il n'y pas d'éditeur de formule sur le forum

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
I <- 1
#1
Tant que I <= N faire: #2
   Y <- Y + TAB[X] #3
   I <- I + 1 #4 
Fin tant que

Pour calculer le temps d'exécution "t(n)" on supposera en utilisant les constante ci-dessous comme des constantes indépendantes de "n":

• On note "T1" le temps d'exécution entre le début et #1
• On note "T2" le temps d'exécution de l'étape #2
• On note "T3" le temps d'exécution de l'étape #3
• On note "T4" le temps d'exécution de l'étape #4

On aura donc :
On définit iT le temps d'exécution d'une itération ce qui donne:
On obtient alors: ( le temps dépend linéairement de la taille "n" (fonction affine de n) )
Le comportement asymptotique donne : Conclusion l'algorithme est asymptotiquement linéaire en "n"
L'exemple ci-dessus montre comment en effectue la complexité d'un algorithme mais cela n'est pas finis il faut le cas le plus défavorable qu'il faut traité.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
procédure insérer( tableau, position, valeur)
début
  pour i de position à tableau.longueur faire
    tableau[i+1]=tableau[i]
  tableau[position]=valeur
fin.

......
Cet algorithme a donc une complexité en moyenne et au pire des cas en O(n), sachant qu'une insertion en fin est en O(1).

Corrigez-moi si je me trompe mais cette règle s'applique aux tableaux dynamiques pour lesquels on agrandit la taille pour ajouter des éléments et donc le coût d'ajout de l'élément dans le tableau en moyen est "O(1)" et le pire en "O(n)". Mais en revanche, si on prend mot pour mot votre exemple, le cas défavorable de votre exemple se présente quand la boucle atteint l'itération proche de la condition d'arrêt"tableau.longueur" (qui est la taille finie du tableau si on parle de tableaux statiques) ou pire quand en fourni une indice hors tableaux en clair, on déborde le tableau (si on parle d'implémentation d'algorithme et exécution du code on a un dépassement de tampon ou mieux le code à comportement d'une attaque buffer overflow bref ).
Serait-il plus simple de préciser, qu'il s'agit d'un tableau dynamique ?
à bientôt

[foetus]

Serait-il plus simple de préciser, qu'il s'agit d'un tableau dynamique ?

En réalité en C, il n'y a pas de tableau dynamique ou
Tu crées un tableau A (avec malloc), ensuite tu fais un realloc, mais cela peut être le tableau A comme un nouveau tableau B.

Non, si tu veux être tatillon la complexité c'est le maximum entre O(n) (pour faire l'insertion) et la complexité de realloc.

[sambia39]

En réalité en C, il n'y a pas de tableau dynamique ou
Tu crées un tableau A (avec malloc), ensuite tu fais un realloc, mais cela peut être le tableau A comme un nouveau tableau B.

Non, si tu veux être tatillon la complexité c'est le maximum entre O(n) (pour faire l'insertion) et la complexité de realloc.

Un tableau est une variable qui peut contenir plusieurs données du même type exemple tableaux d'entier qui contient uniquement des entiers, tableaux de caractère que des caractères.

On comprend également que le tableau à une taille dite "dimension" ainsi on peut trouver des tableaux à deux dimensions, trois, etc.
Il existe alors:
Des tableaux dis statiques car, la taille est connue d'avance et des tableaux, dis dynamiques par le biais des variables pointeurs dont la taille est connue qu'à l'exécution..

La particularité d'un tableau statique est qu'il correspond à une allocation statique de mémoire cela signifie que l'espace mémoire est réservé en début du programme une fois pour toutes et de ce fait le tableau possède une taille fixe.
Quant au tableau dynamique l'espace mémoire est réservé et connu qu'à l'exécution ainsi donc, elle est dite dynamique et cette particularité ne peut se faire grâce au variable pointeur qui pointe sur une zone mémoire allouée par le système et mieux en peut solliciter une redimension de cette mémoire

En langage C quand on crée un tableau avec la fonction d'allocation "malloc" en alloue un bloc de taille n (et non un bloc d'un type donné) que le système d'exploitation renvoie à une variable pointeur, l'adresse du bloc alloué en cas d'erreur ou plus de mémoire la fonction renvoie NULL.

Pour redimensionner ou augmenter un tableau. On utilise la fonction "realloc()" qui a la charge de redimensionner un bloc mémoire alloué dynamiquement avec un pointeur et elle renvoie a ce pointeur l'adresse du nouveau bloc ré-alloué tout en gardant le contenu du précédent tableau. (Elle retourne NULL s'il y a échec).

Tu crées un tableau A (avec malloc), ensuite tu fais un realloc, mais cela peut être le tableau A comme un nouveau tableau B.
Non, si tu veux être tatillon la complexité c'est le maximum entre O(n) (pour faire l'insertion) et la complexité de realloc.

Votre réponse correspond à une allocation dynamique et ma question parle de la conclusion de @picodev par rapport au notation qui traite le cas de la complexité de son exemple. En clair, son exemple est-il basé sur un tableau static ou dynamique ?
car, "i+1" en indice avec comme condition d'arrêt de la boucle "tableau longueur" qui est la taille du tableau, je ne peux que conclure qu'il s'agit d'un tableau static dont la taille est connue à l'avance
bref, pour l'instant il se fait tard. En attendant une réponse je vous souhaite une bonne nuit.
à bientôt

[foetus]

En clair, son exemple est-il basé sur un tableau static ou dynamique ?

Impossible de le savoir . On peut très bien faire XXX list[5000]; (5000 ou un nombre assez large pour nos besoins si on peut borner)


Pour le reste tu as raison

[l1informatique]

Bonjour,

Je suis plus perdu qu'avant, pour ma question au tout début, je ne me retrouve toujours pas.

si c'est possible de me donner une idée pour un premier exemple de tableau pour commencer.

Merci

[picodev]

[...]
Votre réponse correspond à une allocation dynamique et ma question parle de la conclusion de @picodev par rapport au notation qui traite le cas de la complexité de son exemple. En clair, son exemple est-il basé sur un tableau static ou dynamique ?
car, "i+1" en indice avec comme condition d'arrêt de la boucle "tableau longueur" qui est la taille du tableau, je ne peux que conclure qu'il s'agit d'un tableau static dont la taille est connue à l'avance
bref, pour l'instant il se fait tard. En attendant une réponse je vous souhaite une bonne nuit.
à bientôt

Comme je donnais un aperçu sur le tableau 1.1 de la référence donné par le PO il s'agit évidemment d'un tableau statique (à taille fixe donc). Je ne traite pas le cas «tableau plein» car ce n'est pas important ici, on essaye de déterminer la complexité d'une fonction si elle n'échoue pas. Mais c'est vrai qu'on peut être plus exhaustif.

Dans le cas d'un tableau à croissance dynamique on introduit la notion de complexité amortie. Si la croissance est exponentielle d'un facteut 𝛼>1 alors la complexité en temps amortie de l'insertion reste en O(n) malgré les réallocations qui pourraient laisser faire croire le contraire.

[Bktero]

Des tableaux dis statiques car, la taille est connue d'avance et des tableaux, dis dynamiques par le biais des variables pointeurs dont la taille est connue qu'à l'exécution..

La particularité d'un tableau statique est qu'il correspond à une allocation statique de mémoire cela signifie que l'espace mémoire est réservé en début du programme une fois pour toutes et de ce fait le tableau possède une taille fixe.
Quant au tableau dynamique l'espace mémoire est réservé et connu qu'à l'exécution ainsi donc, elle est dite dynamique et cette particularité ne peut se faire grâce au variable pointeur qui pointe sur une zone mémoire allouée par le système et mieux en peut solliciter une redimension de cette mémoire

En langage C quand on crée un tableau avec la fonction d'allocation "malloc" en alloue un bloc de taille n (et non un bloc d'un type donné) que le système d'exploitation renvoie à une variable pointeur, l'adresse du bloc alloué en cas d'erreur ou plus de mémoire la fonction renvoie NULL.

Pour redimensionner ou augmenter un tableau. On utilise la fonction "realloc()" qui a la charge de redimensionner un bloc mémoire alloué dynamiquement avec un pointeur et elle renvoie a ce pointeur l'adresse du nouveau bloc ré-alloué tout en gardant le contenu du précédent tableau. (Elle retourne NULL s'il y a échec).

Je crois qu'il y a quelques imprécisions dans tout cela.

En C, malloc() ne sert pas à créer des tableaux ; il alloue une bloc de mémoire et renvoie un pointeur sur le début de la zone.

La norme (n1256) donne la définition suivante au point 20 de la section 6.2.5 Types:

An array type describes a contiguously allocated non empty set of objects with a particular member object type, called the element type.
Array types are characterized by their element type and by the number of elements in the array.
An array type is said to be derived from its element type, and if its element type is T,the array type is sometimes called
‘‘array of T’’. The construction of an array type from an element type is called ‘ ‘array type derivation’’.

Un tableau est donc bien typé.

Un tableau n'est pas alloué une bonne fois pour toute à la compilation, sauf s'il est global ou statique. Sinon, il a une allocation automatique est donc normalement alloué sur la pile comme les autres variables automatiques.

C'est un abus de langage de parler de tableaux statiques et dynamiques, surtout quand le C99 introduit les VLA.

J'ai consigné des notes sur le sujet ici : https://gradot.wordpress.com/2012/08...ointeurs-en-c/

[sambia39]

Bonsoir,

Bonne remarque, mais il y a une ambiguïté à ce que vous avez posté. Sauf erreur de ma part, je n'ai peut-être pas été clair, mais j'ai écrit:

En langage C quand on crée un tableau avec la fonction d'allocation "malloc" en alloue un bloc de taille n (et non un bloc d'un type donné) que le système d'exploitation renvoie à une variable pointeur, l'adresse du bloc alloué en cas d'erreur ou plus de mémoire la fonction renvoie NULL.

Donc, j'entends par là que quand on utilise la fonction "malloc" pour créer un tableau, celui-ci (malloc) procède à une réservation dynamique de la mémoire, plus exactement une zone mémoire de "n" octets au moment de l'exécution du programme. De ce fait, pour allouer un vecteur de mémoire (tableau) de "n" octects de type entier, on utilisera une variable pointeur sur un type donné (entier) à laquelle on alloue une zone mémoire qui correspond "n" type [/I](entier).[I]
Au final, je n'est pas dit que "malloc" servait juste à créer un tableau (sous entendus), mais qu'il sert à allouer une zone mémoire et grâce aux variables pointeur, on obtient un tableau dynamique de donnée qui est en réalité un bloc mémoire de taille "n".
Un tableau n'est rien d'autre qu'une suite de blocs de même taille. Donc, si vous créez un tableau dynamique grâce (en utilisant) à la fonction "malloc" de taille "n", vous ne faites qu'allouer "n" blocs de taille "type". (n * taille type).

Je crois qu'il y a quelques imprécisions dans tout cela.
En C, malloc() ne sert pas à créer des tableaux ; il alloue une bloc de mémoire et renvoie un pointeur sur le début de la zone.
La norme (n1256) donne la définition suivante au point 20 de la section 6.2.5 Types:
Un tableau est donc bien typé..

J'admet que la norme aide mais il ne faut pas la prendre non plus pour "argent comptant".
Le langage C, est un langage fortement typé. Il est tout à fait logique que les tableaux soient typés, d'ailleurs un tableau de type entier ne peut que contenir des élements de type entier. Pareil pour les caractères et c'est ce que j'ai mentionné dans mon précédent poste, en disant:

Un tableau est une variable qui peut contenir plusieurs données du même type exemple tableaux d'entier qui contient uniquement des entiers, tableaux de caractère que des caractères.

Un tableau n'est pas alloué une bonne fois pour toute à la compilation, sauf s'il est global ou statique. Sinon, il a une allocation automatique est donc normalement alloué sur la pile comme les autres variables automatiques.

J'ai écris:

Des tableaux sont dit statiques car la taille est connue d'avance et des tableaux sont dit dynamiques par le biais des variables pointeurs dont la taille est connue qu'à l'exécution.
La particularité d'un tableau statique est qu'il correspond à une allocation statique de mémoire, cela signifie que l'espace mémoire est réservé en début du programme une fois pour toute et de ce fait, le tableau possède une taille fixe.
.

Donc, pour le cas d'un tableau statique, exemple " int iTab[10]". iTab est un tableau de 10 éléments de type entier. 10 est une valeur constante (obligatoire). La taille du tableau "iTab" est donc défnitive (une fois pour toute) et ne peut pas être modifiée en cours d'exécution d'où j'ai écris :

La particularité d'un tableau statique est qu'il correspond à une allocation statique de mémoire cela signifie que l'espace mémoire est réservé en début du programme une fois pour toutes et de ce fait le tableau possède une taille fixe.

C99 introduit les VLA oui mais, il s'agit de tableaux à taille variable et si je devrais le classer, (personnellement) je le mettrais dans la catégorie
des tableaux dite dynamique car sa taille est déterminée au moment de l'exécution.

Pour finir, sans parler de la norme C99 avec l'introduction de la VLA, je dirais qu'il n'y a pas d'abus de langage mais qu'il y a bien deux types de tableaux:
statique et dynamique et pour les raisons que j'ai énnoncé plus haut.
à bientôt

[picodev]

[...]
J'admet que la norme aide mais il ne faut pas la prendre non plus pour "argent comptant".
[...]

Bah si, la norme est parole d'évangile bien au contraire. Un compilateur+bibliothèque standard conforme se doit de la respecter et de documenter les comportements laissés à l'implémentation. C'est fait pour ça la norme.