Voici la liste des cours avec leur volume horaire et un résumé:
On this page... (hide)
La combinatoire des mots est l’étude des suites finies et infinies de symboles pris dans un alphabet fini. Dans ce cours, on s’intéressera en particulier à deux problèmes : construire des mots qui évitent certaines répétitions, et compter le nombre de mots finis de chaque longueur qui apparaissent dans un mot infini donné. Ce sera l’occasion de présenter des résultats importants comme le théorème de Fine et Wilf ou celui de Pansiot, et de rencontrer des problèmes ouverts qui peuvent constituer des sujets de recherche intéressants.
Les substitutions sont parmi les objets les plus fondamentaux de la dynamique symbolique : une substitution est un morphisme du mono¨ıde libre, qui consiste à remplacer chaque lettre par un mot. Les substitutions permettent de construire, sous certaines conditions algébriques (cas Pisot), des pavages curieux dont les tuiles, qui ont une frontière fractale, sont appelées fractals de Rauzy. Ces pavages ont de nombreuses applications en approximation diophantienne. En géomètrie discrète, il y a de nombreux liens entre les fractals de Rauzy généralisés et les plans discrets. La forme des pièces qui engendrent un plan discret est étroitement liée à la forme des fractals de Rauzy. Pour toutes ces raisons, une étude approfondie des propriétées topologiques des fractals de Rauzy est d’une grande importance.
La dynamique symbolique dresse un pont entre la combinatoire des mots (infinis) et les systèmes dynamiques (mesurés ou topologiques). Le but de ce cours est principalement d’introduire les notions fondamentales de théorie ergodique et de dynamique topologique (mesures invariantes, ergodicité, minimalité), et d’établir le dictionnaire qui permet de les interpréter dans le contexte de la combinatoire des mots. Par exemple, la minimalité s’interprète en termes de récurrence uniforme et l’unique ergodicité s’interprète en termes de fréquences pour les facteurs finis du mot infini considéré. De nombreux exemples instructifs seront traités. Si le temps le permet, nous verrons quelques applications concernant des majorations du nombre de mesures invariantes, afin de préparer le terrain pour des cours ou exposés focalisés sur une classe particulière de systèmes dynamiques (échanges d’intervalles, isométries par morceaux, pavages, automates cellulaires).
On s’intéresse à une classe particulière de systèmes dynamiques : les isométries par morceaux. On considère une partition de Rn en cellules dont les bords sont des hyperplans. Une isométrie par morceaux est une application de cet espace dans lui-même, dont la restriction à chaque cellule est une isométrie. On code ces applications par l’isométrie associée. Le but est de décrire le langage d’une telle application et la complexité du langage obtenu. Ce type d’applications se rencontre dans l’étude du billard polyédral, dans les échanges d’intervalles, dans les translations d’intervalles etc. Les techniques varient et relient les propriétés géométriques et combinatoires des objets.
Les pavages sont un objet d’´etude entre l’informatique et les math´ematiques. Un jeu de tuiles est un ensemble de formes géoméetriques sur lesquelles on impose des contraintes de juxtaposition. On s’int´eresse alors aux différents agencements de ces tuiles permettant de recouvrir le plan sans chevauchement de tuiles. De nombreux probl`emes apparaissent sous la forme d’une question de pavage : probl`emes physiques avec des contraintes locales comme la cristallographie, probl`emes de calculabilit´e en encodant un comportement dans les contraintes, etc... Dans ce cours on présentera d’abord, de manière historique, les groupes de symétries possibles d’un pavage périodique. On s’intéressera ensuite à la construction de pavage apériodiques à partir de substitutions multidimensionnelles. Ce type de construction a un intérêt informatique en permettant de montrer l’indécidabilité de certaines propriétés sur les pavages, mais aussi en mathématiques. En effet on peut faire agir le groupe des translations sur un pavage et étudier l’ensemble des pavages issus d’un jeu de tuiles comme un système dynamique. On explorera certaines de ses propriétés qui permettent de mieux comprendre les pavages, voire de les classifier, tout en évoquant certains problèmes ouverts.
Classiquement, la théorie algorithmique des graphes avait pour objectif de partitionner les problèmes entre ceux qui possèdent un algorithme polynomial pour les résoudre (problèmes a priori faciles, dits polynomiaux) et ceux pour lesquels on pense qu’un tel algorithme n’existe pas (problèmes a priori difficiles, dits NP-complets). Depuis une quinzaine d’années, a émergé un raffinement de cette dichotomie à l’intérieur des problèmes NP-complets afin de fournir des algorithmes possiblement efficaces même pour de tels problèmes. Le but de ce cours est d’introduire les problèmes paramétrés et leur classification du point de vue de la complexité : problèmes FPT, problèmes W1, problèmes admettant un noyau polynomial, etc. Après un rappel des deux classes de complexité classiques, les notions et techniques classiques du domaine seront abordés et illustrés par des exemples, selon le d´eroulement du cours nous aborderons les algorithmes de couverture par sommets dans les graphes, les techniques de réduction à un noyau, la programmation dynamique sur les graphes à largeur arborescente bornée, la compression itérative, les problèmes FPT sans noyau polynomial, etc.
Sage (http://www.sagemath.org) est un logiciel libre de mathématiques développé depuis 2005 par une communauté internationale de plusieurs centaines d'enseignants et de chercheurs, et qui combine la puissance de nombreux programmes libres dans une interface commune basée sur le langage de programmation Python. Il offre une alternative libre (et gratuite !) à des logiciels comme Magma, Maple, Mathematica ou Matlab. Ce cours, s'appuyant sur le livre libre Calcul mathématique avec Sage (http://sagebook.gforge.inria.fr), comportera une initiation à l’utilisation de Sage, avec un accent sur les fonctionnalités en rapport avec les thèmes des autres cours. Il sera accompagné de sénces de travaux pratiques.
Une clef-USB permettant de démarrer linux et sage sera offerte aux participant-e-s.