Informatique et algorithmique
Cours · mathématiques appliquées (ECG 1re année), chapitre 11 · prépa ECG, 1re année · le début du chapitre, la suite sur Adloun
En ECG, l'informatique n'est pas une matière séparée : elle fait partie du programme de mathématiques, dont l'intitulé officiel est d'ailleurs « mathématiques appliquées – informatique ». Ce chapitre rassemble ce qui se travaille en travaux pratiques tout au long de l'année, et que les chapitres précédents ont déjà mis en œuvre.
Trois objectifs, énoncés par le programme : consolider la programmation commencée au lycée, mettre en place une discipline — découpage en fonctions, commentaires, évaluation par tests — et pratiquer des algorithmes utiles au traitement de l'information, à la modélisation et à la simulation.
L'étude des algorithmes simples fera apparaître deux questions : l'algorithme s'arrête-t-il (terminaison), et renvoie-t-il ce qu'on attend (correction). Le programme demande de les dégager sans les formaliser, et précise que ces notions ne sont pas exigibles.
11.1 Algorithmique des listes
11.1.1 Parcourir
Python : Recherche séquentielle
Le schéma de base : on parcourt, on teste, on s'arrête dès qu'on a trouvé.
def appartient(L, x):
"""Renvoie True si x figure dans la liste L."""
for element in L:
if element == x:
return True
return False # atteint seulement si la boucle s'est acheveeLa ligne return False est hors de la boucle. Placée dedans, elle renverrait False dès le premier élément différent de — erreur classique, et invisible sur une liste dont le premier élément est le bon.
Python : Maximum et second maximum
def maximum(L):
m = L[0] # une liste vide n'a pas de maximum
for x in L[1:]:
if x > m:
m = x
return m
def deux_plus_grands(L):
"""Renvoie (plus grand, second) en UN seul parcours."""
if L[0] >= L[1]:
m1, m2 = L[0], L[1]
else:
m1, m2 = L[1], L[0]
for x in L[2:]:
if x > m1:
m1, m2 = x, m1 # l'ancien maximum devient le second
elif x > m2:
m2 = x
return m1, m2On pourrait chercher le maximum, le retirer, recommencer : deux parcours au lieu d'un, et une liste modifiée. Tenir deux variables coûte une ligne et évite les deux.
Python : Boucles imbriquées : les deux valeurs les plus proches
def plus_proches(L):
n = len(L)
meilleure = abs(L[0] - L[1])
couple = (L[0], L[1])
for i in range(n):
# j > i : chaque paire une seule fois
for j in range(i + 1, n):
d = abs(L[i] - L[j])
if d < meilleure:
meilleure = d
couple = (L[i], L[j])
return coupleLa boucle intérieure part de i + 1 : sans cela on examinerait chaque paire deux fois, et l'on comparerait chaque élément avec lui-même — distance nulle, réponse absurde. Le nombre de comparaisons est .
Un parcours simple fait de l'ordre de opérations, deux boucles imbriquées de l'ordre de . Sur une liste de éléments, cela fait contre : quelques millisecondes contre plusieurs minutes. Le choix de l'algorithme pèse bien davantage que celui du langage.
11.1.2 Dichotomie
Python : Recherche dichotomique dans une liste triée
def recherche_dichotomique(L, x):
"""L est TRIEE par ordre croissant. Renvoie un indice, ou -1."""
a, b = 0, len(L) - 1
while a <= b:
m = (a + b) // 2
if L[m] == x:
return m
elif L[m] < x:
a = m + 1
else:
b = m - 1
return -1Chaque tour divise par deux le nombre de candidats : sur une liste d'un million d'éléments, vingt tours suffisent, contre un million pour la recherche séquentielle. L'hypothèse « liste triée » n'est pas un détail — sans elle, l'algorithme renvoie n'importe quoi, sans erreur.
À chaque tour, diminue strictement : la boucle s'arrête. C'est le type d'argument que le programme demande de dégager, sans le formaliser.