Les Fonctions

def est_premier(n):
    """n est-il un nombre premier ? n entier quelconque."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2                    # seuls les diviseurs impairs restent a tester
    return True

def premiers_jusqua(n):
    """Liste croissante des nombres premiers <= n."""
    return [k for k in range(2, n + 1) if est_premier(k)]

def nieme_premier(k):
    """k-ieme nombre premier, k >= 1."""
    compte, n = 0, 1
    while compte < k:
        n += 1
        if est_premier(n):
            compte += 1
    return n

def decomposition(n):
    """Facteurs premiers de n >= 2, avec multiplicite, en ordre croissant."""
    facteurs = []
    d = 2
    while d * d <= n:
        while n % d == 0:         # on epuise le facteur d
            facteurs.append(d)
            n //= d
        d += 1
    if n > 1:                     # reste un facteur premier > sqrt(n initial)
        facteurs.append(n)
    return facteurs

assert premiers_jusqua(20) == [2, 3, 5, 7, 11, 13, 17, 19]
assert nieme_premier(1) == 2 and nieme_premier(100) == 541
assert decomposition(360) == [2, 2, 2, 3, 3, 5]
assert decomposition(97) == [97]
from math import prod
for n in range(2, 2000):
    assert prod(decomposition(n)) == n

Dans decomposition, le test final if n > 1 est indispensable : apres la boucle, ce qui reste de n est soit 1, soit un facteur premier superieur a la racine de la valeur courante (par exemple pour \(n = 2\cdot 97\)).

def mon_max(t):
    """Plus grand element de la liste non vide t."""
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

def mon_sum(t):
    """Somme des elements de t (0 si t est vide)."""
    s = 0
    for x in t:
        s += x
    return s

def mon_abs(x):
    return x if x >= 0 else -x

def mon_min(a, b):
    return a if a < b else b

def moyenne_ponderee(valeurs, poids):
    """Moyenne de valeurs ponderee par poids.

    Preconditions : meme longueur, somme des poids non nulle.
    Renvoie None si elles ne sont pas verifiees.
    """
    if len(valeurs) != len(poids) or len(valeurs) == 0:
        return None
    total = mon_sum(poids)
    if total == 0:
        return None
    s = 0
    for i in range(len(valeurs)):
        s += valeurs[i] * poids[i]
    return s / total

assert mon_max([-5, -2, -9]) == -2
assert mon_sum([]) == 0
assert moyenne_ponderee([12, 16], [1, 3]) == 15.0
assert moyenne_ponderee([1], [0]) is None

Noter que mon_sum([]) vaut 0 (element neutre) alors que mon_max([]) n'a pas de sens : d'ou la precondition « liste non vide », qu'il faut expliciter.

1.

[1]
[1, 2]
[3]
[1, 2, 4]

2. L'expression [] qui sert de valeur par defaut est evaluee une seule fois, au moment ou l'instruction def est executee. La liste ainsi creee est stockee dans l'attribut mystere.__defaults__ et reutilisee a chaque appel omettant l'argument. Les appels 1, 2 et 4 partagent donc la meme liste, qui s'allonge. Le troisieme appel fournit explicitement une nouvelle liste, sans effet sur celle par defaut.

print(mystere.__defaults__)     # ([1, 2, 4],)  : la liste partagee

3.

def correcte(t, x=None):
    """x=None signifie 'liste vide neuve a chaque appel'."""
    if x is None:
        x = []
    x.append(t)
    return x

4. Oui, si la valeur par defaut n'est jamais modifiee, ou si le partage est precisement l'effet recherche (memoisation par cache partage, compteur d'appels). Mais il faut alors le documenter explicitement, car c'est contre-intuitif :

def fib(n, cache={0: 0, 1: 1}):
    """Le cache partage entre les appels est ici volontaire (memoisation)."""
    if n not in cache:
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
    return cache[n]

def tabule(f, a, b, n):
    """Valeurs de f en n+1 points equirepartis de [a, b]."""
    h = (b - a) / n
    return [f(a + k*h) for k in range(n + 1)]

def compose(f, g):
    """Renvoie la fonction x -> f(g(x))."""
    def h(x):
        return f(g(x))
    return h

def iterer(f, n):
    """Renvoie f o f o ... o f (n fois). n = 0 donne l'identite."""
    def h(x):
        for _ in range(n):
            x = f(x)
        return x
    return h

def point_fixe(f, x0, eps=1e-12, nmax=1000):
    """Iteration de point fixe. Renvoie (x, nb_iterations, convergence)."""
    x = x0
    for k in range(1, nmax + 1):
        y = f(x)
        if abs(y - x) < eps:
            return y, k, True
        x = y
    return x, nmax, False

from math import cos, sqrt
carre = lambda x: x*x
assert compose(carre, lambda x: x + 1)(3) == 16      # (3+1)^2
assert iterer(lambda x: 2*x, 5)(1) == 32             # 2^5
assert iterer(carre, 0)(7) == 7                      # identite

x, k, ok = point_fixe(cos, 1.0)
print(x, k, ok)      # 0.7390851332151607  (le "nombre de Dottie"), ~90 iterations

La convergence de \(x_{k+1} = \cos(x_k)\) est garantie par le theoreme du point fixe : \(\cos\) est \(k\)-lipschitzienne de rapport \(|\sin| \le \sin(1) \approx 0{,}84 < 1\) sur \([0,1]\), qui est stable par \(\cos\). La convergence est lineaire, d'ou le nombre eleve d'iterations ; la methode de Newton (chapitre 21) fera bien mieux.

def evalue(P, x):
    """Valeur en x du polynome P = [a0, a1, ..., an], par Horner. n multiplications."""
    v = 0
    for a in reversed(P):
        v = v * x + a
    return v

def somme(P, Q):
    """Somme de deux polynomes."""
    n = max(len(P), len(Q))
    R = [0] * n
    for i, a in enumerate(P):
        R[i] += a
    for i, a in enumerate(Q):
        R[i] += a
    return R

def produit(P, Q):
    """Produit de deux polynomes (algorithme naif)."""
    if not P or not Q:
        return []
    R = [0] * (len(P) + len(Q) - 1)
    for i, a in enumerate(P):
        for j, b in enumerate(Q):
            R[i + j] += a * b
    return R

def derive(P):
    """Polynome derive."""
    return [i * P[i] for i in range(1, len(P))]

P = [1, 2, 3]        # 1 + 2X + 3X^2
Q = [0, 1]           # X
assert evalue(P, 2) == 1 + 4 + 12
assert somme(P, Q) == [1, 3, 3]
assert produit(P, Q) == [0, 1, 2, 3]
assert derive(P) == [2, 6]

# (PQ)' = P'Q + PQ'
import random
for _ in range(200):
    A = [random.randint(-5, 5) for _ in range(random.randint(1, 6))]
    B = [random.randint(-5, 5) for _ in range(random.randint(1, 6))]
    g = derive(produit(A, B))
    d = somme(produit(derive(A), B), produit(A, derive(B)))
    g += [0] * (len(d) - len(g))
    d += [0] * (len(g) - len(d))
    assert g == d
print("formule de Leibniz verifiee")

5. La double boucle de produit effectue exactement \(\deg P \cdot \deg Q\) multiplications, soit \(\Theta(nm)\) et \(\Theta(n^2)\) pour deux polynomes de meme degre. L'algorithme de Karatsuba abaisse ce cout a \(\Theta(n^{\log_2 3}) \approx \Theta(n^{1{,}585})\), et la transformee de Fourier rapide a \(\Theta(n\log n)\).

Le schema de Horner, lui, n'utilise que \(n\) multiplications et \(n\) additions pour evaluer un polynome de degre \(n\), contre \(\Theta(n^2)\) pour la methode naive qui recalcule chaque \(x^i\). On peut montrer que \(n\) multiplications sont necessaires : Horner est optimal.

def verifie(nom, obtenu, attendu):
    """Compare obtenu et attendu, affiche le resultat, renvoie un booleen."""
    if obtenu == attendu:
        print(f"  OK   {nom}")
        return True
    print(f"  ECHEC {nom} : obtenu {obtenu!r}, attendu {attendu!r}")
    return False

def lance_tests(f, cas):
    """cas : liste de (tuple_arguments, resultat_attendu). Renvoie (reussis, total)."""
    reussis = 0
    print(f"Tests de {f.__name__} :")
    for args, attendu in cas:
        nom = f"{f.__name__}{args}"
        try:
            obtenu = f(*args)
        except Exception as e:
            print(f"  ERREUR {nom} : {type(e).__name__} : {e}")
            continue
        if verifie(nom, obtenu, attendu):
            reussis += 1
    print(f"=> {reussis}/{len(cas)} tests reussis\n")
    return reussis, len(cas)

def fibonacci(n):
    """n-ieme terme de la suite de Fibonacci, F(0)=0, F(1)=1."""
    if n < 0:
        raise ValueError("n doit etre positif")
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

lance_tests(fibonacci, [
    ((0,), 0), ((1,), 1), ((10,), 55), ((30,), 832040),
    ((-1,), None),          # provoque volontairement une exception
    ((5,), 999),            # echec volontaire
])

Tests de fibonacci :
  OK   fibonacci(0,)
  OK   fibonacci(1,)
  OK   fibonacci(10,)
  OK   fibonacci(30,)
  ERREUR fibonacci(-1,) : ValueError : n doit etre positif
  ECHEC fibonacci(5,) : obtenu 5, attendu 999
=> 4/6 tests reussis

4. Sans le bloc try / except, la premiere exception interromprait toute la campagne de tests. Le capturer permet de signaler l'anomalie et de poursuivre. Noter f.__name__ qui donne le nom de la fonction, et f(*args) qui deballe le tuple d'arguments.

def memoise(f):
    """Renvoie une version memoisee de f (fonction d'un ou plusieurs arguments hachables)."""
    cache = {}
    def g(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    g.cache = cache          # accessible pour l'inspection
    g.__name__ = "memo_" + f.__name__
    return g

2. Pour atteindre \((i,j)\), le dernier pas vient soit de \((i-1,j)\), soit de \((i,j-1)\). Ces deux familles de chemins sont disjointes et les recouvrent toutes, d'ou \[ C(i,j) = C(i-1,j) + C(i,j-1), \qquad C(i,0) = C(0,j) = 1. \]

appels = 0

def chemins(i, j):
    global appels
    appels += 1
    if i == 0 or j == 0:
        return 1
    return chemins(i-1, j) + chemins(i, j-1)

appels = 0; chemins(10, 10); print(appels)        # 369511 appels

chemins_memo = memoise(chemins)
appels = 0; print(chemins_memo(10, 10), appels)   # 184756, et bien moins d'appels

3. Sans memoisation, l'arbre des appels a exactement \(C(n,n)\) feuilles (chaque feuille correspond a un chemin complet, puisque le calcul explore un a un tous les chemins). Un arbre binaire a \(F\) feuilles ayant au moins \(F\) noeuds internes lorsque chaque noeud interne a deux fils, le nombre total d'appels est \(\ge 2C(n,n) - 1\), avec \(C(n,n) = \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}\) : croissance exponentielle.

Avec memoisation, chaque couple \((i,j)\) de la grille n'est calcule qu'une fois, et son calcul coute \(O(1)\) : le total est \(\Theta(n^2)\) operations et \(\Theta(n^2)\) memoire. On passe de \(4^n\) a \(n^2\).

4. Un chemin de \((0,0)\) a \((i,j)\) est une suite de \(i+j\) pas dont exactement \(i\) sont horizontaux : il est entierement determine par le choix des positions de ces \(i\) pas parmi \(i+j\). D'ou \(C(i,j) = \binom{i+j}{i}\).

from math import comb
for i in range(9):
    for j in range(9):
        assert chemins_memo(i, j) == comb(i + j, i)
print("formule verifiee")