Algorithme

Aspects théoriques de la pensée computationnelle
◀▬▬▶
⚐ à améliorer	☸ débutant
⚒ 2022/10/14
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ée 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 recherche. De ce fait, l'article propose d'abord de définir qu'est-ce qu'un algorithme en fonction de trois perspectives différentes mais 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 suite de l'article, différentes typologies d'algorithmes seront abordées: la transformation de l'information, les systèmes experts, les algorithmes intelligents ou auto-génératif, et les algorithmes hybrides. Enfin, une série de stratégies pour enseigner/apprendre les algorithmes est proposée.

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'inputs bien définis, dans un output ou série d'outputs bien définis (Cormen et al., 2009). 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 représente 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 chiffres) 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 (Denning et al., 1989) ?

La naissance de l'ordinateur - grâce notamment aux travaux de Alan Turing et Alonso Church (Copeland, 2020 ; Turing, 1936), 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. La répétition d'activités similaires est en elle-même une forme d'algorithme, surtout lorsqu'elle est régit par des algorithmes sous-jacents. 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) à des nouvelles données disponibles. 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 plutôt de manière implicite et 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 la théorie de l’action raisonnée ou la théorie de l’action planifié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 à travers les dispositifs numériques, 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 informatiques à soutenir l'activité des personnes de manière satisfaisante. De ce fait, la manière spécifique dont les algorithmes sont implémentés 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 (Du Boulay, O’Shea, & Monk, 1981).

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 (O'Neil, 2016). 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 (Collet, 2021).
• 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 reconduites à 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

Il existe différentes manières de catégoriser les algorithmes, par exemple en termes techniques selon leur fonctionnement interne (séquentiels, parallèles, récursifs, etc.). Dans cette section, nous proposons une perspective transversale aux trois niveaux identifiés dans la section précédente.

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 experts, 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 experts 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 est d'intégrer dans la logique des éléments pseudo-imprédictibles. Ceci peut être fait principalement pour deux manières 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 experts, 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 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 polyvalente, 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 par des formules établies directement à 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 empiriques, utilisées pour créer l'algorithme lui-même.

Par exemple, les applications de traduction ont beaucoup évolué dans le temps, notamment après un changement de perspective. Au lieu d'essayer d'implémenter toutes les règles syntaxiques et orthographiques des langues (i.e. émulant donc un système expert), l’algorithme de traduction est entraîné grâce à des textes qui sont jugés de qualité et qui sont fourni dans les différentes langues comme training set. L'algorithme reconnaît à ce moment des similarités, des patterns, entre le texte fourni pour la traduction et des textes qui ont été utilisés pour l'entraînement. En utilisant ces similarités, l'application génère la traduction correspondante. La qualité de l'algorithme dépend donc entièrement de la qualité des textes qui sont fournies pour rendre le système intelligent et auto-génératif. Si des biais s'installent au niveau du corpus des textes fournis, ces mêmes biais se propagent à l'algorithme de traduction.

Dans le cas de ce type d'algorithmes, donc, obtenir le code source de l'application ne sert pratiquement à rien, car c'est dans la boîte noire où la magie se passe. En même temps, ce type d'algorithme peut continuer à apprendre au fil du temps, en exploitant des nouvelles informations pour augmenter sa capacité à trouver des similarités et, par conséquent, produire des outputs encore plus adéquats.

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.

Stratégies pour enseigner/apprendre les algorithmes

Les algorithmes sont l'une des éléments essentiels de la pensée computationnelle et donc il est difficile de les dissocier d'une compétence plus large. Néanmoins, il existe des stratégies qui peuvent être plus spécifiquement axées sur les algorithmes en tant que suites d'opérations. Cette section en illustre quelques unes, avec une brève discussion.

Analogie

Surtout à un stade initiale, les algorithmes sont souvent traités par analogie avec des démarches de la vie quotidienne. L'un des exemples les plus fréquents consiste dans l'analogie avec une recette de cuisine :

• Les ingrédients représentent les données d'entrées
• Les différentes étapes de préparation représentent la suite d'opérations qui respectent les caractéristiques d'un algorithme (finitude, réplicabilité, précision, efficience, ...)
• Le plat final représente l'output de sortie

D'autres analogies similaires sont représentées par l'exécution de noeuds complexes selon des étapes bien définies ; des jeux de magie avec des cartes qui permettent au magicien de remonter à la carte choisie par la personne ; donner des directions pour atteindre un lieu en suivant un chemin bien précis ; monter un meuble à partir de pièces détachées ; et d'autres encore.

Ces analogies ont l'intérêt de renforcer l'aspect systématique des algorithmes, en réduisant une démarche plus complexe à des étapes plus simples, dont la combinaison permet d'attendre le résultat souhaité. En même temps, la démarche par analogie présente une limitation importante : elle s'adresse à un système computationnel différent des machines. En d'autres termes, les consignes sont créées par des êtres humains afin que d'autres êtres humaines les exécutent. Les algorithmes s'adressent au contraire à des systèmes computationnels (abstraits ou réels) avec une capacité de modélisation réduite par rapport aux être humains. En d'autres termes, il est difficile de définir une analogie dans laquelle la composante inférentielle de l'exécutant-e est entièrement délimitée. Pour ce faire, il faudrait donner des spécifications en amont sur les connaissances que chaque personne exécutant la séquence d'opérations possède sans explications préalables. Cet aspect est traité de manière très implicite ou totalement négligé dans des analogies de ce type.

Pseudo-code

Le pseudo-code représente un langage intermédiaire entre la communication humaine et un langage formalisé pour instruire une machine. Contrairement à la stratégie par analogie, le pseudo-code prend plus en considération le transfère de l'exécution sur un autre agent computationnel qui ne partage pas les mêmes compétences inférentielles des êtres humains. En même temps, les capacités de traitement de l'information reçue à travers le pseudo-code ne doivent pas être formalisées de manière détaillé, ce qui laisse beaucoup de flexibilité sur le niveau de granularité et précision des instructions. Dans ce sens, le pseudo-code s'approchent déjà beaucoup aux langages de programmation formalisés, qui peuvent eux-mêmes différer en termes de proximité avec un système symbolique de communication entre personnes (voir Introduction à la programmation).

Adaptation d'exemples

Cette stratégie consiste à fournir des algorithmes complet, mais définis de manière à ce que des changements peuvent être apportés afin de varier les différentes composants (input, computation et output). Les algorithmes sont déjà implémentés dans un format (textuel ou graphique) qui est exécutable par un agent computationnel différent des êtres humains.

Pour maximiser la compréhension, il peut être utile d'utiliser des algorithmes qui soient saillants dans le domaine ou contexte de référence, et/ou par rapport aux connaissances et intérêts des apprenantes. La capacité de généraliser des algorithmes à différents contextes s'acquièrent avec l'expérience, et la possibilité de relier des exemples à des finalités ou connaissances spécifiques partagés par les apprenant-es peut rendre les exemples plus concrets et intéressants.

Résolution d'algorithmes incomplets

Contrairement à la stratégie précédente, les algorithmes sont dans ce cas fournis seulement dans un format incomplet. Les apprenant-es doivent donc réfléchir sur les éléments manquants et les implémenter directement dans le format (textuel ou graphique) choisi pour implémenter l'algorithme de manière concrète.

Encore une fois, choisir des algorithmes en relation avec le contexte ou le domaine d'intérêt peut contribuer à rendre la tâche plus saillante.

Rétro-ingénierie

Cette stratégie consiste à fournir aux apprennant-es seulement les données d'entrées et de sortie d'un algorithme. La tâche consiste donc dans la compréhension d'abord de la logique de l'algorithme, c'est-à-dire identifier des régularités entre les données d'entrées et de sortie, et ensuite remonter aux passages nécessaires pour implémenter la transformation.

Résolution de problèmes ouverts

Les consignes sont explicitées en termes de résolution d'une problématique spécifique, mais dans les grandes lignes. Les apprenant-es doivent à ce moment effectuer le processus complet de résolution de la problématique dans un algorithme fonctionnel. Des contraintes spécifiques peuvent être définies en amont.

Création d'un algorithme personnalisé

Les apprenant-es définissent en autonomie les finalités de l'algorithme et essayent de l'implémenter pour qu'il fonctionne de la manière souhaité. Comparé aux exemples précédent, dont la faisabilité de l'algorithme était implicitement garantie par la tâche elle-même, dans ce cas les apprenant-es sont confronté-es à une double difficulté :

1. Est-ce que la problématique donnée se prête à une solution algorithmique ?
2. Est-ce que l'apprenant-e est capable de formaliser cette solution si elle est possible ?

Discussion d'un algorithme

Cette stratégie comporte davantage une réflexion méta-cognitive et peut concerner plusieurs niveaux d'analyse (i.e. technique, interaction personne-machine, sociale). La discussion peut porter sur des algorithmes célèbres, des exemples ad-hoc, ou même des algorithmes personnalisés créés par les apprenant-es.

Documenter un algorithme

En documentant le fonctionnement d'un algorithme, les apprenant-es sont forcé-es de faire le cheminement contraire : remonter du fonctionnement de l'algorithme à la manière dont ce fonctionnement peut-être compris par une personne intéressée à l'adopter. Il s'agit encore une fois d'une stratégie méta-cognitive qui implique, entre autres, les réflexions suivantes :

• Formaliser de manière explicite la fonction de l'algorithme
• Identifier et nommer de manière non ambiguë les différentes composantes de l’algorithme
• Spécifier un problème ou une classe de problèmes qui peuvent bénéficier de la solution algorithmique implémentée
• Imaginer des cadres d'utilisation potentiels, par exemple à travers des exemples ou petits tutoriels

Conclusion

Cet article a proposé un survol de la notion d'algorithme, devenu de plus en plus centrale dans le fonctionnement non seulement des dispositifs numériques, mais également d'un point de vue de l'interaction personne-machine et des conséquences sur les comportements et valeurs sociaux. Le focus d'analyse des algorithmes est en effet flottant sur plusieurs niveaux et la conception de ceux-ci doit intégrer des perspectives qui dépassent la faisabilité technique.

Références

• Church, A. (1936). An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, 58: 345–363
• Collet, I. (2021). L'intelligence artificielle, révélateur des rapports de domination de la société. Cahier Du CIEP, (29), 5-10. Retrieved from https://archive-ouverte.unige.ch/unige:152093
• Connolly, R. (2020). Why computing belongs within the social sciences. Communications of the ACM, 63(8), 54‑59. https://doi.org/10.1145/3383444
• Copeland, B. J. (2020). The Church-Turing thesis. In E. N. Zalta (Éd.), The Stanford encyclopedia of philosophy (Summer 2020). Metaphysics Research Lab, Stanford University. https://plato.stanford.edu/archives/sum2020/entries/church-turing/
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Alogrithms (3rd ed.). Cambridge, MA: MIT press.
• Du Boulay, B., O’Shea, T., & Monk, J. (1981). Black box inside the glass box : Presenting computing concepts to novices. Int. J. Man-Machine Studies, 14(3), 237‑249. https://doi.org/10.1006/ijhc.1981.0309
• Denning, P. J., Comer, D. E., Gries, D., Mulder, M. C., Tucker, A., Turner, A. J., & Young, P. R. (1989). Computing as a discipline. Computer, 22(2), 63. https://doi.org/10.1109/2.19833
• O’Neil, C. (2016). Weapons of math destruction : How big data increases inequality and threatens democracy (First edition). Crown.
• Shneiderman (2003). Leonardo's Laptop: Human Needs and the New Computing Technologies. MIT Press
• Turing, A. M. (1936). On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society, 1, 230‑265. https://doi.org/10.1112/plms/s2-43.6.544