Discussion :

[sorry60]

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 :

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

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

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

[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

[borisd]

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 :

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

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 :

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

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

?

[borisd]

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

Code :

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

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

[sorry60]

Ca je confirme qu'il est pas evident ! 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

[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 ?

[sovitec]

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.

[sorry60]

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

[borisd]

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

[sorry60]

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

J'ai plus qu'à trouver et prouver la complexité

[sorry60]

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

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

[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 ?

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

[borisd]

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.

[sorry60]

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

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

[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à :

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 ?

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

[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

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 ?