MPA Mathématiques en Python : contrôle continu du 20 mars 2024

Procédure :

• lancez Anaconda, soit en vous connectant au serveur v100, soit avec votre ordinateur personnel.
• créez un nouveau notebook jupyter.
• répondez au questions dans le notebook.
• quand vous avez fini, allez dans file/export notebook as.../ puis choisissez HTML. Merci de mettre votre nom de famille dans le nom de fichier, par exemple DUPONT_Kevin_CC2.html.
• envoyez ce fichier par email à guillot@math.unistra.fr en mettant impérativement comme sujet "Python CC2".
• attendez que je vous confirme la bonne réception de l'email avec sa pièce jointe au bon format, puis quittez la salle.

ATTENTION : 2 points de présentation

Le barème intègre 2 points (ce qui est beaucoup) pour "la présentation". Ceci inclut:

• l'utilisation du "markdown" pour faire des titres, du gras, de l'italique, ou ce que vous voulez.
• il doit y avoir un titre, la date du jour, votre nom.
• le code doit être agréable à lire et facile à comprendre. S'il est utile de produire du code clair, il faudra néanmoins le commenter, avant pendant et après.
• les cellules ayant produit une erreur doivent être effacées (en appuyant sur d deux fois), sauf si vraiment vous tenez à me les montrer. De même, je ne veux pas voir plusieurs propositions de réponse, mais seulement votre dernier mot. Les questions doivent être traitées dans l'ordre.

Exercice 1 : une fonction récursive

On considère la fonction $A : \mathbb{N}\times \mathbb{N} \to \mathbb{N}$ définie par récurrence de la manière suivante :

• $A(0,n) = n+1$
• $A(m,0)= A(m-1,1)$
• $A(m,n)= A(m-1, A(m, n-1))$ pour $m>0$ et $n>0$.

Remarque: il n'est pas évident de montrer que cette définition est bien fondée, c'est-à-dire que la récurrence se termine toujours, mais on ne vous demande pas d'y réfléchir (vous le ferez chez vous après l'examen).

Question 1. Ecrire une fonction A(m,n) qui calcule ceci. Attention, n'essayez que des valeurs de $m$ et $n$ petites (par exemple $A(4,1)$ est à peu près impossible à calculer avec Python).

Question 2. Mettez les valeurs $A(m,n)$ pour $0 \le m < 4$ et $0 \le n < 5$ dans une liste de listes. Indication : la dernière ligne doit être [5, 13, 29, 61, 125].

(Si vous n'avez pas réussi à faire la question précédente, prenez la fonction A= lambda m,n : (m,n) à la place.)

Question 3 (plus difficile, hors barème). Ecrire une variante, disons B(m,n), qui renvoie une liste à 2 éléments [a, b] où a est le nombre A(m,n) comme ci-dessus, et b est le nombre de fois que la fonction B a été appelée au total pour arriver au résultat. Par exemple B(0,n) doit renvoyer [n+1, 1] (il n'y a pas eu d'appel récursif, donc $1$ seul appel en tout). Commentez.

def A(m,n):
    if m == 0:
        return n+1
    elif n == 0:
        return A(m-1, 1)
    else:
        return A(m-1, A(m, n-1))

tests= [ [A(m,n) for n in range(5)] for m in range(4)]

for ligne in tests:
    print(ligne)

[1, 2, 3, 4, 5]
[2, 3, 4, 5, 6]
[3, 5, 7, 9, 11]
[5, 13, 29, 61, 125]

Question supplémentaire pour le plaisir (elle n'était pas dans l'épreuve):

def B(m,n):
    if m == 0:
        # aucun autre appel donc 1 appel en tout
        return [n+1, 1]
    elif n==0:
        # un appel récursif qui génére b appels en tout :
        a,b= B(m-1,1)
        # b+1 appels en tout
        return [a, b+1]
    else:
        a1, b1= B(m, n-1)
        a2, b2= B(m-1, a1)
        return [a2, b1+b2+1]

B(3, 4)

[125, 10307]

Le nombre d'appels à la fonction grandit très vite, et est en fait bien supérieur à l'entier que l'on est en train de calculer!

Exercice 2 : sommes de cubes

Nous avons vu que tout entier positif peut s'écrire comme la somme de 4 carrés. Dans cet exercice nous allons explorer un peu, sans aller très loin, ce qui se passe avec les sommes de cubes. Attention, certains cubes sont négatifs!

Nous aurons besoin de networkx donc n'oubliez pas de faire tout de suite:

import networkx as nx

Question 1. Ecrire une fonctions cubes(N) qui renvoie la liste des cubes d'entiers entre 1 et $N$. Par exemple cubes(1000) doit renvoyer

[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

(Vous pouvez recopier cette liste, si vous n'arrivez pas à traiter la question, c'est utile dans la suite.)

Note: vous n'avez pas besoin de la fonction "racine cubique" pour faire cette question, mais si vous voulez vous en servir tout de même, sachez que l'on peut écrire x**(1/3.0) pour la racine cubique (approchée) de x.

def cubes(N):
    reponse= []
    n= 1
    n_cube= n**3
    while n_cube <= N:
        reponse.append(n_cube)
        n= n+1
        n_cube= n**3
    return reponse

cubes(1000)

[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

Question 2. Ecrire une fonction graphe_cubes(N) qui renvoie un graphe dont les sommets sont les entiers $i$ avec $0 \le i < N$, et avec une arête entre $i$ et $j$ lorsque $i<j$ et $j-i$ est un cube. Puis, dessinez le graphe pour $N=10$.

(Si vous n'avez pas fait la question précédente, remplacez "$j-i$ est un cube" par "$j-i$ est dans la liste ci-dessus". Pour les valeurs de $N$ que nous allons essayer dans la suite, ça revient au même.)

def graphe_cubes(N):
    G= nx.Graph()
    G.add_nodes_from(range(N))
    L= cubes(N)
    for i in range(N):
        for j in range(i+1, N):
            if j-i in L:
                G.add_edge(i,j)
    return G

nx.draw(graphe_cubes(10), with_labels= True)

Question 3. Soit G= graphe_cubes(200). Avec la fonction nx.shortest_path(G, i, j) vous obtenez un chemin de longueur minimale entre les sommets $i$ et $j$; la longueur de ce chemin est appelée la distance entre $i$ et $j$.

Montrer que pour $i=0$, la distance est maximale pour $j=175$ (et uniquement pour ce nombre). Puis, écrire 175 comme somme de 6 cubes. Enfin, remplacez $N=200$ par $N=1000$ et écrivez 175 comme une somme de 4 cubes.

G= graphe_cubes(200)

distances= [len(nx.shortest_path(G, 0, i)) for i in range(200)]

max(distances)

7

for i in range(200):
    if distances[i] == 7:
        print(i)

175

nx.shortest_path(G, 0, 175)

[0, 8, 7, 15, 23, 50, 175]

On voit que $175 = 8 + (-1) + 8 + 8 + 27 + 125 = 2^3 + (-1)^3 + 2^3 + 2^3 + 3^3 + 5^3$.

G= graphe_cubes(1000)

nx.shortest_path(G, 0, 175)

[0, 343, 686, 174, 175]

Cette fois-ci, on a $175 = 343 + 343 + (-512) + 1 = 7^3 + 7^3 + (-8)^3 + 1^3$.