Les définitions – Les programmes scolaires – Les questions initiales

Des définitions clés

Nous souhaitons présenter dans cette section, quelques définitions générales sur les concepts d’algorithme, d’algorithmique et de programmation informatique. Pour cela, nous allons partir de définitions issues de la littérature scientifique et celles que nous retenons. 

Un algorithme

Les expressions « algorithme » et « programme informatique » sont polysémiques. Il nous semble ainsi nécessaire de clarifier le sens de ces expressions, et de préciser la définition que nous retiendrons pour le concept d’algorithme. De nombreux chercheurs, tant en informatique qu’en mathématique, ont donné différentes définitions du concept d’algorithme. Nous proposons ici de ne présenter que celles qui nous ont semblé les plus en accord avec notre approche de l’algorithmique comme objet d’apprentissage de nouvelles notions mathématiques. Cependant, ces définitions ne sont pas exhaustives. Selon Knuth (1973), « La signification moderne de l’algorithme est assez similaire à celle de la recette, du procédé, de la méthode, de la technique, de la procédure, de la routine, sauf que le mot « algorithme » connote quelque chose de légèrement différent ». En effet, un algorithme ne se réduit pas à un simple ensemble fini de règles donnant une séquence d’opérations pour résoudre un type spécifique de problème. Un algorithme doit répondre à Les définitions – Les programmes scolaires – Les questions initiales. Laval Dominique – Thèse de doctorat – 2018 39 cinq caractéristiques importantes que sont : (1) la finitude (Finiteness). L’algorithme doit se terminer après un nombre fini d’étapes ; (2) la définition de chaque étape (Definiteness). Chaque étape de l’algorithme est définie avec précision, et les actions qui les caractérisent sont effectuées sans aucune ambiguïté ; (3) les entrées (Input). Un algorithme peut avoir zéro entrée, une entrée ou plusieurs entrées. On entend par « entrée », les quantités, les valeurs qui lui sont données initialement avant que ne débute l’algorithme. Ces entrées vont être prises dans des ensembles d’objets spécifiés ; (4) les sorties (Output). Un algorithme est constitué d’une ou plusieurs sorties. Ces sorties sont constituées des quantités ayant une relation spécifiée avec les entrées ; (5) l’efficacité (Effectiveness). Pour qu’un algorithme puisse être utilisé pour répondre à une tâche donnée, celui-ci doit également être efficace. On entend par efficacité le fait que toutes les opérations à effectuer dans l’algorithme doivent être suffisamment fondamentales pour pouvoir en principe être exécutées exactement et dans un laps de temps fini par un homme utilisant du papier et un crayon.

Un programme informatique

Le concept d’algorithme est moins primitif que celui d’un problème. En effet, un même problème, comme trier une liste, peut-être résolu par plusieurs algorithmes. Cependant, ce concept est plus primitif que la notion de programme informatique. En effet, plusieurs  programmes informatiques peuvent correspondre à un même algorithme. Se pose alors la question de définir le concept de programme informatique. Selon Chí Thành et Bessot (2010), qui s’appuient sur une définition proposée par Arsac (1995), « un programme informatique est une liste des instructions auxquelles la machine devra obéir, dans l’ordre de leur exécution […]. On le chargera dans la mémoire de la machine, où elle puisera les instructions au fur et à mesure de leur exécution, à sa propre vitesse. » 

Le concept de langage de programmation

L’algorithme utilisé par nos cellules pour synthétiser une protéine à partir d’un brin d’ARN9 messager n’a pas été écrit, ni verbalisé, avant d’être exécuté dans les premières cellules, puis transmis de génération en génération (d’après les connaissances scientifiques actuelles). Cependant, comme le souligne Dowek10, écrire cet algorithme est une étape obligatoire afin de communiquer le processus à une machine paramétrable. Pour cela, il est nécessaire d’avoir un langage de communication. Un pâtissier n’a pas besoin de connaître les verbes « éplucher », « mélanger », « étaler » … pour exécuter la recette de la tarte aux pommes, mais il a besoin de créer, ou d’apprendre, ces mots, s’il veut la verbaliser et l’écrire (Dowek11). Pour écrire des algorithmes, nous pouvons utiliser un langage naturel comme le français. Cependant, écrire un algorithme dans un langage de programmation est actuellement indispensable pour que celui-ci puisse être implémenté dans un environnement numérique afin qu’il soit exécuté. En effet, nous ne savons pas encore fabriquer des machines qui pourraient tester des algorithmes exprimés dans un langage naturel. Les langages de programmation permettent de définir les ensembles d’instructions effectuées par l’ordinateur lors de l’exécution d’un programme. Un programme est donc l’expression d’un algorithme dans un langage donné pour une machine donnée. (Chí Thành et Bessot, 2010, p. 138). Les langages de programmation sont l’intermédiaire entre l’humain et l’environnement numérique. Ils permettent d’écrire dans un langage proche de la machine mais intelligible par l’humain, les opérations que l’ordinateur va être amené à effectuer après l’implémentation de l’algorithme .