%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Topologie algébrique discrète – topologie algorithmique

Intervenants potentiels : Dimitri Ara, Alexandra Bac

Résumé ou plan du cours :

Introduction
  - Topologie algébrique : du continu au discret

Les fondements
  - Espaces topologiques, complexes simpliciaux et cubiques
  - Bases du langage des catégories
  - Un peu d’algèbre homologique
  - Homologie singulière
    + Invariance par homotopie
    + Suite exacte de Mayer-Vietoris et calculs
  - Homologie simpliciale et cubique
    + Esquisse de comparaison avec l’homologie singulière
  - Ouverture vers les groupes d’homotopie

Vers la géométrie discrète :
  - Notions de géométrie discrète (objets binaires et leur topologie, complexes
    associés)

Calcul de l’homologie singulière :
  - soit par des approches algébriques (forme normale de Smith)
  - soit approches combinatoires (théorie de Morse discrète)
  - soit en combinant les deux (homologie effective - basée sur la notion de
    réduction ... là on est proche des catégories)

Persistance homologique

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Modèles de calcul naturel - MOCANA

Intervenants potentiels : Pablo Arrighi, Giuseppe Di Molfetta, Kévin Perrot,
Sylvain Sené

Résumé ou plan du cours :

Cette UE vise à donner aux étudiants qui la suivent une "culture" dans le
domaine du calcul naturel, à la frontière des mathématiques discrètes et de
l'informatique (fondamentale). Nous y introduirons certains des principaux
modèles classiques du domaine comme les automates cellulaires et plus largement
les réseaux d'automates, ainsi que les piles de sable. Par ailleurs, une partie
de cette UE visera à présenter les fondamentaux de l'informatique et de
l'information quantiques. La présentation de ces différents domaines du calcul
naturel permettra aussi d'établir des liens que les mathématiques discrètes et
l'informatique entretiennent avec d'autres disciplines, comme la biologie et la
physique.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Introduction à la logique modale

Intervenants potentiels :
C. Greillois, E. Wurbel, V. Risch, N. Olivetti, L. Santocanale

Résumé ou plan du cours :
1- Introduction
2- Sémantique de Kripke
3- Système fondamentaux : K, 4, 5, B, D, T,
4- Axiomatisation et complétude des axiomatisations
5- Systèmes de preuves et méthodes de décision (tableaux)
6*- Théorie de la correspondance (Salhqvist, Kracht)
7*- Logique computationnelles (PDL, mu-calcul)
8*- Logique modale pour l'lA (logique épistémique et autres)
* : selon le temps à disposition.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Logiques Computationnelles

Intervenants potentiels : C. Greillois, L. Santocanale, B. Monmège

Résumé ou plan du cours :

1. Intro
2. Systèmes des transitiion
3. Logique polymodale
4. Bisimulation
5. Expressivité : de la logique polymodale à PDL.
6. Étoile de Kleene et plus petit point fixe.
5. Expressivité : de  PDL au mu-calcul.
7. Théorème de Knaster-Tarski, théorème de
   Gallier-Park-Cousot. Formule de Bekic.
8. Mu-calcul: syntaxe et sémantique
9. Jeux de parité et sémantique des jeux
10. Model checking par resolution des jeux de parité.
11. Algorithmes de résolution de jeux de parité
12*. Automates alterants comme formules du mu-calcul
13*. MSOL et théorème de Rabin
14*. Comparaison du mu-calcul avec MSOL.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Ensembles ordonnés en combinatoire

Intervenants potentiels :
F. Olive, F. Brucker, K. Knauer, L. Santocanale

Résumé ou plan du cours :

1. Ensembles ordonnées et treillis
2. Largeur d'un ensemble ordonné et ses partitions
en chaînes, théorème de  Dilworth.
3.* Ensembles ordonnés série parallèle
4. Familles d'ensembles fermés sous l'intersection (familles de
Moore), opérateurs de clôture, connexions de Galois
5. Treillis distributifs et modulaires
6. Caractérisations locales des treillis (semi)distributifs et (semi)modulaires
7. Bijection entre treillis distributifs et ensembles ordonnés finis,
théorème de Birkhoff
8. Treillis distributifs sur objets combinatoires: c-orientations
des graphes, couplages des graphes bipartis planaires, tensions des
graphe, pavages de dominos, treillis de chemins
9. Matroïdes simples et treillis géométriques
10. Géométries convexes, antimatroïdes, treillis semidistributifs
11. Treillis semidistributifs sur objets combinatoires: arbres
binaires,  (associaèdres, treillis de Tamari et Cambriens) ;
permutations (permutoèdres)

12*. Groupes de Coxeter finis et leurs treillis

13*. Hierarchies

*: Selon le temps à disposition

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Fondements de la PPC et SAT

Intervenants potentiels : les membres de l'équipe COALA
(1PR, 9MC et au total 4 HDR)

Résumé ou plan du cours :

Cette option traite des fondements de la programmation par contraintes (PPC) et
de la résolution de SAT. Elle couvre les aspects allant des algorithmes,
architectures et fondements théoriques des solveurs SAT et CSP, jusqu'à l'étude
des classes polynomiales dans ces deux formalismes.

Les points abordés portent sur :

(1) classes polynomiales ("tractable classes") pour SAT, CSP et au-delà ;
   + classes définies par restrictions de langages,
   + classes définies par décomposition de graphes et hypergraphes
     (exploitation des résultats sur les problèmes exprimables en MSO sous
     l'hypothèse de largeurs bornées)
   + classe hybrides

(2)  architecture des solveurs :
   + algorithmes de résolution
   + algorithmes de propagation
   + heuristiques
   + clauses et no-goods learning
   + notion de redémarrage avec preuve de complétude

(3)  méthodes de résolution pour l'optimisation dans les formalismes VCSP,
     MaxSAT, WMaxSAT,
   + méthodes complètes (B&B et ses optimisations)
   + méthodes incomplètes (recherche locale, recherche tabou, algorithmes
     génétiques,...)
   + algorithmes de propagations de pondérations

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Optimisation combinatoire

Intervenants potentiels : B. Couëtoux, G. Naves et Y. Vaxès

Résumé ou plan du cours :

Un problème d'optimisation combinatoire est caractérisé par un espace de
solution très grand mais que l'on peut décrire de manière compacte, comme
l'ensemble des couplages, des st-chemins, des arbres couvrants ou des cycles
hamiltoniens d'un graphe ou encore l'ensemble des permutations de n
entiers. Une fonction objectif permet d'évaluer la qualité de chacune des
solutions de l'espace de recherche. Résoudre un problème d'optimisation
combinatoire c'est trouver une solution qui minimise ou maximise la fonction
objectif. De nombreux problèmes aussi bien pratiques que théoriques se
formulent de cette manière.

L'objectif du cours est de présenter quelques idées fondamentales qui
permettent de concevoir des algorithmes efficaces pour résoudre de façon exacte
ou avec une garantie de performance des problèmes d'optimisation combinatoire.

On insistera en particulier sur les notions suivantes :

1. L'approche polyédrale consiste à représenter chaque solution de l'espace de
recherche par son vecteur caractéristique et à étudier l'enveloppe convexe de
ces vecteurs. Si celle-ci peut-être décrite de façon compacte (par exemple, par
un nombre d'inégalités polynomial dans la taille de l'entrée du problème) alors
la programmation linéaire permet d'obtenir un algorithme de résolution
efficace.

2. Une telle description vient souvent avec un résultat de type min-max qui
permet de définir l'optimum du problème de minimisation que l'on cherche à
résoudre comme l'optimum d'un autre problème de maximisation (ou l'inverse). La
dualité de la programmation linéaire fournit un tel résultat. Elle est à la
base de la conception de nombreux algorithmes efficaces (polynomial) de
résolution exacte ou approchée via la méthode primale-duale.

3. Même lorsqu'une représentation polyédrale compacte n'est pas disponible, en
particulier pour les problèmes NP-difficiles, l'approximation de l'enveloppe
convexe par des inégalités linéaires, appelées coupes, permet de fournir des
bornes cruciales pour la résolution pratique des problèmes NP-difficiles par
des méthodes de type séparation-évaluation-coupes (branch-and-cut).

Nous illustrerons chacune de ces notions ou approches sur différents problèmes
classiques : couplage, flot et coupes, arborescence, TSP, indépendant commun à
deux matroïdes, arbre et réseau de Steiner, problème de localisation, etc.

Selon les années et les intervenants, la liste des problèmes étudiés et
l'importance relative des différentes notions pourra varier.

Prérequis: Un intérêt pour les structures discrètes, la programmation linéaire
et l'algorithmique. Toutes les notions utilisées dans le cours seront définies
et expliquées.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Théorie Métrique des Graphes

Intervenants potentiels : J. Chalopin, V. Chepoi et Y. Vaxès

Résumé ou plan du cours :

L'objectif du cours est de présenter les résultats principaux de la théorie
métrique des graphes et des liens existant entre cette théorie et d'autres
domaines comme la théorie géométrique des groupes ou la théorie de la
concurrence.  On présentera des méthodes algorithmiques, combinatoires,
géométriques et topologiques.

1. Plongements isométriques dans des hypercubes et des produits de graphes

2. Graphes médians, graphes bridged et la méthode "local vers global"
   - Équivalence entre les graphes médians, les complexes cubiques CAT(0) et
     les domaines de structures d'événements.
   - Équivalence entre graphes bridged et complexes simpliciaux systoliques

3. Graphes et espaces hyperboliques au sens de Gromov
   - Métrique d'arbres et 0-hyperbolicité
   - Définitions et caractérisations de l'hyperbolicité
   - Propriétés algorithmiques des graphes hyperboliques
   - Problème du mot dans les groupes hyperboliques

4. Plongement l_1 à faible distorsion et théorème de Bourgain. Applications
   algorithmiques

5. Graphes de Helly et enveloppes injectives

Selon les années et les intervenants, l'importance relative de ces différents
thèmes pourra varier.

Prérequis : Un intérêt pour la combinatoire, les structures discrètes et
l'algorithmique. Toutes les notions utilisées dans le cours seront définies et
expliquées.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Logique catégorique d'ordre supérieur

Intervenants potentiels :

D. Ara, C. Grellois, L. Santocanale, L. Vaux

Résumé ou plan du cours :

Le cours se propose d'exposer certains développements de la logique
contemporaine intégrant le langage des catégories comme un outil de
description, de compréhension ou de conception. Historiquement motivée
par la recherche fondamentale en logique et pour la conception
des langages de programmation, cette approche est aujourd’hui vivante
dans la pratique de la programmation fonctionnelle.

Le cours sera éclairé par de nombreux exemples tirés des mathématiques
(algèbre, ordres, topologie, etc.) et de l'informatique (automates,
structures de données, programmation fonctionnelle, etc.).

Progression :

1 Théorie des catégories
1.1 Catégories, foncteurs, transformations naturelles
1.2 Limites et colimites
1.3 Adjonctions et monades

2 Catégories cartésiennes fermées
2.1 Catégories monoidales
2.2 Catégories cartésiennes fermées et lambda-calcul simplement typé
2.3* Modèles du lambda calcul pur (objets réflexifs)

3 Logique catégorique
3.1 Logique intuitionniste d'ordre supérieur
3.2* Théorie des ensembles intuitionniste
3.3 Modèles de réalisabilité
3.4 Objet de valeur de vérité dans une catégorie et topos

* : selon le temps à disposition.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Sémantique dénotationnelle et logique linéaire

Intervenants potentiels : Emmanuel Beffara, Myriam Quatrini, Laurent
Regnier, Lionel Vaux.

Résumé ou plan du cours :

Dans une première partie le cours présente la sémantique dénotationnelle
à partir de la notion d'espace cohérent, qui est à l'origine de la
logique linéaire, dont on étudiera les propriétés. On présentera
notamment le calcul des séquents de la logique linéaire, ainsi que la
notion de réseau de preuve, qui fournit une approche asynchrone de
l'élimination des coupures. On termine le cours par une ouverture
à des sujets plus contemporains.

Plan :

  1. Le modèle cohérent du λ-calcul.
  2. Logique linéaire : calcul des séquents et élimination des coupures.
  3. Réseaux de preuve et séquentialisation : le cas multiplicatif.
  4. Exponentielles dans les réseaux.
  5. Prolongements (au choix, en fonction du temps et des
     intervenants) :
      a. Au-delà du cas purement fonctionnel : opérateurs de contrôle ;
         concurrence.
      b. Sémantique quantitative et développement de Taylor.
      c. Focalisation et recherche de preuve.
      d. Ludique.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Réalisabilité classique

Intervenants potentiels : Emmanuel Beffara, Laurent Regnier, Lionel Vaux

Résumé ou plan du cours :

On commencera par rappeler les principes de la réalisabilité intuitionniste
dans le cadre de l'arithmétique du second ordre, la présentation de la machine
de Krivine pour le lambda-calcul avec continuations et son utilisation pour
étendre la réalisabilité intuitionniste à la logique classique.

On passera ensuite aux résultats de base de la théorie : réalisation du schéma
de récurrence, terme de stockage, réalisation des formules du premier ordre de
l'arithmétique.

Si le temps le permet on abordera les extensions au cadre de la théorie des
ensembles et l'on verra comment la réalisabilité peut être vue comme une
extension du forcing permettant de construire des modèles inédits de ZFC.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Algorithmique Distribuée

Intervenants potentiels :
J. Chalopin, S. Das, E. Godard, D. Imbs, A. Labourel

Résumé ou plan du cours :

L'objectif de ce cours est de présenter des problèmes fondamentaux
d'algorithmique distribuée, ainsi que des résultats de calculabilité et de
complexité associés. On utilisera des méthodes algorithmiques pour résoudre ces
problèmes classiques et des méthodes combinatoires et topologiques pour montrer
des résultats d'impossibilité et des bornes inférieures de complexité

0. Modèlisation des Systèmes Distribués
   - Panorama des systèmes distribués
   - Calculabilité distribuée
   - Equivalence entre modèles
   - Vers un modèle unifié ?

1. Systèmes à passages de messages
   - Modèles de communication
   - Algorithmes pour la diffusion et l'élection
   - Algorithmes probabilistes pour les réseaux anonymes

2. Mémoire partagée
   - Impossibilité du consensus sans attente
   - Modèle du snapshot itéré et impossibilité du k-consensus
   - Diffusion tolérante aux défaillances
   - De la mémoire partagée aux réseaux dynamiques

3. Agents mobiles
   - Modèles et mesures de complexité
   - Exploration et rendez-vous

Selon les années et les intervenants, l'importance relative de ces différents
thèmes pourra varier.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Combinatoire des mots

Intervenants potentiels : Julien Cassaigne

Résumé ou plan du cours :
- Combinatoire des mots finis (morphismes, codes, conjugaison, periodicité)
- Combinatoire des mots infinis (mots morphiques, récurrence, complexité,
  graphes de Rauzy)
- Quelques applications (en dynamique, en théorie des nombres)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Vérification : de la théorie à la pratique

Intervenants potentiels : C. Bertolissi, D. Lugiez, R. Morin, JM Talbot,
B. Monmege, PA Reynier, M. Shirmohammadi

Résumé ou plan du cours :

L’objectif du cours est de montrer une ou plusieurs approches de type « méthode
formelle » pour la vérification et/ou la synthèse. Il s’agira de présenter aux
étudiants les bases théoriques sur lesquelles repose l’approche en question, et
d’aller, dans la mesure du possible, jusqu’à la présentation d’outils logiciels
existants.

* Vérification et synthèse de systèmes temps-réel : automates et jeux
  temporisés, extensions à coûts et robustesse, logiciel UppAal TiGa

* Vérification de protocoles cryptographiques : logique de séparation, logiciel
  ProVerif

* Analyse et conception de systèmes distribués : théorie des traces de
  Mazurkiewicz, MSC, réseaux de Petri

* Synthèse à partir de spécifications LTL : logique LTL, jeux de parité,
  extensions temps-réel

* Sécurité de workflow : modélisation de politiques de sécurité et leurs
  propriétés, applications au contrôle d accès dans les processus métiers

Selon les années et les intervenants, la liste des problèmes étudiés et
l'importance relative des différentes notions pourra varier.

Prérequis: Un intérêt pour les automates, la logique et l'algorithmique. Toutes
les notions utilisées dans le cours seront définies et expliquées.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Théorie des automates : extensions et applications

Intervenants potentiels : N. Baudru, S. Fratani, B. Monmege, JM Talbot, PA
Reynier, M. Shirmohammadi

Résumé ou plan du cours :

L’objectif du cours est de présenter une ou plusieurs extensions du modèle
classique des automates finis, en insistant sur les résultats positifs obtenus
pour cette extension, les applications visées par cette extension, ainsi que
les enjeux actuels.

* Automates pondérés : équivalences entre automates et logiques, résultats de
  décidabilité, modèles pour les arbres et pour les mots, automates
  probabilistes

* Transducteurs : modèles unidirectionnels et bidirectionnels, modèle des SST,
  déterminisation et fonctionnalité

* Ordre supérieur : langages indexés, langages d’ordre supérieur, automates à
  piles de piles

Selon les années et les intervenants, la liste des problèmes étudiés et
l'importance relative des différentes notions pourra varier.

Prérequis: Un intérêt pour les automates, la logique et l’algorithmique. Toutes
les notions utilisées dans le cours seront définies et expliquées.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Modélisation et simulation à événements discrets

Intervenants potentiels : L. Brenner, I. Demongodin, C. Frydman, A. Hamri

Résumé ou plan du cours :

Ce cours porte sur les méthodes de spécification des systèmes complexes et les
formalismes à événements discrets. Afin de maîtriser la spécification
comportementale de ces systèmes, ce cours présente les formalismes permettant
une spécification de haut niveau. Il fournit les bases théoriques en
modélisation, analyse, simulation à événements discrets pour les domaines de
l’informatique et des systèmes dynamiques complexes.

Plan de cours :

Présentation de divers formalismes à événements discrets avec et sans
représentation du temps :

* DEVS : Discrete EVent System Specification
* RdP : Réseaux de Petri

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Théorie algorithmique des nombres

Intervenants potentiels: Yves Aubry, Stéphane Ballet, David Kohel, Stéphane
Louboutin, Serge Vladut

Résumé ou plan du cours:

La théorie computationnelle des nombres suscite de plus en plus d’intérêt au
sein de la société en raison de son utilité dans le domaine de la sécurité
informatique en générale. L’utilisation d’algorithmes mettant en oeuvre des
objets mathématiques de plus en plus sophistiqués nécessite en amont une
approche de la théorie algorithmique des nombres orienté vers l’effectivité.

Dans ce cours, nous nous proposons donc d’étudier des algorithmes ou méthodes de calculs en géométrie algébrique effective :

- algorithmique dans les corps finis
- arithmétiques efficaces sur les courbes elliptiques
- calculs explicites dans les espaces de Riemann-Roch définis sur des corps
  finis
- arithmétique des algèbres de quaternions et courbes de Shimura
- calculs explicites dans les corps de nombres

Nous illustrerons le cours par des calculs en Sage et/ou Magma.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Théorie de l'information : Algorithmique pour la cryptographie et le
codage

Intervenants potentiels: Stéphane Ballet, Alexis Bonnecaze, Ignacio
Garcia-Marco, David Kohel

Résumé ou plan du cours :

Les outils mathématiques utilisés en cryptographie et codage évolue pour
s'adapter à la puissance des ordinateurs et des services demandés.  C'est
particulièrement vrai en ce qui concerne la cryptographie asymétrique dont la
sécurité repose sur la difficulté de résoudre certains
problèmes. L'introduction des courbes elliptiques a permis de réduire la taille
des clés tout en gardant un niveau de sécurité identique. Les pairings ont
permis d'obtenir de nouvelles primitives cryptographiques et ont en particulier
amené la cryptographie basée sur l'identité. Le futur est actuellement
principalement incarné par des outils basés sur des propriétés de la physique
quantique.

L'objectif de ce cours est de présenter ces outils théoriques ainsi que leurs
applications en cryptographie et codage, et de s'intéresser à certaines
implémentations en langages Sage, Magma et C.

Plan du cours :
- Introduction
- Problèmes difficiles (DLP, factorisation, CDH, DDH, etc)
- Courbes elliptiques pour la cryptographie
- Pairings et IDBased crypto
- Introduction à la cryptographie post-quantique
- Introduction au codes correcteurs d'erreurs quantiques


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Introduction aux systèmes dynamiques et à la théorie ergodique

Intervenants potentiels : il y a le choix! (par exemple : Pierre Arnoux,
Arnaud Hilion, pour ne donner que les noms de ceux qui se sont exprimés
explicitement dans une suite emails récents)

Résumé ou plan du cours :

1. Théorie ergodique
   - Systèmes dynamiques mesurables. Exemples issus de la géométrie, de la
     dynamique symbolique et de la théorie des nombres.
   - Théorème de récurrence de Poincaré. Théorèmes ergodiques de von Neumann et
     de Birkhoff.
   - Propriétés ergodiques : ergodicité, mélange faible et théorie spectrale,
     mélange fort. Classification des systèmes à spectre discret. Entropie
     métrique.

2. Dynamique topologique
   - Systèmes discrets (fonction) et systèmes continus (flots).
   - Systèmes dynamiques topologiques. Point fixe, périodique,
     récurrent. Ensemble errant et non-errant, transitivité topologique, mélange
     topologique, minimalité, entropie topologique. Exemples.

3. Quelques constructions classiques
   - Application de premier retour d'un flot sur une section.
   - Suspension d'une application avec temps de retour donné.
   - Extension naturelle au sens de Rokhlin.
   - Construction de mesures invariantes.
   - Application à des problèmes de géométrie, de théorie des nombres et de
     combinatoire: du billard aux fractions continues, au flot géodésique sur la
     surface modulaire et aux substitutions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Théorie de Ramsey

Intervenants potentiels : Lionel Nguyen Van Thé

Résumé ou plan du cours :

1) Théorème de Ramsey, fini et dénombrable.
   - Applications : Théorèmes d'Erdos-Szekeres sur les sous-suites monotones,
     et sur les polygones convexes du plan.
   - Bornes : Bornes sup et double récurrence, borne inf et méthode
     probabiliste.

2) Théorèmes de partition en théorie des nombres :
   - Théorème de Schur.
   - Théorème de Rado sur les systèmes d'équations régulières par partitions.
   - Théorème de van der Waerden, via le théorème de Hales-Jewett.

3) Théorie de Ramsey euclidienne :
   - Ensembles de Ramsey du plan: Tout ensemble de Ramsey est sphérique.
   - Nombre chromatique du plan. Prétexte de ce probème pour évoquer la
     pertinence de l'axiomatique de la théorie des ensembles.

4) Théorie de Ramsey infinie : (le but de cette partie sera surtout de
poursuivre la réflexion sur la pertinence de la théorie des ensembles en tant
que cadre axiomatique)
   - Théorème de Hindman, via les ultrafiltres.
   - Théorème de Galvin-Prikry.
   - Le rôle de l'axiome du choix et des axiomes de détermination.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : Dynamique symbolique

Intervenants potentiels : Pierre Guillon, Guillaume Theyssier, Nicolas Bédaride
voire Arnaud Hilion, Pierre Arnoux, Kevin Perrot, Sylvain Sené, Julien
Cassaigne (ou une sous-partie de ça ; je mets plein de noms au cas où on
veuille combiner avec d'autres propositions -même si ce n'est vraiment naturel
pour aucune peut-être mais peut-être qu'on veut quand même partager)

Résumé ou plan du cours :

Dynamique symbolique 1D : sous-décalages, sofiques, SFT, représentation par
graphes, lien avec la combinatoire des mots, représentation matricielle,
propriétés dynamiques topologiques, entropie topologique

Dynamique symbolique 2D : pavages apériodiques, hiérarchie, problème du pavage
du plan, simulation Turing, indécidabilité, systèmes substitutifs

Ouverture sur thématiques avancées : dynamique symbolique mesurée, dynamique
symbolique sur les groupes, dynamique directionnelle et automates cellulaires
(ou une sous-partie de ça).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Intitulé : ASP : fondements théoriques, calcul et applications

Intervenants potentiels : Eric Würbel, Belaid Benhamou, Farid Nouioua (?),
Vincent Risch

Résumé ou plan du cours :

ASP est un paradigme de représentation et de raisonnement sur les
connaissances, apparu il y a une vingtaine d'années, et qui connaît
actuellement un développement important de par l'existence de solveurs
efficaces. Le but de cette option est d'étudier ASP sous ses angles théoriques,
calculatoires, et pratiques.

- fondements théoriques :
   modèles stables, non-monotonie
   equilibrium logics, équivalences de programmes
   sémantiques modales

- calcul des modèles stables :
   solveurs de type branch and bound
   solveurs basés sur la recherche de conflits

- applications :
   ASP en pratique
   méthodologies de développement

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%