Les mathématiques dans la vie quotidienne: le navigateur satellite
Le navigateur par satellite est certainement un outil très courant, et on suppose souvent que son fonctionnement consiste simplement à recevoir des informations de satellites qui "montrent le chemin". En réalité, sa capacité à établir le chemin pour atteindre n'importe quelle destination est le résultat d'une combinaison de différentes techniques, qui concernent la capacité à identifier avec précision où nous sommes à tout moment, la disponibilité de cartes routières précises et actualisées et surtout, la possibilité de calculer le meilleur itinéraire pour atteindre notre destination. Dans cet article, nous concentrerons notre attention sur ce dernier point, en expliquant qu'à la base de ce calcul se trouve une théorie mathématique très précise, la "théorie des graphes»Ce qui nous permet de comprendre comment il est possible d'identifier le chemin le plus court entre deux points. En pratique, nous voyons comment une notion scientifique abstraite devient le fondement d'un objet pratique, réel et surtout très utile.
Tout d'abord, commençons par le bas: qu'est-ce qu'un graphique?
En réalité, ce n'est rien de plus qu'un ensemble d'éléments reliés entre eux: chacun des éléments est appelé «nœud», et les connexions sont appelées «arcs». Un exemple de graphique est celui qui a pour éléments une série de villes reliées entre elles par le réseau routier: dans ce cas, les nœuds sont les villes et les arcs sont les segments d'autoroute entre les villes elles-mêmes. Nous pouvons imaginer un graphique comme une série de boules ou de cercles colorés (les nœuds) reliés entre eux par des lignes (les arcs). Un arc peut être orienté ou non orienté: un arc orienté est celui qui permet uniquement le passage du nœud de départ au nœud d'arrivée (et non l'inverse); un arc non orienté est celui qui permet le passage dans les deux sens. Dans notre exemple de navigateur, une route peut être considérée comme un arc orienté si elle est à sens unique, alors qu'elle peut être considérée comme un arc non orienté si elle est à double sens.
Un graphique est dit pondéré si une valeur, appelée poids, est associée à chaque arc. Cette valeur peut généralement être positive ou négative. En se référant à l'exemple précédent de villes et d'autoroutes, on peut obtenir un graphique pondéré en associant chaque tronçon d'autoroute à sa longueur en kilomètres. Dans un graphe, il est théoriquement possible de passer du nœud A au nœud B de plusieurs manières différentes, en utilisant des arcs différents, tout comme en réalité il est possible de passer d'une ville à une autre en utilisant des routes différentes. Nous appellerons alors "chemin le plus court" le "chemin le plus court" pour connecter le nœud A au nœud B.
Pour notre navigateur satellite, trouver le chemin entre le point de départ et le point final équivaut à trouver le chemin le plus court dans un graphique. Dans la théorie mathématique des graphes, le problème du calcul du chemin le plus court a été étudié et analysé à tous les points de vue, et de nombreux algorithmes sont produits. L'un des plus utilisés, par exemple, est Algorithme de Dijkstra, mais il y en a beaucoup d'autres. C'est donc au choix du constructeur du navigateur de choisir l'algorithme qu'il juge le plus approprié. Dans ce choix, il faut certainement considérer que la théorie sous-jacente à la recherche du chemin le plus court entre deux nœuds peut être très complexe, surtout lorsqu'il s'agit d'effectuer le calcul sur des cartes routières très complexes. Par exemple, l'algorithme A * a été développé qui recherche le chemin le plus court en utilisant une "estimation statistique" pour chaque nœud; parlant en «mots difficiles», cette estimation représente l'évaluation a priori de l'avantage de passer par un nœud par rapport à un autre sur le chemin de la destination finale. Dans tous les cas, entrer dans les détails des algorithmes devient quelque peu compliqué et nécessite des connaissances spécifiques; nous espérons en tout cas avoir fourni une vision de base du problème et peut-être avoir stimulé l'intérêt pour une théorie mathématique ayant de nombreuses implications pratiques dans la vie quotidienne.
John Calcerano