Combinatoire et didactique

Présentation Thème combinatoire et didactique

Les recherches spécifiques au thème combinatoire et didactique de l’Institut Fourier concernent essentiellement les thèmes 1, 2 et 3 de la structure fédérative « Maths à Modeler » (https://mathsamodeler.univ-grenoble-alpes.fr).

Les sujets de combinatoire sont issus de la théorie des graphes, théorie au cœur de la combinatoire. Les problématiques abordées peuvent être inspirées par des questions d’optimisation telles que la théorie des codes correcteurs, la coloration ou la domination ou aussi de combinatoire énumérative.

Ces dernières années, dans le cadre du projet ANR IDEA, nous nous sommes intéressés aux problèmes d'identification dans des structures discrètes : comment distinguer les éléments de la structure en l'interrogeant ? Ce domaine de recherche est très actif comme peut en témoigner la bibliographie en ligne d'Antoine Lobstein (http://perso.enst.fr/~lobstein/debutBIBidetlocdom.pdf).
Le problème le plus étudié, entrant dans ce cadre, est celui des codes identifiants, introduit en 1998 par Karpovsky, Chakrabarty et Levitin. Il s'agit de trouver un sous-ensemble dominant de sommets d'un graphe, appelé code identifiant, tel que chaque sommet du graphe a une intersection unique avec le code. Déterminer la taille minimale d’un tel code s’avère être un problème difficile, d’un point de vue algorithmique il est NP-difficile. Cependant, nous avons été en mesure de déterminer des codes identifiants optimaux dans des structures régulières associées à des métriques telles que Lee et Sierpinsky. Ce problème reste ouvert en métrique de Hamming.
Nous avons abordé l’étude des codes identifiants dans des structures définies par sous-graphes exclus. Nous montrons que le problème des codes identifiants est toujours NP-complet dans la classe des graphes adjoints, graphes de permutations et graphes d'intervalles. Cependant, s'il existe en général des codes identifiants de taille logarithmique (par rapport au nombre de sommets du graphes) ce n'est plus le cas pour les classes citées précédemment où les codes sont de taille au minimum racine carré du nombre de sommets. Enfin, nous généralisons ces résultats en montrant un résultat de dichotomie sur toutes les classes de graphes stable par sous-graphe induit, en utilisant notamment la dimension de Vapnik-Chervonenkis.
L’étude de ces familles de graphe nous a conduit à étudier des problèmes de coloration identifiante pour laquelle nous avons apporté les premiers résultats relatifs à une classification en terme de complexité algorithmique ainsi que des encadrements serrés sur une valeur optimale. Ces résultats sont présents dans les thèses d’Aline Parreau et Souad Slimani. 
Dans les questions de recherche à venir, le projet ANR GAG (début 2015), issu de travaux préliminaires dans le cadre du PEPS Misère, porte sur l’étude des jeux combinatoires. Ces recherches sur des questions mathématiques (évaluation de fonction de Grundy, étude de complexité, détermination de stratégie dans le cadre de jeux partisans issus de problème d’optimisation combinatoire comme le jeu de coloration) sont en partie motivées par leur application à l’enseignement de la preuve mathématique. La thèse de Ximena Colipan, soutenue en 2014, a montré que l’on pouvait mettre en place en classe des situations recherche inspirées de jeux combinatoires. D’autres ingénieries didactiques de situation recherche ont été réalisées notamment dans la thèse de Simon Modeste autour de l’algorithmique. Parallèlement des outils théoriques autour de la notion de concept-problème ont été développés dans la thèse de Nicolas Giroud afin de permettre l’analyse épistémologique et didactique de situation d’apprentissage complexe.

Dans le cadre des recherches en didactique des mathématiques, nous souhaitons mettre en avant une collaboration récente Maths-SHS : étudier « l’appropriation par les apprenants des systèmes de désignations en mathématiques », en articulant, dans une perspective constructiviste, les apports de la didactique des mathématiques et de la sémiotique. Ce souci d’articulation se concrétise par une organisation interdisciplinaire, avec d’une part une représentante de l’Institut Fourier, Denise Grenier et d’autre part un représentant d’un laboratoire des sciences de l’éducation, Christian Dépret (E.A. 602, U.P.M.F.).
Le travail s’est principalement développé dans l’étude des manuels scolaires selon les dimensions suivantes :

1- L’analyse et la catégorisation des formalismes existants.
Nous avons par exemple constaté une tripartition des formalismes.
- Disciplinaire (les systèmes symboliques propres aux mathématiques).
- Didactique (les formalismes mis en place afin de faciliter l’identification des objets     d’apprentissage et de leurs caractéristiques).
- D’exposition (les formalismes dont la fonction est esthétique ou qui procèdent de      monstration portant sur d’autres objets que ceux d’apprentissage).

2- L’identification de notions clés (« convention sans légende » ; « localité d’une convention »).
La notion de convention sans légende (comme celle de localité d’une convention) renvoie aux connaissances implicites à l’utilisation de signes. Alors qu’il y a une multiplication des conventions graphiques, l’absence d’explication pose la question des rapports de l’évidence, de la norme et de l’ostension (cette problématique rencontre celle posée par M. Bosch dans son travail sur les ostensifs). Enfin, cela rend suspect l’évaluation, par l’adulte, de la clarté de manuels qui s’adressent aux enfants.

3- L’analyse du processus de compréhension des conventions locales par les élèves et les enseignants.
On peut procéder à l’analyse a priori des processus inférentiels utilisés dans la compréhension d’une convention graphique : la déduction, l’induction, mais aussi l’abduction (comme un outil dédié, par Peirce, à ce type d’analyse). Nous avons aussi réalisé, et testé auprès d’élèves et d’enseignants, un instrument (questionnaire) permettant d’identifier les hypothèses produites relativement à certaines conventions sans légende observées dans des manuels.

Ces développements ont été présentés lors séminaires et colloques et ont donné lieu à la rédaction de mémoires de master.  Deux étudiants poursuivent maintenant en thèse (M. Galilée est en thèse au laboratoire des sciences de l’éducation de Grenoble, et I. Glogger est en thèse à l’université de Landau -Allemagne-).
Le projet en cours consiste d’une part à valoriser ce qui a été fait (un article en cours) et d’autre part à approfondir la notion de localité des conventions mathématiques en milieu scolaire (primaire et collège) et les difficultés d’acquisitions liées, en particulier du point de vue des pratiques enseignantes.