Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

I. Introduction

En 2012, pour sa première introduction au baccalauréat scientifique français, l'algorithmique a été présente dans 7 sujets sur 9 (seuls les sujets « Nouvelle-Calédonie » et « Liban » en étant dépourvus) pour un total de 9 exercices. Les questions posées ont été de contenu variable et nous nous proposons ici d'en faire un petit bilan. Nous n'évoquerons pas les modifications que nous avons parfois proposées à certains sujets, uniquement le contenu original.

II. Les sujets

  • Métropole : Utilisation d'un algorithme pour formuler des conjectures sur le comportement d'une suite.

    Questions posées :

    • résultat affiché par l'algorithme pour une entrée donnée,
    • légère modification de l'algorithme pour changer le résultat,
    • interprétation des résultats obtenus.
  • Amérique du Nord : Déterminer le plus petit entier vérifiant une certaine propriété.

    Questions posées :

    • écriture d'un court algorithme (4 à 6 lignes).
  • Antilles-Guyane (non-spécialistes) : Simulation d'une variable aléatoire.

    Questions posées :

    • loi suivie par la variable aléatoire simulée par l'algorithme présenté,
    • détermination de ses paramètres.
  • Antilles-Guyane (spécialistes) : Étude d'un algorithme en arithmétique.

    Questions posées :

    • résultat affiché pour une entrée donnée,
    • but de l'algorithme dans le cas général.
  • Asie : Analyse d'un algorithme de suites numériques.

    Questions posées :

    • faire fonctionner l'algorithme pour des entrées données, déterminer les valeurs des variables au cours du temps.
  • Centres Étrangers : Étude d'un algorithme de suites numériques.

    Questions posées :

    • terme de la suite affiché par l'algorithme.
  • Polynésie : Calcul de suite numérique.

    Questions posées :

    • résultat affiché pour une entrée donnée.
  • Pondichéry : Tirage aléatoire sans remise.

    Questions posées :

    • déterminer si une sortie donnée a pu être produite par l'algorithme,
    • but de l'algorithme dans le cas général.
  • Pondichéry (spécialistes) : Encodage de texte.

    Il n'y a pas d'algorithme à proprement parler, mais une suite d'étapes permettant de faire l'encodage est présentée et celle-ci doit être exécutée à la main sur un exemple par l'élève.

III. Résumé

Au vu de ces 9 sujets, on peut distinguer 3 grandes catégories de sujets :

  • Analyse d'un algorithme (8 sujets) : déterminer le résultat affiché pour certaines entrées ou but général de l'algorithme.
  • Écriture d'un algorithme (2 sujets) : modification d'un algorithme existant ou écriture directe d'un algorithme.
  • Esprit algorithmique (1 sujets) : utilisation de l'esprit et du contexte algorithmique au sein d'un exercice mathématique.

IV. Remarques

Lien entre algorithmique et mathématiques

Si certains sujets arrivent à lier intelligemment les deux composantes, par exemple en utilisant un algorithme pour faire des hypothèses, qu'on démontre ensuite, pour d'autre sujets l'algorithme arrive de manière impromptue. Il est beaucoup plus facile de faire accepter un algorithme (à la fois par les élèves et les enseignants) lorsque celui-ci se présente naturellement et apporte quelque chose au problème mathématique proposé.

Pseudo-code

Dans l'ensemble, le pseudo-code proposé était assez clair, avec des variations d'un sujet à l'autre. On notera cependant le sujet de Pondichéry sur le cyclisme qui introduisait la notation « := », peu claire pour les élèves, et qu'on peut facilement remplacer par une phrase en langage naturel du type « Affecter à X la valeur… ».

Le nom des variables a également son importance, en particulier le choix de $u$ dans le sujet Métropole n'était pas des plus judicieux dans l'algorithme présenté car ce n'est pas $u_n$ qui est calculé. Le choix de noms de variables, de préférence plus longs qu'une seule lettre, est important pour faciliter la compréhension d'un algorithme.

Importance de tester les algorithmes

Tout algorithme proposé devrait avoir été testé préalablement sur machine, afin que son utilisation pratique ne donne pas de résultats contradictoires avec les résultats démontrés mathématiquement. Les élèves vont être amenés à tester les algorithmes proposés dans les sujets de bac et il n'est donc pas possible de proposer un algorithme divergeant fortement au bout de 50 itérations, même si le sujet ne propose d'étudier que les 20 premières (voir « Centres Étrangers »).

S'assurer de la stabilité des algorithmes proposés évitera aux élèves de s'interroger sur des questions trop difficiles pour eux. Un cours sur la stabilité numérique est proposé ici.

V. Algorithme théorique et programme pratique

Lorsqu'on travaille avec du pseudo-code, on a tendance à supposer qu'on travaille, comme en mathématiques, avec des objets « absolus », ayant une précision infinie, un monde dans lequel il est possible de tester l'égalité de deux décimaux. Malheureusement, en pratique nous travaillons avec des outils concrets : les ordinateurs.

Se pose donc la question des objets à étudier : des algorithmes « théoriques » ou « pratiques » ? Dans la mesure où les élèves sont amenés à programmer les algorithmes vus, il faut s'efforcer de ne présenter que des algorithmes dont on sait que l'implémentation de pose pas de problèmes, afin de pas exposer les élèves à ces difficultés.

Il est cependant possible de les sensibiliser à ce problème, sur un cas simple, par exemple tester qu'un angle est droit alors qu'il est exprimé en radians : il est impossible de construire un tel programme en pratique ; on ne pourra que conclure que l'angle est droit « à une certaine précision ».

D'une manière générale, utiliser un modèle dans lequel les nombres ne sont connus qu'à une certaine précision permet de réconcilier la théorie et la pratique, tout en s'abstrayant des détails de mise en œuvre.

Sur cette différence entre valeur exacte et approchée, on peut s'intéresser à trois des sujets proposés cette année :

  • Le sujet Centres Étrangers ne semble pas souhaitable dans la mesure où l'algorithme est instable dès qu'on le transpose dans la plupart des langages de programmation à la disposition des élèves : le passage de l'algorithme idéal à son implémentation pratique se fait mal.

  • Le sujet Antilles-Guyane (spécialistes) proposait de tester la divisibilité d'un nombre en testant si $$ \frac{A}{N} = \left\lfloor \frac{A}{N} \right\rfloor $$ L'approche est maladroite car elle fait appel à une fonction qui entraîne nécessairement des calculs approchés alors qu'il existe une solution plus simple, et au programme, qui permet de faire des calculs exacts. Ainsi, on ne peut jamais vraiment tester l'égalité de deux décimaux ; mais il est bien plus simple de proposer l'utilisation du modulo, en testant si $$ A \equiv 0 \mod{N}. $$

  • Le sujet Métropole pourrait entraîner la confusion dans la mesure où la première partie de l'énoncé attire l'attention des élèves sur le résultat exact car la fraction $$ \frac{11}{6} $$ était attendue à la question « Donner la valeur exacte affichée par cet algorithme… ». Ce calcul exact avec des rationnels peut être obtenu à condition de gérer manuellement numérateur et dénominateur, ce qui modifie quelque peu l'algorithme présenté.

    Or, toute implémentation de l'algorithme proposé (hors langage de calcul formel) va afficher la valeur approchée :

    1.833333333
    

    Des élèves ayant de bonnes connaissances en informatique, conscients de ce problème, ont d'ailleurs été perturbés par cette question.

    Afin d'uniformiser l'exercice, et étant donné que la seconde partie introduit un logarithme (ce qui conduit nécessairement à un calcul approché), il semble souhaitable de poser toutes les questions de manière approchée, tout au long de l'exercice, et de rester ainsi dans une certaine continuité.

En cours de mathématiques, on insiste beaucoup sur la différence entre valeurs exactes et valeurs approchées. Les élèves sont amenés à utiliser presque uniquement les premières lors de la rédaction des preuves.

Dans la mesure où l'algorithmique apparaît dans le cours de mathématiques, il nous paraît souhaitable de faire la différence entre les algorithmes dont la mise en pratique conduit à des calculs exacts et qui par conséquents ont force de preuve, et ceux qui conduisent nécessairement à des calculs approchés et dont les résultats restent toujours sujets à caution.

Une manière simple de faire cette distinction est de considérer comme approché tout algorithme ayant à manipuler des décimaux. En cas d'ambiguïté, il faut essayer d'être précis dans les questions et demander soit une « valeur approchée », soit une « fraction » ou utiliser une formulation telle que « En supposant que l'algorithme suivant puisse calculer avec une précision infinie… ».

VI. Conclusion

Il s'agissait de la première année pour l'introduction de l'algorithmique et dans l'ensemble les sujets proposés ont été de bonne facture, avec quelques maladresses plus ou moins grandes pour certains d'entre eux.

En particulier, le sujet Métropole nous est apparu comme un bon exemple à tout point de vue, que ce soit pour l'intégration de l'algorithme au sein de l'exercice mathématique ou pour le pseudo-code proposé. Des aménagements, notamment sur les aspects calcul exact ou approché, auraient cependant été nécessaires.

En tant qu'algorithmiciens, nous regrettons cependant que la partie « écriture d'algorithme » soit en fin de compte assez faible dans ce sujet (comparé au sujet « Amérique du Nord » par exemple) mais les réactions des élèves face à cet exercice ont montré qu'il était perçu comme difficile.

Gageons que, au fur et à mesure que la formation des élèves s'améliorera, les sujets proposerons plus régulièrement l'écriture de petits programmes, en plus de l'analyse d'algorithmes.

Par Loïc Février et Guillaume Le Blanc

Note : Une analyse de ces sujets de baccalauréat a été publiée par l'APMEP Île-de-France, à cette adresse.

Pensez à vous inscrire pour valider les cours et résoudre les exercices.