Aborder un problème informatique

En bref

Résumé de l’article

Dans cet article, vous apprendrez à passer d’un problème, décrit en langage naturel, à un algorithme, puis à un programme qui résout ce problème.

Points clés à retenir

• Pour résoudre un problème, il est préférable de le formaliser, puis de spécifier sa solution, et enfin de coder cette solution.

• La formalisation consiste à réexprimer le problème avec des termes et concepts adaptés.

• La spécification consiste à décrire une solution algorithmique en utilisant ce formalisme.

• Le codage traduit l’algorithme en un programme.

Contenu de l’article

Vidéo

Veuillez consulter la vidéo ci-dessous (en anglais, affichez les sous-titres si besoin). Nous fournissons également une traduction du contenu de la vidéo juste après, si vous préférez.

Pour aller plus loin

Un exemple complet : les ponts de Königsberg

Pour voir les trois étapes à l’œuvre, prenons un problème célèbre, que vous retrouverez dans l’article suivant sur la théorie des graphes.

Au XVIIIe siècle, la ville de Königsberg est traversée par une rivière, qui délimite quatre zones : une rive nord, une rive sud, une île centrale et une zone à l’est. Ces zones sont reliées par sept ponts. Les habitant(e)s se demandent s’il est possible de faire une promenade qui traverse chacun des ponts exactement une fois.

Formaliser

Énoncé ainsi, le problème semble demander d’essayer tous les itinéraires possibles dans la ville. En 1736, Leonhard Euler remarque que la plupart des informations sont inutiles : la forme des zones, la longueur des ponts ou le chemin suivi à l’intérieur d’une zone ne changent rien à la réponse. Seul compte le fait qu’un pont relie deux zones.

Il formalise donc la ville ainsi :

• Chaque zone devient un sommet.
• Chaque pont devient une arête entre les deux sommets qu’il relie (plusieurs arêtes peuvent relier les deux mêmes sommets).

La question devient alors : existe-t-il, dans ce graphe, une marche qui emprunte chaque arête exactement une fois ?

Spécifier

Une fois le problème exprimé en termes de graphe, Euler montre le résultat suivant. Dans un graphe connexe, une telle marche existe si et seulement si le nombre de sommets de degré impair (c’est-à-dire touchés par un nombre impair d’arêtes) vaut 0 ou 2.

L’intuition est la suivante : à chaque fois que la marche passe par un sommet, elle y arrive par une arête et en repart par une autre. Les arêtes d’un sommet vont donc par paires, sauf pour le sommet de départ et le sommet d’arrivée.

La solution consiste donc à compter le degré de chaque sommet, puis à compter les sommets de degré impair. Il n’y a plus besoin d’essayer d’itinéraires.

Coder

Le code s’écrit alors en quelques lignes :

def has_eulerian_walk ( edges: list[tuple[str, str]]
                      ) ->     bool:

    """
    This function checks if there is a walk using each edge of a graph exactly once.
    The graph is assumed to be connected.

    Args:
        edges: The edges of the graph, as pairs of vertices (the same pair can appear several times).

    Returns:
        True if such a walk exists, False otherwise.
    """

    # Count the number of edges touching each vertex
    degrees = {}
    for u, v in edges:
        degrees[u] = degrees.get(u, 0) + 1
        degrees[v] = degrees.get(v, 0) + 1

    # Euler's result: 0 or 2 vertices with an odd degree
    nb_odd_vertices = sum(1 for degree in degrees.values() if degree % 2 == 1)
    return nb_odd_vertices in (0, 2)



# Bridges of Königsberg (N = north bank, S = south bank, I = island, E = east)
bridges = [("I", "N"), ("I", "N"), ("I", "S"), ("I", "S"), ("I", "E"), ("N", "E"), ("S", "E")]
print(has_eulerian_walk(bridges))

Ce programme affiche False : l’île a 5 ponts et les trois autres zones en ont 3 chacune, soit 4 sommets de degré impair. La promenade est donc impossible.

Remarquez que la difficulté de ce problème ne se trouvait pas dans le code, mais dans la formalisation. Une fois le bon formalisme trouvé, la solution est presque immédiate.

Formaliser, c’est aussi choisir

Un même problème peut souvent être formalisé de plusieurs manières, et ce choix a des conséquences sur la suite.

Par exemple, un labyrinthe PyRat peut être vu comme une grille de cases, ou comme un graphe dont les sommets sont les cases et les arêtes les passages entre cases voisines. Le second formalisme permet de réutiliser directement tous les algorithmes connus sur les graphes, comme les parcours que vous verrez dans cette séance. Même une fois ce formalisme choisi, il existe plusieurs façons de représenter un graphe en mémoire, qui ont chacune leurs avantages (voir l’article sur la représentation des graphes).

Il faut aussi faire attention à ne pas écarter une information utile. Dans la prochaine séance, le labyrinthe contiendra de la boue, qui ralentit le déplacement du rat. Un formalisme qui ne retient que l’existence des passages ne suffira plus : il faudra associer à chaque arête un poids. C’est précisément le genre de situation où une formalisation trop rapide oblige à tout reprendre.

Spécifier, c’est écrire un contrat

Dans l’exemple précédent, la spécification ne se limite pas à « compter les sommets de degré impair ». Elle précise aussi :

• Les entrées – une liste d’arêtes, où chaque arête est une paire de sommets.
• Les sorties – un booléen indiquant si la marche existe.
• Les conditions d’utilisation – le graphe doit être connexe. Sur un graphe en deux morceaux, la fonction pourrait répondre True alors qu’aucune marche ne permet de passer d’un morceau à l’autre.

On peut voir cela comme un contrat : si l’appelant(e) respecte les conditions sur les entrées, la fonction garantit le résultat annoncé.

En Python, ce contrat se traduit naturellement en code avant même d’écrire l’algorithme :

• La signature de la fonction et ses annotations de types décrivent les entrées et sorties.
• La docstring décrit ce que fait la fonction et ses conditions d’utilisation (voir l’article sur la documentation).
• Les tests vérifient que le contrat est respecté sur des exemples choisis (voir l’article sur les tests). Ici, on pourrait vérifier qu’un triangle admet une telle marche, et que les ponts de Königsberg n’en admettent pas.

C’est d’ailleurs ce que vous ferez dans les activités pratiques PyRat : les méthodes à compléter vous sont fournies avec leur signature et leur docstring, et vous n’avez plus qu’à écrire leur contenu. Une spécification précise est aussi ce qui permet de confier l’écriture du code à une IA, comme vous le verrez dans l’article dédié.

Pour aller encore plus loin

• Une petite présentation de Coq

  Coq permet de prouver des programmes informatiques, comme on prouverait un théorème mathématique.
• Comment poser et résoudre un problème

  Le livre classique de George Pólya, qui décrit une méthode en quatre étapes pour aborder n’importe quel problème.