Problème combinatoire/complexité liée à une k-composition

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Problème combinatoire/complexité liée à une k-composition

Messagepar fractaz » Mercredi 20 Septembre 2006, 19:24

Bonjour les matheux/euses,
une question liée à de la cryptographie m'a fait poser le problème suivant :

Trouver un algorithme qui, pour tout entier $n$, donne le $k$-uplet $(a_1, a_2,...,a_k)$ qui vérifie $a_1 + ... + a_k = n$ (ie. une $k$-composition de $n$) et qui ait le plus grand ppcm, la suite des $a_i$ étant croissante et strictement positive.

En pratique, hormis les $a_i=1$, on aura des nombres distincts et premiers entre eux.

Voici ce que cela donne pour 15 à 21 (faits à la "main") :
Code: Tout sélectionner
Nb :      Décomp° :    produit :
15        3 5 7        105
16        4 5 7        140
17        2 3 5 7      210
18        5 6 7        210
19        3 4 5 7      420
20        1 3 4 5 7    420
21        1 1 3 4 5 7  420


Comme on peut le voir, "1" peut y être alors même qu'il n'augmente pas le produit. Sans le "1" :
Code: Tout sélectionner
20        4 7 9        252
21        5 7 9        315


Prendre la suite $(a_k)_k$ croissante a pour but d'optimiser le temps de recherche (inutile pour 15 de trouver (5,3,7) ; (3,7,5) etc.) et d'avoir unicité du $k$-uplet (en fait, l'ordre des éléments n'a pas d'importance, il s'agit de trouver un ensemble de nombres. Mais il est, je pense, plus simple de prendre un $k$-uplet avec des $a_k$ croissants).

C'est de la combinatoire et de la complexité (plus que de l'algorithmique). J'aurais tendance à penser à une complexité exponentielle... mais j'en sais rien. Mon prof de combinatoire n'a pas su me répondre.

Accrochez-vous, c'est pas évident ! :shock:
Dernière édition par fractaz le Mercredi 20 Septembre 2006, 19:37, édité 1 fois.
fractaz
Utilisateur
 
Messages: 5
Inscription: Mercredi 20 Septembre 2006, 19:07

Publicité

Messagepar Arnaud » Mercredi 20 Septembre 2006, 19:28

Je pense que tu recherches un algorithme optimisé.

C'est un problème intéressant, mais je ne saisis pas pourquoi tu veux que le ppcm soit le plus petit possible.
Arnaud

Un peu d'info - Pyromaths
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar fractaz » Mercredi 20 Septembre 2006, 19:35

Je recherche bien sûr le meilleur algo possible :) qui marche (à défaut qui approche la solution).

Je veux le ppcm le plus grand et c'est précisément le but de ce problème de trouver la k-composition qui marche (les k-compositions de n, elles ne sont pas dures à trouver...)
fractaz
Utilisateur
 
Messages: 5
Inscription: Mercredi 20 Septembre 2006, 19:07

Messagepar Arnaud » Mercredi 20 Septembre 2006, 19:39

Heu oui le plus grand, vive les fautes de frappe et un partout :D.

Si tu sais trouver les k-compositions, tu as automatiquement le ppcm, donc je ne cerne pas la question...

( j'ai encore dit une bêtise ? :D )
Arnaud

Un peu d'info - Pyromaths
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar fractaz » Mercredi 20 Septembre 2006, 19:43

Si tu sais trouver les k-compositions, tu as automatiquement le ppcm, donc je ne cerne pas la question...


Oui...mais le nombre de k-composition de n est énorme par rapport à n (ça doit être de l'ordre du $n!$ il me semble, j'ai pas envie de refaire les calculs là). Ce qu'il faut c'est utiliser la propriété voulue pour ne pas toutes les chercher.
fractaz
Utilisateur
 
Messages: 5
Inscription: Mercredi 20 Septembre 2006, 19:07

Messagepar guiguiche » Mercredi 20 Septembre 2006, 21:01

Si mes souvenirs sont, le nombre de compositions de $n$ est $2^n$ (suites non nécessairement croissantes). Si on fixe le nombre d'éléments $k$ de la composition et si la suite est strictement croissante, cela doit faire beaucoup moins (mais c'est peut-être encore exponentiel).
guiguiche
Modérateur
 
Messages: 8073
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Messagepar Samurai_2k5 » Vendredi 22 Septembre 2006, 15:08

salut,

en cryptographie $n$ est grand, dans le cas : $n>>k^2  (1)$ , pourquoi ne pas prendre les entiers autour de $n/k$ ?

Je m'explique :
Si $(1)$ est verifié on aura $n/k>>k$ , et donc les $k$ entiers dans l'intervalle $[n/k-k/2 , n/k+k/2]$ sont une bonne approximation(*) de la k-compsition maximale (**).

(**) la solution du probleme d'optimisation ${ArgMax(ab)/ a+b=Cte}$ est bien $a=b=Cte/2$
(*) pour $a$ et $b$ d'une telle k-composition $a-b<k$ et $a>>k , b>>k$ donc le PPCM a de grandes chances d'etre le produit...

C'est juste une piste :idea:
_ rien a faire, je suis perdu
Samurai_2k5
Déca-utilisateur
 
Messages: 35
Inscription: Vendredi 22 Septembre 2006, 12:58


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: MSN [Bot] et 3 invités