Sujet de TER.

Algorithmes de pavage de la droite.

Encadrants: Raluca Uricaru (uricaru_AT_lirmm.fr) et Eric Rivals (rivals_AT_lirmm.fr)

4 étudiants.

Etant donné un ensemble d'entier, par exemple {0,2,4}, on cherche à savoir si l'on peut combler un intervalle des entiers, par exemple, [0,11], en posant à différentes positions des copies de l'ensemble. Dans notre exemple, il suffit de poser des tuiles aux positions : 0, 1, 6, 7 pour combler exactement l'intervalle [0,11]. On dira alors que {0,2,4} est une tuile de [0,11]. Le mot paver est synomyme de combler. Dans un pavage, aucune position ne peut être remplie plus d'une fois, et chaque position doit être remplie au moins une fois. Il est facile de vérifier que {0,2,3} n'est pas une tuile de [0,11], ni d'aucun intervalle [0,n], quel que soit l'entier n.

Le premier travail est d'implanter un algorithme de reconnaissance d'un ensemble qui pave un intervalle donné. Cet algorithme existe, est décrit dans un article de recherche, et sera fourni. Ensuite, il convient de développer une interface pour visualiser un pavage, dans un objectif pédagogique. Pour compliquer un peu, on considère ensuite un intervalle circulaire (c.a.d., un intervalle [0,n] dans lequel après la position n on revient sur la position 0). Ce type d'intervalle est appelé tore. La tâche sera d'énumérer des tuiles du tore qui ne sont pas de tuiles de l'intervalle simple (non circulaire). Vous pourrez aussi essayer de donner des propriétés des tuiles qui sont spécifiques du tore.