Année : 2012

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

• David Coeurjolly
• Guillaume Iooss

Programme de l’UE

A) Partie Informatique: Possibilités inattendues offertes par le hasard en algorithmique (N. Schabanel)

Depuis une trentaine d’années, les informaticiens ont révélé que l’on pouvait faire des usages assez étonnants du hasard, d’autant plus étonnants que ces résultats sont violemment contre-intuitifs. Nous verrons dans ce cours comment utiliser du hasard pour compter exactement avec une mémoire toute petite (randomized counters), comment corriger un programme buggé sans modifier son code (autocorrection de code), comment tester si quelqu’un sait quelque
chose, sans rien apprendre ni savoir de son secret (zero-knowledge), étudier les étranges propriétés des graphes expandeurs et leurs étonnantes applications.

Le plus surprenant est que ces méthodes sont très simples, tant  prouver et qu’  mettre en oeuvre, et sont le plus souvent bien plus efficaces que leurs alternatives déterministes: à la fois plus rapides et plus économiques en ressources. Ces techniques ont donc toutes les chances d’être favorisées par la sélection naturelle et pourraient donc bien se retrouver dans la nature, donc autant s’y préparer ! Le hasard est ainsi loin d’être seulement un bruit dont on chercherait à se débarrasser mais est au contraire appeler à jouer des rôles moteur insoupçonnés. Nous verrons également comment la notion de hasard peut être reliée à la notion de problèmes difficiles.

B) Partie physique :  Bruit et/ou information  (P. Borgnat et P. Flandrin)

Classiquement le bruit est vu comme une nuisance dont il faut s’affranchir dans des méthodes d’analyse de données, que ce soit en traitement du signal et des images, en statistiques ou dans des opérations d’acquisition de données. Cependant, au-delà de dire parfois que l’information peut être portée par du bruit, certaines méthodes proposent d’utiliser le bruit comme aide à l’analyse et à la décision. Plusieurs de ces approches ont une origine dans le monde des sciences physiques. On propose de couvrir trois familles d’approches en ce sens :

1. Accès à des données avec de l’aléatoire dans les mesures : Echantillonnage ou quantification aléatoires ou irréguliers ; idée d’échantillonnage compressif (compressed sensing) ; estimation par projections aléatoires (scketch, filtres de Bloom,…)
2. Méthodes de brassage aléatoire des données : bootstrap ; données substituts (surrogates),…
3. Analyse assistée par le bruit : résonance stochastique ; moyennes robustes par l’ajout de bruit ; liens avec les algorithmes ou les simulations assistés par le bruit (gradients stochastiques, méthodes de Monte-Carlo, recuit simulé).

C) Partie biologie: le hasard au coeur de la cellule (O. Gandrillon) (à confirmer)

Mots clés.

 

Prérequis.

 

Modalités de l’examen.

 

Intervenants

• Nicolas Schabanel, DR CNRS (responsable)
• Pierre Borgnat, CR CNRS
• Patrick Flandrin, DR CNRS
• Olivier Gandrillon, Univ. Lyon 1

Programme de l’UE

On étudiera les systèmes concurrents et le calcul fonctionnel par le biais de deux formalismes: les calculs de processus d’une part, et le lambda-calcul d’autre part. Des problèmes comparables se posent pour
l’analyse des systèmes dans les deux cadres: peut-on statiquement garantir que l’exécution d’un programme va terminer ? Peut-on apporter des bornes de complexité en temps sur cette terminaison?

Dans le cas des calculs concurrents, on développera les concepts permettant de raisonner sur la dynamique des systèmes, sur l’équivalence de processus, et sur leur terminaison. Dans celui du lambda-calcul on présentera des systèmes de types dérivés de la logique linéaire et permettant de garantir statiquement des bornes de complexité sur les programmes. On illustrera ainsi comment des techniques communes (typage) peuvent être exploitées à la fois dans le cadre concurrent et dans le cadre fonctionnel.  Enfin si le temps le permet on verra comment les méthodes développées pour la complexité dans le cadre du calcul fonctionnel inspirent des approches similaires dans le cadre concurrent.

Prérequis. 

• notions élémentaires de lambda-calcul simplement typé,
• définitions de base de classes de complexité en temps déterministe (les notions des cours d’algorithmique de L3 sont suffisantes). Les définitions nécessaires seront cependant rappelées.

Calendrier prévisionnel : 08/10, 09/10, 16/10, 22/10, 23/10, 6/11, 12/11, 13/11, 19/11, 26/11, 27/11, 4/12

Modalités d’examen. Un devoir à la maison en cours de trimestre, et un examen écrit à la fin du cours.

Intervenants:

• Patrick Baillot, CR CNRS (responsable)
• Damien Pous, CR CNRS

Programme de l’UE

L’arithmétique virgule flottante, grâce à son efficacité (grande « dynamique » et opérateurs très rapides) s’est imposée en calcul scientifique. Aucun des problèmes numériques de très grande taille qui se posent quotidiennement aux ingénieurs (mécanique des fluides, calculs de structures, etc.) ne serait résoluble en temps raisonnable autrement qu’en arithmétique virgule flottante. Pourtant son caractère approché peut parfois poser problème (des erreurs d’arrondis peuvent s’accumuler). Egalement, une programmation erronée ou naïve peut rendre le comportement des programmes imprévisibles. Enfin, les utilisateurs ignorent trop souvent que depuis quelques années le comportement des opérations virgule flottante est complètement spécifié (norme IEEE 754), et qu’on peut élaborer des preuves qui utilisent ces spécifications. Ce dernier point est très important lorsque l’arithmétique virgule flottante est utilisée dans un contexte où une erreur pourrait avoir des conséquences graves (transport aérien, contrôle de processus physico/chimiques dangereux, etc.)

L’objet de ce cours est d’abord de présenter aux étudiants des propriétés « fines » de l’arithmétique virgule flottante: grâce aux spécifications de la norme IEEE 754, on peut construire et prouver des algorithmes qui permettent de faire des calculs « exacts » (ou très précis) avec cette arithmétique « approchée » (calculs exacts de sommes, de produits scalaires, mise au point d’algorithmes de division, de calcul des fonctions « transcendantes »). On se focalisera ensuite sur la possibilité d’élaborer des preuves formelles des algorithmes virgule flottante, en illustrant ce point par la formalisation dans l’assistant de preuve Coq de l’arithmétique virgule flottante.

Modalités d’examen. L’évaluation se fera par une analyse d’articles présentée par un rapport écrit et une soutenance orale, lors de laquelle des questions portant sur le cours pourront être posées.

Prérequis: un minimum de notions de logique et d’algorithmique. Les débutants complets en Coq sont les bienvenus, le cours s’adaptera à eux.

Bibliographie pour le cours

• Le récent « Handbook of Floating-Point Arithmetic« 
• l’article « Floating-Point verification » de John Harrison
•  la page web de Guillaume Melquiond, et celle de Sylvie Boldo

Calendrier prévisionnel

11/09, 18/09, 19/09, 25/09, 2/10, 3/10, 9/10, 16/10, 17/10, 24/10, 6/11, 7/11 [de 8h à 10h].

Intervenants

• Jean-Michel Muller, DR CNRS (responsable)
• Damien Pous, CR CNRS
• Laurent Théry, CR INRIA

Programme de l’UE

Une grande majorité des problèmes en algorithmique des graphes sont NP-difficiles, comme par exemple le problème du voyageur de commerce. En revanche, la plupart de ces problèmes deviennent polynomiaux lorsque les graphes considérés sont acycliques, e.g. des arbres. Une manière de contourner la difficulté est de structurer le graphe en le décomposant de façon arborescente. L’objectif de ce cours est de présenter ces techniques, dont notamment la désormais incontournable notion de tree-width, ou largeur arborescente, introduite par Robertson et Seymour. Une introduction aux algorithmes FPT (fixed parameter tractable), qui découlent de cette théorie, sera aussi proposée.

1. Introduction des notions de largeur arborescente (tree-width) et de ses nombreux dérivés, dont la path-width et la branch-width. Résultats de base, jusqu’au Grid-Minor Theorem.
2. Programmation dynamique sur les graphes de largeur arborescente bornée.  Ce résultat est le point de départ du chapitre suivant.
3. Introduction à la complexité paramétrée.
4. Notion de Noyau et d’algorithme de compression.
5. Le théoreme des mineurs de graphes. Avec son corollaire principal: Pour toute classe de graphe close par mineur, il existe un algorithme polynomial qui décide si un graphe appartient à cette classe ou pas. Nous présenterons ce résultat, certainement le plus difficile et le plus profond de la théorie des graphes. Une application directe est par exemple qu’il est polynomial de décider si un graphe se plonge sur une surface donnée. La largeur arborescente et le routage (linkage) sont les clés de ce résultat.
6. Graph Searching. La notion de largeur arborescente est interprétable en termes de nombre minimum d’agents requis pour rechercher un fugitif dans un réseau. Les stratégies gagnantes des deux camps suggèrent une dualité.
7. Certificat dual de la tree-width. Introduction de la notion de bramble et autres certificats des mesures de largeur arborescente.
8. Introduction de la notion de clique-width de Courcelle. Une mesure de complexité qui capture plus de graphes que la tree-width, et stable par complémentation. Equivalence avec la notion de rank-width de Seymour et Oum.

Prérequis. Le cours s’adaptera au public.

Calendrier prévisionnel. 14/09, 17/09, 21/09, 24/09, 28/09, 01/10, 05/10, 12/10, 15/10, 26/10, 5/11, 9/11

Modalités d’examen. Examen écrit et oral.

Bibliographie

• Une petite Introduction aux mineurs de graphes, de László Lovász.
• Le Graph Theory, de Reinhard Diestel, est à conseiller. Le chapitre 12, traite de la ‘tree-width’.
• Le Parameterized Complexity Theory, de Jorg Flum et Martin Grohe, est une bonne réference pour les algorithmes FPT.

Pour les plus courageux, la série des Graph Minors de I à XXIII, de Neil Robertson et Paul Seymour, est intéressante à parcourir, pour se rendre compte de la difficulté du résultat.

Lien sur la page du cours

Intervenant

• Stéphan Thomassé, Pr ENS Lyon

Programme de l’UE

Prouver des bornes inférieures sur la complexité algorithmique de problèmes spécifiques est souvent très difficile.  Par exemple, la question « P=NP ? » est de cette forme: il s’agit d’obtenir une borne inférieure superpolynomiale sur la complexité en temps du problème SAT (ou de manière équivalente sur la complexité de n’importe quel problème NP-complet).  Etant donnée la difficulté de ce problème et d’autres problèmes de ce type, on a proposé des modèles de calculs algébriques, variantes des modèles booléens « standards »; et on espère que les questions analogues soient plus abordables dans ces nouveaux modèles.

Les deux principales versions algébriques du problème « P=NP ? » sont dûes à Valiant et à Blum-Shub-Smale, et sont toujours ouvertes. Par exemple, le contenu algorithmique du problème « P=NP ? » dans le modèle de Blum-Shub-Smale sur le corps des nombres réels est le suivant: étant donné un polynôme dedegré 4 en n variables, peut-on décider s’il admet une racine réelle en un nombre d’opérations arithmétiques et de comparaisons polynomial en n ? Les meilleurs algorithmes connus à ce jour effectuent un nombre d’opérations exponentiel en n.

Dans le modèle de Valiant on ne s’intéresse pas à des problèmes de décision mais à l’évaluation de polynômes. Le contenu algorithmique de la question VP=VNP peut être formulé ainsi: est-il possible d’évaluer le permanent d’une matrice en un nombre d’opérations arithmétiques polynomial en la taille de cette matrice ?

On présentera ces deux modèles de calcul et des approches proposées pour aborder les versions correspondantes du problème P=NP:

• conjecture tau de Shub et Smale: n! (ou un multiple) ne peut pas se calculer en un nombre d’opérations arithmétiques polynomial en log n
• La version de cette conjecture sur le nombre de racines entières des polynômes donnés par circuits (qui est supposé polynomial en la taille du circuit).
• La non généralisation aux racines réelles (polynômes de Chebyshev, exemple de Borodin-Cook).
• Une version réelle pour les sommes de produits de polynômes creux.

On présentera également des résultats sur la réduction de profondeur pour les circuits arithmétiques, certains anciens (Muller-Preparata, Valiant-Skyum-Berkowitz-Rackoff), d’autres plus récents (Agrawal-Vinay).  Ces résultats sont non seulement intéressants du point de vue du calcul parallèle, mais aussi comme on le verra pour les bornes inférieures.

Prerequis: Il s’agit d’un cours de complexité donc un certain goût pour ce sujet et les connaissances acquises à l’occasion d’un premier cours (par exemple, le cours de complexité algorithmique de M1) ne peuvent pas faire de mal. Mais il n’y aura pas de besoin de connaissances specialisées dans le domaine car le cours porte sur des modèles de calcul alternatifs à la traditionnelle machine de Turing. Si nécessaire, quelques rappels de complexite booléenne seront faits.

Modalités d’examen : exposé sur un article (petit rapport + présentation orale) et examen écrit « classique » à la fin.

Intervenant

• Pascal Koiran, Pr. ENS Lyon

Programme de l’UE

Nous passons en revue une partie de la théorie de l’approximation du point de vue du calcul effectif. Comment calculer des approximants polynomiaux ou rationnels, développer efficacement en série de Taylor ou sur des bases de polynômes orthogonaux, calculer des approximants de Padé, puis comment utiliser ces développements pour obtenir des approximations à précision donnée (algorithmes de Remez, modèles de Taylor et de Chebyshev). La puissance de ces techniques sera illustrée en développant trois applications, attachées à des domaines scientifiques différents : preuves d’irrationalité en théorie des nombres, évaluation efficace de fonctions numériques, problème des « Near-Earth Objects ».

Prérequis :

Calendrier prévisionnel : 19/09, 24/09, 26/09, 01/10, 08/10, 10/10, 15/10, 22/10, 24/10, 5/11, 7/11, 12/11.

Modalités d’examen : Examen écrit, et un travail à la maison noté.

Intervenants

• Nicolas Brisebarre, CR CNRS (responsable)
• Bruno Salvy, DR INRIA

Programme de l’UE

L’ordonnancement est une branche de la recherche opérationnelle qui vise à allouer des ressources à un ensemble de tâches, et de planifier leur exécution dans le but d’optimiser une certaine fonction objective (temps d’exécution, rendement, etc). Dans ce cours, nous étudierons les problèmes d’ordonnancement présents dans les systèmes informatiques, et en particulier dans les plates-formes de calcul parallèles.

Nous commencerons par présenter des problèmes et techniques classiques en ordonnancement, puis nous introduirons progressivement des modélisations qui permettent de prendre en compte les spécificités des plates-formes de calcul actuelles tout en permettant de résoudre les problèmes d’ordonnancement. Nous présenterons enfin des objectifs propres à ces plates-formes, ainsi que les techniques employées pour résoudre les problèmes qu’ils soulèvent.

Plan du cours

1. Approches classiques de l’ordonnancement
   • introduction et problèmes classiques (list scheduling, Smith ratio, etc.)
   • modélisation des applications (graphes de tâches, flow-shop, tâches malléables, etc.)
   • rappel de NP-complétude, algorithmes d’approximation
   • ordonnancement à la volée et non-clairvoyant
2. Vers une modélisation plus réaliste des plates-formes de calcul introduction des coûts de communications
   • ordonnancement de tâches divisibles
   • ordonnancement en régime permanent
   • prise en compte de interférences calculs/communications
3. Nouveaux objectifs et nouvelles techniques en ordonnancement
   • tolérance aux pannes, robustesse
   • réduction de la consommation d’énergie
   • ordonnancement multi-organisation
   • apports de la théorie des jeux
   • approche stochastique
   • ordonnancement multi-critère

Toutes les techniques exposées seront abondamment illustrées par des études de cas.

Modalités d’examen. L’évaluation consistera à une analyse et présentation d’articles. Certains cours seront d’ailleurs l’occasion pour les étudiants de pratiquer la lecture et l’analyse d’articles.

Pré-requis: il est souhaitable (mais pas indispensable) d’avoir suivi le cours d’Algorithmique Parallèle de M1. Des étudiants motivés peuvent s’en passer en lisant quelques chapitres importants du livre correspondant.

Intervenants

• Loris Marchal, CR CNRS
• Frédéric Vivien, DR INRIA

Programme de l’UE

Un compilateur n’est autre qu’un traducteur d’un langage (par exemple C ou Caml) vers un autre (par exemple un langage assembleur). Bien entendu, les langages de programmation sont dotés de propriétés sympathiques (par exemple grâce aux grammaires LALR) qui font que les traductions des compilateurs sont, heureusement, nettement plus convaincantes que celles d’un traducteur de langage naturel comme Babel Fish! On ne s’intéressera pas dans ce cours à ces problèmes de traduction, aujourd’hui bien maîtrisés.

Aujourd’hui, on demande bien plus à un compilateur, on veut qu’il génère du code non seulement correct (traduction) mais aussi efficace pour l’architecture cible (compilateur optimisant). Écrire « from scratch » un compilateur pour un processeur spécifique prend plusieurs années pour une équipe d’ingénieurs et, avec la pression du marché (« time-to-market ») et l’évolution rapide des processeurs, cette approche n’est pas viable. On préfère produire des compilateurs dits reciblables, optimisants, pour une gamme de processeurs.

La difficulté et l’intérêt (du point de vue du chercheur) résident dans la mise au point d’optimisations. On souhaite que le code soit rapide, qu’il génère le moins de trafic mémoire possible, qu’il consomme peu, qu’il soit compact, etc. En pratique, une optimisation est une recette de cuisine pour transformer, améliorer le code, enrichir l’information que l’on a de celui-ci. Les recettes de cuisine sont bien entendu plus ou moins sophistiquées et coûteuses, et la difficulté pour l’ingénieur-cuisinier est de les faire cohabiter et de les utiliser à bon escient. Ainsi, la compilation est avant tout un problème d’ingénierie (certes d’experts) où la difficulté réside dans le choix des représentations intermédiaires du code et des informations qui lui sont associées: la représentation intermédiaire permet ou non d’exprimer trivialement certaines propriétés, ce qui influence considérablement l’implémentabilité de tel ou tel outil d’analyse.

On verra entre autres que les outils « mathématiques » nécessaires aux optimisations en compilation sont relativement divers (théorie des graphes, propriétés de treillis, programmation linéaire, ordonnancement) selon les représentations intermédiaires (graphe de flot de contrôle, forme SSA, forme psi-SSA, boucles imbriquées), les niveaux d’abstraction du code (code source ou code assembleur), et les fonctionnalités architecturales (instructions avec prédicats, registres). Le but de ce cours sera donc de décrire un certain nombre de phases d’analyses et de transformations relativement classiques et d’en profiter pour donner un aperçu des outils utilisés par le chercheur en optimisation de programmes.

Contenu du cours (indicatif)

Les thèmes suivants seront traités:

• Représentations (CFG, psi-SSA, dominance, loop-forest, etc.)
• Analyse (dependances, durée de vie, alias, flot de données, interprétation abstraite — treillis, points fixes, étiquetage de graphe)
• Transformations (fusion de boucles, pavage, data-layout, source-à-source, unimodulaire — ILP, graphes, polyèdres, réseaux)
• Allocation de registres (assignation vs allocation, vidage en mémoire, coalescing — graphes, optimisation combinatoire, LP)
• Ordonnancement (ordonnancement, pipeline logiciel — ILP, approximabilité, retiming)

Calendrier prévisionnel

12/09, 17/09, 19/09 [de 16h à 18h]

Intervenants

• Alain Darte, DR CNRS
• NN

Programme de l’UE

Ce cours vise à offrir une présentation la plus large possible de ce qui fait en recherche autours des grilles (dans différentes déclinaisons grilles de calcul, grille de recherche, grille de production, etc.). Nous aborderons des sujets tels que les architectures de grille, la gestion de données (Hadoop, etc.), les intergiciels, la notions de services (SOA, PaaS, SaaS, …), le Cloud computing, etc. ainsi que les différents modèles de programmation, tels que les worflows, les composants logiciels, les squelettes algorithmiques ou encore les modèles chimiques. Ce cours de seconde année de master sera fortement orienté recherche par l’étude d’articles du domaine par les étudiants.

Intervenants

• Eddy Caron
• Christian Perez

Programme de l’UE

La théorie des jeux est aujourd’hui un outil indispensable pour comprendre l’évolution de domaines aussi divers que l’apprentissage, la tarification, l’optimisation distribuée ou l’algorithmique des réseaux de communications.

Plan général:

• En introduction, nous allons introduire les concepts principaux de la théorie des jeux (définition, matrice de gain, équilibre de Nash, de Wardrop, notions d’équité, mesure d’efficacité).
• Dans un deuxième temps, nous allons étudier plus précisément certains types de jeux: jeux à somme nulle, jeux de potentiel, jeux super-additifs.
• Une troisième partie présentera les mécanismes d’enchères et les coalitions qui donnent lieu à des notions d’équilibres légèrement différentes.
• Une quatrième partie sera consacrée à quelques applications dans le domaine des réseaux de communication (on montrera en particulier que TCP est équitable au sens de l’équité proportionnelle), et des méthodes de résolution de routage optimal.

Le deuxième volet du cours sera consacré aux algorithmes de calcul des équilibres dans les contextes présentés précédemment.

• On présentera la dynamique de meilleure réponse, de réplication,… et on montrera leurs propriétés de convergence vers les équilibres de Nash.
• Nous étudierons ensuite des versions algorithmiques distribuées de ces dynamiques en mettant en évidence les difficultés qui apparaissent alors.
• Une dernière partie sera consacrée à étudier les liens avec les dynamiques d’apprentissages (recuit simulé, méthode de Monte Carlo et plus généralement, les méthodes d’approximations stochastiques)

Dates des cours :

Liens sur des transparents.

Intervenants

• Bruno Gaujal, DR INRIA
• Corinne Touati, CR INRIA

Programme du cours

• Architecture de l’internet du futur (réseaux/équipements) : evals de perfs, simulation, modélisation
• Introduction à la simulation à événements discrets (2 x 2h)
• Cas pratique d’un routeur (2 x 2h)

Nouveaux protocoles réseaux : services/middleware, QoS, réseaux verts

• Réseaux autonomes et programmables (2h)
• Réseaux fiables (2h)
• Réseaux verts (2 x 2h)

• Communication entre processus (par message (socket), par mémoire partagée (RPC)) (3h)
• Liens entre middleware (MPI), réseaux rapides et infrastructures (3h)

Planning prévisionnel :

20/09, 27/09, 4/10, 11/10, 18/10, 25/10

Intervenants

• Thomas Begin, MCF UCBL
• Laurent Lefèvre, CR INRIA

Programme de l’UE

Dans de nombreux contextes des grands graphes jouent un rôle essentiel ; citons par exemple la topologie de l’Internet, les graphes du Web ou les échanges Pair-à-Pair, mais aussi les réseaux sociaux, réseaux de contact, biologiques ou linguistiques. La disponibilité de données massives, de capacités de traitement adéquates, et l’observation de diverses propriétés en commun ont récemment donné naissance à un vaste effort de recherche sur ces objets. Son originalité réside dans le fait qu’on part de graphes issus d’observations, et non définis formellement. C’est en ce sens que ce sont des « graphes de terrain« .

Ce cours abordera les différentes problématiques soulevées par ce domaine que l’on peut regrouper en quatre familles complémentaires :

• Mesure et Métrologie Mener des mesures fiables, de qualité et à grande échelle est une problématique de recherche en soi, qu’il ne faut pas ignorer. savoir ce que l’on mesure, comment et pourquoi est l’un des points de départ crucial de l’analyse des grands graphes de terrain.
• Analyse : On abordera les outils et les formalismes pour décrire les grands graphes de terrain afin d’en extraire les principales propriétés.
• Modélisation. Une fois les principales propriétés d’un graphe identifiées, les capturer dans un
  modèle formel est crucial notamment pour les expliquer, obtenir des résultats formels, et mener
  des simulations.
• Algorithmique. La taille des graphes considérés interdit l’utilisation d’algorithmes quadratiques ou plus ; de nombreux problèmes pour lesquels des solutions habituellement satisfaisantes sont connues doivent donc être retravaillés. Par ailleurs, la présence de propriétés caractéristiques des graphes de terrain ouvre la voie au développement d’algorithmes efficaces dans ces cas.

Intervenants

• Alain Barrat, CR CNRS, Centre de Physique Théorique, Marseille, France
• Eric Fleury, Professeur ENS Lyon
• Christophe Crespelle, Maître de conférences, Université de Lyon 1

Support de cours