Algorithmique et Python

Trois structures organisent le déroulement :

• conditionnelle — if / elif / else exécute une branche selon un test booléen ;
• boucle bornée — for k in range(n) répète un bloc pour k prenant les valeurs \(0, 1, \dots, n-1\) (le nombre de répétitions est connu à l'avance) ;
• boucle non bornée — while condition répète tant que la condition booléenne est vraie (le nombre de répétitions n'est pas connu à l'avance).

Une conditionnelle typique calculant le signe d'un nombre : \begin{verbatim} def signe(x): if x > 0: return 1 elif x < 0: return -1 else: return 0 \end{verbatim}

Une liste de valeurs calculées se construit de deux façons équivalentes. Par une boucle avec append : \begin{verbatim} L = [] for k in range(1, 6): L.append(k * k) \end{verbatim} ou, plus compactement, par compréhension : \begin{verbatim} L = [k * k for k in range(1, 6)] \end{verbatim} les deux produisent [1, 4, 9, 16, 25]. La fonction range(a, b) parcourt \(a, a+1, \dots, b-1\).

Pour savoir si x est dans une liste L et à quel indice, on balaie une fois et on renvoie le premier indice correspondant, ou \(-1\) s'il est absent : \begin{verbatim} def recherche(L, x): for i in range(len(L)): if L[i] == x: return i return -1 \end{verbatim} Le return à l'intérieur de la boucle arrête le balayage dès que x est trouvé. Dans le pire cas (x absent), la boucle s'exécute len(L) fois : le coût croît linéairement avec la longueur de la liste.

Le maximum d'une liste non vide se trouve en conservant une meilleure valeur courante, mise à jour à chaque étape : \begin{verbatim} def maximum(L): m = L[0] for x in L: if x > m: m = x return m \end{verbatim} Pour obtenir le second maximum (la plus grande valeur strictement inférieure au maximum, sur une liste ayant au moins deux valeurs distinctes) en une passe, on conserve deux valeurs m1 (le meilleur) et m2 (le deuxième), toutes deux initialisées à \(-\infty\) (en Python, float("-inf")). Pour chaque valeur x : si x est égale à m1, on l'ignore (c'est un doublon du maximum) ; sinon, si x > m1, l'ancien m1 devient le nouveau m2 et m1 devient x ; sinon, si x > m2, on met à jour m2 seul. Ignorer les doublons de m1 garantit que m2 termine sur la deuxième valeur distincte, même quand le maximum apparaît plusieurs fois.

On maintient une fenêtre [g, d] d'indices candidats, d'abord la liste entière, et on la divise par deux à chaque étape : \begin{verbatim} def recherche_dicho(L, x): g, d = 0, len(L) - 1 while g <= d: m = (g + d) // 2 if L[m] == x: return m elif L[m] < x: g = m + 1 else: d = m - 1 return -1 \end{verbatim} À chaque tour, la largeur d - g est au moins divisée par deux, donc la boucle s'exécute au plus environ \(\log_2(\texttt{len(L)})\) fois avant que g > d : cela garantit la terminaison sur une liste finie.

Pour payer un montant n avec des valeurs de pièces listées par ordre décroissant, on prend à plusieurs reprises autant d'exemplaires que possible de la plus grande pièce ne dépassant pas le montant restant : \begin{verbatim} def rendu(n, pieces): resultat = [] for c in pieces: # pieces en ordre decroissant while n >= c: resultat.append(c) n = n - c return resultat \end{verbatim} Avec le système canonique pieces = [50, 20, 10, 5, 2, 1] (en centimes), le choix glouton est optimal (le moins de pièces) ; pour un système quelconque il peut ne pas l'être — par exemple avec [4, 3, 1] et n = 6, le glouton donne \(4 + 1 + 1\) (trois pièces) alors que \(3 + 3\) n'en utilise que deux.

On suppose \(f\) continue sur \([a, b]\) avec \(f(a)\) et \(f(b)\) de signes opposés. On divise par deux l'intervalle d'encadrement jusqu'à ce que sa largeur passe sous une tolérance eps : \begin{verbatim} 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 \end{verbatim} Le test f(a) * f(m) <= 0 conserve la demi-portion sur laquelle le changement de signe persiste. Après \(k\) étapes la largeur vaut \((b - a)/2^k\), donc atteindre la tolérance eps demande environ \(\log_2\!\bigl((b-a)/\texttt{eps}\bigr)\) étapes.

On itère \(u \leftarrow g(u)\) à partir d'une valeur initiale u0, en s'arrêtant quand la mise à jour déplace la valeur de moins de eps : \begin{verbatim} def point_fixe(g, u0, eps): u = u0 v = g(u) while abs(v - u) > eps: u = v v = g(u) return v \end{verbatim} Le test d'arrêt abs(v - u) > eps compare deux termes consécutifs ; il ne doit être utilisé que lorsqu'on sait, par une étude mathématique préalable, que la suite converge. Un petit écart entre deux termes consécutifs est un signal d'arrêt pratique, et non une garantie que la valeur renvoyée soit à eps près du vrai point fixe — c'est l'étude préalable qui justifie de s'y fier.

Avec import pandas as pd et une table df = pd.read_csv("data.csv") :

• df.head() — les premières lignes ; df.shape — le couple (lignes, colonnes) ;
• df.describe() — un résumé (effectif, moyenne, écart-type, min, quartiles, max) de chaque colonne numérique ;
• df["age"].mean(), .median(), .std(), .count() — les indicateurs d'une colonne ;
• df.sort_values("age") — la table triée selon la colonne "age".

La moyenne et la médiane coïncident avec celles définies dans Statistiques univariées. Deux réserves : .var() et .std() divisent par \(N - 1\) par défaut, alors que Statistiques univariées divise la variance empirique par \(N\) (pour retrouver la valeur du cours, on passe l'option ddof=0, par exemple df["age"].std(ddof=0)) ; et les quartiles renvoyés par describe ou .quantile() utilisent une convention d'interpolation qui peut différer de celle du cours, donc sur de petits échantillons ils peuvent ne pas coïncider exactement avec les quartiles calculés à la main.

Avec import matplotlib.pyplot as plt :

• plt.plot(x, y) puis plt.show() — une courbe passant par les points \((x_i, y_i)\) (graphes de fonctions, termes d'une suite) ;
• plt.bar(x, h) — un diagramme en bâtons de hauteurs h aux positions x ;
• plt.hist(data) — un histogramme des valeurs de data ;
• plt.boxplot(data) — une boîte à moustaches (quartiles) de data.

On construit une figure en émettant les commandes de tracé, puis un unique plt.show().

Le graphe est donné par listes d'adjacence pondérées : adj[i] est une liste de couples (j, w) signifiant une arête de i vers j de poids w. Les distances valent \(+\infty\) au départ, sauf la source à \(0\) : \begin{verbatim} import numpy as np def dijkstra(adj, source): n = len(adj) dist = [np.inf] * n dist[source] = 0 fixe = [False] * n for _ in range(n): # choisir le sommet non fixe le plus proche u, best = -1, np.inf for i in range(n): if not fixe[i] and dist[i] < best: u, best = i, dist[i] if u == -1: break fixe[u] = True for (j, w) in adj[u]: # relacher les aretes issues de u if dist[u] + w < dist[j]: dist[j] = dist[u] + w return dist \end{verbatim} La liste renvoyée dist contient la distance minimale de la source à chaque sommet. Pour récupérer le chemin lui-même — et pas seulement sa longueur — on stocke, à chaque relâchement, le prédécesseur du sommet amélioré dans une liste séparée et on le remonte depuis la cible ; on ne conserve ici que les distances. Chaque étape externe fixe un sommet (ou s'arrête plus tôt dès que les sommets non fixés sont inatteignables), donc l'algorithme s'arrête après au plus \(n\) étapes.

Une épreuve de Bernoulli de paramètre \(p \in [0, 1]\) renvoie \(1\) (succès) avec probabilité \(p\), en comparant un tirage uniforme à \(p\) ; en sommant \(n\) épreuves indépendantes, on obtient un comptage binomial \(\mathcal{B}(n, p)\) : \begin{verbatim} import numpy.random as rd def bernoulli(p): if rd.random() < p: return 1 return 0 def binomiale(n, p): s = 0 for k in range(n): s = s + bernoulli(p) return s \end{verbatim} La condition rd.random() < p est vraie avec probabilité exactement \(p\), puisque le tirage est uniforme sur \([0, 1[\).

Avec import numpy.random as rd, les lois usuelles du chapitre Lois discrètes usuelles se tirent par :

• rd.randint(a, b) — un entier uniforme dans \(\{a, \dots, b-1\}\) ;
• rd.binomial(n, p) — un tirage selon \(\mathcal{B}(n, p)\) ;
• rd.geometric(p) — un tirage selon la loi géométrique de paramètre \(p\) (rang du premier succès) ;
• rd.poisson(lam) — un tirage selon la loi de Poisson de paramètre lam.

Un troisième argument donne un échantillon entier d'un coup : rd.binomial(10, 0{,}2, 100) renvoie un vecteur de \(100\) tirages indépendants selon \(\mathcal{B}(10\,;\,0{,}2)\).