Liste injective

[left_shift]

Imagine que tab[j] est un drapeau qui est :
- levé (tab[j] = True) lorsque l'élément j a déjà été vu dans la liste l ;
- baissé (tab[j] = False) lorsque l'élément j n'a pas encore été vu dans la liste l
puis passe en revue les différents éléments de la liste l : l[0], l[1], l[2], ...

Si, lorsque tu examine l, le drapeau tab[l] est déjà levé, c'est que l'élément l a déjà été vu une fois auparavant. Dans ce cas la liste n'est pas injective et on peut stopper l'énumération en retournant False.
Dans le cas contraire, il faut lever le drapeau tab[l] et poursuivre l'énumération en examinant l'élément l[i+1]. Si on peut poursuivre ainsi jusqu'à avoir examiné tous les éléments de l, c'est que cette liste est injective.

[np*]

Essaie d'obtenir un énoncé plus clair même sans aucune indication d'aide, si tu veux arriver à faire quelque chose...
Là, je l'ai encore relu ce matin, c'est imbitable, on ne comprend ni l'objectif, ni le rapport avec les indications données.

L'énoncé n'est en effet pas très pédagogique et on comprend qu'il puisse poser problème. Voici mon interprétation des objectifs de cette séquence d'exercices avec un énoncé qui me semble plus clair et plus progressif :

On cherche dans cet exercice à savoir si une liste est injective. Une liste est injective si elle ne contient pas deux fois ou plus le même élément, autrement dit elle ne contient aucun doublon.

Partie A

Une première idée est de comparer les éléments de la liste deux à deux. Si l'on en trouve deux égaux, la liste contient un doublon et l'on peut arrêter la recherche. On pourra par exemple comparer le premier élément avec tous les suivants, puis le deuxième avec tous les suivants et ainsi de suite.

Question 1) Que donne cette idée sur la liste [1, 2, 3, 2, 4] ?

Question 2) Écrire le pseudo-code de cet algorithme et le vérifier sur la liste précédente

Question 3) Écrire en Python une fonction est_injective(liste) qui renvoie True si la liste est injective et False sinon.

Question 4) Combien de comparaisons entre deux éléments sont effectuées par votre programme sur la liste [1, 2, 3, 2, 4] ? Dans le pire des cas, combien de comparaisons peuvent être effectuées sur une liste de taille n et donner une telle liste ? Quelle est donc la complexité de cette méthode ?

Partie B

La complexité de la méthode précédente n'est pas satisfaisante. On va donner ici une solution de complexité linéaire en la taille de la liste. L'idée est de se souvenir des éléments de la liste que l'on a déjà rencontrés auparavant. On peut par exemple créer un tableau deja_vu dont la case i vaut True si l'on a déjà rencontré un élément de valeur i et False sinon. Lorsque l'on découvre un nouvel élément de valeur i deux cas peuvent se présenter : (a) deja_vu est vrai, dans ce cas on peut arrêter la recherche et la liste n'est pas injective; (b) deja_vu n'est pas vrai, dans ce cas on met deja_vu à jour et on continu.

Question 1) Quelle doit être la taille du tableau deja_vu?

Question 2) Écrire en Python une fonction maximum(liste) qui renvoie le maximum d'une liste et la tester.

Question 3) Écrire en Python une fonction initialise(taille, valeur) qui créée un tableau (une liste en Python) de taille taille avec tous les éléments initialisés à valeur.

Question 4) Écrire le pseudo-code d'un algorithme mettant en place l'idée exposée dans cette partie. Le vérifier sur les listes [1, 2, 3, 2, 4] et [1, 2, 3, 5, 4].

Question 5) Écrire en Python une fonction est_injective_rapide(liste) qui implémente ce pseudo-code.

Question 6) Quelle est la complexité de cette méthode (rem: ne pas oublier la complexité des fonctions maximum et initialise) ?

[fakbill]

Partie C (à laquelle qlqs % des taupins seulement vont répondre):
Que penser de ce trade off complexité temps / complexité mémoire?