DEA de Mathématiques Discrètes 
et Fondements de l'Informatique

Université de la Méditerranée - Faculté des Sciences de Luminy 
Université de Provence 
CNRS - Institut de Mathématiques de Luminy 
INRIA - Sophia Antipolis

Année 1999-2000

 
responsable Jean-Yves Girard
coordinateur Pierre Ille
correspondants Joëlle Despeyroux (Sophia Antipolis) 
Pierre Liardet (Université de Provence)
secrétariat Jeanine Brohan
adresse Institut de Mathématiques de Luminy, 
163 avenue de Luminy, case 907, 
13288 Marseille Cedex 9
téléphone 04 91 26 96 40
télécopie 04 91 26 96 55
adresse électronique dea@iml.univ-mrs.fr
site web http://iml.univ-mrs.fr/dea/
  Fichiers Postscript disponibles :

Le DEA MDFI (Mathématiques Discrètes et Fondements de l'Informatique) s'adresse aux étudiants titulaires d'une maîtrise de mathématiques, d'informatique, ou d'un diplôme équivalent, et qui désirent recevoir une solide formation théorique avant d'aborder la recherche. Il est cohabilité par l'Université de la Méditerranée (Aix-Marseille II) et l'Université de Provence (Aix-Marseille I). L'effectif souhaité est d'environ 20 étudiants.

Programme du DEA MDFI :

Tous les cours ont lieu à la Faculté des Sciences de Luminy, sauf le cours intensif, qui a lieu à Sophia Antipolis. Sur le site de Luminy, les étudiants ont accès à une salle équipée de postes de travail, et à la bibliothèque du CIRM (Centre International de Rencontres Mathématiques).

Les cours fondamentaux portent sur les structures discrètes de l'algèbre, de la combinatoire, et de la logique. Les connaissances ainsi acquises sont utilisées dans les options, qui abordent les thèmes de recherche actuels, aussi bien en mathématiques qu'en informatique. En accord avec le responsable du DEA MDFI, les étudiants peuvent valider des options appartenant à un autre DEA de l'Ecole Doctorale de Mathématiques et Informatique de Marseille.
 

Cours fondamentaux
Courbes, codes et cryptographie
Combinatoire des graphes et des mots
Preuves et types
 
Options
Groupes issus de la géométrie algébrique et cryptographie
Théorie analytique des nombres
Codes correcteurs d'erreurs
Calcul formel
Introduction aux fractions continues et à l'approximation diophantienne
Structures discrètes aléatoires
Réseaux d'interconnexion
Logique linéaire
Calculs de processus distribués et mobiles
Mécanisation des preuves
 
Laboratoires d'accueil
IML (Institut de Mathématiques de Luminy, UPR 9016 du CNRS)
INRIA - Sophia Antipolis
I3S (Laboratoire Informatique, Signaux et Systèmes de Sophia Antipolis, UPRESA 6070)
GECT (Groupe d'Etude du Codage de Toulon, EA 1355)
 
Dates limites de dépôt des dossiers de préinscription : 30 juin (1ère session) et 15 septembre (2ème session).

Cours fondamental : Courbes, codes et cryptographie

par François Rodier & Pascal Véron (IML - ATI & GECT)
  1. Courbes et codes. La théorie des codes correcteurs d'erreur a pour but de protéger les transmissions de données des erreurs qui peuvent y survenir (dues par exemple au bruit dans une ligne de communication). Une des techniques pour construire des codes efficaces se sert des courbes sur des corps finis.
  2. Après avoir introduit les corps finis et leur structure, on étudiera les variétés (systèmes d'équations) sur les corps finis. On mènera une étude plus détaillée mais encore élémentaire des courbes algébriques en vue de la construction de codes correcteurs d'erreur. Ensuite, après une présentation générale des codes, on traitera de la construction et des propriétés générales des codes géométriques algébriques (codes de Goppa).

    Le cours sera illustré de nombreux exemples.
     

  3. Cryptographie. La cryptographie à clé publique et ses divers standards : chiffrements - échanges de clés - signatures - procédés d'authentification - contrôles d'intégrité - fonctions à sens unique - méthodes arithmétiques et géométriques (primalité, factorisation, courbes elliptiques et hyperelliptiques).
Bibiographie : S. Vladut & M.A. Tsfasman, Algebraic-geometric codes, Kluwer Akad. Publ., 1991. - H. Stichtenoth, Algebraic function fields and codes, Springer, 1993. - J. Harris, Algebraic geometry, Springer, 1993. - R. Lidl & H. Niederreiter, Finite fields, Enc. of Math. and its Appl. 20, Addison-Wesley, 1983. - F.J. McWilliams & N.J.A. Sloane, The theory of error-correcting codes, North-Holland, 1977. - O. Papini & J. Wolfmann, Algèbre discrète et codes correcteurs, Mathématiques & Applications 20, Springer-Verlag, 1994. - T. Hoholdt, J.H. van Lindt & R. Pellikaan, Algebraic geometry codes, Mathématiques & Applications 20, Springer-Verlag, 1994.

Cours fondamental : Combinatoire des graphes et des mots

par Julien Cassaigne & Pierre Ille (IML - SDD & LDP)

L'objectif de ce cours est de présenter les notions élémentaires et les outils classiques intervenant en combinatoire, tant dans l'étude des graphes que dans celle des mots. Dans une première partie, nous considérerons des classes de graphes particuliers, comme les arbres, et nous aborderons les problèmes de k-connexité (théorème de Menger). Nous poursuivrons par l'étude des graphes euleriens, hamiltoniens et nous envisagerons, enfin, des questions similaires pour les graphes orientés.

Dans une seconde partie, en utilisant certains aspects de la théorie des graphes, nous introduirons les outils de base de la combinatoire des mots, comme les automates finis, la fonction de complexité et les graphes de mots. Nous présenterons ensuite diverses applications de la combinatoire des mots tant du point de vue de la dynamique symbolique que de celui de la théorie des langages formels.

Bibiographie : S. Eilenberg, Automata, Languages and Machines, Academic Press, 1974. - M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, 1980. - M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and Applications 17, Addison-Wesley, 1983.


Cours fondamental : Preuves et types

par Thomas Ehrhard & Laurent Regnier (IML - LDP)

La théorie de la démonstration est issue du grand débat sur les fondements des mathématiques initié à la fin du siècle dernier. S'il est vrai qu'avec son fameux théorème d'incomplétude, Gödel a montré les limites du formalisme, le développement de l'informatique a suscité un net regain d'intérêt pour cette discipline. L'interprétation algorithmique des preuves de la logique intuitionniste conduit en effet au lambda-calcul typé, qui est la base de toute la programmation fonctionnelle. Plus récemment encore, le domaine a été renouvelé par l'émergence de la logique linéaire, qui introduit en particulier une présentation géométrique de la syntaxe (réseaux de preuves, sémantique dénotationnelle et géométrie de l'interaction), permettant une modélisation plus fine de certains aspects concrets du calcul tels que la gestion des ressources et le parallélisme.

Nous présenterons les concepts et les résultats qui nous semblent les plus pertinents, aussi bien du point de vue de l'élégance mathématique que de celui des applications informatiques : calcul des séquents et déduction naturelle - élimination des coupures - lambda-calculs typés du premier et du second ordre - éléments de sémantique dénotationelle. Toutes ces notions nous mèneront naturellement à une introduction détaillée à la logique linéaire.

Bibiographie : J.-Y. Girard, Proofs and Types, Cambridge Tracts in Theoretical Computer Science 7, Cambridge University Press, 1989.


Option : Groupes issus de la géométrie algébrique et cryptographie

par Robert Rolland (IML - ATI)

Cours fondamental conseillé : Courbes, codes et cryptographie

Il s'agit d'étudier les jacobiennes de certaines courbes algébriques conduisant à des groupes intéressants en cryptographie.

Bibiographie : Koblitz, A course in number theory and cryptography, Springer-Verlag.


Option : Théorie analytique des nombres

par Serge Vladut (IML - ATI)

Cours fondamental conseillé : Courbes, codes et cryptographie

  1. La fonction zêta de Riemann et son équation fonctionnelle, les séries L de Dirichlet.
  2. Applications: Nombres premiers dans une progression arithmétique ; théorème de Dirichlet.
  3. Corps de nombres algébriques, groupe des classes d'idéaux. Formule pour le nombre de classes d'un corps de nombres algébriques. Propriétés des corps cyclotomiques et de leur groupe des classes.
Bibiographie : Z. Borevitch & I.R. Shafarevitch, Number theory. - S. Lang, Algebraic number theory.

Option : Codes correcteurs d'erreurs

par Jacques Wolfmann (GECT - CODES)

Cours fondamental conseillé : Courbes, codes et cryptographie

Problèmes généraux des codes correcteurs d'erreurs (en bloc) : borne d'empilement de sphères - aspects combinatoires, configurations associées. Codes linéaires : rappels et compléments sur les corps finis - définition des codes linéaires, propriétés, constructions, orthogonalité, bornes, décodage standard - différentes descriptions, équations associées sur les corps finis - familles classiques de codes linéaires. Codes cycliques : définition des codes cycliques - représentations polynomiales, algèbres de polynômes sur les corps finis - techniques de construction, de codage et de décodage des codes cycliques - codes BCH, codes de Reed-Solomon et autres codes classiques. Compléments et problèmes ouverts : classes de bons codes, codes auto-duaux, rayon de recouvrement, fonctions courbes, liens avec la cryptographie, suites parfaites et presque parfaites, codes et équations sur les corps finis, etc.

Bibiographie : O. Papini & J. Wolfmann, Algèbre discrète et codes correcteurs, Mathématiques & Applications 20, Springer-Verlag, 1994.


Option : Calcul formel

par Ioannis Emiris, Jean-Pierre Merlet & Bernard Mourrain (INRIA - SAGA)

Cours fondamental conseillé : Courbes, codes et cryptographie

Le but de l'option est d'étudier, au travers d'applications diverses, des algorithmes récents de calcul sur les polynômes à plusieurs variables, qui sont au coeur des activités de recherche en calcul formel polynomial. En particulier on développera le calcul des bases de Gröbner (algorithme de Buchberger) et celui des résultants. Le résultant creux, ou torique, exploite la structure des polynômes et son degré dépend du volume mixte plutôt que de la borne classique de Bezout. Le Bezoutien donne une méthode alternative qui conduit à des matrices plus compactes. Enfin, la technique de Dixon est une combinaison de ces deux approches.

On illustrera ces méthodes dans des domaines variés : robotique, vision par ordinateur, démonstration automatique en géométrie élémentaire et, bien sûr, résolution d'équations polynomiales. Ce dernier problème pose certaines questions numériques que nous aborderons dans la limite du temps disponible. La mise en pratique de ces méthodes se fera par l'initiation à quelques systèmes de calcul formel comme Maple, ou à la bibliothèque ALP que nous sommes en train de développer en C++.


Option : Introduction aux fractions continues et à l'approximation diophantienne

par Valérie Berthé & Pascal Hubert (IML - SDD)

Cours fondamental conseillé : Courbes, codes et cryptographie ou Combinatoire des graphes et des mots

Si l'algorithme des fractions continues est l'un des plus anciens et des plus connus des algorithmes arithmétiques, il intervient aussi activement dans de nombreux domaines de recherche des mathématiques (théorie ergodique, théorie des nombres, géométrie hyperbolique, ...). Nous introduirons dans un premier temps des notions de base sur les fractions continues et l'approximation diophantienne : nous donnerons en particulier des résultat métriques à l'aide de quelques outils élémentaires de théorie ergodique. Nous appliquerons ces méthodes à l'étude des systèmes dynamiques symboliques engendrés par des suites sturmiennes. Ces résultats peuvent se généraliser dans différentes directions :

  1. étude de l'approximation non homogène, de ses implications dynamiques et combinatoires (dynamique des rotations) ainsi que les liens avec les sytèmes de numération (numération d'Ostrowski) ;
  2. approximation d'un réel par une famille de nombres algébriques (fractions continues de Rosen) ;
  3. approximation simultanée ; on présentera plusieurs algorithmes tant d'un point de vue analytique que géométrique (Jacobi-Perron, Poincaré, ...).
Bibiographie : J. W. S. Cassels, An introduction to diophantine approximation, Cambridge University Press. - A. Y. Khinchin Continued fractions, Chicago University Press. - F. Schweiger Ergodic theory of fibred systems and metric number theory, Oxford University Press.

Option : Structures discrètes aléatoires

par Hervé Daudé & Pierre Liardet (IML - DSA)

Cours fondamental conseillé : Combinatoire des graphes et des mots

Le cours est une initiation aux diverses techniques d'investigation dans le domaine des structures discrètes qui relèvent de méthodes probabilistes et analytiques. Les outils de bases seront introduits à partir de thèmes choisis dans la théorie des graphes aléatoires (phénomènes de seuil et optimisation) et l'algorithmique (analyse en moyenne et génération aléatoire).

Bibiographie : P. Erdös & J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, 1974. - B. Bollobas, Random Graphs, Academic Press, 1985.


Option : Réseaux d'interconnexion

par Jean-Claude Bermond (I3S - PACOM)

Cours fondamental conseillé : Combinatoire des graphes et des mots

Le but du cours est d'étudier divers problèmes combinatoires motivés par la construction et l'utilisation de machines parallèles, en particulier tout ce qui concerne les échanges d'information et les communications entre processeurs (ou stations, ou processus). Un premier problème est la conception du réseau d'interconnexion pour les futures machines parallèles. Divers paramètres interviennent : temps de transmission des messages, nombre limité de liaisons issues de chaque processeur, symétrie, tolérance aux pannes, ... (l'outil essentiel étant la théorie des graphes). Un deuxième problème concerne les communications entre processeurs dans des architectures à mémoire distribuée (routages, diffusion, échange total de messages, ...). Un troisième problème consiste à plonger le graphe de tâches associé à un algorithme dans le graphe modélisant le réseau d'interconnexion.

Bibiographie : J. de Rumeur, Communication dans les réseaux de processeurs, Masson, 1994.


Option : Logique linéaire

par Jean-Yves Girard & Yves Lafont (IML - LDP)

Cours fondamental conseillé : Preuves et types

La logique linéaire, inventée il y a une dizaine d'années, est issue d'une relecture de la théorie de la démonstration à la lumière de l'informatique. Le cours se propose d'introduire à la logique linéaire en développant la notion d'espace cohérent (sémantique de la logique linéaire) et celle de réseau de démonstation, qui en est la contrepartie syntaxique. L'intérêt des réseaux en relation avec l'informatique vient de leur caractère non séquentiel : il s'agit de la première syntaxe parallèle.

Bibiographie : J.-Y. Girard, Y. Lafont & L. Regnier (éditeurs), Advances in Linear Logic, London Mathematical Society Lecture Note Series 222, Cambridge University Press, 1995.


Option : Calculs de processus distribués et mobiles

par Gérard Boudol, Ilaria Castellani & Davide Sangiorgi (INRIA - MEIJE)

Cours fondamental conseillé : Preuves et types

Le pi-calcul est un calcul de processus parallèles, évolution du calcul CCS, qui permet de rendre compte de systèmes dont la topologie de communication change dynamiquement. Ce calcul est maintenant considéré comme un possible fondement de la programmation distribuée, au même titre que le lambda-calcul est considéré comme le fondement de la programmation fonctionnelle. En particulier, le pi-calcul permet de rendre compte de la notion de localité et de migration au cours de calculs.

Dans le cours on présentera le pi-calcul : syntaxe, exemples de base, sémantique par réduction et par système de transitions étiquetées, bisimulations et théorie algébrique. On examinera en détail ses relations avec le lambda-calcul, dans le cadre d'un nouveau calcul, le calcul bleu, qui unifie ces deux approches, distribuée et fonctionnelle. On abordera également la question du typage de ces divers calculs, et de possibles modélisations de la migration.

Bibiographie : R. Milner, J. Parrow, & D. Walker, A Calculus of Mobile Processes (Parts I and II), Information and Computation 100, 1992. - R. Milner, The polyadic pi-calculus: a tutorial, ECS-LFCS-91-180, LFCS, Univ. Edinburgh, 1991. - D. Sangiorgi, From pi-calculus to Higher-Order pi-calculus - and back, Proceedings TAPSOFT '93, LNCS 668, 1993. - G. Boudol, The pi-calculus in direct style, POPL'97, 228-241, 1997.


Option : Mécanisation des preuves

par Yves Bertot & Joëlle Despeyroux (INRIA - LEMME & CERTILAB)

Cours fondamental conseillé : Preuves et types

L'utilisation des lambda-calculs typés pour décrire la logique et les fondements de la théorie de la démonstration a donné naissance à la théorie des types, et à des systèmes d'aide au développement de preuves sur ordinateur basés sur une théorie typée. Nous nous intéresserons tout particulièrement au calcul des constructions inductives, un lambda calcul typé d'ordre supérieur introduit par G. Huet, Th. Coquand et C. Paulin qui incorpore également des primitives de constructions récursives. Ces constructions se révèlent très utiles pour décrire aussi bien des objets mathématiques que la syntaxe et la sémantique des langages de programmation. Un tel calcul permet non seulement de vérifier des preuves de résultats mathématiques, mais également de certifier que des algorithmes remplissent des spécifications, exprimables à l'aide du langage des types.

Après une présentation des principes qui régissent le calcul des constructions inductives, le cours abordera les aspects pratiques de la mise en oeuvre de ce calcul dans un système (l'assistant à la preuve Coq) et étudiera quelques champs d'applications, en mathématiques et en sémantique des langages de programmation.

Bibiographie : G. Dowek, Théorie des types, Notes de cours. - J.Despeyroux, Sémantique Naturelle : Spécifications et Preuves, Notes de cours, rapport de recherche INRIA RR-3359, février 1998. - L. Théry, A certified version of Buchberger's Algorithm, Cade 15, LNAI 1421, Springer.


Equipes d'accueil de l'Institut de Mathématiques de Luminy


ATI (Arithmétique et théorie de l'information)

Cette équipe, dirigée par Gilles Lachaud, rassemble des chercheurs dont les travaux portent sur l'arithmétique et ses applications à la théorie de l'information.

L'arithmétique, c'est la théorie des nombres, c'est-à-dire l'étude des propriétés des entiers et de leurs généralisations : propriétés algébriques, algorithmiques, approximations diophantiennes, équations diophantiennes, etc. Dans cette discipline classique, les problèmes actuels se multiplient. Par exemple, l'approche des données irrationnelles et la quantification des distributions continues de données conduisent à l'étude des réseaux (maillages de l'espace) et des pavages de l'espace.

La théorie de l'information traite du problème suivant : comment décrire la structure d'un assemblage de données isolées ? Il s'agit aussi bien d'étudier des configurations régulières de points que de rendre compte de la manière dont un ordinateur traite et code l'information qu'on lui a confiée. En particulier, la théorie algébrique de l'information utilise l'arithmétique sur les corps finis (les champs de Galois) pour la correction des erreurs de transmission, la protection des données (cryptographie), la compression des fichiers, et l'élaboration de techniques de calcul comme la multiplication rapide. 


LDP (Logique de la programmation)

Cette équipe, dirigée par Jean-Yves Girard, étudie la théorie de la démonstration et ses applications à l'informatique. Cette discipline, qui est une branche de la logique mathématique, a été renouvelée par l'introduction de la logique linéaire. On peut distinguer trois axes de recherche :

SDD (Systèmes dynamiques discrets)

Cette équipe, dirigée par Pierre Arnoux, a une palette de thèmes de recherche très variée. L'idée centrale est d'explorer les rapports qu'entretiennent arithmétique, systèmes dynamiques, théorie des langages, et combinatoire. Un exemple frappant parmi d'autres : les suites sturmiennes sur un alphabet fini - celles dont le nombre de mots de longueur n vaut exactement n+1 - engendrent des systèmes dynamiques qui sont les bonnes représentations symboliques des rotations irrationnelles du cercle, et ceux-là seulement.

Parmi les thèmes relevant le plus exclusivement des mathématiques discrètes, on peut citer : les systèmes de numération (il n'y a pas que la représentation des nombres en base n), la combinatoire des mots, la transcendance en caractéristique non nulle, les méthodes de corps finis pour la génération de suites quasi-aléatoires, la combinatoire des graphes, et l'étude dynamique des automates cellulaires. On s'intéresse aussi aux rapports entre les mathématiques discrètes et d'autres sujets, que ce soit en géométrie, avec divers types de codage pour des systèmes classiques, ou en arithmétique. Tout cet ensemble recèle d'innombrables questions ouvertes, dont beaucoup ne sont même pas inventoriées.


Equipes d'accueil de l'INRIA - Sophia Antipolis


CERTILAB (Spécifications formelles et certification de logiciel)

L'objectif du projet CERTILAB est le développement de méthodes et de bibliothèques de spécifications et de preuves sur ordinateur, dans le domaine de la certification de logiciel. Le principal assistant à la preuve utilisé est le système Coq, basé sur le calcul des constructions inductives.

Notre projet recouvre deux axes de recherche connexes:

  • La preuve de propriétés de langages de programmation: étude d'exemples (l'exemple typique est la preuve de correction d'un compilateur), élaboration de méthodes de description des langages, recherche de nouvelles théories typées et étude de leurs propriétés ;
  • La preuve de correction de programmes. Les méthodes sont ici très variées, allant de la preuve de correction d'une abstraction du programme à l'extraction du programme à partir de la preuve de sa correction. 
  • LEMME (Logiciel et mathématiques)

    Le projet LEMME s'intéresse au développement de programmes corrects à partir de descriptions mathématiques des données, algorithmes, propriétés des objets mathématiques et des preuves de ces propriétés, en utilisant et éventuellement en étendant les outils fournis par le calcul des constructions inductives.

    La réalisation de l'objectif du projet LEMME passe par trois grands thèmes:

  • La formalisation de théories mathématiques suffisamment large pour couvrir tous les objets mathématiques manipulés dans les programmes de calcul scientifique, par exemple les structures algébriques de groupes, anneaux, corps, espaces vectoriels.
  • Le développement d'outils facilitant le travail de preuve et permettant l'acquisition des compétences nécessaires par des mathématiciens et des ingénieurs.
  • La formalisation d'algorithmes reconnus pour leur utilité dans le calcul scientifique: Calcul sur les polynômes, les équations booléennes. 
  • MEIJE (Parallélisme, synchronisation et temps réel)

    Le projet MEIJE, dirigé par Gérard Berry et Robert de Simone, est commun à l'INRIA et au Centre de Mathématiques Appliquées de l'Ecole des Mines à Sophia Antipolis. Il a pour objectif la modélisation et l'étude des systèmes parallèles et communicants, ainsi que la définition et l'implémentation de langages et de systèmes de vérification liés à ces systèmes. Plus précisément, ses activités s'articulent autour de trois thèmes :
  • l'étude et la modélisation algébrique (par le biais de calculs algébriques de processus) des concepts théoriques liés aux systèmes parallèles et répartis, par exemple la formalisation des notions de mobilité et de localité ;
  • l'étude plus spécifique de formalismes réactifs synchrones : en particulier le développement du langage Esterel et de ses modèles sémantiques, ainsi que du langage RC, extension réactive du langage C, et d'un langage d'objets et de scripts réactifs ;
  • le développement d'outils d'analyse et de vérification automatique de programmes issus des deux thèmes précédents, basés sur des méthodes d'analyse par systèmes de transitions étiquetées.


  • SAGA (Systemes Algébriques, Géométrie et Applications)

    Le récent projet SAGA, est consacré à l'algèbre, à la géométrie et à leurs applications. Il se propose de rechercher des méthodes symboliques et numériques pour le traitement de problèmes polynomiaux, de développer des outils logiciels adaptés, et de les appliquer dans différents domaines ou apparaissent de tels problèmes, comme la robotique, la vision, le traitement du signal, ... L'interaction, constante entre algorithmiques algébriques, techniques d'implémentation et applications des méthodes est au coeur des activités de l'équipe. Parmi celles-ci, mentionnons :
  • calcul formel sur les objets géométriques (points, droites, ...) - démonstration automatique de propriétés - application à l'analyse d'images ;
  • géométrie algébrique effective - théorie de l'élimination, des résidus algébriques, bezoutiens, résultants creux, variétés toriques ;
  • résolution exacte ou approchée de systèmes d'équations polynomiales - homotopies - algèbre linéaire pour les polynômes - matrices structurées - fiabilité numérique ;
  • implémentation, et application à des problèmes de robotique (robot parallèle), de vision (calibration, reconstruction 3D), de biologie moléculaire (reconstruction), de traitement du signal.



  • Autres équipes d'accueil


    DSA (Dynamique Stochastique et Algorithmique)

    Située sur le site de Château Gombert, cette équipe rattachée à l'IML est dirigée par Pierre Liardet. Elle a pour domaines de recherche les mathématiques de l'informatique et la modélisation stochastique. Elle développe une approche probabiliste qui permet de résoudre de nombreux problèmes issus des mathématiques discrètes et qui ouvre un vaste champ d'investigations. Les principaux thèmes développés concernent les structures aléatoires discrètes (combinatoire des mots, graphes, générateurs pseudo-aléatoires), l'algorithmique dans ses multiples aspects (complexité, analyse en moyenne, systèmes évolutionnaires) ainsi que les systèmes dynamiques issus de la théorie des nombres (fractions continuées, numérations généralisées). 

    CODES

    Au sein du Groupe d'Etude du Codage de Toulon, cette équipe est dirigée par Jacques Wolfmann. Elle s'intéresse aux mathématiques discrètes liées à la théorie de l'information et plus particulièrement à la théorie du codage. Elle aborde aussi bien les aspects théoriques en relation avec différentes branches des mathématiques (algèbre finie, arithmétique, combinatoire algébrique, géométries finies, géométrie algébrique sur les corps finis, ...), que l'aspect informatique et les applications (traitement et protection de l'information et du signal numérisé, compression des données, synchronisation, transmissions, ...). 

    PACOM (Parallélisme et combinatoire)

    Au sein du Laboratoire Informatique, Signaux et Systèmes de Sophia Antipolis, cette équipe est dirigée par Igor Litovsky, et regroupe des chercheurs ayant des compétences en parallélisme ou en combinatoire. Pour une grande part, les recherches menées dans la branche combinatoire de l'équipe sont motivées, à des degrés divers, par des problèmes liés au parallélisme asynchrone dans des réseaux de processeurs communicants. La programmation parallèle dans le cadre des langages asynchrones est étudiée dans la branche parallélisme de l'équipe. On peut classer les travaux du thème en trois rubriques :
  • ceux qui relèvent à la fois de la combinatoire et du parallélisme (études de divers protocoles de communication dans les réseaux d'interconnexion),
  • ceux qui concernent l'étude de langages pour le parallélisme (langages parallèles asynchrones),
  • ceux qui relèvent de la combinatoire algébrique (étude des codes auto-correcteurs), de la théorie des automates cellulaires, de la combinatoire des mots (langages rationnels de mots infinis), et de la géométrie algorithmique.
  • Plusieurs membres de l'équipe font partie du projet commun SLOOP (CNRS - INRIA - Université de Nice), dirigé par Jean-Claude Bermond, et axé sur le développement de méthodes et d'outils permettant l'utilisation efficace de machines multi-processeurs pour la simulation de systèmes à événements discrets.