9. Conclusion¶
9.1. Les algorithmes et nous¶
Sans le développement de l’algorithmique, de nombreux problèmes n’auraient pas pu être résolus par les ordinateurs dans un temps raisonnable.
L’étude des algorithmes a un effet bénéfique sur notre manière de réfléchir et de résoudre des problèmes dans notre vie quotidienne. L’étude de l’algorithmique permet de structurer notre pensée et de prendre des décisions fondées sur une réflexion argumentée.
Les algorithmes sont omniprésents. « Ils » décident de ce que nous voyons sur les réseaux sociaux, ils influencent nos choix quand nous cherchons une personne qui nous correspond, ils nous suggèrent des livres à lire et des films à regarder, corrigent nos textes, les traduisent ou encore embellissent nos photos en un clic. Ils font la pluie et le beau temps en bourse, décident si un prévenu doit être emprisonné, rédigent des articles de journaux, conduisent des voitures autonomes. Cette liste s’allonge chaque jour…
Comprendre le fonctionnement de base des algorithmes permet de mieux appréhender ce qu’il se passe dans toutes ces situations. Nous y reviendrons plus en détail dans la deuxième partie du cours d’algorithmique.
9.2. Focus sur l’automatisation¶
Grâce aux algorithmes, la machine a pu remplacer l’homme dans de nombreuses tâches (comparez les deux images ci‑dessous), en allant des robots constructeurs d’automobiles aux pilotes automatiques dans les avions, ou encore aux logiciels de trading. L’automatisation permet aux employés de se concentrer sur des tâches plus valorisantes et permet aux entreprises de réaliser des économies.
Usine du début du siècle dernier. Les machines dans cette usine de métallurgie à Vallorbe dans le canton de Vaud sont au service des ouvriers. Source : https://wikivaud.ch/metallurgie-vaudoise/
Usine du début de ce siècle. Les machines dans cette usine de montage Mistubishi en Chine ont remplacé les ouvriers. Source : https://www.lemonde.fr/blog/fredericjoignot/2015
Selon un rapport publié en 2017 par DELL et le Think Tank californien « L’institut du futur », cité par la chasseuse de têtes Isabelle Rouhan dans sans livre « Les métiers du futur », 85% des métiers qui seront exercés en 2030 par les écoliers d’aujourd’hui n’ont pas encore été inventés.
À retenir
Un algorithme est une suite d’instructions dans un ordre bien précis qui permet de résoudre un problème. L’algorithme va produire un résultat en sortie, en fonction de données reçues en entrée.
Pour arriver à résoudre un problème, il faut commencer par le décomposer en sous‑problèmes.
Afin de pouvoir rechercher de manière efficace, les données doivent impérativement être triées en utilisant un algorithme de tri.
Il existe de multiples manières de résoudre un problème, par exemple différents algorithmes de tris. Toutes ces manières ne se valent pas. Il faut choisir l’algorithme en fonction de ce qui doit être optimisé : le temps de résolution, l’espace de stockage, la consommation d’énergie, la précision de la solution, etc.
L’algorithme n’est pas un programme. Pour être exécuté sur un système informatique, l’algorithme doit être transcrit en un programme, pour résoudre le problème concrètement et de manière automatisée.
Remarque – Souhaiteriez‑vous devenir neuro‑manageur.euse ou éducateur.rice de robots ?
Extrait. Intelligence artificielle. Enquête sur ces technologiques qui changent nos vies. Les algorithmes vont‑ils tuer l’emploi ?, éd. Flammarion, 2008, pp. 72‑73.
Résultat, ce ne sont pas seulement les cols-bleus qui sont touchés, mais également les cols blancs, cadres de professions intermédiaires et même supérieures, comptables, traducteurs ou encore traders, etc. Pour l’essayiste Hakim El Karoui, la robotisation pourrait être à ces derniers ce que la mondialisation a été aux premiers. Goldman Sachs, la star des banques d’affaires new-yorkaises, a provoqué une onde de choc dans la profession lorsqu’un de ses responsables a déclaré début 2017 que son desk de trading actions, qui employait 600 traders à son pic en 2000, n’en comptait plus que deux ! « Ces 600 traders, ils occupaient beaucoup d’espace », a-t-il lâché, sûr de son effet, lors d’un colloque à l’université de Harvard. Des bataillons de traders disparus pour cause de bascule vers le trading électronique à haute fréquence, qui représente aujourd’hui 99% des ordres d’achat et de vente chez Goldman Sachs, 75% chez les concurrents et 45% toutes classes d’actifs confondus dans le secteur bancaire. Ce géant de la finance les a avantageusement remplacés par… 200 ingénieurs. Ce sont eux qui pilotent désormais, pour des salaires jusqu’à cinq fois moins importants, des algorithmes programmés pour gagner des sommes certes infinitésimales, mais sur des millions d’opérations quotidiennes en limitant au maximum le risque. Au suivant ?
Important
L’analyse de complexité des algorithmes nous permet de sélectionner les meilleurs algorithmes pour un problème donné et nous permet de comprendre pourquoi certains problèmes ne peuvent pas être (à ce stade) résolus dans un temps raisonnable.
L’algorithmique a permis de mettre en place des stratégies intelligentes de résolution de problèmes comme les principes de « diviser pour régner » ou encore la récursivité. Ces stratégies ont rendu possibles les avancées technologiques fulgurantes du dernier demi‑siècle.
Pour des problèmes difficiles, s’il est impossible de trouver la solution exacte, on peut souvent trouver une solution approchée. L’étude formelle de l’algorithmique nous permet d’estimer la qualité de notre solution approchée.
À retenir
Dans la pratique, il est important de garantir qu’un algorithme va se terminer.
L’algorithme de tri rapide (et du tri par fusion) est plus efficace que les algorithmes de tri vus dans les chapitres précédents. Ceci est possible grâce à la stratégie algorithmique « diviser pour régner », qui divise un grand problème difficile à résoudre en plein de petits sous‑problèmes plus faciles à résoudre. La solution au grand problème s’obtient en combinant les solutions des petits problèmes.
L’ordre de complexité d’un algorithme nous dit si l’algorithme est lent ou rapide. Un algorithme avec un ordre de complexité logarithmique est plus rapide qu’un algorithme avec complexité linéaire, qui à son tour est plus rapide qu’un algorithme de complexité quadratique, ou pire, exponentielle.
Un algorithme récursif est un algorithme qui fait appel à lui‑même. Une condition d’arrêt est nécessaire pour que l’algorithme se termine.
Un algorithme avec une complexité exponentielle implique que le temps nécessaire pour résoudre problème est trop long en pratique. Dans ce cas, on ne va pas pouvoir trouver une solution exacte, mais seulement une solution approchée en utilisant des méthodes heuristiques.
Ai-je compris ?
Vérifiez votre compréhension :
Je sais appliquer l’algorithme de recherche binaire.
Je comprends comment fonctionne la stratégie algorithmique « diviser pour régner ».
Je sais appliquer l’algorithme de tri rapide.
Je sais calculer la complexité temporelle d’un algorithme.
[En option] Je comprends comment fonctionne la récursivité.
Je sais pourquoi un algorithme de complexité exponentielle est lent.
Je comprends ce qu’est une solution heuristique.
Pour aller plus loin – Quelques liens web
Visualisation de problèmes
https://imgur.com/gallery/voutF
https://interstices.info/le-probleme-du-sac-a-dos/
https://visualgo.net/en
https://graphonline.ru/fr
https://clementmihailescu.github.io/Pathfinding-Visualizer/
Problèmes difficiles
https://www.franceculture.fr/emissions/le-journal-des-sciences/le-journal-des-sciences-du-mardi-01-decembre-2020
https://www.bfmtv.com/sciences/ou-est-charlie-l-algorithme-pour-le-detecter-du-premier-coup_AN-201502100004.html
https://www.lebigdata.fr/algorithme-definition-tout-savoir
P = NP ?
https://www.youtube.com/watch?v=AgtOCNCejQ8