Semi-anneaux et algorithmes sur les graphes P. Simonnet et P. Delfini

L’IUFM en relation avec Monsieur Jacques CARON, IPR-IA de mathématiques, a donné la possibilité à l’IREM d’intervenir dans le Plan Académique de Formation, tous les ans, sous la forme de trois journées de formation (une par trimestre) proposées aux professeurs de l’académie.

En accord avec Monsieur l’IPR-IA les journées académiques de l’IREM ne sont pas destinées à fournir des documents au professeur pour qu’il les utilise dans sa classe. Ces journées s’adressent plutôt aux professeurs désireux de reprendre contact avec les mathématiques du supérieur, éventuellement avec la recherche, désireux d’élargir le champ de leurs connaissances mathématiques ou d’approfondir certaines de ces connaissances.

Le travail effectué ici se situe dans le cadre d’une de ces " journées académiques de l’IREM ". Il est le fruit d’une réflexion sur les nouveaux programmes qui introduisent en terminale ES, option mathématique, la théorie des graphes.

L’un des auteurs, Pierre Simonnet maître de conférence en informatique, enseigne en IUP où l’on retrouve la théorie des graphes, l’autre auteur, Pierre Delfini maître de conférence en mathématiques, enseigne la théorie des groupes aux licences de mathématiques. L’idée de ce travail est né de discussions sur l’intérêt des structures ; les monoïdes face aux groupes. Pourquoi étudier tant les groupes alors que ce ne sont finalement que des monoïdes?

La théorie des graphes offre la possibilité d’illustrer l’intérêt des monoïdes. On verra dans ce travail comment un seul algorithme peut résoudre des problèmes sur les graphes et un problème lié à la théorie des automates. Il suffit pour chaque cas de se placer dans le bon monoïde…

Ce travail a été mis par écrit, il est téléchargeable ci-dessus au format pdf. Quelques collègues ont fait une lecture rapide et nous ont proposé des corrections (merci à Nelcy Paoletti), mais il y a certainement encore des erreurs, vos remarques seront donc les bienvenues.