Complexité algorithmique

Programme de l’UE

What computing resources do we need to solve a computational problem? The computational complexity theory studies this question from a structural point of view. Building up on the Turing machine model, we will discover and study deterministic and nondeterministic complexity classes, space and time complexity and hierarchy, completeness, randomized algorithms classes, boolean circuits and counting classes.

 

Bibliography:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak (mostly chapters 1 to 7)

more about computational complexity

 

De quelles ressources avons nous besoins pour résoudre un problème, faire un calcul ? La théorie de la complexité algorithmique étudie ce problème d’un point de vue structurel. En nous appuyant sur le modèle des machines de Turing, nous étudierons les classes de complexité déterministes et non déterministes, en temps et en espace, les hiérarchies entre ces classes, les problèmes complets, les algorithmes et classes probabilistes, les classes définies par les circuits ainsi que quelques notions sur les classes de comptage.

 

Bibliographie :

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, principalement les chapitres 1 à 7

Pour en savoir plus sur la théorie de la complexité algorithmique

https://fr.wikipedia.org/wiki/Théorie_de_la_complexité_(informatique_théorique)

Page du cours (for 2013-2014)

Intervenants

  • Omar Fawzi, MdC ENS Lyon

CB-03 : Arithmétique des ordinateurs

Programme de l’UE

L’arithmétique des ordinateurs s’intéresse à la fois à la conception d’opérateurs arithmétiques, et à leur utilisation fine pour réaliser des fonctions plus complexes.

Ce cours présente un panorama des représentations utilisées en machine pour manipuler les nombres entiers, les réels et les polynômes, ainsi que l’algorithmique associée à chaque représentation pour réaliser les opérations de base (addition, multiplication, division, racine carrée… ) et calculer des fonctions « élémentaires » (logarithme, exponentielle, fonctions trigonométriques, etc.).

On s’intéressera d’abord à la manipulation de nombres en « précision fixée » (entiers, virgule flottante, norme IEEE 754) ainsi qu’à diverses techniques permettant d’augmenter ou de garantir la précision des calculs: on montrera ainsi qu’une arithmétique « approchée » comme la virgule flottante permet de faire des calculs exacts.

On étudiera ensuite la complexité et l’algorithmique des opérations de base sur les polynômes (multiplication, division, évaluation, interpolation), en arithmétique exacte.

Enfin, nous aborderons la question du calcul sur les polynômes en arithmétique approchée. Cela permettra d’une part de présenter les notions fondamentales de conditionnement d’un problème et de stabilité d’un algorithme et, d’autre part, de comprendre pourquoi l’évaluation polynomiale est de plus en plus souvent au coeur des implantations (logicielles ou matérielles) d’opérateurs arithmétiques de base comme la division ou la racine carrée.

Intervenants

  • Jean Michel Muller, DR CNRS (http://perso.ens-lyon.fr/jean-michel.muller/)
  • Claude Pierre Jeannerod, CR INRIA (http://perso.ens-lyon.fr/claude-pierre.jeannerod/)

Quelques ouvrages de référence

  • Ercegovac et Lang, Digital Arithmetic, The Morgan Kaufmann Series in Computer Architecture and Design, 2004
  • D.E. Knuth, The Art of Computer Programming, Volume 2, Addison Wesley 1997
  • Muller, Arithmétique des Ordinateurs, Masson, 1989 (texte intégral accessible à http://prunel.ccsd.cnrs.fr/ensl-00086707)
  • J. von zur Gathen et J. Gerhard, Modern Computer Algebra, Cambridge 2003.
  • Muller, Elementary functions, algorithms and implementation, 2ème édition, Birkhauser, 2006
  • P. Burgisser, M. Clausen, et M.A. Shokrollahi, Algebraic Complexity Theory, Springer 1997.
  • Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Seconde édition, Août 2002
  • Muller, Brisebarre, de Dinechin, Jeannerod, Lefèvre, Melquiond, Revol, Stehlé et Torrès, Handbook of Floating-Point Arithmetic, Birkhauser, 2010

Algorithmique et programmation parallèles

Programme de l’UE

Le parallélisme est devenu incontournable en informatique, le moindre processeur étant multi-cœurs. Cette UE a pour objet la conception d’algorithmes parallèles efficaces et leur mise en œuvre pratique.
Les séances de cours auront pour objet les modèles théoriques utilisés pour la conception et l’analyse des algorithmes et l’étude de problèmes algorithmiques particuliers (complexité, définition et analyse d’algorithmes, algorithmes d’approximations, etc.).
Les séances de cours seront accompagnées de six séances de TDs et de six séances de TPs. Les TPs auront pour but l’initiation à la programmation parallèle par passage de messages (MPI).

Plan indicatif des cours:

– Modèle théorique des réseaux de tri
– Modèle théorique des PRAMs
– Algorithmique sur anneau et grille de processeurs: produit matrice-vecteur, produit matrice-matrice, stencil 2D, etc.
– Ordonnancement de graphes de tâches avec et sans communications, avec ou sans contraintes de ressources: complexité, algorithmes d’approximations et heuristiques
– Analyse de dépendance et parallélisation automatique
– Exemple d’algorithme pour GPU

La note de contrôle continu est établie à partir d’un partiel organisé en milieu de semestre et d’un devoir à la maison de programmation.

Intervenants

Evaluation de performance

Programme de l’UE

L’objectif principal de ce cours est de présenter les techniques de base servant à l’évaluation qualitative et quantitative des performances de systèmes de communication et informatiques. L’accent sera mis sur les aspects théoriques mais sera illustré par l’analyse de plusieurs exemples de systèmes réels (réseaux de communication, de transport, de logistique). Ce cours comprendra aussi une introduction aux statistiques et abordera des questions de méthodologie expérimentale.

Plan indicatif :

  1. Rappels de probabilités
  2. Schémas de simulation & génération aléatoire
  3. Chaînes de Markov à temps discret
  4. Chaînes de Markov à temps continu & Files d’attente
  5. Processus de décision markoviens
  6. Réseaux de Petri
  7. Statistiques

Intervenants

Pré-requis

  • Des connaissances élémentaires de probabilités sont fortement recommandées (typiquement cf le cours « Probabilités » du L3 Informatique dont le contenu est décrit dans les pages L3)

Réseaux

Programme de l’UE :

Le but de ce cours est de présenter certains fondements des réseaux, dans son fonctionnement mais aussi des points de vues algorithmique et
d’évaluation de performances. Le module s’articule autour d’une présentation de l’architecture de l’Internet et des protocoles réseaux,
et des outils/méthodologie d’évaluation de performances. Les notions abordées lors de ce cours sont les suivantes :

  • Notions, principes et les architectures réseaux.
  • Algorithmes d’accès à un médium de communication
  • Méthode statistique pour l’évaluation des performances
  • Evaluation des performances des réseaux sans fil
  • Principe de l’IP et de l’Internet
  • Notions avancés de routage
  • Algorithmes des protocoles de transport (TCP, partage, performance)

Modalité d’évaluation

  • Examen écrit
  • TP ou Mini-projet

Fiche d’évaluation

Intervenants

Compilation

Programme de l’UE

Le compilateur est un outil fondamental pour l’informaticien, qui se situe au coeur de tout développement informatique. Le but de ce cours est de donner aux étudiants une compréhension globale du fonctionnement d’un compilateur en présentant les aspects fondamentaux de la compilation de code natif pour les langages impératifs et à objets. Un accent particulier sera mis sur les méthodes d’analyse sémantique et d’optimisation de programmes utilisées dans les compilateurs récents (icc, gcc, etc). Ces notions de base seront complétées par un panorama des développements récents de la recherche dans le domaine. Enfin, on insistera sur la mise en oeuvre logicielle des différents aspects de la compilation à travers l’écriture d’un compilateur pour un langage impératif simple dans le cadre des travaux pratiques.

Voir la page www du cours.

Plan indicatif du cours

  1. Analyse lexicale
    Automates finis, théorie des analyseurs lexicaux, optimisations, outil Lex.
  2. Analyse syntaxique
    Grammaires algébriques, analyse descendante/ascendante, gestion des erreurs, outil Yacc.
  3. Grammaires attribuées
    Evaluation dynamique, test de Kennedy-Warren, grammaires S-attribuées, schémas de traduction.
  4. Compilateur simple
    Organisation de la mémoire, traduction dirigée par la syntaxe, algorithme de Sethi-Ullman.
  5. Fonctions
    Activations, pile de controle, conventions d’appel, fonctions imbriquées.
  6. Production de code intermédiaire
    Représentations intermédiaires, forme SSA, optimisations élémentaires.
  7. Sélection d’instructions
    Pavage, complexité, programmation dynamique, algorithme de Koes & Goldstein
  8. Allocation de registres
    Interférences, coalescing, complexité, algorithmes « historiques » (Chaitin, Briggs), algorithmes de référence (IRC, Linear scan).
  9. Analyse de programme
    Analyse statique/dynamique, complexité, analyse de flot de données, exemples, limites.
  10. Compilation polyédrique
    Contrôle statique, opération, analyse de dépendences, ordonnancement, génération de code.
  11. Compilation des langages à objet
    Descripteurs, liaison dynamique, résolution des méthodes abstraites, héritage multiple.

Références

  1. Modern compiler implementation in C. Andrew Appel. Cambridge press.
  2. Compilers: principles, techniques and tools. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman. Interéditions.
  3. Parsing theory, volumes I et II. Seppo Sippu and Eljas Soisalon-Soininen. EATCS Monographs on Theoretical Computer Science.
  4. Principles of program analysis. Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Springer.
  5. Theory of linear and integer programming. Alexander Schrijver. Wiley.

Intervenants

Systèmes distribués

Résumé

Cet enseignement se focalise sur les aspects algorithmiques des systèmes distribués (ou répartis). La mise en œuvre d’algorithmes distribués pour résoudre les problèmes de communication, d’allocation de ressources et de synchronisation seront abordés. Ainsi les  les problèmes d’élection de leader, les algorithmes à vagues, la détection de terminaison, les algorithmes de routages, la tolérance aux fautes, l’auto-stabilisation, etc. sont autant d’illustrations des points qui seront abordés dans cet enseignement. Différents types de mise en oeuvre de systèmes distribués seront également abordés au travers d’ERLANG, de CORBA ou encore de l’intergiciel DIET.

Intervenants

  • Eddy Caron, MdC ENS Lyon
  • Vincent Lanore, doctorant ENS Lyon

Langue

Anglais ou Français en fonction de la demande.

ER-01 (2010) : Algorithmes pour l’approximation géométrique

du 11 au 15 janvier 2010 — ENS Lyon

Objectifs

De plus en plus de domaines comme la biologie, l’analyse statistique ou l’apprentissage automatique, ont à traiter des données qui sont en fait des nuages de points dans des espaces de grandes dimensions. Ces données sont porteuses de caractéristiques topologiques et géométriques qui traduisent les propriétés des systèmes modélisés. Par exemple, la densité du nuage de points peut être concentrée autour d’une variété de dimension intrinsèque bien inférieure à celle de l’espace ambiant. Extraire une telle information n’est pas une tâche facile. Tout d’abord les données sont généralement bruitées, Ensuite, les structures et algorithmes de la géométrie algorithmique ont souvent des complexités exponentiellement croissantes en fonction de la dimension et passent mal à l’échelle pour ce type de données.

Ce cours propose une introduction à la géométrie algorithmique, axée sur les problématiques de l’approximation et de l’échantillonnage des objets géométriques. Il part de certains concepts classiques (enveloppe convexe, diagrammes de Voronoi) et aborde des méthodes récemment développées (core sets, persistance topologique) pour approcher les propriétés géométriques et topologiques des objets en dimensions supérieures, tout en évitant l’explosion exponentielle de la complexité, lié à la dimension.

Intervenants :

  1. Jean-Daniel Boissonnat
  2. Frédéric Chazal
  3. Mariette Yvinec

Plan du cours

Algorithmes pour l’approximation géométrique

  1. Structures métriques pour les ensembles de points
    • Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat)
    • Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal)
    • Algorithmes randomisés et core sets (M. Yvinec)
  2. Approximation simpliciale de variétés
    • Génération de maillage par raffinement de Delaunay (M. Yvinec)
    • Triangulation de Delaunay restreinte, epsilon-échantillons et génération
      de maillage de surfaces (J.-D. Boissonnat)
    • Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat)
  3. Inférence géométrique (F. Chazal)
    • Théorie de l’échantillonnage des compacts
    • Homologie persistante et analyse de données

Prérequis

Le cours ne suppose pas de prérequis. Toutes les notions fondamentales de géométrie algorithmique utilisées dans le cours seront exposées au préalable.

Bibliographie

  • M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
  • J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces, Springer-Verlag, 2006.
  • J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
  • F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled « Tesselations in the Sciences », November 2007.
  • F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compacts in Euclidean Space, Proceedings of the 22nd ACM Symposium on Computational Geometry 2006.
  • E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
  • K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
  • A. Zomorodian, Topology for Computing, Cambridge Monographs on Applied and Computational Mathematics, cambridge University Press, 2005.

Inscription

Il n’y a pas de frais d’inscription. Pour des questions d’organisation, il est toutefois nécessaire de s’inscrire en ligne ; [inscription fermée].

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal de la partie « sciences exactes » de l’ENS Lyon).

Un emploi du temps possible est le suivant:

  • Lundi 11 janvier
    • 14h-17h. Enveloppes convexes, diagrammes de Voronoi et triangulations de Delaunay (J.-D. Boissonnat).
      Transparents disponibles ici puis ici.
  • Mardi 12 janvier
    • 8h30 – 11h30. Génération de maillage par raffinement de Delaunay (M. Yvinec).
      Transparents disponibles ici puis ici.
    • 13h30 – 16h30. Triangulation de Delaunay restreinte, epsilon-échantillons et génération de maillage de surfaces (J.-D. Boissonnat).
      Transparents disponibles ici.
  • Mercredi 13 janvier
    • 8h30 – 11h30. Réduction de dimension, recherche approchée de plus proches voisins, l’algorithme k-means (F. Chazal).
      Transparents disponibles ici.
    • 13h30 – 16h30. Algorithmes randomisés et core sets (M. Yvinec).
      Transparents disponibles ici puis ici.
  • Jeudi 14 janvier
    • 8h30 – 11h30. Théorie de l’échantillonnage des ensembles compacts (F. Chazal).
      Transparents disponibles ici.
  • Vendredi 15 janvier
    • 8h30 – 11h30. Reconstruction de variétés en dimension 3 et en dimension supérieure (J.-D. Boissonnat).
      Transparents disponibles ici.
    • 13h – 16h. Homologie persistante et analyse de données (F. Chazal).
      Transparents disponibles ici.

Correspondants locaux

Un certain nombre d’informations utiles se trouve sur la page principale des écoles de recherche en informatique fondamentale de l’ENS Lyon.

ER-02 (2010) : Graphes et optimisation combinatoire

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2,cours3)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

  • méthodes inductives (Thomassen)
  • déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

  • constructions
  • méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

  • méthodes algébriques (Borsuk-Ulam)
  • méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

  • Introduction du concept de graphes parfaits
  • Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
  • utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
  • Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
  • Exemples de graphes triangulés: graphes d’intervalles, graphes « splits ».

Cours 2 (Vendredi 9h30-12h45):

  • Relation entre nombre chromatique et orientation (Gallai-Roy)
  • graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
  • théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

  • Flot maximum
  • Algorithme « Push-Relabel » et flots paramétriques.
  • Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

  • Flot de coût minimum.
  • Les k-flots non nuls.
  • Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

  • Quelques modèles d’optimisation combinatoire.
  • Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

  • Algorithme de l’intersection de deux matroïdes.
  • Applications.

Cours 3 (Mercredi 14h-16h)

  • Algorithme de couplage de cardinalité maximum (Edmonds).
  • Théorème de caractérisation lié (Tutte-Berge).
  • Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)

ER-03 (2010): Game theory for networks

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

Location and schedule

All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).

Schedule:

  • Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
    Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc.  We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value.   Solution of 2 by 2 matrix games.
    Non-zero sum games. We present the notion of Nash equilibrium as   well as epsilon Nash equilibrium. We then introduce    Coordination Games and present their properties. We then study    Lemke’s algorithm for computing the equilibrium in non-zero sum games    with two players. We present examples of channel selection games.   We end this part with the concept of Correlated equilibrium

    Afternoon: Corinne Touati 14h30 – 17h00
    Notions from cooperative game theory: Bargaining and fairness.
    Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
    1. Optimalité
    a. Définition de Pareto et notions liées
    b. Propriétés des ensembles de Pareto (par ex. compacité)
    c. Epsilon-approximation et méthodes de résolutions
    d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.

  • Tuesday 26/01/10  Morning: Corinne Touati 10:30 – 12:30
    2. Fairness and Nash bargaining.
    a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
    b. Equivalent optimizations and properties
    c. Alpha fairness
    d. Algorithmic solutions.
    e. Application to flow control and TCP.
    3. Performance evaluation of the resource allocation:
    a. The Gain index,
    b. Price of anarchy
    c. Selfish Degradation Factor
    d. Pareto equilibrium

    Afternoon: Eitan Altman 14:00 – 16:30
    Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria,   The strict diagonal concavity property (which extends concavity    to a game context). This notion is used to establish    uniqueness of equilibrium in convex games.
    We then introduce games with coupled constraints    as in Rosen, as well as the related    notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.

  • Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
    Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
    Medium access games: the aloha game.

    Afternoon Rachid El-Azouzi 14:00 – 17:00
    Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
    Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
    Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.

  • Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
    Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
    Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.

    Afternoon: Corinne Touati 14:00 – 17:00
    Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence

  • Friday 29/01/10Morning: Eitan Altman  11:00  – 13:00
    The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium.  Parallel links. Load balancing problems. Relation to Ad-hoc networks.

    Afternoon: Eitan Altman 14:30 – 17:00
    Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.

Correspondant local

  • Paulo Goncalves

ER-04 (2010) : Nouveaux paradigmes de calcul : modèles physiques de calcul, algorithmique efficace

Du 1er au 5 février 2010 — ENS Lyon

Intervenants :

Emploi du temps: (Salle Amphi B de l’ENS-Lyon)

  • Première partie: Lun. 14:00-18:00, Mar. 14:00-18:00, Merc. 9:00-13:00.
  • Deuxième partie: Merc. 14:00-17:00, Jeu. 9:00-12:00 & 14:00-17:00, Ven. 9:00-12:00.

Résumé du cours : 
Notre compréhension de ce qu'est un ordinateur (modèles de calculs) et de la manière
 dont il peut résoudre des problèmes mathématiques(algorithmique) est en évolution
 constante. Au-delà de l'approche traditionnelle, essentiellement fondée sur des
 systèmes déterministes et discrets (automates etc.) , une nouvelle vision émerge
 et qui se saisit des phénomènes probabilistes (aléatoire, approximation) et  même
 des phénomènes quantiques (interférence, enchevêtrement) en les concevant non plus
 comme des difficultés à surmonter, mais comme de nouveaux outils offrant des
perspectives remarquables. Quelles sont les limites de l'approche traditionnelle et
 qui sont franchies grâce à ces nouveaux outils? Jusqu'où peut-on éspèrer aller grâce
à eux?

Partie 1 (P.Arrighi, J.Degorre): Information quantique, causalité et automates cellulaires
La physique quantique a précisément mis en évidence des phénomènes extrêmement
 utiles pour représenter, traiter et communiquer l'information. Ceci a donné
 lieu dans les 15 dernières années à de splendides  résultats théoriques qui
 montrent que des performances quantitatives et qualitatives hors de portée de
 l'informatique classique deviennent alors possibles. Ainsi il est prouvé
qu'un ordinateur quantique  pourrait factoriser des nombres entiers en temps
 polynomial, ou bien rechercher un élément parmi une liste désordonnée de
 taille n en temps racine carrée de n.  Ces résultats menacent la
 cryptographie moderne; mais ce que la physique quantique prend d'une main
 elle le redonne de l'autre.  Ainsi des systèmes de transmission quantiques,
 déjà commercialisés, permettent d'obtenir une sécurité prouvée et
 inconditionnelle des communications. Ce cours effectuera d'abord tous les
 rappels nécessaires en algèbre linéaire. Les postulats de la mécanique
quantique seront introduits, puis les principaux concepts et résultats connus
 et ayant trait à la nature particulière et non-locale de l'information
 quantique.
Le cours sera alors axé vers la quête d'un modèle de calcul à la fois quantique et
 distribué, prenant en compte plusieurs des symmétries fondamentales de la physique
 (causalité, invariance par translation). C'est ce qui nous amènera à aborder des
 thèmes comme la causalité en mécanique quantique, les automates cellulaires dans
 un tel contexte, et la nature des relations entre physique et calcul.
Plan:
- Rappels d'algèbre linéaire
- Postulats de la théorie quantique
- Explorations sur la nature de l'information quantique (Algorithme de Deutsch,
Non-disctinction d'états non-orthogonaux, No-cloning, Codage Super-dense,
 Téléportation)
- Matrices de densité, opérateurs quantiques
- Enchevêtrement quantique (classification, boîtes non-locales)
- Opérateurs causaux et leur structure
- Automates cellulaires : trois définitions et leur équivalence
- définition axiomatique des automates cellulaires quantiques
- théorèmes de structure
- automates cellulaires quantiques universels
Partie 2 (F. Magniez): Algorithmique efficace
Le but du cours est d'aborder les techniques permettant d'élaborer des algorithmes
 efficaces  dans  plusieurs contextes. Les techniques reposent sur des outils
 probabilistes et d'approximation. Les contextes modélisent les contraintes
 exercées sur la machine concernant ses ressources (temps, espace,  aléa, requête,
 communication) et l'accès aux données (non contraint (random access) ou
séquentiel (streaming)).
Les domaines abordées seront donc :
- Marches aléatoires : k-SAT, (s,t)-CONNECTIVITY dans RL
- Graphes d'expansion (expander) : derandomizaton, (s,t)-CONNECTIVITY dans L
- Algorithmes d'approximation (approximation du résultat)
- Property testing (approximation sur l'entrée)
- Théorème PCP (version light) : application à des preuves de non approximation
- Streaming algorithms
- One-way communication complexity : application a des preuves de non
 existence de streaming  algorithms

Correspondant local
 Pablo Arrighi

ER-05 (2010) : Game semantics and linear logic

February, 8-12, 2010 — ENS Lyon

Lecturers :

Introduction

Linear logic was introduced by Jean-Yves Girard in 1986 as a
refinement of intuitionnistic logic. In the context of the
Curry-Howard correspondence between proofs and programs, linear logic
has renewed a lot of questions in proof theory in relation with the
semantics of programs.

Partly inspired by models of linear logic, game semantics provided in
1994 the first fully abstract model of the functional programming
language PCF. It has evolved towards the interpretation of various
additional programming features as well as applications to the
verification of programs.

These topics have evolved in two separate directions (proof theory for
linear logic, and programming semantics for game semantics) but with
many transfers of ideas between them along the past fifteen years.

Location and schedule

The lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building at 46, allée d’Italie).
Tentative schedule:

  • Monday, February 8:
    • 10:00 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Tuesday , February 9:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Wednesday, February 10:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Thursday, February 11:
    • 9:30 AM – 12:30 AM Linear logic
  • Friday, February 12:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 3:00 PM Game semantics

On thursday, Febr. 11 afternoon, the
Choco seminar , on related topics, might also interest the participants.

Course outline

Course 1: Game Semantics with Applications [in English, 12h]

Dan Ghica (University of Birmingham)

content:

  • basic concepts of game semantics
  • the fully abstract game model of a procedural concurrent programming language
  • concrete algorithmic representations of game models
  • applications of finite-state game models to program verification
  • approximating and refining game models
  • a survey of more advanced techniques for program verification using game models
  • Geometry of Synthesis, a categorical framework for circuit design
  • extracting circuit descriptions from game semantics
  • a survey of open problems in game semantics and applications

Course 2: Linear Logic [12h]

Lorenzo Tortora de Falco (University of Roma 3)
Olivier Laurent (LIP – ENS Lyon)
content:

  • sequent calculus for linear logic (1h30, monday LTdF)
  • proof-nets (3h, monday, tuesday LTdF)
  • translations of intuitionistic and classical logics (3h, tuesday, wednesday OL)
  • the coherent model and the relational model (1h30,wednesday LTdF)
  • geometry of interaction and game semantics for linear logic (3h, thursday OL)

(LTdF: Lorenzo Tortora de Falco, OL: Olivier Laurent)

References and documents

Course 2:

  • Olivier Laurent. Théorie de la démonstration. pdf .
    pages 89-90 (section 5.3), 87-89 (section 5.2), pages 143-150 (chap. 10), pages 111-122 (chap. 7), pages 130-134 (section 8.3)
  • Samson. Abramsky. Semantics of Interaction: an introduction to Game Semantics. pdf pages 1-14.

Local contact

There are several useful informations on the main page of the research schools in Computer Science at ENS Lyon.

ER-06 (2010) : Beyond the PC. Application specific systems: design and implementation

du  15 au 19 février 2010 — ENS Lyon

Plus d’informations sur: http://perso.ens-lyon.fr/florent.de.dinechin/beyond_the_pc.html

Intervenants :

  • Accélérateurs matériels  pour la bioinformatique (Dominique Lavenier, 6 hours)
  • High-Level Synthesis (Philippe Coussy, 6 hours)
  • Introduction au test numérique (Michel Renovell, 4 hours)
  • Optimizations for multicore and GP-GPU architectures (J. Ramanujam, 6 hours)
  • Optimisation de la consommation (Yves Durand, 2 hours)

Correspondants locaux

  • Christophe Alias
  • Florent de Dinechin