Algorithme sur ensembles

**Tumeconnais** · 09/04/2012, 13h27

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

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.

**kwariz** · 09/04/2012, 15h00

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.

**Tumeconnais** · 09/04/2012, 15h29

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

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

**prgasp77** · 10/04/2012, 20h34

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

).

**kwariz** · 10/04/2012, 21h33

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

**prgasp77** · 10/04/2012, 22h08

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