Présentation

Ce sujet est organisé en deux problèmes, comme les épreuves d'informatique de certains des concours communs.

Le premier problème vous propose de revoir le lemme de l'étoile, puis de découvrir un lemme analogue dû à Guo-Qiang Zhang et E. Rodney Canfield.

Le deuxième problème est orienté vers la programmation; il définit une structure de données permettant de décrire les parties finies ou cofinies de N, puis demande l'écriture de fonctions réalisant les calculs usuels dans cette algèbre: tests d'appartenance et d'inclusion, complémentation, union, intersection.

Référence pour le premier problème: The end of pumping, Guo-Qiang Zhang et E. Rodney Canfield, Theoretical Computer Science, vol. 174, Issue 1-2, 1997, 275-279. Une copie de cet article est disponible ici.

Ce sujet a été soumis à la sagacité des étudiant(e)s le mercredi 27 octobre 1999.