ER03: Problèmes de satisfaction de contraintes

21-25 Janvier 2013, ENS Lyon.

Orateurs: Manuel Bodirsky, Michael Pinsker.

Une description plus complète se trouve sur la version anglaise de cette page.

Lundi 21/01. Introduction. Exemples de CSPs de l’intelligence artificielle. Les formules primitives positives et des preuves de NP-difficulté. Des algorithmes efficaces. La conjecture de Feder et Vardi.

Mardi 22/01. L’approche d’algèbre universelle. La correspondance de Galois Inv-Pol, le noyau d’une structure, la conjecture de faisabilité, les operations cycliques.

Mercredi 23/01. Des CSPs sur des domaines infinis. Les limites de Fraïssé, le théorème de Ryll-Nardzewski. La correspondence Inv-Pol sur des domaines infinis. La topologie de convergence simple. Les graphes de Henson et autres exemples.

Jeudi 24/01. Introduction à la théorie de Ramsey. Fonctions canoniques. Classification de problèmes de Graph-SAT

Vendredi 25/01. Problèmes ouverts, projets de recherche.

Inscription

Inscription gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 8 janvier en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternatvement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à research.school.1@gmail.com, avec le sujet « Registration form — research school 3 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school ‘Constraint satisfaction problems’, taking place at ENS Lyon, from Jan. 21 to Jan. 25.

Géométrie discrète et images numériques

Programme de l’UE

L’objectif de ce cours est d’introduire les notions de base d’analyse et de traitement d’images. Après quelques séances durant lesquelles on se focalisera sur des problèmes de représentation de données, on se focalisera plus particulièrement sur des problèmes algorithmiques et théoriques liés à l’analyse géométrique de formes numériques. Ainsi, on sera amené à s’intéresser des outils de géométrie discrète, de géométrie algorithmique voire d’arithmétique et de combinatoire.

Le cours sera accompagné de séances de TP ayant comme objectif de s’intéresser à l’implémentation de certains outils théoriques présentés dans le cours.

Plan indicatif:

  • Représentation images/formes
  • Traitement et analyse d’images (filtrage, segmentation)
  • Géométrie discrète pour l’analyse de formes
  • Géométrie algorithmique et structures de données

Pré-requis: Des connaissances élémentaires en algorithmique

Livres:

  • « Géométrie discrète et images numériques », D. Coeurjolly, A. Montanvert and J.-M. Chassery, Ouvrage collectif, Traité IC2, Hermès, 416 pages, 2007
  • « Computational Geometry: Algorithms and Applications », Mark de Berg, TU Eindhoven (the Netherlands) Otfried Cheong, KAIST (Korea),Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands), Springer-Verlag

Fiche d’évaluation

Intervenants

Cryptographie et sécurité

Programme de l’UE :

La cryptographie a pour objectif de sécuriser les communications, en présence de parties malhonnêtes. Cette discipline a de nombreux liens avec l’informatique théorique (théorie de la complexité, preuves de sécurité) mais également de nombreuses retombées pratiques : Les protocoles cryptographiques sont omni-présents dans la vie quotidienne (commerce électronique, cartes de paiement, vote électronique, etc).

Ce cours est une introduction aux différents aspects de la cryptographie contemporaine. Nous aborderons les thèmes suivants :

  • Chiffrement symétrique
  • Chiffrement asymétrique
  • Fonctions de hachage cryptographiques
  • Authentification
  • Générateurs pseudo-aléatoires
  • Preuves à divulgation nulle de connaissance
  • Infrastructure de clés publiques
  • Crytanalyse
  • Sécurité prouvée
  • Partage de secret

Nous décrirons également plusieurs applications pratiques des concepts théoriques développés : PGP, TLS/SSL, vote électronique.

Intervenants

Analyse de programmes et vérification de systèmes

Programme de l’UE :

  1. Structures ordonnées
    Ordres et topologies. Points fixes. Approximations et correspondances de Galois. Domaines de Scott
  2. Sémantiques dénotationnelles
    Domaines d’interprétation. Sémantique directe et par continuations.

    Correction et complétude de la Sémantique Axiomatique.
  3. Analyse de programmes
    3.1. Analyses dynamique et statique. Systèmes de types.

    3.2. Interprétation abstraite : principes, élargissement/rétrécissement,
    analyses avant et arrière, analyse polyédrale.
  4. Vérification
    4.1. Logiques modales. Structures de Kripke. Model checking.

    4.2. Systèmes réactifs. Logiques temporelles LTL et CTL.

Intervenants

ER 04 (2011) : Separation logics and applications

Cette école de recherche se déroulera durant la semaine 31 janvier – 4 février 2011. Les cours de cette école seront dispensés en anglais.

Intervenants:

  • Hongseok Yang (Lecturer, Queen Mary University of London, UK)
  • Alexey Gotsman (Assistant Professor, IMDEA, Spain)
  • Matthew Parkinson (Researcher, Microsoft Research, Cambridge, UK)

Voir la version anglaise de cette page pour un descriptif du cours, et des informations à jour (remarque importante: les cours seront dispensés en anglais).

Responsable local: Daniel Hirschkoff (LIP), avec l’aide bienveillante d’Etienne Lozes (LSV).