• 1h45 sans documents et sans internet.
• Vous pouvez consulter les codes présents sur votre machine.
• Vous devez rendre un unique fichier Python.
• Les questions de cours doivent être écrites sous forme de commentaires dans le fichier source.
• Chaque fonction écrite doit contenir une description, des doctests et une analyse de complexité sinon elle ne sera pas corrigée.

Partie 1. Réécriture de code simple

1. Proposez une implémentation impérative de la fonction suivante.

def f1(L):
    if not L:
        return ()
    return (L[0], f1(L[1:])

• Ajoutez une documentation contenant une analyse de complexité.

2. Proposez une implémentation fonctionnelle de la fonction suivante.

def f2(L):
    i = 0
    acc = 0
    for x in L:
        if i % 2 == 0:
            acc += x
        i += 1
    return acc

• Ajoutez une documentation contenant une analyse de complexité.

3. Proposez une description et analyse de complexité de la fonction suivante.

def f3(L):
    n = len(L)
    if n == 1:
        return tuple(L)
    if n == 2:
        return (min(L[0], L[1]), max(L[0], L[1]))
    K = f3(L[:n//2])
    T = f3(L[n//2:])
    result = []
    for i in range(n):
        if K[0] < T[0]:
            result.append(K.pop(0))
        else:
            result.append(T.pop(0))
    return result

Partie 2. Exercice de programmation

Écrire une fonction efface qui prend en argument deux chaines de caractères et efface de la première les lettres qui apparaissent dans la seconde.

Par exemple efface('abacacab', 'b') retourne ‘aacaca. De mêmeefface(’abacacab’, ‘abaac’)` retourne la chaine vide. N’oubliez pas d’indiquer la complexité de votre implémentation et de faire tests (qui marchent!).

Partie 3. Polynômes entiers

Dans la suite, on va représenter des polynômes entiers de manière récursive:

• Un nombre entier est un polynôme
• La chaine de caractère “Y” est un polynôme
• Si P et Q sont des polynôme, alors (P, 'x', Q) et (P, '+', Q) sont des polynômes

Par exemple:

(3, 'x', ('Y', 'x', 'Y')) représente le polynôme de \(\mathbb{N}[Y]\): \(3Y^2\).

0. Donnez une représentation quelconque du polynôme \((3Y^3+2Y)Y\)

1. Écrire une fonction evaluate qui prend une représentation de polynôme \(P\) et un entier \(n\) et qui retourne la valeur de \(P(n)\).

On rappelle que le degré d’un polynôme sur \(\mathbb{N}[Y]\) se calcul de manière inductive par \(\text{deg}(P + Q)=\max(P, Q)\), \(\text{deg}(PQ)=\text{deg}(P)+\text{Q}\) et \(\text{deg}(i) = 0\).

2. Écrire une fonction deg qui prend un polynôme et calcul son degré.

En mathématiques, un polynôme est sous forme développée s’il s’écrit de la forme \(\sum_i a_i Y^i\). On rappelle qu’une fonction polynomiale à une unique forme développée.

Pour \(P\) un polynôme, on note dev(P) la forme développé dans notre codage des polynôme. Si on suppose que \(P = a_d Y^d + Q\) avec \(\deg{Q} < d\), alors dev(P) doit retourner ((a_d, 'x', R(d)), '+', dev(Q))

avec R(d) qui défini également par récurrence via la relation, \(R(0):=1\) et \(R(d) = (Y, 'x', R(d-1))\).

3. Écrire la fonction R.

4. Implémenter fonction dev et en déduire une fonction test qui vérifie que deux polynômes sont égaux.

Compiled the: ven. 22 nov. 2024 20:25:48 CET