Discussion :

[biba1980]

Bonjour à tous,
Je voudrais savoir la signification d'un algorithme qui calcule la plus courte sous suite commune de deux éléments.
Pour la plus longue sous suite, j'ai trouvé plein de références, mais la plus courte, je n'ai pas trouvé d'explications.
Je ne sais pas comment je pourrais écrire un algorithme si je ne sais pas ce qu'il doit faire exactement.
Si quelqu'un à une idée.
Merci à tous.

[pseudocode]

Facile : la plus petite suite commune, c'est la suite "vide".

Plus sérieusement, tu es sur que c'est la plus "courte" sous suite commune que tu dois chercher ?

[biba1980]

Je suis sérieuse, je ne plaisante pas et d'ailleurs j'ai même pas le temps pour plaisanter, à moins qu'il n'y ait une erreur dans l'énoncé.
L'exemple donné dans l'exo était le suivant:
A = informatique B = fourniture
C(la plus petite sous suite commune) serait (infourmatniqture)
Après une longue recherche, j'ai trouvé ce qu'on appelle "la plus courte super sous suite commune". et je me suis dit que c'est peut être ça. Pouvez vous me dire, d'après cet exemple s'il s'agit de ça ou pas.
Merci.

[souviron34]

Pouvez vous me dire, d'après cet exemple s'il s'agit de ça ou pas.

je ne pense pas...

Je pense que ce serait fo :

informatique
fourniture

quel ensemble de lettres dans le même ordre et accolées est-il commun entre les 2 chaînes ?

[Jedai]

A priori le problème serait "la plus courte super suite commune" ou un truc comme ça, en tout cas, quel que soit le nom approprié, la définition d'une "super suite commune" serait la suivante : Elle contient A et B comme sous-suites (par exemple AB convient, BA aussi). Et il faut donc trouver la plus courte ou une plus courte.

--
Jedaï

[Jedai]

Un premier algorithme serait :

Code Haskell :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
-- shortest common supersequence
scs :: (Eq a) => [a] -> [a] -> [a]
scs [] ys = ys
scs xs [] = xs
scs xxs@(x:xs) yys@(y:ys)
    | x == y    = x : scs xs ys
    | otherwise = minBy (comparing length) (x : scs xs yys) (y : scs xxs ys)
 
minBy :: (a -> a -> Ordering) -> a -> a -> a
minBy comp x y =
    case comp x y of
      LT -> x
      _  -> y

Mais son efficacité est horrible bien sûr (tout comme l'algorithme naïf pour lcs), donc il faudrait introduire de la programmation dynamique, je laisse ça au soin du posteur, je pense avoir déjà bien débroussaillé le sujet !

--
Jedaï

[biba1980]

Si ce programme était écrit simplement en pseudo code, ça aurait était mieux. Car je n'ai pas tout saisi.
En tout cas, l'essentiel c'est que j'ai connu le principe.
Merci à tous.

[Jedai]

En pseudocode donc :

Code Pseudocode :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
scs(xs, ys) =
  Si xs est vide 
  Alors ys
  Sinon (
    Si ys est vide
    Alors xs
    Sinon (
      Soit (x,y) := (premier élément de xs, premier élément de ys)
      Si x = y
      Alors x concaténé à scs(suite de xs, suite de ys)
      Sinon minimum selon longueur entre (x concaténé à scs(suite de xs, ys)) et (y concaténé à scs(xs, suite de ys))
    )
  )

C'est plus facile à lire ?
(NB : Le passage à la programmation dynamique de SCS est parfaitement identique à celui de LCS)
--
Jedaï

[biba1980]

Merci, ce que je voulais savoir c'était juste de connaître si c'est bien de rechercher la plus courte super sous suite commune.
Mais, t'es sûr que ton programme résolut vraiment ce problème?

[pseudocode]

Merci, ce que je voulais savoir c'était juste de connaître si c'est bien de rechercher la plus courte super sous suite commune.

Oui c'est bien le problème SCS (shortest common supersequence)

[Jedai]

Merci, ce que je voulais savoir c'était juste de connaître si c'est bien de rechercher la plus courte super sous suite commune.
Mais, t'es sûr que ton programme résolut vraiment ce problème?

C'est pas "super sous suite" c'est "super suite" (une "super-suite" de A c'est une suite qui contient A comme sous-suite).
Et mon programme résout proprement le problème, il est simple de le vérifier par induction.

--
Jedaï

[biba1980]

Oui, alors merci à tous.