[Recursif] Recherche sequence

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

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

---

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:

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 ?

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.

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).

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é) ?

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:

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:

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...

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 ?

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).

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.

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 :)

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:

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 ?

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) :? )

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 ?