[Recursif] Recherche sequence

Version imprimable

[Recursif] Recherche sequence, calcul complexité

Bonjour à tous

Je dois ecrire un algo qui recherche la plus grande sequence de 1 dans un tableau à 1 dimension composé uniquement de 1 et de 0.

Pour cela on nous a donné quelques pistes : choisir un pivot (le milieu du tableau). Utiliser deux fonctions : head(T,i,j) qui retourne le plus long sous tableaux préfixe de T[i...j] uniquement composé de 1, et tail(T,i,j) qui retourne le plus long sous tableaux suffixe de T[i...j] uniquement composé de 1.

En m'aidant de ça et de ce que nous a dit la prof..j'ai concocté ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 fonction rechRec(T,i,j) : (p,n) // (position plus grande sequence,longueur) n <- j - i + 1 // taille tableau si n = 1 alors si T[i] = 0 alors retourner (0,0) sinon retourner (i,1) finSi sinon solutiong <- rechRec(T,i,i+(n/2)-1) // (p,n) de la meilleure solution à gauche solutiond <- rechRec(T,(n/2)+i,j) // (p,n) de la meilleure solution à droite si solutiong.n > solutiondroite.n alors maxsol = solutiong sinon maxsol = solutiond finSi g <- tail(T,i,i+(n/2)-1) d <- head(T,i+(n/2),j) longueur = g.longueur + d.longueur si longueur > maxsol alors si g est vide alors retourner(i+(n/2),longueur); sinon retourner(i+(n/2) - g.longueur,longueur) else retourner (maxsol) finSi finSi finFonction
Je l'ai rapidement implémenté en C et ça n'a pas l'air de renvoyer le bon resultat :(
Je pense que ça vient de l'algo.. car j'ai suivit un peu sans comprendre ce que nous a dit la prof..
Car je ne vois pas trop comment il peut fonctionner cet algo :aie:

Si vous pouviez m'eclairer un peu car je patauge bien depuis une semaine :?
Merci pour votre aide

29/10/2006, 16h22
Captain_JS

Mouais personnelement avec un nombre délimitant la position du premier 1, la longueur max des 1 et une fonction > (ou < suivant les choix), l'algo est plus simple et moins tortueux

Ca n'est pas des plus simples, mais ça a l'air de fonctionner...
As-tu un exemple sur lequel ça ne marche pas ?

[edit]
Pourquoi faire
Code:

1 2 3 si g est vide alors retourner(i+(n/2),longueur); sinon retourner(i+(n/2) - g.longueur,longueur)
au lieu de
Code:

1 2 retourner(i+(n/2) - g.longueur,longueur)
?

Une autre possibilité, peut-être buggée, c'est juste pour l'idée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
fonction rechRec(T,i,j) : (p,n) // (position plus grande sequence,longueur)
  n <- j - i + 1 // taille tableau
  si n = 1 alors
    si T[i] = 0 alors retourner (0,0)
    sinon retourner (i,1)
    finSi
  sinon
    milieu_g <- tail(T,i,i+(n/2)-1)
    milieu_d <- head(T,i+(n/2),j)
    longueur_milieu <-milieu_g.longueur + milieu_d.longueur
    pos_milieu <- i+(n/2) - milieu_g.longueur
    solutiond <- rechRec(T,pos_milieu+longueur_milieu,j) // (p,n) de la meilleure solution à droite
    solutiong <- rechRec(T,i,pos_milieu-1) // (p,n) de la meilleure solution à gauche
    Renvoyer la meilleure solution parmi milieu, solutiong et solutiond
  finSi
finFonction

31/10/2006, 12h43
sorry60

Ca je confirme qu'il est pas evident ! :D Mais je n'ai pas le choix...
Il est censé être en O(log(n)) où n est la taille du tableau.

Merci pour tes infos, je vais y jeter un oeil ;)
Je pense que mes bugs viennent de l'implementation des fonctions head() et tail() que j'ai fait un peu à la va-vite :oops:
31/10/2006, 13h12
borisd

L'algorithme que j'ai proposé est en O(N) : dans tous les cas, chaque case du tableau est examinée une et unique fois (par le cas terminal (n=1) ou par une des fonctions head et tail), bien que le nombre d'appels à RechRec soit logarithmique.
Tu peux améliorer la complexité moyenne en stockant la taille maximale de la suite de 1 déjà trouvée, et en n'examinant pas les intervalles de taille inférieure (peut-être le seul intérêt de la méthode ?); aussi en affinant les intervalles gauche et droite (d'une unité à droite pour le gauche et d'une unité à gauche pour le droite, puisque ces cases contiennent forcément un 0).

Attention, le tien, par contre, examine parfois plusieurs fois chaque case du tableau.

Avoir une complexité de log(N) me semble impossible : comment savoir même seulement combien de 1 contient le tableau sans le parcourir au moins une fois ?
31/10/2006, 14h10
sovitec

Citation:

Envoyé par sorry60

Il est censé être en O(log(n)) où n est la taille du tableau.

En moyenne ou dans le pire des cas ?

Edit: Je n'aurai pas du laisser la fenêtre ouverte pendant une heure sans sauver.
31/10/2006, 15h44
sorry60

Citation:

Envoyé par sovitec

En moyenne ou dans le pire des cas ?

Edit: Je n'aurai pas du laisser la fenêtre ouverte pendant une heure sans sauver.

Je ne sais pas, je n'ai pas encore étudié cette question :)

Les fonctions head() et tail() doivent etre en O(n).
31/10/2006, 15h53
borisd

Citation:

Citation:
sovitec a écrit :
En moyenne ou dans le pire des cas ?

Edit: Je n'aurai pas du laisser la fenêtre ouverte pendant une heure sans sauver.

Je ne sais pas, je n'ai pas encore étudié cette questio

Tu dois écrire une procédure de complexité O(log(n)) au pire cas (ce que je pense impossible, puisque dans le cas d'un tableau rempli de 1, tu dois forcément examiner chaque case pour t'assurer qu'aucun 0 ne traine) ou tu supposes que celle que tu as écrite est de cette complexité au pire cas (ce qui est faux), ou tu dois écrire une procédure de complexité moyenne O(log(n)) (ce qui est peut-être le cas de celle que je t'ai proposé, j'avoue que je n'ai pas l'habitude d'évaluer ce type de complexité) ?
31/10/2006, 16h03
sorry60

Bon je viens de re-implementer les fonctions tail() et head(), c'est bon ça fonctionne :D

J'ai plus qu'à trouver et prouver la complexité :aie:
31/10/2006, 16h05
sorry60

Citation:

Envoyé par borisd

Tu dois écrire une procédure de complexité O(log(n)) au pire cas (ce que je pense impossible, puisque dans le cas d'un tableau rempli de 1, tu dois forcément examiner chaque case pour t'assurer qu'aucun 0 ne traine) ou tu supposes que celle que tu as écrite est de cette complexité au pire cas (ce qui est faux), ou tu dois écrire une procédure de complexité moyenne O(log(n)) (ce qui est peut-être le cas de celle que je t'ai proposé, j'avoue que je n'ai pas l'habitude d'évaluer ce type de complexité) ?

non en fait la procédure nous etait quasiment donné (du pseudo algo). Je dois trouver sa complexité.
Vu que l'exo d'avant donnait un O(n) et que celui ci est censé etre meilleur, j'ai pensé à du O(log(n)) mais je n'ai encore rien cherché, c'etait juste une supposition :roll:
31/10/2006, 16h39
sorry60

Pour la complexité, j'obtiens cette equation :

T(n) = c + 4*T(n/2)
T(n/2) = c + 4*T(n/4)
...
...
T(1) = c

où T(n) : temps mis pour un tableau de taille n
c : temps constant

C'est tres loin de donner du log(n) dans le pire-cas...
31/10/2006, 16h44
nletteron

Petite question.

Le pivot est il le milieu du tableau tout court ? pivot ne doit surtout pas être un élément du tableau contenant un 1 il me semble non ?

Est ce que c'est un conseil de l'exercice ou est ce que c'est toi qui subodore qu'il faut une recherche dichotomique ?
31/10/2006, 16h46
borisd

La démonstration de la complexité est plus facile sur l'algo que j'ai donné : le tiens effectue des traitements inutiles et pas faciles à cerner. En effet, tu commences par lancer ton calcul récursivement sur le sous-intervalle gauche, puis la fonciton tail() re-examine une partie de l'intervalle (idem à droite).
Mon algo examine une seule fois chaque case (si une case est traitée par tail() ou head(), les intervalles sur lesquels on relance la procédure récursivement ne comprennent pas cette case). On arrive donc globalement à une complexité de O(n).
31/10/2006, 16h48
borisd

Citation:

Envoyé par nletteron

Petite question.

Le pivot est il le milieu du tableau tout court ? pivot ne doit surtout pas être un élément du tableau contenant un 1 il me semble non ?

Ca ne pose pas de problème : head est appliqué sur i+(n/2),j.
31/10/2006, 16h56
sorry60

Citation:

Envoyé par borisd

La démonstration de la complexité est plus facile sur l'algo que j'ai donné : le tiens effectue des traitements inutiles et pas faciles à cerner. En effet, tu commences par lancer ton calcul récursivement sur le sous-intervalle gauche, puis la fonciton tail() re-examine une partie de l'intervalle (idem à droite).
Mon algo examine une seule fois chaque case (si une case est traitée par tail() ou head(), les intervalles sur lesquels on relance la procédure récursivement ne comprennent pas cette case). On arrive donc globalement à une complexité de O(n).

J'avais pas vu que tu avais posté un algo :oops:
En effet il est beaucoup mieux que le mien.. en y reflechissant, c'est vrai que qu'il est tres inutil de rappeller en recusif sur le tableau contenant le milieu..

Merci pour ton aide, je vais corriger ça :)
01/11/2006, 12h04
sorry60

J'ai revu mon algo, en ajoutant tes corrections.
J'obtiens les equations suivantes :

Meilleur-cas :
T(n) = c + 2T(n/2)
en effet : tail() et head() => T(n/2)
les 2 appels recursifs : O(1) (car dans le meilleur cas, il n'y a que des 1)
T(n) = c +2(c + 2T(n/4))
T(n) = c + 2c + 4(c +2T(n/8))
...
...
T(n) = c + 2c + 4c + ... + (2^(n/2))c
T(n) = c(1+2+4+...+(2^(n/2)))
T(n) = c((2^(n/2 +1)) - 1)
=> meilleur cas : 2^(n/2)

Pire-cas :
T(n) = c + 4T(n/2)
en effet : tail() et head() => T(n/2)
les 2 appels recursifs : T(n/2) (car dans le pire cas, pas de sequence de 1 au milieu)
Meme demo
..
..
T(n) = c((4^(n/2 +1)) - 1)
=> pire cas : 4^(n/2)

C'est assez tiré par les cheveux mais j'avoue que je patauge pas mal..:oops:
01/11/2006, 14h16
borisd

On se limite au cas où n=2^k. Dans le cas contraire, il suffit d'ajouter des 0 au bout du tableau pour avoir n=2^k, et on saura qu'on a une complexité meilleure (mais du même ordre) que celle qu'on calcule ici.

* Dans le cas où il n'y a que des 1 :
- head() et tail() parcourent, au premier appel, tout le tableau -> O(n)
- les appels récursifs sont alors lancés sur des intervalles de taille nulle (cas spécial gérable en O(1)
--> complexité dans ce cas : O(n)

* Dans le cas où il n'y a que des 0 :
- head() et tail() s'exécutent à chaque fois en O(1) : elles s'arrêtent dès qu'elles rencontrent un 0, i.e. dès le début
- appels récursifs initiaux : 2T(n/2)
-> complexité sur un tableau de taille n : 2T(n/2)+c
d'où T(n/2) = 2T(n/4)+c
...
Or, on a T(1)=c
donc T(2)=2T(1)+c=3c
T(4)=2T(2)+c=7c
T(8)=2T(4)+c=15c
...
T(n)=(2n-1)c
Cette valeur peut se retrouver en dessinant l'arbre des appels et en comptant le nombre de noeud qu'il comporte. La racine correspond à un tableau de taille n, ses deux fils à des tableaux de tailles n/2, les feuilles à des tableaux de tailles 1, leurs parents à des tableaux de taille 2...
Le nombre de feuilles est de n ; le nombre de noeuds total est donc de 2n-1.
--> complexité dans le cas que des 0 en O(n)

* Cas où il y a un mélange de 0 et de 1 : la procédure se comporte globalement comme dans le cas où il n'y a que des 0. Lorsque des 1 se présentent sur un intervalle [i,j], head() et tail() sont de complexité O(j-i+1) et les appels récursifs sont effectués sur des ensembles de taille réduite de j-i+1; leur complexité étant globalement linéaire, on reste en O(n).

Je crois avoir repéré tes erreurs :
* Partie Meilleur-cas : s'il n'y a que des 1, les appels récursifs sont en O(1)
* La démonstration pour la partie "que des 1" est bien commencée pour, en fait "que des 0". Il y a juste un petit problème là :

Citation:

T(n) = c +2(c + 2T(n/4))
T(n) = c + 2c + 4(c +2T(n/8))
...
...
T(n) = c + 2c + 4c + ... + (2^(n/2))c

On a en fait :
T(n) = c + 2c + 4c + ... + (2^(log2(n)))c = c + 2c + 4c + 8c + ... + nc = (2n-1)c

Qu'en penses-tu ?
01/11/2006, 18h55
sorry60

Je ne pense pas que ça soit en O(n), j'ai fait des mesure de temps, tracé la courbe, ça ressemble bien à de l'exponentiel (tableau initialisé aleatoirement avec un taux de 0 de l'ordre de 40%).

Par contre pour le meilleur cas, oui là tu as raison c'est du O(n).
Je vais reflechir pour le pire cas (que des 0) car dans ce cas, c'est vrai que head() et tail() sont en O(1)...

Edit : pour le pire cas, on tombe sur : t(n) = c + 2t(n/2)
Generalement ce genre de truc donne du 2^n (Fibbonnacci par ex, bienque pour fibbonnacci c'est t(n) = c + 2t(n-1) :? )
01/11/2006, 19h25
sorry60

En y reflechissant un peu mieux :

Meilleur cas (que des 1) :
on ne fait que tail() et head() => O(n) + O(n) => O(n)

Pire cas (que des 0)
tail() et head() => O(1)
donc l'equation se resume à :
T(n) = c + 2T(n/2) (avec c = temps constant)
Reste plus qu'à resoudre cette jolie equation :aie:

Edit : allons y :)

T(n) = 2T(n/2) + c
T(n/2) = 2T(n/4) + c
...
...
T(n/n) = c

Multiplions par 2 :

2T(n) = 2*2T(n/2) + 2c
2T(n/2) = 2*2T(n/4) + 2c
...
2T(n/n) = 2c
------------------------------------------ Additionnons tout (simplification en diagonale)
2T(n) = n*2 + n*2c
T(n) = n + n*c

==> O(2n)

Qu'en dites vous ?
01/11/2006, 19h38
borisd

Comme je l'ai dit plus haut, trace l'arbre des appels pour n=8 par exemple et compte les noeuds, tu devrais être d'accord avec moi : son nombre de noeuds est exponentiel par rapport à sa profondeur (2^profondeur) mais sa profondeur est de l'ordre de log2(n). Tu as bien un nombre de noeuds linéaire, multiplié par une constante -> O(n).
Ceci est valable pour l'algorithme que j'ai donné. Si le tiens est différent, je n'ai aucune idée de sa complexité.

[Edit] Je viens de voir ton edit. Je suis plutôt d'accord vu que ça concorde avec ce que je dis depuis le début ;)
01/11/2006, 19h39
sorry60

Citation:

Envoyé par borisd

Comme je l'ai dit plus haut, trace l'arbre des appels pour n=8 par exemple et compte les noeuds, tu devrais être d'accord avec moi : son nombre de noeuds est exponentiel par rapport à sa profondeur (2^profondeur) mais sa profondeur est de l'ordre de log2(n). Tu as bien un nombre de noeuds linéaire, multiplié par une constante -> O(n).
Ceci est valable pour l'algorithme que j'ai donné. Si le tiens est différent, je n'ai aucune idée de sa complexité.

As tu lu ma resolution d'equation ? (en Edit)

Car O(2n) et O(n) c'est pareil :)
01/11/2006, 19h41
sorry60

Citation:

Envoyé par borisd

[Edit] Je viens de voir ton edit. Je suis plutôt d'accord vu que ça concorde avec ce que je dis depuis le début ;)

Ok nickel :D

Edit: oui tu le dis depuis le debut mais je voulais y arriver par moi meme avec une demonstration de ce type ;)
01/11/2006, 19h41
borisd

:mouarf: cf mon post précédent
[Edit] les aléas du différé... :mouarf:
01/11/2006, 19h42
sorry60

Citation:

Envoyé par borisd

:mouarf: cf mon post précédent

On s'y perd avec tous ces Edits :lol:

Merci pour ton aide en tout cas ;)