Complexité algorithmique

par **Rockleader** » 02 Juin 2014, 14:35

Bonjour,

je suis en train de préparer mon rattrapage de complexité, et j'ai un peu de mal à me remettre dans le bain. Je voudrais refaire l'exam de la première session que j'avais à priori raté.

Voici donc le premier exo de cet exam:

Soit l'algo suivant:

Code: Tout sélectionner: Pour i=1...n faire Pretraitement(i) Pour j=1....n faire Traitement(i,j) fin pour fin pour

Cet algorithme repose sur deux procédures. On souhaite étudier sa complexité globale lorsque la complexité de ces deux procédures varient afin de choisir la meilleure combinaison des deux.
On note P(i) la complexité de Prétraitement et T(i,j) la complexité de Traitement.

Plusieurs options:

a-P(i)=i*n et T(i,j)=j

b-P(i)=1 et T(i,j)=i*j

c-P(i)=i et T(i,j)=i+j

d-P(i)=n et T(i,j)= log2(j) (ce qui revient à dire ln(j) sauf erreur de ma part).

Dans chacun des cas ci dessous je dois déterminer la complexité de l'algorithme et donner son ordre de grandeur.

Bien, alors je ne sais plus ce que j'avais fait le jour de l'exam, mais aujourd'hui afin de résoudre le problème je pense que je commencerais par exprimer la complexité en fonction de P et T.

Soit:

Code: Tout sélectionner: Pour j=1....n faire // n Traitement(i,j) // T(i,j) fin pour

On a donc pour cette boucle une complexité C de n*T(i,j)

Code: Tout sélectionner: Pour i=1...n faire // n Pretraitement(i) //P(i) [...] // C fin pour

Cette programme a donc une complexité générale de C' de n*[P(i)+n*(T(i,j))]

Et donc par la suite pour exprimer la complexité de chacun des cas il suffit de remplacer par les valeurs de P et T données.

Est ce la bonne méthode ? Par ailleurs je ne vois pas ce qui est attendu par ordre de grandeur; pour moi en donnant la complexité on donne l'ordre de grandeur également....

A partir de cela, il faut déterminer quelle est la meilleure solution en terme de complexité.

Il suffit de regarder lequel est le plus petit entre les polynôme fonction de n obtenu Ca Cb Cc Cd

En rappel on me note que somme des i=1 à n de i vaut n(n+1)/2; mais je ne vois pas vraiment ou l'on en a besoin; donc je pense que j'ai un truc qui cloche dans mon raisonnement.

Voilà pour le premier exo, je passerais à la suite lorsque celui ci sera bouclé^^

par **fatal_error** » 02 Juin 2014, 15:27

Hello,

dans ce cas là

Code: Tout sélectionner: Pour i=1...n faire Pretraitement(i) Pour j=1....n faire Traitement(i,j) fin pour fin pour

Tu as cout S qui vaut

Code: Tout sélectionner: S = 0 pour i=1 à n S+=P(i) pour j=1 à n S+=T(i,j) finpour finpour

Ton but, c'est de choisir les P(i) et T(i,j) tels que S soit minimal.

Ex:
a: P(i)=i*n et T(i,j)=j
S = 0
somme des P(i) pour i = 1 à n = n(n(n+1)/2)
somme des T(i,j) pour j=1 à n: (n(n+1)/2) et pour i=1 à n:
n(n(n+1)/2)
Au final :
S=n^2(n+1)

Tu calcules pareil pour les autres et tu compares

par **Rockleader** » 02 Juin 2014, 15:49

Sa revient au même que ce que je disais non ?

S+=P(i) si je me trompe pas sur la notation ça veut dire S=S+P(i) or on boucle n fois.

Donc au final on a bien S=n*P(i) je ne vois pas pourquoi on fait intervenir n fois (n(n+1)/2)

Pour moi, dans le cas a on a:

S= n*[P(i)+n*(T(i,j))] = n*(in+nj) = (i+j)n²

par **Doraki** » 02 Juin 2014, 17:40

A ton avis que veulent dire i et j dans ta réponse "S = (i+j)n²" ?

par **Rockleader** » 02 Juin 2014, 17:47

J'ai pas de réponses précises à donner.

Ce sont des nombres.

par **Doraki** » 02 Juin 2014, 17:53

Des nombres qui représentent quoi ? Qui sortent d'où ?
n on le connait c'est le paramètre du programme (les bornes des bouclent dépendent de ce paramètre), et d'ailleurs on cherche la complexité du programme en fonction de n.

Mais i et j !?

Elle vaut quoi la complexité du programme avec n=3 dans le cas a ?
Dans ta réponse on doit en faire quoi du i et du j ?

par **Rockleader** » 02 Juin 2014, 18:02

i et j n'ont de sens qu'en fonction de n, donc de donner un résultat avec i et j n'a pas de sens si on ne connait pas le tour d'itération auquel correspond i et j entre 1 et n.
Je comprends ça et je comprends donc que mon expression n'est pas correcte.

Mais ça ne me dit pas comment trouver le bon résultat car "mathématiquement" le résultat que j'ai trouvé ne me semble pas faux.

par **Doraki** » 02 Juin 2014, 18:08

Ben en fait dès le début tu écris un truc qui n'a aucun sens

Rockleader a écrit:Soit:

Code: Tout sélectionner
Pour j=1....n faire // n Traitement(i,j) // T(i,j) fin pour

On a donc pour cette boucle une complexité C de n*T(i,j)

A cet endroit du programme, n et i sont des paramètres, mais j n'existe pas. Il n'existe qu'à l'intérieur parcequ'il sert à indicer les étapes dans la boucle.

Donc la complexité correspondante dépend de n et de i (et de T), mais pas de j.

Par exemple pour i=1 et n=3, la boucle est

"Pour j=1...3 faire Traitement(1,j) (complexité T(1,j)) fin pour"

Quelle est la complexité totale de la boucle (en fonction de T) ?

par **Rockleader** » 02 Juin 2014, 18:23

A cet endroit du programme, n et i sont des paramètres, mais j n'existe pas. Il n'existe qu'à l'intérieur parcequ'il sert à indicer les étapes dans la boucle.

Ok j'ai compris pourquoi mon raisonnement est faux.

Il va donc falloir exprimer j sous la forme n(n+1)/2

T(i,j) vallant j

la boucle vaut la somme des j de 1 à n donc la complexité de cette boucle est n(n+1)/2

La complexité totale est donc S = n [P(i)+(n(n+1)/2) ] en fonction de P(i) et n ?

par **Doraki** » 03 Juin 2014, 08:23

Rockleader a écrit:La complexité totale est donc S = n [P(i)+(n(n+1)/2) ] en fonction de P(i) et n ?

Pourquoi tu recommences la même bêtise ?

par **Rockleader** » 03 Juin 2014, 10:43

Est ce que l'on est d'accord pour cette étape ? Si ce n'est pas le cas, je vais vous demander de me détailler votre correction car je ne vois pas vraiment ce que c'est...j'ai rajouté le C pour bien insister sur le fait qu'il s''agit du coup.

Sauf que sur cette étape j'écris un morceau fonction de i alors que i n'existe pas à l'intérieur...

J'apprécierais vraiment une correction détaillé sur un sur de ces exemples. Après tout si je l'ai raté ce partiel il y a bien une raison et j'aimerais bien voir la correction une fois pour comprendre et ne pas chercher dans le vide.

Une nouvelle fois, merci pour votre patience.

par **Doraki** » 03 Juin 2014, 11:16

P et T désignent déjà le cout de quelquechose donc normalement tu n'as pas besoin de le répéter

A part ça, c'est bon.

Le truc à l'intérieur de la somme a le droit d'être indépendant de i (l'indice de la somme)
C'est le truc à l'extérieur (la complexité du programme) qui ne peut pas dépendre de i (l'indice d'une somme / d'une boucle à l'intérieur du programme)

Des sommes où le truc à l'intérieur ne dépend pas de i ben c'est des trucs très simple.

Par exemple, la somme pour i = 1 à 4 de 17, ça fait 17+17+17+17, donc 4*17.
Là c'est pareil, la somme pour i=1 à n de n(n+1)/2 c'est n*n(n+1)/2

par **Rockleader** » 03 Juin 2014, 11:21

J'ai donc du (n²(n+1))²/4

par **Doraki** » 03 Juin 2014, 11:56

Ah oui la vieille technique du "je remplace une addition par une multiplication et hop ! personne n'a rien vu ! ils ne sauront jamais comment quand j'avais tout bon j'ai pu écrire un résultat faux à la dernière ligne"

par **lulubibi28** » 03 Juin 2014, 12:07

Mais c'est un truc de dingue cette exercice .En fait , tu as tout élevé à la puissance de 2 .

par **Rockleader** » 03 Juin 2014, 12:34

Doraki a écrit:Ah oui la vieille technique du "je remplace une addition par une multiplication et hop ! personne n'a rien vu ! ils ne sauront jamais comment quand j'avais tout bon j'ai pu écrire un résultat faux à la dernière ligne"

Oui merde pardon :mur:

S= n²(n+1)

Ce qui correspond bien au résultat trouvé par fatal plus haut :doh:

Merci pour vos explications, j'ai compris la technique pour cet exo.

Ensuite suffit juste de comparer les polynômes obtenus dans chaque cas et sélectionner le plus petit.

par **Rockleader** » 03 Juin 2014, 12:54

Bon, alors voici le second exo.

On nous propose 3 algo récursifs pour résoudre un même problème. Leur complexité respectives satisfont les récurrences suivantes.

Ta(n)=4Ta(n/4)+5n
Tb(n)=2Tb(n/4)+n²
Tc(n)=2Tc(n/2)+10

a- Quelle est la complexité asymptotique de chaque algorithme (approchées et demandé sous la forme d'un ordre de grandeur (grand théta(f(n))))

b- Lequel de ces algo est le plus rapide quand n-->oo

Pour la question b, il suffira de réutiliser les résultats de la première question.

Ce qui m'amène donc à la question a.

Si je ne me trompe pas complexité asymptotique ça signifie bien lorsque n tend vers l'infini ?

Comment peut on étudier vers quoi vont tendre ces suites alors qu'on a aucun point de départ du style Ta(0)=1 ?

Je tente quand même.

Dans les récurences divisés, on adopte la forme T(n)=a.T(n/b)+f(n)

Dans mon cas j'ai donc

f1(n)=5n
f2(n)=n²
f3(n)=10

Je dois donc montrer pour chaque f qu(il existe au moins un c >0 tel que T(n)=c.f(n)

Sa c'est pour la théorie, mais du point de vue pratique je ne vois pas comment on fait.

par **Rockleader** » 04 Juin 2014, 17:20

Up ;)

Du coup je dois prendre quoi comme T(n) ?

Sa voudrait dire qu'il me faudrait faire un truc de ce style là:

Ta(n)
<=>

4Ta(n/4)+5n < c*5n

Soit

(4/5n)*Ta(n/4) +1 < c

Mais comme on n'a pas d'expression exacte de Ta c'est un peu compliqué...une idée ?

par **Doraki** » 04 Juin 2014, 18:18

Pour commencer tu prends un exemple concret où T(1) = 1, et tu regardes T(4^n) pour n=1,2,3,4,5 dans chaque cas et tu observes ce que tu obtiens.

par **Rockleader** » 04 Juin 2014, 19:01

Hypothèse Ta(1)=1

==>

Ta(4)=4Ta(1)+5*4 = 24
Ta(16)=4Ta(4)+5*16= 64+81= 145

Je vois pas vraiment ce que l'on peut en déduire; on va avoir une suite croissante, je vois pas vraiment d'autre relation à faire.
Qui plus est on part de T(1)=1 mais au final on en sait rien ça pourrait très bien être T(1)=2 ou autre...

Complexité algorithmique

Complexité algorithmique

Qui est en ligne