Algorithme

Cet article est en construction: un auteur est en train de le modifier.

En principe, le ou les auteurs en question devraient bientôt présenter une meilleure version.

---

Aspects théoriques de la pensée computationnelle
◀▬▬▶
⚐ à améliorer	☸ débutant
⚒ 2022/10/12
Voir aussi
Pensée computationnelle Introduction à la programmation
Catégorie: Aspects théoriques de la pensée computationnelle

Introduction

Cet article propose un survol du concept d'algorithme qui intègre plusieurs perspectives. La définition classique tirées des sciences informatiques nécessite d'être augmentée par des considérations issues des sciences sociales. Les algorithmes jouent en effet un rôle de plus en plus prépondérant dans différents aspects de la vie quotidienne, dans la technologie éducative, ainsi que dans la construction, la sélection, l'évaluation et le partage du savoir scientifique. De ce fait, l'article se propose d'abord de définir qu'est-ce qu'un algorithme en fonction de trois perspectives différentes, quoi que complémentaire: une définition technique/informatique, une définition issue du domaine de l'interaction personne-machine, et enfin une définition avec un ancrage sociale. Dans la deuxième partie de l'article, différentes typologies d'algorithmes seront abordés: la transformation de l'information, les systèmes experts, les algorithmes intelligents ou auto-génératif, et enfin les algorithmes hybrides.

Qu'est-ce qu'un algorithme

Définition technique/informatique

Dans la perspective technique/informatique, l'objectif d'un algorithme est de résoudre un problème.

Dans cette perspective, un algorithme est définit comme une suite d'opérations formalisées qui transforment un input ou une série d'input bien définis, dans un output ou séries d'output bien définis. Les caractéristiques suivantes sont souvent associées à un algorithme à complément de cette définition :

• Finitude : l'algorithme doit aboutir à une solution, c'est-à-dire à un stade de sortie qui considère la suite d'opérations terminée
• Réplicabilité : à parité d'inputs d'entrées et de conditions d'opération, l'algorithme doit aboutir à chaque fois aux mêmes outputs
• Précision : la suite d'opérations doit être formalisée de manière non-ambiguë
• Efficience : la suite d'opérations doit être exécutée dans un temps jugé adéquat en fonction de la complexité et des alternatives possibles

On perçoit dans cette conception d'un algorithme les aspects liés au traitement automatique de l'information qui était l'une des forces de propulsion de l'informatique. Le mot computer en anglais, d'ailleurs, se référait au départ à des personnes qui effectuaient des calcules à la main, en utilisant des techniques pour minimiser les erreurs (e.g. réporter les résultats intermédiaire sur une autre feuille). L'héritage numérique (dans le sens des calcules sur des unités numériques) des algorithmes a donc fait ainsi que la perspective soit au départ principalement mathématique et liée à des enjeux d’ingénierie: comment peut-on automatiser efficacement la solution de problèmes ?

La naissance de l'ordinateur - grâce notamment aux travaux de Alan Turing et Alonso Church, formalisés ensuite dans l'architecture des ordinateurs nommée d'après John Von Neumann - applique d'ailleurs la notion d'algorithme de manière récursive à la machine elle-même. En effet, un ordinateur en tant que machine universelle émerge de la possibilité d'exécuter un nombre potentiellement infini d'algorithmes sur la base d'un nombre fini d'opérations symboliques.

La notion technique d'algorithme est néanmoins limitée si on prend en compte l'utilisation qui est faite plus en général des dispositifs informatiques. Par exemple, le concept de finitude devient problématique si on prend en compte un jeu ou un réseau social dont la finalité est celle de continuer à l'utiliser. On peut bien entendu séparer l'exécution de l'algorithme spécifique (e.g. l'opération en elle-même) de l'utilisation répétée du même algorithme faite par l'utilisateur, mais cette distinction ne serait que formelle. Au même titre, la réplicabilité des algorithmes est également mise en question lorsqu'on prend en considération les algorithmes qui sont basés sur des éléments aléatoires, ou qui s'adaptent de manière progressive (voir le type d'algorithmes plus bas). De ce fait, la perspective suivante prend en compte plus largement l'interaction personne-machine.

Définition issue de l'interaction personne-machine

Dans la perspective de l'interaction personne-machine, l'objectif d'un algorithme est d'accomplir une tâche.

Le passage de la résolution d'un problème à l'accomplissement d'une tâche génère une définition plus flexible d'un algorithme. En effet, dans la perspective technique/informatique, l'accent est plutôt mis sur la suite d'opérations à effectuer, tandis que les inputs et les outputs sont perçus de quelque manière déterministe. Au contraire, dans l'interaction personne-machine, la notion de input et output est fondamentale : d'une part, nous possédons aujourd'hui différentes manières pour encoder de l'information ou donner des commandes à un ordinateur (e.g. voix, gestes, ...), de l'autre, les output des ordinateurs sont de plus en plus complexes (sons, objets 3D, véhicule à guide autonome, ...).

Un algorithme dans la perspective de l'interaction personne-machine prend donc en compte l'ensemble des échanges entre la personne et la machine selon le principe de l'action raisonnée : qu'est-ce qu'on veut obtenir en exploitant les algorithmes sous-jacent le dispositif que nous sommes en train d'utiliser ? On retrouve à ce stade donc des considérations plus larges relatives par exemples à l'acceptabilité des algorithmes que nous utilisons, la manière dont nous les déclenchons et les réponses que nous obtenons depuis les opérations effectués. Schneiderman (2003) résume bien cette perspective de la manière suivante « L'ancienne informatique concerne ce que les ordinateurs peuvent faire, la nouvelle informatique concerne ce que les gens peuvent faire. » (traduction libre). En d'autres termes, les inputs et les outputs passent du rang d'information statique à traiter à éléments constitutifs de l'algorithme lui-même.

Par conséquent, l'accent n'est plus simplement mis sur la qualité des algorithmes en termes de capacité à exécuter des opérations, mais plus en général sur la capacité des dispositifs informatique à soutenir l'activité des personnes de manière satisfaisante. De ce fait, la manière spécifique dont les algorithmes sont implémentées de manière sous-jacente n'est pas déterminante du moment où elle ne modifie pas des caractéristiques qui peuvent affecter la satisfaction de la personne (e.g. un algorithme qui prend plus de temps par rapport à un autre pour effectuer la même opération). En même temps, cette perspective ne peut pas être détachée de la perspective technique/informatique, car ce que la machine peut ou ne peut pas faire est déterminé en large partie par les algorithmes au sens plus strict.

De plus, l'interaction personne-machine est désormais de plus en plus distribuée, avec des personnes qui n’interagissent pas simplement avec une application, mais avec d'autres personnes à travers des applications. La prochaine perspective tient donc en compte cet horizon plus étendu.

Définition sociale

Dans la perspective sociale, l'objectif d'un algorithme est d'apporter un changement sur le plan comportemental et/ou des valeurs qui soit bénéfique pour la société.

Cette transition vers un horizon sociale nécessite d'une prise de conscience plus large du rôle que les algorithmes jouent dans notre société. Connolly (2020) résume bien cette perspective dans l'affirmation suivante « Étant donné que l'informatique en tant que discipline est de plus en plus intégrée dans la vie humaine et sociale, l'informatique en tant que discipline universitaire doit s'éloigner des modèles de programmes d'études inspirés par l'ingénierie et intégrer les perspectives analytiques fournis par les théories et les méthodologies des sciences sociales » (traduction libre).

En d'autres termes, il n'est pas suffisant d'analyser un algorithme en termes de sa capacité de résoudre un problème ou accomplir une tâche, il faut aussi se questionner sur l'impact plus général de l'algorithme sur les comportements et les valeurs de la société de référence. Un algorithme est dans ce sens la traduction en code informatique d'une intention, d'une opinion vis-à-vis des comportements à adopter par les gens. Ceci peut impliquer des aspects liés par exemple à :

• L'acceptabilité éthique de comment les données sont obtenues, traitées et de quelles conclusions sont tirées par cette opération.
• L'égalité de traitement des algorithmes indépendamment des caractéristiques des personnes qui les utilisent. Par exemple, la reconnaissance vocale a la tendance à être basée principalement sur des voix masculines, plus basses et graves, et par conséquent les voix plus aiguë sont moins bien reconnues.
• Les conséquences d'un usage répété et prolongé d'un algorithme non seulement en fonction de l'activité elle-même, mais aussi en termes de soustraction à d'autres activités alternatives (e.g. dépendance de réseaux sociaux)
• La capacité (et la responsabilité) des algorithmes à s'intégrer dans un contexte complexe et polyvalent (e.g. les choix des véhicules autonomes lors des situations critiques)
• La transparence du fonctionnement des algorithmes lorsque ceux-ci sont utilisés dans des prises de décisions avec des conséquences importantes sur les individus (e.g. quelles sources d'informations afficher lors d'une recherche dans le web)

De manière plus abstraite, ces réflexions peuvent être reconduite à l’enjeu suivant : le fait qu'on dispose des connaissances suffisantes pour implémenter un algorithme (technique) et de lui faire accomplir une tâche (interaction personne-machine) ne signifie pas automatiquement que cet algorithme soit bénéfique pour la société.

Types d'algorithmes

Transformation de l'information

Les algorithmes qui s'intéressent principalement au traitement de l'information sont responsables notamment de l'encodage de l'information dans un format que le dispositif computationnel peut identifier, traiter et décoder de manière satisfaisante. Le mécanisme sous-jacent est entièrement transparent, dans le sens où il s'agit en général de règles de conversion et optimisation de l'information. Par exemple les formats .mp3 pour les fichiers audio ou les formats .jpeg pour les images sont des algorithmes de compression de l'information qui essaie de trouver un équilibre entre le poids des fichiers et le maintient de la qualité de la source originale.

Ces algorithmes sont donc affectés de manière considérable par les aspects techniques/informatiques, mais dépendent aussi de considérations plus larges notamment sur la possibilité d'encoder et décoder certaines types d'informations. Par exemple, il existe des mécanismes d'encodage de la pensée humaine permettent de contourner le langage (humain ou informatique) à travers des interfaces neuronales directes.

Systèmes experts

Dans les algorithmes de type systèmes expertes, la logique est intégrée de manière transparente par les créateurs. En d'autres termes, en ayant accès au code source de l'algorithme, il est possible de comprendre et prédire entièrement son fonctionnement. En technologie éducative on peut utiliser les QCM comme exemples de systèmes experts : si les étudiant-es avaient accès au code source du test, il serait possible de remonter aux réponses correctes.

Les systèmes expertes sont donc des algorithmes entièrement déterministes, dans le sens où il n'y a aucun facteur qui n'est pas prédit à l'avance (sauf sans le cas des bugs) qui est censé pouvoir modifier le fonctionnement de l'algorithme. L'algorithme est également insensible à son usage : à parité d'input, l'output sera toujours le même.

Algorithmes aléatoires

Les algorithmes aléatoires sont caractérisés en partie ou en totalité par le recours à des principes probabilistes. L'idée à la base des algorithmes aléatoires et d'intégrer dans la logique des éléments pseudo-imprédictibles. Ceci peut être fait principalement pour deux manière qui sont, de manière paradoxale, l'opposé l'une de l'autre :

1. Apporter de la variabilité au fonctionnement des algorithmes, par exemple dans les cas des jeux.

   Contrairement aux systèmes expertes, donc, l'output de l'algorithme n'est pas, au moins dans les intentions, totalement transparent. Par conséquent, à parité d'input, l'output peut ne pas être le même.

2. De manière de quelque sorte contre-intuitive, on peut exploiter des phénomènes aléatoires dans une perspective déterministe/experte.

   Ce mécanisme est par exemple exploité dans des simulations (e.g. Markov Chain Monte Carlo) ou dans des situations ou les inputs sont incertaines. L'aléatoire est dans ces cas utilisé pour maximiser les chances que l'algorithme détermine la solution la plus adéquate dans un ensemble de solutions alternatives.

La notion d'aléatoire est en elle-même complexe et polyvalent, ainsi qu'un exemple d'enjeu majeur au niveau technique : comment un phénomène aléatoire est-il implémenté dans une machine qui est à la base déterministe ? Par exemple, les fonctions aléatoires dans plusieurs langages de programmation sont en réalité tirées depuis des longes listes de chiffres qui ne suivent pas une logique précise ou des fonctions mathématiques pré-déterminés. Dans d'autres cas, l'aspect aléatoire est apporté par des phénomènes qui, à l'heure actuelle, sont considérés comme imprédictibles, comme par exemple le bruit de l'univers exploité par le site random.org.

Algorithmes intelligents ou auto-génératifs

Les algorithmes intelligents ou auto-génératifs exploitent des sortes de boîtes noires dont le fonctionnement interne est déterminée sur la base de formules qui ont été établies directement par la machine à travers des mécanismes d'apprentissage (e.g. machine learning). Ces algorithmes utilisent des mécanismes probabilistes, souvent avec des composantes aléatoires (voir plus haut), mais dont les paramètres sont inférés directement par des données qui sont utilisées pour créer l'algorithme lui-même.

Par exemple les systèmes de recommandation des portail d'achats en ligne ou des plateformes de streaming sont désormais basés sur des algorithmes de ce type. Il n'y a pas un algorithme qui suggère de manière transparente certaines options en fonction de règles établies par les concepteurs. Au contraire, l'algorithme exploite les données antécédentes (e.g. les achats ou les chansons écoutées par tous les utilisateurs) afin de déterminer de manière probabiliste quels autres éléments pourraient intéresser la personne en fonction de son comportement passé. En même temps, la manière dont ces algorithmes sont entraînés dépend aussi des choix qui ont été faite en amont par le concepteur, par exemple en termes des données utilisées pour créer l'apprentissage.

Algorithmes hybrides

Les types d'algorithmes présentés plus haut ne sont pas mutuellement exclusifs. Il existe plusieurs recouvrements et, dans la plupart des cas, ils sont utilisés de manière complémentaire.