Informatique et algorithmique

Cours complet · mathématiques approfondies (ECG 1re année), chapitre 11 · prépa ECG, 1re année

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

En ECG, l'informatique n'est pas une matière séparée : l'intitulé officiel du programme est « mathématiques approfondies – informatique ». Son rôle est énoncé sans ambiguïté — dès qu'un calcul numérique est envisagé, dès qu'un problème incite à tester expérimentalement un résultat, dès qu'une situation aléatoire peut être simulée, le recours à l'ordinateur doit devenir naturel.

AttentionCe qui est exigible

Le langage est Python. Seules les commandes figurant dans la liste ci-dessous sont exigibles, et leur syntaxe précise sera rappelée dans les énoncés. On peut en employer d'autres, mais avec parcimonie : l'objectif reste la mise en pratique des mathématiques, pas la virtuosité en Python. Les commandes break et continue ne sont pas exigibles.

11.1 Structures de programmation

Python : Les quatre structures


if condition:          # structure conditionnelle
    ...
elif autre_condition:
    ...
else:
    ...

for k in range(a, b):  # boucle inconditionnelle
    ...
for x in T:            # T : matrice, vecteur ou chaine de caracteres
    ...

while condition:       # boucle conditionnelle
    ...

def f(x, y):           # definition d'une fonction
    ...
    return ...

ImportantLa discipline avant la virtuosité

Découper en fonctions, commenter à bon escient, tester. Un commentaire utile dit pourquoi, pas quoi : # on s'arrête quand le reste est majoré par eps vaut mieux que # boucle while.

11.2 Les commandes exigibles

Python : Vecteurs, matrices, et opérations élément par élément


import numpy as np
import numpy.linalg as al

M = np.array([[1., 2.], [3., 4.]])
print(np.shape(M))                 # (2, 2)
print(M * M)                       # coefficient par coefficient !
print(np.dot(M, M))                # LE produit matriciel
print(al.inv(M), al.rank(M))
print(al.matrix_power(M, 5))
print(al.solve(M, np.array([1., 2.])))     # resout MX = B

Attention`M * M` n'est pas le produit matriciel

Dans numpy, * multiplie coefficient par coefficient. Le produit matriciel s'écrit np.dot(M1, M2). C'est l'erreur la plus fréquente, et la plus silencieuse : le calcul aboutit, mais il ne calcule pas ce qu'on croit.

11.3 Suites et fonctions

Python : Représenter une suite, et l'escalier d'une récurrence


import matplotlib.pyplot as plt

u = [0.4]
for n in range(12):
    u.append(0.5 * u[-1] + 1)      # u_{n+1} = f(u_n), point fixe 2

plt.plot(range(len(u)), u, "o")    # les points (n, u_n)
plt.show()

Pour une suite définie par récurrence, le programme demande aussi la représentation sur le graphe de $f$ : on trace $y = f (x)$ et $y = x$ , et l'on construit l'escalier — c'est la figure du chapitre 4.

Python : Approcher une limite, une somme, une racine, une intégrale


def somme_serie(f, eps):
    """Somme jusqu'a ce que le terme ajoute soit sous eps.
       Le rang d'arret DOIT venir d'une majoration du reste."""
    s, n = 0.0, 0
    while abs(f(n)) >= eps:
        s = s + f(n); n = n + 1
    return s, n

def dichotomie(f, a, b, eps):
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0: b = m
        else:                a = m
    return (a + b) / 2

def rectangles(f, a, b, n):
    h = (b - a) / n
    return h * sum(f(a + k * h) for k in range(n))

Le programme insiste : la détermination du rang d'arrêt résulte directement de l'étude mathématique. Un seuil choisi au jugé ne garantit rien — c'est la majoration du reste, établie sur le papier, qui le fixe.

ImportantVérifier le lien primitive-intégrale

Pour $f$ de primitive $F$ connue, comparer $F (b) - F (a)$ à la valeur approchée donnée par les rectangles : c'est un contrôle que le programme demande explicitement, et le meilleur moyen de mesurer la qualité d'une méthode numérique.

11.4 Simulation et statistique

Python : Simuler des lois usuelles


import numpy.random as rd

print(rd.random())                      # uniforme sur [0,1[
print(rd.binomial(10, 0.2))             # une realisation
print(rd.binomial(10, 0.2, 100))        # un vecteur de 100
print(rd.binomial(10, 0.2, [100, 10]))  # une matrice 100 x 10
print(rd.geometric(0.3), rd.poisson(4.0))

On peut aussi tout construire à partir de rd.random seul — c'est ce que le programme demande de savoir faire : une Bernoulli est un test rd.random() < p, une binomiale une somme de Bernoulli, une géométrique une attente.

Python : Série statistique d'un échantillon


import numpy as np, matplotlib.pyplot as plt

X = rd.binomial(20, 0.3, 100000)
print(np.mean(X), 20 * 0.3)           # moyenne empirique vs esperance
print(np.var(X),  20 * 0.3 * 0.7)     # variance empirique vs variance
print(np.median(X))
plt.hist(X, bins=range(0, 21))          # frequences
plt.show()

Le programme demande explicitement ces rapprochements : fréquences et loi, fréquences cumulées et fonction de répartition, moyenne et espérance, variance empirique et variance. C'est la loi faible des grands nombres, vue à l'œuvre.

ImportantEstimer une probabilité par simulation

Si $P (A)$ est difficile à calculer, on simule l'expérience un grand nombre de fois et l'on assimile $P (A)$ à la fréquence de réalisation de $A$ . C'est légitime, et c'est la loi faible des grands nombres qui le fonde — pas une intuition.

11.5 Approche expérimentale de la loi de Gauss

ImportantUne loi qu'on ne définira qu'en deuxième année

Le programme demande d'en donner une approche expérimentale : superposer l'histogramme de

$\frac{X - n p}{n p ( 1 - p )}, X ↪ B (n, p),$

et la courbe de $x \mapsto \frac{1}{2 π} e^{- x^{2} /2}$ . La variable centrée réduite issue d'une binomiale se met, quand $n$ grandit, à épouser cette courbe — quels que soient $n$ et $p$ .

Python : La courbe en cloche apparaît


import numpy as np, numpy.random as rd, matplotlib.pyplot as plt

n, p = 200, 0.35
X = rd.binomial(n, p, 200000)
Z = (X - n*p) / np.sqrt(n*p*(1-p))          # centree reduite

plt.hist(Z, bins=60, density=True)
x = np.linspace(-4, 4, 400)
plt.plot(x, np.exp(-x**2/2) / np.sqrt(2*np.pi))
plt.show()

La bibliothèque scipy.special fournit $Φ$ , la fonction de répartition de cette loi, sous le nom sp.ndtr.

11.6 L'essentiel du chapitre

Fiche de synthèse

Quatre structures : if/elif/else, for, while, def. break et continue ne sont pas exigibles.
! Dans numpy, * multiplie coefficient par coefficient ; le produit matriciel est np.dot.
numpy.linalg : inv, rank, matrix_power, solve, eig.
numpy.random : random, binomial, randint, geometric, poisson, exponential, normal, gamma.
Le rang d'arrêt d'un calcul approché vient d'une majoration du reste établie mathématiquement, jamais d'un seuil choisi au juger.
Rapprocher : fréquences $\leftrightarrow$ loi, fréquences cumulées $\leftrightarrow$ $F_{X}$ , moyenne $\leftrightarrow$ espérance, variance empirique $\leftrightarrow$ variance.
Une probabilité difficile à calculer s'estime par la fréquence — la loi faible des grands nombres le fonde.
L'histogramme de $\frac{X - n p}{n p ( 1 - p )}$ épouse la courbe en cloche : approche expérimentale de la loi de Gauss.

Continuer sur Adloun : animation, QCM, fiches, exercices