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 les réponses de l’exercice 5 du TD2.

Exercice 2. Documentation et Complexité

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

def f1(u: str):
    a = ""
    for x in u:
        a = a + x
    return a

def f2(L: list[int]):
    m = 0
    for a in L:
        m += a
    return m/len(L)

def f3(n: int):
    if n == 0:
        return [[]]
    p = []
    for u in f3(n-1):
        for i in range(n):
            p.append(u[:i] + [n] + u[i:]) 
    return p

Exercice 3. Plus proches

Proposez une implémentation et une analyse de complexité pour le problème suivant:

Plus proche
- Entrée: une liste de points du plan représentée par un couple de nombre.
- Retourne: Les deux points les plus proches

Vous pouvez utiliser cette fonction distance pour calculer la distance entre deux points:

import math
Point = tuple[float, float]

def distance(p: Point, p2: Point) -> float:
    return math.sqrt((p[0]-p2[0])**2 + (p[1]-p2[1])**2)

Pour vous aider, je vous donne la signature de la fonction:

def plus_proche(L: list[Point]) -> tuple[Point, Point]:
    ...

Exercice 4. Permutations

On considère des permutations de l’ensemble \(\{0,\ldots, n\}\), c’est-à-dire des applications bijectives de \(\{0,\ldots, n\}\) dans \(\{0, \ldots, n\}\).

On represente une permutation comme une paire entre une fonction et un entier. Par exemple:

def identite(x: int) -> int:
    return x

I_3 = (identite, 3) # Permutation identité sur {0, 1, 2}
I_4 = (identite, 4) # Permutation identité sur {0, 1, 2, 3}
I_4 = (lambda e:e, 4) # définition alternative de I4

def C3(x: int) -> int:
    if x == 0:
        return 1
    if x == 1:
        return 2
    if x == 2:
        return 0

Cycle_3 = (C3, 3) # La permutation qui associe 0 -> 1, 1->2, 2->0
Cycle_3 = (lambda e:(e+1)%3, 3) # définition alternative

Completez la fonction suivante en indiquant sa complexité.

from typing import Callable # Le type d'une fonction
def verifie(permutation: tuple[Callable, int]) -> bool:
    """ Vérifie que `permutation` est bien une permutation.
    
    Exemples:
    ========

    >>> verifie(I_4)
    True
    >>> verifie((lambda e:1, 3))
    False
    >>> verifie(Cycle_3)
    True
    """
    ...

Deux permutations sont égales si pour chaque entier plus petit que \(n\), leur image sont égale. Completez la fonction suivante, en indiquant sa complexité.

def egalite(p1: tuple[Callable, int], p2: tuple[Callable, int]) -> bool:
    """ retourne si p1 est égale à p2

    Exemples:
    =========

    >>> egalite(I_4, (lambda e:e, 4))
    True
    >>> egalite(I_4, (lambda e:e, 3))
    False
    >>> egalite(Cycle_3, (lambda e:(e+1)%3, 3))
    True
    """

Sachant que la composition de deux permutations est une permutation, completez la fonction suivante en indiquant sa complexité.

def compose(p1: tuple[Callable, int], p2: tuple[Callable, int]) -> tuple[Callable, int]:
    """ Retourne la composition de p1 et de p2 

    Exemples:
    =========

    >>> egalite(I_4, compose(I_4, I_4))
    True
    >>> Cycle_3b = compose(compose(Cycle_3, Cycle_3), Cycle_3)
    >>> egalite(Cycle_3, Cycle_3b)
    False
    >>> egalite(I_3, compose(Cycle_3, Cycle_3b))
    False
    """

Pour tout permutation \(p\), il existe un entier \(k\) tel que \(p^k\) est l’identité. Cet entier s’appelle l’ordre de \(p\). Proposez une fonction qui le calcul.
Difficile Pour \(p\) une permutation sur \(n\) et \(i<n\) un entier, l’orbite de \(i\) est l’ensemble \(\{i, p(i), p^2(i), \ldots p^{t}(i),\ldots,\}\) avec \(p^t\) la composition de \(p\) par lui même \(t\) fois.

Écrire une fonction génératrice qui étant donnée une permutation et un entier retourne un itérateur de la séquence \(p^t(i)\). Remarquez qu’il s’agit d’une séquence infinie.
En déduire une fonction qui calcul l’orbite de \(i\) par \(p\).
Une permutation \(p\) sur \(n\) est un cycle s’il existe \(i<n\) tel que pour tout \(j<n\) qui n’est pas dans l’orbite de \(i\), on a \(p(j)=j\). Autrement dit, \(p\) admet une unique orbite qui n’est pas de taille 1 (on dit alors qu’elles sont triviales).
Deux cycles sont disjoints si leur unique orbites non triviales sont disjointes.
Toute permutation peut se décomposer en une composition de cycles deux à deux disjoints. Écrire une fonction qui retourne cette décomposition.

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