DS 2 — Sous-ensembles et points fixes¶

MP2I, année 2021-2022. Devoir surveillé 2 du 13 novembre 2021. Durée totale 4h.

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles. Utilisez de préférence plusieurs couleurs. Commentez votre code dès que ce qu'il fait n'est pas évident.

Manipulation de sous-ensembles de $\range{0}{n-1}$¶

On va ici supposer définie une constante entière $n > 0$ accessible directement en C (on peut donc écrire int t[n]; pour déclarer un tableau de cette taille).

L'objectif de ce problème est de réaliser une bibliothèque de manipulation de sous-ensembles de $E = \range{0}{n-1} = \{0,1,2,\dots,n-1\}$.

Pour cela, on va les représenter sous la forme de tableaux de booléens (on suppose stdbool.h inclus). Si $S \subset E$ on le représente par le tableau t de $n$ booléens tel que $\forall i \in E, i \in S \iff \texttt{t[i] = true}$.

Ainsi, le sous-ensemble $\{1,3,5\}$ de $\range{0}{5}$ est représenté par le tableau

`i`	0	1	2	3	4	5
`t[i]`	false	true	false	true	false	true

Dans la suite du sujet on utilise le mot sous-ensemble pour désigner un tel tableau représentant un sous-ensemble de $E$.

Convention d'appel : comme les sous-ensembles seront tous représentés par des tableaux de taille $n$, il n'est pas nécessaire de passer leur taille en argument. On écrira donc juste f(bool *t) pour une fonction prenant un tableau, f(bool *t1, bool *t2) pour une en prenant deux, et ainsi de suite.

Remarque : on vous laisse ici souvent libre des arguments, des valeurs de retour, de la nomenclature de votre fonction. En contrepartie, on attend que la déclaration des fonctions soit brièvement documentée.

Q1. Écrire une fonction qui, étant donné un sous-ensemble $S$ de $E$ et un élément $x$, renvoie true si et seulement si $x \in S$.

Corrigé

bool appartient(bool *S, int x)
{
    return S[x];
}

Q2. Écrire une fonction qui renvoie le nombre d'éléments d'un sous-ensemble.

Corrigé

int cardinal(bool *S)
{
    int s = 0;

    for (int i = 0; i < n; i++)
    {
        if (S[i])
        {
            s++;
        }
    }

    return s;
}

Q3. Écrire une fonction void complementaire(bool *e, bool *ce); qui prend en entrée un sous-ensemble e et place son complémentaire dans ce.

Corrigé

void complementaire(bool *e, bool *ce)
{
    for (int i = 0; i < n; i++)
    {
        ce[i] = !e[i];
    }
}

Q4. Prouver la correction de la fonction précédente.

Corrigé

Il n'y a pas de problèmes de terminaison ici dans la mesure où on est sur une boucle for effectuant un nombre fini d'itérations.

Pour la correction, on va montrer l'invariant suivant :

\[ I(i) = \forall j \in \range{0}{i-1}, \texttt{ce}[j] = \texttt{true} \iff j \not\in \texttt{e} \]

en identifiant $\texttt{e}$ et le sous-ensemble qu'il représente.

Initialisation : comme $\range{0}{-1} = \emptyset$, on a directement $I(0)$.
Hérédité : si $I(i)$ est vérifiée en début d'itération, en fin d'itération on passe à $i+1$ et on a placé $\texttt{true}$ dans $\texttt{ce}[i]$ si et seulement si il y avait $\texttt{false}$ dans $\texttt{e}[i]$ et donc si et seulement si $i \not \in \texttt{e}$, ce qui permet de prolonger l'invariant et d'obtenir $I(i+1)$.

On a donc l'invariant $I(n)$ en sortie de boucle et ainsi $\texttt{ce}$ contient bien le complémentaire.

Remarque : ici, la vérification est triviale, et c'était plus une question portant sur la méthode.

Q5. Écrire une fonction bool disjoint(bool *e1, bool *e2); qui prend en entrée deux sous-ensembles e1 et e2, puis renvoie true si et seulement si les sous-ensembles sont disjoints : ils n'ont aucun élément en commun.

Corrigé

bool disjoint(bool *e1, bool *e2)
{
    bool dis = true;

    for (int i = 0; i < n; i++)
    {
        dis = dis && !(e1[i] && e2[i]);
    }

    return dis;
}

Q6. Écrire une fonction void union(bool *e1, bool *e2, bool *ue); qui prend en entrée deux sous-ensembles e1 et e2, puis place leur union dans ue.

Corrigé

Attention : à l'écrit cela ne pose pas de problèmes mais on ne peut pas utiliser union en C car c'est un mot clé du langage.

void reunion(bool *e1, bool *e2, bool *ue)
{
    for (int i = 0; i < n; i++)
    {
        ue[i] = e1[i] || e2[i];
    }
}

Q7. Écrire une fonction void intersection(bool *e1, bool *e2, bool *ie); qui prend en entrée deux sous-ensembles e1 et e2, puis place leur intersection dans ie.

Corrigé

void intersection(bool *e1, bool *e2, bool *ie)
{
    for (int i = 0; i < n; i++)
    {
        ie[i] = e1[i] && e2[i];
    }
}

Q8. Écrire une fonction void difference(bool *e1, bool *e2, bool *de); qui prend en entrée deux sous-ensembles e1 et e2, puis place la différence $\texttt{e1} \backslash \texttt{e2}$ dans de.

Corrigé

void difference(bool *e1, bool *e2, bool *de)
{
    for (int i = 0; i < n; i++)
    {
        de[i] = e1[i] && !e2[i];
    }
}

On note $I = \range{0}{2^{n}-1}$. Si $S \subset \range{0}{n-1}$, on pose $u(S)= \sum_{i \in S} 2^i$.

Q9. Écrire une fonction int ensemble_vers_entier(bool *e); qui prend en entrée un sous-ensemble $e$ et renvoie l'entier $u(e)$.

Corrigé

int ensemble_vers_entier(bool *e)
{
    int u = 0;
    int p = 1;

    for (int i = 0; i < n; i++)
    {
        if (e[i])
        {
            u = u + p;
        }

        p = p * 2;
    }

    return u;
}

Q10. Écrire une fonction void entier_vers_ensemble(int u, bool *e); qui prend en entrée un entier $u$ et place dans $e$ le sous-ensemble tel que $u = u(e)$.

Corrigé

void entier_vers_ensemble(int u, bool *e)
{
    for (int i = 0; i < n; i++)
    {
        e[i] = u % 2 == 1;
        u = u / 2;
    }
}

On dit qu'une suite finie $F_0, \dots, F_{p-1}$ de sous-ensembles de $E$ est une couverture de $E$ si et seulement si

\[ \forall i \in E, \exists j \in \range{0}{p-1}, i \in F_j \]

Si, de plus, les $F_j$ sont deux à deux disjoints, on dit qu'ils forment une partition de $E$.

Q11. Écrire une fonction bool couverture(int *f, int p); qui prend en entrée un tableau de $p$ entiers $f$ où pour tout $i \in \range{0}{p-1}$, $\texttt{f[i]} = u(F_i)$ avec $F_i$ un sous-ensemble de $E$, et renvoie un booléen indiquant si $(F_0,\dots,F_{p-1})$ est une couverture de $E$.

Indications : on pourra soit garder les ensembles sous forme d'entiers, soit passer par des représentations temporaires en tableau en tirant parti du fait que $n$ est constant pour les déclarer en tant que variables locales.

Corrigé

bool couverture(int *f, int p)
{
    bool couv = true;

    for (int i = 0; i < n; i++)
    {
        bool present = false;
        for (int j = 0; j < p; j++)
        {
            bool fj[n];
            entier_vers_ensemble(f[j], fj);
            if (fj[i])
            {
                present = true;
            }
        }

        couv = couv && present;
    }

    return couv;
}

Q12. Prouver la correction de la fonction précédente.

Corrigé

On va montrer la correction de la boucle intérieure ; comme elle termine directement, cela signifie de montrer qu'elle vérifie

\[ C(i) = \texttt{present} = \texttt{true} \iff \exists k \in \range{0}{p-1}, i \in S(\texttt{f}[k]) \]

où $S(k)$ est l'ensemble tel que $u(S(k)) = k$.

Pour cela, on va prouver l'invariant

\[ I(j) = \texttt{present} = \texttt{true} \iff \exists k \in \range{0}{j-1}, i \in S(\texttt{f}[k]) \]

Initialisation : encore une fois, c'est vide donc direct d'avoir $I(0)$ car on a initialisé present à false.
Hérédité : si on a $I(j)$ en début d'itération, deux cas : soit $i \in S(\texttt{f}[j])$ et on met present à true, soit $i \not \in S(\texttt{f}[j])$ et on ne change pas sa valeur ; comme par hypothèse elle valait $\texttt{true} \iff \exists k \in \range{0}{j-1}, i \in S(\texttt{f}[k])$ on a encore $\texttt{true} \iff \exists k \in \range{0}{j}, i \in S(\texttt{f}[k])$.

On a donc bien $I(j+1)$.

Ainsi $I(p) = C(i)$ est vérifié.

On montre alors facilement que $I'(i) = \texttt{couv} = \bigwedge_{l = 0}^{i-1} \exists k \in \range{0}{p-1}, l \in S(\texttt{f}[k])$ est un invariant car vu ce qu'on vient de montrer, le corps de boucle devient $\texttt{couv} = \texttt{couv} \wedge \exists k \in \range{0}{p-1}, i \in S(\texttt{f}[k])$.

On a donc $I'(n) = \texttt{couv} = \bigwedge_{l = 0}^{n-1} \exists k \in \range{0}{p-1}, l \in S(\texttt{f}[k])$ ce qui est effectivement la correction.

Q13. Écrire une fonction bool partition(int *f, int p); qui prend en entrée un tableau de $p$ entiers $f$ où pour tout $i \in \range{0}{p-1}$, $\texttt{f[i]} = u(F_i)$ avec $F_i$ un sous-ensemble de $E$, et renvoie un booléen indiquant si $(F_0,\dots,F_{p-1})$ est une partition de $E$.

Corrigé

bool partition(int *f, int p)
{
    bool couv = true;

    for (int i = 0; i < n; i++)
    {
        int compte = 0;
        for (int j = 0; j < p; j++)
        {
            bool fj[n];
            entier_vers_ensemble(f[j], fj);
            if (fj[i])
            {
                compte++;
            }
        }

        couv = couv && compte == 1;
    }

    return couv;
}

Q14. Prouver la correction de la fonction précédente.

Corrigé

Il suffit de reprendre rapidement la preuve précédente en remplaçant l'invariant de la boucle intérieure par

\[ I(j) = \texttt{compte} = \left| \enscomp{k \in \range{0}{j-1}}{i \in S(\texttt{f}[k])} \right| \]

ce qui permet d'obtenir la correction de la boucle intérieure

\[ C(i) = \texttt{compte} = \left| \enscomp{k \in \range{0}{p-1}}{i \in S(\texttt{f}[k])} \right| \]

et donc $\texttt{compte} = 1 \iff i$ appartient à un unique sous-ensemble.

On conclut par le même invariant que précédemment, vu que c'est à nouveau une conjonction.

Points fixes de fonctions à domaine fini¶

Cette partie semble reprise, et transposée en C, d'un sujet de concours (style X-ENS, informatique commune) ; la source ne l'indique pas.

Dans ce problème, on s'intéresse aux points fixes des fonctions $f: E \to E$, où $E$ est un ensemble fini. Le calcul effectif et efficace des points fixes de telles fonctions est un problème récurrent en informatique (transformation d'automates, vérification automatique de programmes, algorithmique des graphes, etc.), et admet différentes approches selon la structure de $E$ et les propriétés de $f$.

On suppose par la suite un entier strictement positif $n>0$ fixé et accessible comme une constante entière en C (on peut donc écrire int t[n]; pour déclarer un tableau de cette taille) de même nom (dans la suite du sujet, on confondra l'entier $n$ et la variable informatique n), et on pose $E_n = \{0, \dots, n-1 \}$. On représente une fonction $f : E_n \to E_n$ par un tableau t de taille $n$, autrement dit $f(x) = \texttt{t[x]}$ pour tout $x=0, \dots, n-1$. Ainsi la fonction $f_0$ qui à $x \in E_{10}$ associe $2x+1 \, \mathrm{modulo} \, 10$ est-elle représentée par le tableau t suivant :

`i`	0	1	2	3	4	5	6	7	8	9
`t[i]`	1	3	5	7	9	1	3	5	7	9

Le temps de calcul d'une fonction f de paramètres $p_1, \dots, p_k$ est défini comme le nombre d'opérations (accès en lecture ou écritures à une case d'un tableau ou à une variable, appel à une des primitives données dans l'énoncé) exécutées par f pour ces paramètres ; on note $T(\texttt{f},n)$ le temps de calcul maximal pris sur tous les paramètres possibles pour $n$ fixé. On dit que f s'exécute en temps linéaire s'il existe des réels $\alpha, \beta > 0$ et un entier $N \geqslant 0$ tels que $\alpha n \leqslant T(\texttt{f},n) \leqslant \beta n$ pour tout $n \geqslant N$. De même, on dit que f s'exécute en temps logarithmique s'il existe des réels $\alpha, \beta >0$ et un entier $N \geqslant 0$ tels que $\alpha \log n \leqslant T(\texttt{f}, n ) \leqslant \beta \log n$ pour tout $n \geqslant N$.

Recherche de point fixe : cas général¶

On rappelle que $x$ est un point fixe de la fonction $f$ si et seulement si $f(x)=x$.

Q15. Écrire une fonction bool admet_point_fixe(int *t) qui prend en argument un tableau t de taille $n$ et renvoie true si la fonction $f : E_n \to E_n$ représentée par t admet un point fixe, false sinon. Par exemple, admet_point_fixe devra renvoyer true pour le tableau donné en introduction, puisque $9$ est un point fixe de la fonction $f_0$ qui à $x$ associe $2x+1 \, \mathrm{modulo} \, 10$.

Corrigé

bool admet_point_fixe(int *t)
{
    for (int i = 0; i < n; i++)
    {
        if (t[i] == i)
        {
            return true;
        }
    }
    return false;
}

Q16. Écrire une fonction int nb_points_fixes(int *t) qui prend en argument un tableau t de taille $n$ et renvoie le nombre de points fixes de la fonction $f : E_n \to E_n$ représentée par t. Par exemple, nb_points_fixes devra renvoyer 1 pour le tableau donné en introduction, puisque $9$ est le seul point fixe de $f_0$.

Corrigé

int nb_points_fixes(int *t)
{
    int nb = 0;

    for (int i = 0; i < n; i++)
    {
        if (t[i] == i)
        {
            nb = nb + 1;
        }
    }

    return nb;
}

On note $f^k$ l'itérée $k$-ième de $f$, autrement dit

\[ f^k : \begin{aligned}[t] E_n &\to E_n \\ x &\mapsto \underbrace{f(f(\dots f}_{k \text{ fois }} (x )) \dots)\end{aligned} \]

Q17. Écrire une fonction int itere(int *t, int x, int k) qui prend en premier argument un tableau t de taille $n$ représentant une fonction $f : E_n \to E_n$, en deuxième et troisième arguments des entiers $x,k$ de $E_n$ et renvoie $f^k(x)$.

Corrigé

int itere(int *t, int x, int k)
{
    for (int i = 0; i < k; i++)
    {
        x = t[x];
    }

    return x;
}

Q18. Écrire une fonction int nb_points_fixes_iteres(int *t, int k) qui prend en premier argument un tableau t de taille $n$ représentant une fonction $f : E_n \to E_n$, en deuxième argument un entier $k \geqslant 0$ et renvoie le nombre de points fixes de $f^k$.

Corrigé

int nb_points_fixes_iteres(int *t, int k)
{
    int nb = 0;

    for (int i = 0; i < n; i++)
    {
        if (itere(t, i, k) == i)
        {
            nb = nb + 1;
        }
    }

    return nb;
}

Un élément $z \in E_n$ est dit attracteur principal de $f : E_n \to E_n$ si et seulement si $z$ est un point fixe de $f$, et pour tout $x \in E_n$, il existe un entier $k \geqslant 0$ tel que $f^k(x) = z$.

Afin d'illustrer cette notion, on pourra vérifier que la fonction $f_1$ représentée par le tableau ci-dessous admet $2$ comme attracteur principal.

`i`	0	1	2	3	4	5	6
`t[i]`	5	5	2	2	0	2	2

En revanche, on notera que la fonction $f_0$ donnée en introduction n'admet pas d'attracteur principal puisque $f_0^k(0) \neq 9$ quel que soit l'entier $k \geqslant 0$.

Q19. Écrire une fonction bool admet_attracteur_principal(int *t) qui prend en argument un tableau t de taille $n$ et renvoie true si et seulement si la fonction $f : E_n \to E_n$ représentée par t admet un attracteur principal, false sinon. On ne requiert pas ici une solution efficace.

Corrigé

bool admet_attracteur_principal(int *t)
{
    for (int z = 0; z < n; z++)
    {
        bool attracteur = true;

        for (int x = 0; x < n; x++)
        {
            /* f^0(x), f^1(x), ..., f^n(x) prennent n+1 valeurs
             * dans 0, 1, ..., n-1 qui compte n valeurs distinctes
             * donc on a deux valeurs égales. Or, s'il existe
             * k<l tels que f^k(x) = f^l(x) et qu'on n'a pas vu
             * z, on va rester bloqué sur les mêmes valeurs à partir
             * de k, donc on ne verra jamais z. Si au contraire, z apparait
             * alors on reste sur z car c'est un point fixe.
             * Dans tous les cas, soit z n'est pas accessible, soit f^n(x) = z
             */
            attracteur = attracteur && itere(t, x, n) == z;
        }

        if (attracteur)
        {
            return true;
        }
    }

    return false;
}

On suppose aux questions 20 et 21 que $f$ admet un attracteur principal. Le temps de convergence de $f$ en $x \in E_n$ est le plus petit entier $k \geqslant 0$ tel que $f^k(x)$ soit un point fixe de $f$. Pour la fonction $f_1$ ci-dessus, le temps de convergence en $4$ est $3$. En effet, $f_1(4) = 0, f_1^2(4) = 5, f_1^3(4) = 2$, et $2$ est un point fixe de $f_1$. On note $\texttt{tc}(f,x)$ le temps de convergence de $f$ en $x$.

Q20. Écrire une fonction int temps_de_convergence(int *t, int x) qui prend en premier argument un tableau t de taille $n$ représentant une fonction $f : E_n \to E_n$ qui admet un attracteur principal, en deuxième argument un entier $x$ de $E_n$, et renvoie le temps de convergence de $f$ en $x$. On pourra admettre que $\texttt{tc}(f,x)$ vaut $0$ si $x$ est un point fixe de $f$, et $1 + \texttt{tc}(f,f(x))$ si $x$ n'est pas un point fixe de $f$.

Corrigé

int temps_de_convergence(int *t, int x)
{
    if (t[x] == x)
        return 0;
    return 1 + temps_de_convergence(t, t[x]);
}

Q21. Écrire une fonction temps_de_convergence_max(t) qui prend en argument un tableau t de taille $n$ représentant une fonction $f : E_n \to E_n$ qui admet un attracteur principal et renvoie $\max_{i = 0\dots n-1} \texttt{tc}(f,i)$. On impose un temps de calcul linéaire en la taille $n$ du tableau (une fonction ne respectant pas cette condition ne rapportera pas de point !). À titre d'indication, on pourra au besoin créer des tableaux intermédiaires en tirant parti du fait que $n$ est une constante.

On ne demande pas de démonstration du fait que le temps de calcul de la solution proposée est linéaire, mais il est impératif d'expliquer clairement le fonctionnement de votre fonction.

Corrigé

/* Version naive et quadratique */
int temps_de_convergence_max_n2(int *t)
{
    int m = 0; // atteint pour l'attracteur

    for (int x = 0; x < n; x++)
    {
        int tx = temps_de_convergence(t, x);
        if (tx > m)
        {
            m = tx;
        }
    }

    return m;
}

/* Version linéaire en calculant rapidement les temps
 * de convergence le long des valeurs prises par les itérés de f
 */
int temps_de_convergence_max(int *t)
{
    int m = 0; // max atteint pour l'attracteur
    int temps[n]; // va contenir soit le temps précalculé, soit -1

    for (int x = 0; x < n; x++)
    {
        if (t[x] == x)
        {
            temps[x] = 0; // c'est un point fixe
        }
        else
        {
            temps[x] = -1;
        }
    }

    for (int x = 0; x < n; x++)
    {
        int iteres[n]; // les itérés en partant de x
        int k = 0;
        int u = x;
        iteres[k] = u;
        while (temps[u] < 0)
        {
            u = t[u];
            k = k + 1;
            iteres[k] = u;
        }
        // on est tombe sur un point fixe
        // donc sur l'attracteur principal
        for (int r = k-1; r >= 0; r--)
        {
            temps[iteres[r]] = 1 + temps[iteres[r+1]];
        }

        if (temps[iteres[0]] > m) // c'est le plus grand temps de tous
        {
            m = temps[iteres[0]];
        }
    }

    return m;
}

Recherche efficace de points fixes¶

Toute fonction point_fixe(t) retournant un point fixe d'une fonction arbitraire est de complexité au mieux linéaire en $n$. On s'intéresse maintenant à des améliorations possibles de cette complexité lorsque la fonction considérée possède certaines propriétés spécifiques. Nous examinons deux cas.

Premier cas¶

Le premier cas que nous considérons est celui d'une fonction croissante de $E_n$ dans $E_n$. On rappelle qu'une fonction $f : E_n \to E_n$ est croissante si et seulement si pour tous $x,y \in E_n$ tels que $x \leqslant y, f(x) \leqslant f(y)$.

On admet qu'une fonction croissante de $E_n$ dans $E_n$ admet toujours un point fixe.

À titre d'exemple, la fonction dont le tableau et le graphe sont donnés ci-dessous est croissante. Elle a deux points fixes, à savoir les entiers 5 et 7.

Graphe de la fonction croissante du tableau ; ses points fixes 5 et 7 sont sur la diagonale.

`i`	0	1	2	3	4	5	6	7	8	9
`t[i]`	1	3	3	5	5	5	7	7	7	8

Q22. Écrire une fonction bool est_croissante(int *t) qui prend en argument un tableau t de taille $n$ et renvoie true si la fonction représentée par t est croissante, et false sinon. On impose un temps de calcul linéaire en la taille $n$ du tableau. On ne demande pas de démonstration du fait que le temps de calcul de la solution proposée est linéaire.

Corrigé

bool est_croissante(int *t)
{
    for (int i = 0; i < n-1; i++)
    {
        if (t[i] > t[i+1])
        {
            return false;
        }
    }

    return true;
}

Q23. Écrire une fonction int point_fixe(int *t) qui prend en argument un tableau t de taille $n$ représentant une fonction croissante $f : E_n \to E_n$, et retourne un entier $x \in E_n$ tel que $f(x) = x$. On impose un temps de calcul logarithmique en la taille $n$ du tableau. On ne demande pas ici de démonstration du fait que le temps de calcul de la solution proposée est logarithmique, ceci étant le sujet de la question suivante.

Corrigé

Recherche dichotomique en conservant l'invariant $\texttt{t[i]} \geqslant i$ et $\texttt{t[j]} \leqslant j$ (vrai au départ car les valeurs sont dans $E_n$). En sortie de boucle, $j = i+1$ (ou $i = j$ si $n = 1$) : si $\texttt{t[i]} > i$ alors $\texttt{t[i]} \geqslant j$ donc, par croissance, $j \geqslant \texttt{t[j]} \geqslant \texttt{t[i]} \geqslant j$ et $j$ est un point fixe.

// simple recherche dichotomique
int point_fixe(int *t)
{
    int i = 0;
    int j = n-1;
    while (j - i > 1)
    {
        int m = (i+j)/2;
        if (t[m] == m)
        {
            return m;
        }
        else if (t[m] < m)
        {
            j = m;
        }
        else
        {
            i = m;
        }
    }

    // ici j = i+1 (ou i = j si n = 1), t[i] >= i et t[j] <= j
    if (t[i] == i)
    {
        return i;
    }
    return j;
}

Q24. Démontrer que la fonction de la question 23 termine.

Corrigé

Voir cours, $j-i$ est un variant de boucle.

Deuxième cas¶

On peut généraliser la notion de fonction croissante comme suit. On rappelle qu'une relation binaire $\preccurlyeq$ sur un ensemble $E$ est une relation d'ordre si et seulement si elle est réflexive ($x \preccurlyeq x$ pour tout $x \in E$), anti-symétrique (pour tous $x,y \in E$, si $x \preccurlyeq y$ et $y \preccurlyeq x$, alors $x=y$), et transitive (pour tous $x,y,z \in E$, si $x \preccurlyeq y$ et $y \preccurlyeq z$ alors $x \preccurlyeq z$). Soit $\preccurlyeq$ une relation d'ordre sur $E$. Une fonction $f : E \to E$ est croissante au sens de $\preccurlyeq$ si et seulement si pour tous $x,y \in E$, $x \preccurlyeq y$ implique $f(x) \preccurlyeq f(y)$.

Ceci généralise la notion de fonction croissante de $E_n$ dans $E_n$, que l'on retrouve en prenant $E=E_n$ et $\preccurlyeq$ la relation d'ordre $\leqslant$. On s'intéresse dorénavant à d'autres relations d'ordre sur $E_n$.

On dit qu'un élément $m$ de $E$ est un plus petit élément de $E$ au sens de $\preccurlyeq$ si et seulement si, pour tout $x \in E$, $m \preccurlyeq x$. On admet que pour tout ensemble fini $E$, muni d'une relation d'ordre $\preccurlyeq$ et qui admet un plus petit élément $m$ au sens de $\preccurlyeq$, pour toute fonction croissante $f : E \to E$ au sens de $\preccurlyeq$, il existe un entier $k \geqslant 0$ tel que $f^k(m)$ est un point fixe de $f$ dans $E$.

Q25. Soit $E$ un ensemble fini quelconque muni d'une relation d'ordre $\preccurlyeq$ et admettant un plus petit élément $m$ au sens de $\preccurlyeq$. Soit $f : E \to E$ une fonction croissante au sens de $\preccurlyeq$, et soit $k \geqslant 0$ un entier tel que $f^k(m)$ soit un point fixe de $f$ dans $E$. Démontrer que $f^k(m)$ est en fait le plus petit point fixe de $f$ au sens de $\preccurlyeq$, autrement dit que pour tout autre point fixe $x$ de $f$ dans $E$, on a $f^k(m) \preccurlyeq x$.

Corrigé

Comme $f$ est croissante, alors $f^k$ est croissante, donc $m \preccurlyeq x \Rightarrow f^k(m) \preccurlyeq f^k(x) = x$.

Nous nous intéressons maintenant à un choix particulier d'ordre $\preccurlyeq$, appelé ordre de divisibilité et noté $|$. Précisément, on note $a | b$ la relation d'ordre « $a$ divise $b$ » sur les entiers positifs, vraie si et seulement s'il existe un entier $c \geqslant 0$ tel que $ca = b$. Ainsi l'ensemble $E_{10}$ ordonné par divisibilité peut se représenter graphiquement comme suit :

L'ensemble E_10 ordonné par divisibilité. — L'ensemble $E_{10}$ ordonné par divisibilité.

D'après la définition donnée précédemment, une fonction $f : E_n \to E_n$ croissante au sens de l'ordre de divisibilité est une fonction telle que pour tout $x, y$ dans $E_n$, si $x | y$ alors $f(x) | f(y)$. Par exemple la fonction représentée par le tableau ci-dessous est croissante au sens de l'ordre de divisibilité.

`i`	0	1	2	3	4	5	6	7	8	9
`t[i]`	0	2	4	6	4	8	0	2	0	6

On remarque que, par la question 25, toute fonction de $E_n$ dans $E_n$ croissante au sens de l'ordre de divisibilité a un plus petit point fixe au sens de l'ordre de divisibilité.

On rappelle que le pgcd de deux entiers $x \geqslant 1$ et $y \geqslant 1$ est le plus grand entier non nul qui divise $x$ et $y$. On étend cette définition à des entiers naturels quelconques, en convenant de définir le pgcd d'un entier $x \geqslant 0$ et de $0$ comme valant $x$.

Q26. Soit $f$ une fonction de $E_n$ dans $E_n$, croissante au sens de l'ordre de divisibilité, et notons $x_1, \dots, x_m$ les points fixes de $f$ dans $E_n$. Montrer que le plus petit point fixe de $f$ au sens de l'ordre de divisibilité est exactement le pgcd de $x_1, \dots, x_m$.

Corrigé

Si $p$ est le pgcd des $x_i$ et que $y$ est le plus petit point fixe, on a $p | y$ car $y$ est l'un des $x_i$. On va montrer que $y | p$.

Pour cela, on remarque que $p \in E_n$ et que pour $i \in \range{1}{m}$, $p | x_i$ et par croissance de $f$, $f(p) | f(x_i) = x_i$. Donc $f(p)$ divise leur pgcd : $f(p) | p$. Par croissance de $f$, on en déduit par récurrence que $f^{k+1}(p) | f^k(p)$ pour tout $k$ : la suite $(f^k(p))_k$ est décroissante pour la divisibilité. Comme $E_n$ est fini, elle est nécessairement stationnaire (tant qu'elle n'est pas stationnaire, elle décroît strictement et ne peut donc pas repasser par une même valeur), donc il existe $k$ tel que $f^k(p)$ soit un point fixe de $f$. Comme $y$ est le plus petit point fixe, on a $y | f^k(p)$ et $f^k(p) | p$, donc $y | p$ par transitivité.

Q27. Écrire une fonction int pgcd_points_fixes(int *t) qui prend en argument un tableau t de taille $n$ représentant une fonction de $E_n$ dans $E_n$, croissante au sens de la divisibilité, et renvoie le pgcd de ses points fixes. On impose un temps de calcul logarithmique en la taille $n$ du tableau. On ne demande pas ici de démonstration du fait que le temps de calcul de la solution proposée est logarithmique, ceci étant le sujet de la question qui suit.

Corrigé

$1$ est le plus petit élément de $E_n$ pour la divisibilité (on suppose ici $n \geqslant 2$), donc d'après les questions 25 et 26 :

int pgcd_points_fixes(int *t)
{
    // il suffit de trouver le point fixe accessible
    // depuis 1
    int x = 1;

    while (t[x] != x)
    {
        x = t[x];
    }

    return x;
}

Q28. Justifier que la fonction de la question 27 a un temps de calcul logarithmique en la taille $n$ du tableau.

Corrigé

Quand on boucle, comme $f^k(1) | f^{k+1}(1)$ et que ces deux nombres sont différents : soit $f^{k+1}(1) \ge 2 f^{k}(1)$ (multiple propre), soit $f^{k+1}(1) = 0$ (cas trivial qu'on peut ignorer pour le moment).

Comme on double $f^{k}(1)$ à chaque étape et que les valeurs sont $\le n$, on en effectue au plus $\log n$.

Dans le cas où on obtient $0$, on s'arrête à l'itération suivante.

DS 2 — Sous-ensembles et points fixes¶

Manipulation de sous-ensembles de \(\range{0}{n-1}\)¶

Points fixes de fonctions à domaine fini¶

Recherche de point fixe : cas général¶

Recherche efficace de points fixes¶

Premier cas¶

Deuxième cas¶