Nous allons revenir dans la première partie de l'exposé sur l'apport de Maurice Nivat aux pavages du plan et à la géométrie discrète. Nous évoquerons, bien sûr, le théorème de Beauquier-Nivat et ses nombreux prolongements en informatique théorique et algorithmique. Nous montrerons, ainsi, que Maurice aimait beaucoup faire de la recherche en géométrie discrète et en particulier coder des objets géométriques par des mots. Dans cet esprit et dans la seconde partie de l'exposé, nous montrerons comment le codage de segments discrets de la grille $Z^^2$ et l'informatique théorique donnent de nouveaux outils pour attaquer la conjecture plus que centenaire de Frobenius sur les nombres de Markoff.