Suites de Sturm, complexité et dimension de Vapnik-Chervonenkis

La complexité d'une suite (à valeurs dans un alphabet fini) dénombre tous les facteurs de longueur donnée qui figurent dans cette suite. Pour une suite de Sturm, nous donnons ici une estimation du nombre de mots vus par une fenêtre qui est un ensemble fini quelconque, donc plus générale qu'un intervalle d'entiers consécutifs. Nous en déduisons que la dimension de Vapnik-Chervonenkis d'une suite de Sturm est égale à deux. The complexity of a sequence (with values in a finite alphabet) counts the factors of given length in the sequence.For a Sturmian sequence, we give here an estimation of the number of words which are seen through a window which is an arbitrary finite set, therefore more general than an interval of consecutive integers.As a corollary, we prove that the VC-dimension of a Sturmian sequence is 2.