Une version naïve
Q1. Validation : écrire une fonction qui prend une liste L d’entiers en entrée et qui renvoie True si les termes de la liste forment
une suite strictement croissante et False sinon.
Q2. Quelle est la complexité de cette fonction (par rapport à la taille de la liste L) ?
Q3. Création des sous-listes : on veut une fonction qui, à partir d’une liste d’entiers L, renvoie la liste de toutes les sous-listes de L.
Q4. Combien de sous-listes renvoie cette fonction ?
Q5. Détermination d’une plus longue suite strictement croissante : En utilisant les 2 fonctions précédentes, Construit une fonction PLSSC1 qui, à partir d’une liste L, renvoie la plus longue suite strictement croissante
Q6. Quels sont les défauts de cette méthode ?
Une version par programmation dynamique
Q7. On se donne une liste L strictement croissante d’entiers et un entier k. Comment savoir si la liste L+[k] est strictement croissante ? Q8. Écrire une fonction PLSSC2(L) qui prend une liste d’entiers L en argument et qui renvoie la longueur de la plus longue suite strictement croissante dans cette liste Q9. Comment modifier cette fonction pour qu’elle retourne à la fois la longueur de la plus longue suite strictement croissante ainsi que toutes les suites strictement croissantes de cette longueur ?Amélioration de la version précédente
Q10. Écrire une fonction PLSSC3(L) qui détermine la longueur de la plus longue sous suite strictement croissante, ainsi que l’une de ses suites, en suivant l’algorithme précédent
Q11. Quelle est la complexité de cette fonction (en fonction du nombre n d’éléments dans L) ?
Correction
Une version naïve
Q1.
Q2. Une seule boucle avec un nombre d’opérations en temps constant à l’intérieur : la complexité est en O(n) (où n est la taille de la liste).
Q3.
<b>Q4.</b> On a exactement 2n sous-listes créées (elles sont en bijection avec {0, 1}n).
- Création et stockage de toutes les sous-listes (notamment celles qui ne sont pas croissantes)
- Une complexité exponentielle
Une version par programmation dynamique
Q7. Il suffit de comparer le dernier élément de L avec k (et regarder si k est strictement supérieur). Q8. Q9. Il suffit de rajouter, avant le return :Amélioration de la version précédente
Q10.
Q11.
On a deux boucles imbriquées. La première comporte $n − 1$ passages. À l’intérieur, il y a plusieurs opérations en temps constants et une boucle qui porte sur une liste (plus_longue_fin) de taille $k \le n$. Les calculs à l’intérieur de cette seconde boucle sont en temps constant. On a donc une complexité en $O(n^2)$
