Exercices Problème du doublon

Cours/Algorithmie/Exercices Problème du doublon

Le but de ces exercices est de résoudre le problème algorithmique suivant :

Problème algorithmique

Nom : Doppelganger
Entrée : Un tableau de $n$ entiers compris entre 1 et $n-1$
Sortie : Un entier $v$ tel qu'il existe $0\leq i\neq j < n$ avec $v = T[i] = T[j]$

Ce projet comportent deux parties : l'une algorithmique et l'autre dédiée au code et l'ordre de ses questions racontent une histoire. La suivre vous permettra, j'espère, de passer un bon moment algorithmique.

On vous demande de faire les différents exercices en respectant les consignes suivantes :

Tout algorithme doit être donné en pseudocode et être démontré (finitude et correction).
Toute fonction de code devra être testée.

I. Prélude

Commençons par montrer que notre problème est bien défini et algorithmique :

I.1 Existence

I.1.1

Démontrez que l'entier $v$ du problème Doppelganger existe toujours.

I.1.2

Démontrez que le problème Doppelganger peut admettre plusieurs solutions.

I.2 Algorithme

Montrez que l'algorithme suivant permet de résoudre le problème Doppelganger avec comme complexités :

temporelle en $\mathcal{O}(n^2)$
spatiale en $\mathcal{O}(1)$ (sans compter l'entrée)

algorithme doppelganger_naif(T: [entier]) → entier:
    pour chaque (i := entier) de [0 .. T.longueur[:
        pour chaque (j := entier) de [i+1 .. T.longueur[:
            si T[i] == T[j]:
                rendre T[i]

I.3 Complexité du problème

Le but du problème est de trouver une solution optimale au problème. Commençons par donner des bornes à celui-ci.

I.3.1

Montrer que la complexité temporelle du problème Doppelganger est en $\Omega(n)$ et en $\mathcal{O}(n^2)$.

I.3.2

Montrer que la complexité spatiale du problème Doppelganger est en $\mathcal{O}(1)$ (sans compter l'entrée).

I.4 Simulation

On vous demande de créer un projet vscode dans le dossier doppelganger. Ce projet contiendra :

un fichier doppelganger.py
un fichier test_doppelganger.py qui contiendra les tests des fonctions du fichier doppelganger.py
autant de programmes principaux que demandé dans la suite du projet.

I.4.1 (vérification)

Créez une fonction python vérifiera qu'un tableau passé en paramètre est une entrée valide du problème doppelganger Qui devra rendre une entrée du problème. Sa signature doit être :

doppelganger_valide(T: [int]) → bool

I.4.2 (entrée)

Créez une fonction python qui devra rendre une entrée du problème. Sa signature doit être :

doppelganger_entrée(n: int) → [int]

Vous ferez en sorte que la probabilité $\Pr(T[i] = x)$ soit de $1/(n-1)$ quelques soient $x$ et $i$.

Vous pourrez utiliser la méthode randrange du module random

I.4.3 (sortie)

Implémentez l'algorithme du I.2 dans une fonction de signature :

doppelganger_naif(T: [int]) → int

I.4.4 (programme principal)

Créez un programme principal dans un fichier main_I.py permettant à un utilisateur de rentrer une taille de tableau. Le programme devra :

rendre une sortie du problème Doppelganger
donner le temps mis par l'algorithme pour s'exécuter

Vous pourrez utiliser la technique présentée dans l'étude expérimentale du projet exponentiation pour mesurer le temps d'exécution de votre algorithme.

II. Une première borne

Affinons un peu la complexité de notre problème.

II.1 Trié

II.1.1

Montrer que si le tableau en entrée du problème est trié, on peut résoudre le problème Doppelganger en temps linéaire.

II.1.2

Implémentez un algorithme du II.1.2 dans une fonction de signature :

doppelganger_tri(T: [int]) → int

Qui commence par trier la liste $T$ passée en entrée puis utilise votre algorithme du II.1.1 pour résoudre le problème.

Vous pourrez lire technique de tri du tutoriel python pour savoir comment trier une liste en python.

II.1.3

Le tri utilisé par python est de complexité $\mathcal{O}(n\log(n))$. En déduire que le problème Doppelganger peut être résolu avec une complexité :

temporelle en $\mathcal{O}(n\log(n))$
spatiale en $\mathcal{O}(1)$ (sans compter l'entrée)

II.1.4

Créez un programme principal dans un fichier main_II.py permettant à un utilisateur de rentrer une taille de tableau. Le programme devra :

rendre une sortie du problème Doppelganger
comparer les temps d'exécution des deux algorithmes doppelganger_tri et doppelganger_naif

Expérimentalement, lorsque $n$ augmente, votre algorithme naif doit très souvent aller plus vite que votre algorithme qui tri au préalable votre tableau. Si cela n'arrive pas, faite une amélioration de votre algorithme naif pour que cela arrive.

II.1.5

Montrez que la probabilité que $T[0] \neq T[i]$ pour tout $i >0$ vaut $(1-1/(n-1))^n$

En utilisant le fait que $\lim_{n\to +\infty}(1-1/(n-1))^n = 1/e$ :

II.1.6

Montrez que si $n$ est grand, il y a plus de 50% de chance que $T[0]$ soit répété.

Montrez que si $n$ est grand, quelle est la probabilité qu'aucun des 5 premiers éléments de soient répétés ?

II.1.7

Montrez le expérimentalement en rendant le plus petit indice répété pour des tableaux de grande taille.

Le résultat précédent est cependant statistique. IL existe des cas où notre algorithme naïf est effectivement plus lent que l'algorithme qui tri au préalable :

II.1.8

Donnez un tableau d'entré où le programme de tri est plus rapide que l'algorithme naïf et vérifiez le expérimentalement en ajoutant ce tableau à main_II.py.

II.2

Utilisons le fait que les entiers du tableau pour lequel il faut trouver le doublon sont entre 1 et n-1, soit les indices d'un tableau de taille $n$.

II.2.1

Montrez qu'en utilisant un tableau B de $n$ booléens, on peut créer un algorithme permettant de résoudre le problème Doppelganger avec une complexité :

temporelle en $\mathcal{O}(n)$
spatiale en $\mathcal{O}(n)$ (sans compter l'entrée)

II.2.2

Implémentez l'algorithme du II.2.1 dans une fonction de signature :

doppelganger_bool(T: [int]) → int

Ajoutez au programme principal du fichier main_II.py le temps d'exécution de l'algorithme doppelganger_bool.

II.2.3

L'algorithme doppelganger_bool est-il effectivement le plus rapide ?

II.3

II.3.1

Montrer que pour le problème Doppelganger :

sa complexité temporelle du est en $\Theta(n)$
sa complexité spatiale de $\mathcal{O}(1)$ (sans compter l'entrée).

Quelle est (pour l'instant) la complexité spatiale de l'algorithme en $\mathcal{O}(n)$ et la complexité temporelle de l'algorithme de complexité spatiale $\mathcal{O}(1)$ ?

On va montrer dans la suite qu'il existe un algorithme optimal pour les deux types de complexités en même temps !

Réfléchissez-y un instant avant de continuer. Pensez-vous que ce soit possible ?

III. Interlude

Nous allons montrer que notre problème est équivalent à celui de la recherche de points fixe d'une suite ultimement périodique que nous avons déjà étudié.

Problème algorithmique

Nom : Point fixe
Entrées :
- $f: [\![ 1, n]\!] \to [\![ 1, n]\!]$
- $x \in [\![ 1, n]\!]$
Sortie : Un entier positif $x'$ tel qu'il existe $u \neq v$ pour lesquels $f^u(x) = f^{v}(x) = x'$

Commençons par rappeler ce qu'est une suite ultimement périodique :

Définition

Une suite $(a_i)_{0\leq i}$ est dite ultimement périodique si il existe $\lambda$ et $\mu$ tels que :

les valeurs $a_0$ à $a_{\lambda + \mu - 1}$ sont distinctes
$a_{ n + \lambda} = a_{ n }$ pour tout $n\geq \mu$

Puis associons en une à $f$ :

III.1.1

Montrez que si $f: [\![ 1, n]\!] \to [\![ 1, n]\!]$ et $x \in [\![ 1, n]\!]$ alors la suite $(a_i)_{0\leq i}$ définie telle que :

$a_0 = x$
$a_i = f(a_{i-1})$ pour $i>0$

est ultimement périodique.

III.1.2

Soit $f$ la fonction telle que $f(i) \coloneqq T[i]$ avec $T = [x, 1, 6, 2, 3, 4, 5]$. Donnez la suite associée lorsque $a_0 = T[0] = x$ pour $x$ allant de 1 à 6.

III.2

III.2.1

Adaptez l'algorithme du lièvre et de la tortue des suites ultimement périodiaque pour nos fonctions. Sa signature doit être lièvre_tortue(f: (entier) → entier, x: entier) → entier avec :

f la fonction
x l'entier tel que $a_0 = f(x)$

corrigé

programme lièvre_tortue(f: (entier) → entier,
                        x: entier
                       ) → entier:
    (tortue := entier) ← f(x)
    (lièvre := entier) ← f(f(x))

    tant que tortue ≠ lièvre:
        tortue ← f(tortue)
        lièvre ← f(f(lièvre))
    
    rendre tortue

Vous aurez remarqué qu'un des paramètres du programme est une fonction. Le type d'une fonction est sa signature.

III.2.2

Montrez que la complexité de l'algorithme lièvre_tortue est en $\mathcal{O}(n)$ si $f: [\![ 1, n]\!] \to [\![ 1, n]\!]$ ?

III.3

Nous allons coder cette partie. Pour cela, créez deux fichiers, point_fixe.py et test_point_fixe.py, dans lesquels vous créerez les fonctions demandées.

III.3.1

Codez l'algorithme de la question III.2.2. Cet algorithme devra être de signature :

lièvre_tortue(T: [entier]) -> entier

Le tableau en entrée T sera un tableau de taille $n+1$ et composé d'entiers entre 1 et $n$ avec :

$f(i) = T[i]$ pour tout $1\leq i \leq n$
$x = T[0]$

III.3.2

Codez l'algorithme mu de l'exercice recherche de points fixe d'une suite ultimement périodique pour nos fonctions. Cet algorithme devra être de signature :

mu(T: [entier]) -> entier

Le tableau en entrée T sera un tableau de taille $n+1$ et composé d'entiers entre 1 et $n$ avec :

$f(i) = T[i]$ pour tout $1\leq i \leq n$
$x = T[0]$

III.3.2

Dans un nouveau programme principal main_III.py, demandez à un utilisateur de rentrer une taille $n$ de tableau. Le programme devra :

afficher un tableau créé aléatoirement avec doppelganger_entrée(n + 1)
afficher la sortie de l'algorithme lièvre_tortue
affiche la période de la suite ultimement périodique associée au tableau commençant avec $a_\mu$

IV. Solution optimale

Nous allons montrer dans cette partie que l'on peut résoudre le problème Doppelganger avec un algorithme de complexité :

temporelle en $\mathcal{O}(n)$
spatiale en $\mathcal{O}(1)$ (sans compter l'entrée)

Cet algorithme sera alors optimal et en temps et en espace !

IV.1

Soit ${(a_i)}_{i\geq 0}$ une suite ultimement périodique de paramètres $\mu > 0$ et $\lambda$.

IV.1

Montrez que $f(a_{\mu - 1}) = f(a_{\mu + \lambda - 1})$ et en déduire que $a_\mu$ est une solution au problème Doppelganger pour le tableau $T$ tel que :

$T[0] = a_0$
$f(i) = T[i]$ pour tout $1\leq i \leq n$
$a_{i+1} = f(a_i)$

IV.2

IV.2

Déduire de ce qui précède un algorithme permettant de résoudre le problème Doppelganger avec un algorithme de complexité :

temporelle en $\mathcal{O}(n)$
spatiale en $\mathcal{O}(1)$ (sans compter l'entrée)

IV.3

On termine ce projet en implémentant tout ça !

IV.3.1

IV.3.1

Ajoutez dans le fichier doppelganger.py un algorithme de signature :

doppelganger_optimal(T: [entier]) -> entier

Qui résout de façon optimale en temps et en espace le problème Doppelganger.

IV.3.2

Créez un programme principal dans un fichier main_IV.py qui compare le temps mis pour résoudre le problème Doppelganger avec la version naive, triée et optimale pour une taille de tableau donnée par l'utilisateur et en utilisant 2 tableaux :

un crée par doppelganger_entrée
l'autre dans le cas le pire pour l'algorithme naif et pour le tri

Vous devez expérimentalement retrouver l'ordre de complexité attendu pour le cas le pire.

Assurez vous d'être effectivement dans le cas le pire pour le tri ! Le tri de python est en effet en $\mathcal{O}(n)$ si le tableau initial est déjà presque trié et en $\mathcal{O}(n\log(n))$ sinon.

Pour éviter les effets de bords (non utilisation du tri et du coup algorithme avec le tri plus rapide que l'algorithme optimal), utilisez un exemple du II.1.6 pour le quel le tableau n'est pas déjà trié (vous pourrez utiliser la méthode random.shuffle pour mélanger un tableau trié).