Algorithme sur ensembles

Bonjour,

je révise pour un contrôle et il y a un exo sans correction que je n'arrive pas à faire. Je vous mets l’énoncé :

Citation:

---

Problème :

On considère l'ensemble A = {1,2,....,n}. Un sous-ensemble non-vide S de A est Safe si et seulement si il n'y a pas deux entiers x et y dans S tels que abs(x-y) = 1. (abs = valeur absolue). par exemple si n = 5, alors les sous ensembles {1,3,5}, {2,5}, {4} sont safe, tandis que {1,3,4} n'est pas safe car abs(3-4)=1.

Travail demandé :

Écrire un algorithme efficace SAF (O(n) en temps et espace) qui renvoie le nombre de sous ensemble safe de A. Par exemple, si n= 5 alors SAF(5) = 12 (car les sous-ensembles de A sont {1}, {2}, {3}, {4}, {5}, {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5} et {1,3,5}. Justifier la correction de votre algorithme et calculer formellement sa complexité en temps et en espace. On suppose que toute opération arithmétique et logique est en O(1).

---

Je pense que mon programme doit trouver tous les sous-ensembles et calculer si abs(x-y) = -1, mais je ne vois pas comment faire cela.

Merci de votre aide.

Salut,

Comment construire l'ensemble des parties safe de {1,...,n} ?

En notant P(n) l'ensemble des parties de {1,...,n}, PS(n) l'ensemble des parties safe de {1,...,n}, |A| le cardinal de l'ensemble A (donc ici S(n)=|PS(n)| )

pour n=1, c'est simple :
P(1)={ {}, {1} } => PS(1)={ {1} } => S(1)=|PS(1)|=1

pour n=2, toujours aussi simple :
P(2) = { {}, {1}, {2}, {1,2} } => PS(2)={ {1}, {2} } => S(2)=|PS(2)|=2

pour n=3 :
P(3) = { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
PS(3)= { {1}, {2}, {3}, {1,3} }
S(3) = 4

pour n=4 :
P(4) = { {}, {1}, {2}, {3}, {4},
{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4},
{1,2,3}, {1,2,4}, {2,3,4} }
PS(4) = { {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4} }
S(4)=7

tu peux essayer pour n=5,6 pour te familiariser avec le problème. J'ai souligné les éléments rajoutés par rapport au cas précédent et en gras ceux du cas précédent.

Ensuite on peut se poser la question :
Peut-on trouver une relation entre PS(n+1) et PS(n) ?
Déjà PS(n) est inclu dans PS(n+1), mais quel sont les parties que l'on rajoute ?
Ces parties sont simplement celle qui contiennent n+1 et pas n, celles que l'on construit en ajoutant n+1 aux éléments de PS(n-1), il ne faut pas oublier de rajouter {n+1} :
PS(n+1) = PS(n) U { {n+1} U X / X∊PS(n-1) } U {{n+1}}

Donc S(n+1)=|PS(n+1)| = |PS(n)| + |PS(n-1)| + |{{n+1}}|
S(n+1)=S(n)+S(n-1)+1

Bon il faut formaliser ça un peu mieux, surtout prouver que tu as bien tous les éléments et exactement ceux que tu cherches.

On a une relation simple : S(n+1)=S(n)+S(n-1)+1, peut-on calculer S(n+1) avec un algo linéaire ? La réponse est oui. Pour te donner une indication regarde du côté des algorithmes calculant la suite de Fibonacci (elle ressemble fortement non :) ). Tu peux largement t'en inspirer pour créer un algo en O(n).
Tu pourras même trouver une formule explicite.

Premièrement, Merci beaucoup pour ta réponse détaillé. :ccool:

deuxièmement, je vais m'y penché pour bien comprendre.
Merci beaucoup en tout cas.

Bonjour,
avec un papier et un crayon on voit vite qu'il s'agit à peu de choses près du nombre d'éléments dans une pyramide.

Voici l'expression de SAF(n) que je trouve en fonction de n :

(NB : La version récursive est assez élégante je trouve ; dans les deux cas représenter sur un papier les parties de [|1;n|] safes contenant k éléments sous la forme de k/2 triangles ;)).

Salut prgasp77,

Effectivement c'est un problème qui est graphiquement parlant.
Ton image est petite mais je pense que ta formule pour SAF(n)=n+somme_{k=1}^{floor(n/2)} (n-2k)(1/2)(n-2k+1) ne donne pas le résultat attendu (par exemple SAF(6)=20, tu obtiens 19).

Bonjour kwariz.

Effectivement j'ai fait une image un peu petite, mes excuses. Néanmoins, si tu cliques dessus tu l'auras dans une version un tout petit peu plus grande, suffisamment j'espère pour remarquer qu'il s'agit d'un ceiling plutot que d'un floor :p.

Quand à SAF(6), à la main je compte 19 >_<

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 13
8. 14
9. 24
10. 15
11. 25
12. 35
13. 16
14. 26
15. 36
16. 46
17. 135
18. 146
19. 136

(En supposant ma notation flemmarde compréhensive).

Héhé ... je change de décennie cette année et mes yeux se font vieux ^^ ils n'ont jamais été bon état en même temps 8)

sinon il te manque :

20. 246

Citation:

---

Envoyé par kwariz

sinon il te manque :

20. 246

---

http://alexandrahighcrest.com/blog/w...012/01/JLP.png

C'est toute mon analyse qui tombe à l'eau :'(.

Edit : taille de l'image revue à la baisse

Mais non Jean-Luc ! Un tour en warp 9 et le tour est joué

:lol:

PS: merci pour la taille de l'image ^^