Discussion :

[biba1980]

Bonjour,
Soit le problème suivant, T, un tableau dont les indices vont de 1 à n contenant des 0 et des 1 dans un ordre quelconque.
Trouver un algorithme linéaire en temps et de complexité spatiale en O(1) pour trier ce tableau et retourner le nombre de 0, et ce, sans compter explicitement le nombre de 0 et de 1. Justifiez que votre algorithme est linéaire. Identifiez le type d’algorithme que vous avez conçu (vorace, programmation dynamique, etc.). Décrivez votre algorithme en pseudo-code.

Moi, j'ai fait ce code là:
Programme trier

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
tab, tab1 : tableau [1..n]
debut
    c:=1
    k:=n
    pour i := 1 haut n faire
        si tab[j] =0 alors 
            tab1[c]:=tab[i]
            c:=++
        sinon tab1[k]:=tab[i]
            k:=--
        finsi
    finpour
fin

Je veux, si possible savoir si cet algorithme est de complexité spatiale constante donc dans O(1), Je ne sais pas de quel type est cet algorithme.
Merci à tt le monde.

[ToTo13]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
tab, tab1 : tableau [1..n]
debut
    c:=1
    k:=n
    pour i := 1 à n faire // Ok c'est linéaire
        si tab[i] = 0 alors  tab1[c++]:=tab[i] // Attention tu avais mis tab[J]
        sinon tab1[k--]:=tab[i]
        finsi
    finpour
    retourner c-1 // Ne pas oublier de retourner le nombre de zéros
fin

Ton algorithme est bien linéaire car tu ne parcours qu'une seule fois le tableau sans opérations à l'intérieur et la taille mémoire dépend de n.

[pseudocode]

Ton algorithme est bien linéaire car tu ne parcours qu'une seule fois le tableau sans opérations à l'intérieur et la taille mémoire dépend de n.

Tout a fait. L'algo n'est donc pas en complexité spatiale O(1).

La complexité spatiale O(1) signifie qu'il ne faut pas "dupliquer" le tableau existant. Il faut donc un algo de tri "in place", c'est à dire qu'il modifie directement le tableau de départ.

[lcfseth]

L'algo que j'aurais fais, en gros (je me rappelle plus trop de la syntaxe):

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
 
tab: tableau [1..n]
debut
<div style="margin-left:40px">
i:=1
c:=n
tantque i<= n et c>=i faire
<div style="margin-left:40px">
si tab[i] = 1 alors
<div style="margin-left:40px">
tab[i]:=tab[c]
tab[c]:=1
c--</div>sinon
<div style="margin-left:40px">
i++</div>finsi</div>fintantque
retourner n-c // c est le nombre de 1 :)</div>fin

L'idée et de mettre tout les 1 en fin de tableau, en faisant un simple swap avec la valeur en cours. Si le tableau est plein de 0, i atteindra n, si le tableau est plein de 1, i restera à 1 et c'est c qui ira à 1.
Complexite algorithmique en n au pire, complexite spaciale 1.

[pseudocode]

D'accord avec lcfseth. Quoique j'aurais plutot écrit l'algo ansi :

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
left:=1
right:=n
TANTQUE left<=right FAIRE
    SI tab[left]=0 ALORS
        left++
    SINON
        SI tab[right]=1 ALORS
            right--
        SINON
            tab[left]:=0
            tab[right]:=1
        FINSI
    FINSI
FINTANTQUE
RETOURNER (left-1)

Edit : modif du code pour un tableau commencant à l'indice "1", comme indiqué dans le PO

[lcfseth]

Joli manière de profiter du faible nombre de l'ensemble de départ (0,1)
Respect

[biba1980]

Désolée de ne pas répondre plus tôt, car où je suis il y a un décalage de 6 haures (il est maintenant 7:43 chez moi) et merci beaucoup pour vos réponses, j'avais fait avant quelques choses qui ressemblait au code de lcfseth mais pour les 0 (mettre les 0 en premieres cases et incrémenter à chaque fois le compteur) mais je n'étais pas tout à fait sûre.
Merci encore à tous.

[biba1980]

En tout cas, chapeau pour pseudocod, c'est très ingénieux, bravo et merci.
Et le compteur left donne le nombre de 0 mais il ne compte pas explicitement le nombre de 0.
Il faut maintenant que je le fasse avec un tableau contenant des 0,1 et 2.
Je vais essayer de le faire et je vous montre le code.
Merci.

[biba1980]

Voilà, j'ai écris ce code pour permettre de trier un tableau contenant des 0, 1 et 2

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
 
tab: tableau [1..n]
debut
 
i:=1
c:=n
k :=1
tantque i<= n et c>=k faire
 
si tab[k] =2  alors tab[k]:=tab[c]
                   tab[c]:=1
                   c--
             sinon
             si tab[k] = 0 alors tab[k] := tab[i]  
                                 tab[i] := 0
                                 i++
                                 k++
                           sinon k ++
             finsi
finsi
fintantque
fin

[pseudocode]

il faut "Diviser pour régner" !

[biba1980]

Le but de mon exo est de :
1) ecrire un algorithme de tri pour trier un tableau contenant des 0 et1 avec les contraintes déjà mentionnées
2)prendre le même algorithme et essayer de l'adapter pour des cas de tableau de 0,1 et 2 avec les mêmes contraintes.
3) donner des conditiones pour généraliser cet algorithme pour des nombres quelconques.
Donc, il faut se baser dans les 3 questions sur un même algorithme.
Merci.

[pseudocode]

Donc, il faut se baser dans les 3 questions sur un même algorithme.
Merci.

Oui, j'avais deviné. D'où ma remarque précédente.

[biba1980]

Juste une question, l'algorithme que toi t'as proposé, il est de type diviser pour reigner? ça me permettrait de savoir quel chemin prendre.
Merci pour ta patience.

[lcfseth]

y'a plein d'erreur dans ton algos.

Un algo diviser pour régner, divise le tableau en plusieurs parties. On trie ensuite chaque parties soit on la divisant encore, soit en utilisant un algo qui marche pour un plus petit ensemble.
Notre algo (parcequ'on gros c'est le même) n'est pas du type diviser pour regner (le besoin ne s'est pas fait ressentir). Mais si tu y reflechis bien, tu sais trier un tableau avec deux valeurs possible. Maintenant tu en a 3 voir plus. Si tu pouvais avoir un tableau avec seulement 2 valeurs, le premier algo marcherais a nouveau

[biba1980]

Je t'envoie l'enoncé

Soit T, un tableau dont les indices vont de 1 à n contenant des 0 et des 1 dans un ordre quelconque.
(a)Trouver un algorithme linéaire en temps et de complexité spatiale en O(1) pour trier ce tableau et retourner le nombre de 0, et ce, sans compter explicitement le nombre de 0 et de 1. Justifiez que votre algorithme est linéaire. Identifiez le type d’algorithme que vous avez conçu (vorace, programmation dynamique, etc.). Décrivez votre algorithme en pseudo-code.
(b) Pouvez-vous modifier votre algorithme pour résoudre le même problème mais où le tableau contient
des 0, 1 et 2 dans un ordre quelconque (en utilisant les mêmes contraintes qu’en (a)) ? Si oui, décrivez-en
les grandes lignes. L’algorithme doit avoir une complexité temporelle linéaire et une complexité spatiale
constante.
(c) Dans quelles conditions votre algorithme peut être généralisé pour des valeurs quelconques avec les
mêmes complexités spatiale et temporelle ?

ce n'est pas que cet exo, elle nous donné des exo incohérents, je ne sais même pas s'il existe des solutions à ces exos là.
Moi, j'ai appliquer un algorithme de type algorithme de comptage. c'est linéaire, mais il faut utiliser deux tableaux (complexité spatiale dépendante de n) en plus on est obliger de compter les nombres.

[lcfseth]

J'ai édité mon post. Je sais pas si tu l'a lu.
on je vais te simplifier les choses.

Nous avons vu qu'on pouvais trouver un algo qui peut trier un tableaux ne contenant que des 0 et des 1 (2 valeurs donc).
Maintenant nous avons 3 valeurs ( 0,1,2). Si nous pouvions nous débarrasser de l'une de ces valeurs, on pourra à nouveau utiliser le premier algo. C'est l'idée derrière le paradigme "Diviser pour régner"
Donc si on suppose dans un premier temps que 1 et 2 sont équivalent et qu'ils sont supérieure à 0. En appliquant le premier algorithme on divise notre tableau en deux partie plus petites. La premiére ne contient que des 0. La 2eme ne contient que des 1 et des 2.
Nous revoila donc avec 2 valeurs. On peut à nouveau appliquer le premier algo sur cette partie. Et voila Bingo.

La compléxité de l'algo est toujours n (temporelle) puisque le nombre d'itérations dépend du nombre de possibilités et non du nombre d'élements du tableau et 1 (spatiale) parcequ'on n'utilise pas de second tableau

[biba1980]

Oui, c vrai je me suis trompée dans les indices voilà :

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
 
tab: tableau [1..n]
debut
 
i:=1
c:=n
k :=1
tantque k<= n et c>=k faire
 
si tab[k] =2  alors tab[k]:=tab[c]
                   tab[c]:=2
                   c--
             sinon
             si tab[k] = 0 alors tab[k] := tab[i]  
                                 tab[i] := 0
                                 i++
                           sinon k ++
finsi
fintantque
fin

[pseudocode]

Donc si on suppose dans un premier temps que 1 et 2 sont équivalent et qu'ils sont supérieure à 0. En appliquant le premier algorithme on divise notre tableau en deux partie plus petites. La premiére ne contient que des 0. La 2eme ne contient que des 1 et des 2.
Nous revoila donc avec 2 valeurs. On peut à nouveau appliquer le premier algo sur cette partie. Et voila Bingo.

.

D'où le fait qu'on demandait de renvoyer le nombre de "0", c'est à dire l'offset du commencement de la 2eme partie du tableau.

[biba1980]

J'ai édité mon post. Je sais pas si tu l'a lu

Non, je ne l'ai pa vu. Mais je commence à comprendre, disons juste un peu.

[lcfseth]

Les algos de type Diviser pour régner sont les plus dur à assimiler au début.
Surtout quant il s'agit de calculer la complexité. Mais une fois que c'est rentré, on peut plus s'en passer


Ps:

il faut "Diviser pour régner" !

Quelque chose me dis que tu l'avais vu avant moi