Bonjour tout le monde, alors voilà je suis en deuxième année de licence MASS et je dois rendre un projet d’info. Sauf que je suis vraiment mauvais en cette matière et donc j’ai besoin de votre aide. Je vous transmets l’énoncé :
On se propose de programmer deux algorithmes de calcul dune plus longue sous-suite croissante dans une
permutation des entiers de 1 à n:
On se donne une permutation des entiers entre 1 et n sous la forme dune suite T indexée entre 1 et n;
où T désigne le ième élément de la suite (chaque entier de 1 à n apparaît exactement une fois dans le
tableau). Une sous-suite S de (1; …; n) est dite croissante dans T (et par abus, croissante tout court) si
(i;j) appartiennent à S et i < j impliquent T < T[j]:
A titre dexemple, considérons:
T = (9; 1; 8; 6; 4; 3; 5; 2; 7)
alors la sous-suite de positions S = (2; 5; 7; 9) forme une sous-suite croissante de T (les valeurs associées
sont 1; 4; 5; 7), alors que la sous-suite de positions (1; 2; 3) ne forme pas une sous-suite croissante de T
(les valeurs associées sont 9; 1; 8).
1 2 3 4 5 6 7 8 9
T : 9 1 8 6 4 3 5 2 7
S : 2 5 7 9
Nous nous intéressons ici au problème de lextraction dune sous-suite croissante de longueur maximale à partir dune permutation des entiers de 1 à n.
Dans la suite, nous noterons lis(i) la longueur maximale dune sous-suite croissante dont lindice maximal
(la position la plus à droite) est égal à i. Dans lexemple précédent lis(0) = 0; lis(1) = 1; lis(2) = 1;
lis(3) = lis(4) = lis(5) = lis(6) = 2, lis(7) = 3; lis(8) = 2; et lis(9) = 4
Algorithme I
1.
Analyse
a) A quelle condition sur T, une sous-suite croissante maximale se terminant à la position i
peut-elle être le début dune sous-suite croissante maximale se terminant à la position j, avec j > i
? En déduire une relation simple entre la valeur de lis(i + 1) et les valeurs de lis(j) pour j<=i:
b) Déduire de la question a un algorithme prenant en entrée les valeurs lis,. . . ,lis[k]
(sous la forme dun tableau lis de longueur k) correspond à une permutation T de longueur n, avec
k<=n-1 et qui retourne un tableau lis complété avec la valeur lis[k + 1].
c) Reprendre lalgorithme de la question précédente pour obtenir un algorithme simple
qui prend en argument une permutation des entiers de 1 à n et qui calcule la longueur maximale
dune sous-suite croissante dans cette permutation.
d) Modi?er lalgorithme précédent pour quil retourne un exemple de plus longue sous-suite
croissante. Prouvez la terminaison et la correction de cet algorithme.
Programmation.
Programmer cet algorithme en java.
Voila. Donc j’ai fait quelques trucs mais je suis quasi sur que c’est faux, je voudrais que vous m’aidiez ce serait exceptionnel. Pour des pros du java cela ne doit pas être très difficile! 
Merci infiniment d’avance.
