Ce TD est noté.

• Il est réalisé en durée limité: 2h
• L’utilisation des notes de cours est autorisées, ainsi que vos fichiers de TP disponibles sur votre machine.
• Internet n’est pas autorisé sauf le site de la documentation Python et les notes de cours.
• En cas de blocage, vous pouvez demander de l’aide.
• Vous devez rendre sur Moodle.
• Si vous avez été absent au dernier TP, vous avez un malus de 2pt sur votre note finale.

Exercice 1. Donnez vos réponses à l’exercice 5 du TD 3.

Exercice 2. Documentation et Complexité

Proposez un nom et une documentation (incluant des doctests) et une analyse de complexité pour les fonctions suivantes:

def f1(L: list[int]) -> int:
    n = len(L)
    for x in L:
        c = 0
        t = 0
        for y in L:
            if y < x:
                c += 1
            if y == x:
                t += 1
        if c<= n/2 and n/2 <= c + t:
            return x

def f2(L: list | int) -> int:
    if isinstance(L, int):
        return 1
    return sum(map(f2, L)) + 1

def f3(n: int) -> list[tuple[int]]:
    if n == 1:
        return [(1,)]
    L = [(n,)]
    for i in range(1, n):
        for x in f3(i):
            if n-i >= max(x):
                L.append(x + (n-i,))
    return L

Exercice 3. Algorithmique: sous-facteurs commun maximaux

Dans une chaine de caractères \(u\) (un type str en Python) un sous-facteur \(v\) est une chaine qui apparait dans \(u\) de manière contigüe. Par exemple dans \(ABCAAC\), \(BCA\) est un sous-facteur et \(BAC\) n’en n’est pas un.

Pour une liste de chaines de caractères, un mot \(u\) est un sous-facteur commun si \(u\) est un sous-facteur de toutes les chaines de la listes.

Par exemple, dans ["ABCAA", "DBCAEAB", "choucroute BCA garnie AB"]{python} nous avons \(BCA\) qui est un sous-facteur commun car elle apparait dans chaque chaine de la liste.

1. Écrire une implementation de la fonction sous_facteur_commun qui retourne la liste des sous facteur commun d’une liste de chaines de caractères. On propose la signature suivante:

def sous_facteur_commun(L: list[str]) -> list[str]:
    """
    Exemple:
    ========

    >>> sous_facteur_commun(["ABCAA", "DBCAEAB", "choucroute BCA garnieAB"])
    ["BCA", "AB", "CA", "BC", "A", "B", "C", ""]
    """

2. Faire une analyse rigoureuse de la complexité de votre implémentation.

Un sous-facteur commun est par ailleurs maximal s’il n’est pas un sous-facteur d’un autre sous-facteur commun.

Par exemple, dans l’exemple précédant, \(BCA\) est maximal mais pas \(BC\) car \(BC\) est une sous facteur de \(BCA\).

3. Écrire une fonction sous_facteur_commun_maximal.

def sous_facteur_commun_maximal(L: list[str]) -> list[str]:
    """
    Exemple:
    ========

    >>> sous_facteur_commun_maximal(["ABCAA", "DBCAEAB", "choucroute BCA garnieAB"])
    ["BCA", "AB"]
    """

4. Faire une analyse rigoureuse de la complexité de votre implémentation.

Exercice 4. Ensemble de fonctions

Dans cet exercice on s’intéresse aux fonctions de \(\{0,\ldots, n\} \to \{0, \ldots, n\}\) pour \(n\) fixé. \(T_n\) l’ensemble de ces fonctions, pour tout \(n>0\).

1. Dans cette question, on va implementer une fonction qui prends en entrée une liste d’entier de taille \(n\) et retourne une implémentation Python d’une fonction de taille \(n\). La liste [1, 0, 0]{python} va par exemple représenter la fonction \(0\mapsto 1\), \(1\mapsto 0\) et \(2\mapsto 0\).

def build(L: list[int]):
    """
    Exemple:
    ========
    >>> f = build([1, 0, 0])
    >>> f(0)
    1
    >>> f(1)
    0
    >>> f(2)
    0
    """

2. Écrire une fonction Python compose qui prends deux listes d’entiers de même taille \(n\), vérifie que ce sont bien des fonctions de \(T_n\) et retourne la liste d’entiers de la composition de ces fonctions.

def compose(f, g):
    """
    Exemple:
    ========

    >>> d = compose(build([0, 2, 1]), build([1, 1, 2]))
    >>> [d(0), d(1), d(2)]
    [1, 2, 1]
    >>> k = compose(build([0, 2, 1]), build([2, 1, 0]))
    >>> [k(0), k(1), k(2)]
    [2, 0, 1]
    """

4. Deux fonctions de \(f,g\) de \(T_n\) sont des pseudo-inverse si \(f \circ g\circ f = f\). Écrire une fonction pseudo_inverse qui prends en entrée deux fonctions et \(n\) et vérifie que ce sont des pseudo-inverses.

5. Orbite. Étant donné un élement \(x\) de \(\{0, \ldots, n\}\), et \(f\in T_n\), on appel orbite de \(x\) par rapport à \(f\) l’ensemble \(\{x, f(x), f(f(x)), \cdots \}\). Écrire la fonction orbite{python}

def orbite(f, x) -> set[int]:
    """
    Exemple:
    ========

    >>> orbite(build([4, 0, 2, 1, 2]), 0)
    { 0, 2, 4 }
    """

Compiled the: mer. 16 avril 2025 10:20:51 CEST