Université de la Méditerranée - Faculté des Sciences de Luminy
| responsable | David Kohel |
| secrétariat | Sonia Kerbache |
| correspondant | Bernard Mourrain (INRIA Sophia) |
| adresse | Département de Mathématiques, 163 avenue de Luminy, Case 901, 13288 Marseille Cedex 9 |
| téléphone | 04 91 82 90 80 |
| télécopie | 04 91 82 93 56 |
| adresse électronique | mdfi@iml.univ-mrs.fr |
| page web | http://iml.univ-mrs.fr/MDFI/ |
L'année MDFI est une spécialité de 2ème année du Master Mathématiques et Applications de Marseille. Elle s'adresse aux étudiants titulaires d'une première année de master de mathématiques ou d'informatique (ex-maîtrise), ou d'un diplôme équivalent, et qui désirent recevoir une solide formation théorique avant d'aborder la recherche. La spécialité MDFI est sous la responsabilité de la Faculté des Sciences de Luminy (Université de la Méditerranée). L'effectif souhaité en deuxième année est d'environ 20 étudiants.
Tous les cours ont lieu à l'Institut de Mathématiques 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 l'arithmétique, 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 master MDFI, les étudiants peuvent valider des options appartenant à d'autres spécialités du Master Mathématiques et Applications de Marseille.
Le curriculum franco-italien de master en logique est un projet commun à l'Université de la Méditerranée et à l'Università di Roma Tre, dont l'objectif est de permettre à un petit nombre d'étudiants spécialisés en logique d'obtenir le double diplôme de
Les travaux de Gentzen, et plus tard la découverte de l'interprétation algorithmique des preuves ont permis l'émergence d'une nouvelle discipline qui se donne pour but l'élaboration d'une théorie géométrique du calcul : la logique de la programmation. Celle-ci s'est développée de manière extrêmement vivante au point d'être aujourd'hui l'une des branches majeures de la logique mathématique.
Programme :
La théorie de la calculabilité s'intéresse essentiellement à la question suivante : au moyen d'un ordinateur, quelles fonctions peut-on calculer et quels problèmes peut-on résoudre ? Son développement est concomitant de l'apparition des principaux modèles de calcul (fonctions récursives, machines de Turing, lambda-calcul,...) et est très étroitement lié à öla logique mathématique : théorème d'incomplétude de Gödel (qui sera abordé dans ce cours), lambda-calcul typé (cours Preuves et types)...
La complexité cherche quant à elle à mesurer le degré de difficulté d'un problème, typiquement en termes de temps de calcul et d'espace utilisé. Il s'agit donc de questions plus fines, qui font l'objet de nombreuses recherches actuelles, notamment en rapport avec la logique.
L'objectif de ce cours est de présenter les outils et résultats fondamentaux pour aborder ces questions.
Programme :
Bibliographie :
Jean-Claude Bermond (INRIA-MASCOTTE) et Frédéric Havet (INRIA-MASCOTTE)
L'objectif de ce cours est de présenter les notions élémentaires et les outils classiques intervenant en combinatoire dans l'étude des graphes. Dans une première partie, nous aborderons divers problèmes de graphes en nous intéressant plus particulièrement aux aspects algorithmiques et aux aspects constructifs.
Dans une deuxième partie nous étudierons des applications des outils théoriques à des problèmes de télécommunications. Les principaux sujets traités seront :
Bibliographie
Arnaldo Nogueira (IML-DAC)
Un des objectifs de ce cours est de présenter les notions classiques intervenant dans l'étude des fractions continues et des suites de Farey.
L'algorithme des fractions continues est une extension de l'algorithme euclidien, qui est le plus ancien et le plus connu des algorithmes arithmétiques. Il intervient aussi dans de nombreux domaines de recherche en mathématiques. L'action linéaire du groupe SL(2, Z) et le flot horocyclique permettent de traduire des questions arithmétiques dans un cadre dynamique où la Théorie ergodique s'applique d'une façon tout à fait naturelle.
Une partie importante de ce cours sera consacrée à une introduction aux outils élémentaires de la Théorie ergodique. Nous appliquerons ses méthodes à des systèmes dynamiques symboliques, aux fractions continues (applications de Gauss et de Farey) et aussi à des questions liées à l'approximation diophantienne. Ces résultats se généralisent à l'approximation simultanée en plusieurs dimensions. En particulier nous étudierons les propriétés de base de l'action linéaire du groupe SL(n, Z).
Les thèmes suivants seront abordés dans le cours :
Bibliographie
Stephane Ballet
Dans ce cours, nous donnerons une introduction à la théorie des courbes algébriques définies sur un corps (en particulier les corps finis) avec emphase sur l'aspect corps de fonctions algébriques en une variable. En particulier, nous démontrerons dans ce cadre le théorème de Riemann-Roch.Bibliographie
Christophe Ritzenthaler (IML-ATI)
On présentera les notions suivantes :
Bibliographie
Luigi Santocanale (LIF) et Laurent Regnier (IML-LDP)
Cours fondamentaux conseillés : preuves et types, logique et théorie du calcul
Dans une première partie le cours présente la sémantique dénotationnelle à partir de la notion d'espace cohérent, qui est à l'origine de la logique linéaire, dont on étudiera les propriétés. On présentera notamment le calcul des séquents de la logique linéaire, ainsi que la notion de réseau de preuve, qui fournit une approche asynchrone de l'élimination des coupures.
On présentera d'autre part quelques aspects de la sémantique catégorique.
Bibliographie :
Cours fondamentaux conseillés : logique et théorie du calcul
Le problème suivant est indécidable : peut-on déduire une égalité u = 1 (dans un groupe) à partir d'une liste donnée d'égalités (problème du mot) ? Nous allons expliquer la démonstration de ce résultat classique en utilisant des méthodes modernes, à base de réécriture de mots. Ce travail va nous conduire aux développements les plus récents d'une nouvelle branche de l'algèbre et de l'informatique théorique : la théorie homotopique du calcul.
Programme :
Bibliographie :
Pierre Ille (IML-LDP)
Cours fondamentaux conseillés : combinatoire des graphes
En généralisant la notion usuelle d'intervalle d'un ordre total, on parvient à décomposer certaines structures combinatoires sous forme de quotients. On commencera par exposer le théorème de décomposition de T. Gallai pour les graphes non orientés. On l'adaptera ensuite à des graphes orientés comme les tournois. On le généralisera enfin aux structures binaires, encore appelées 2-structures étiquetées, qui regroupent tous les types de graphes. Le cours se terminera avec les premiers résultats sur les structures binaires indécomposables. La question générale étant : est-ce-qu'une structure binaire indécomposable admet des sous-structures indécomposables et de quelles tailles ?
Bibliographie :
Tomasz Miernowski (IML-DAC) et Serge Troubetzkoy (IML-DAC)
Un partie du cours est consacrée à l'étude des mots sturmiens. Un mot infini est une suite infinie de symboles construite à partir d'une alphabet. Appelons toute sous-suite contigüe et finie un facteur de ce mot. Alors, un mot w est dit dit sturmien si, pour tout entier naturel n, w a exactement n + 1 facteurs de longueur n. Il y a plusieurs caractérisations des mots sturmiens, en particulier géométriques et dynamiques.
Bibliographie
Yves Aubry (IML-ATI)
Cours fondamentaux conseillés : , introduction aux courbes elliptiques et à la cryptographie elliptique
Nous commencerons par une étude de l'Arithmétique sur les corps finis, des résultats les plus élémentaires à certains plus sophistiqués.
Nous enchaînerons par une présentation de la théorie des codes correcteurs d'erreurs.
Nous introduirons alors des éléments de Géométrie Algébrique et plus particulièrement les courbes sur les coprs finis.
Enfin, nous terminerons par une étude des codes géométriques algébriques ainsi que des applications à la Cryptographie.
Bibliographie :
Yves Bertot (INRIA-MARELLE), Loïc Pottier (INRIA-MARELLE) et Laurent Théry
Cours fondamentaux conseillés : preuves et types, logique et théorie du calcul
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 Ch. 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.
Bibliographie :
Evelyne Hubert (INRIA-GALAAD) et Bernard Mourrain (INRIA-GALAAD)
Cours fondamentaux conseillés : , introduction aux courbes elliptiques et à la cryptographie elliptique
L'objectif de ce cours est de présenter quelques aspects constructifs de l'algèbre et leur utilisation pour la résolution de systèmes polynomiaux et différentiels.
Dans la première partie seront présentés des algorithmes fondamentaux sur les polynômes univariés (calcul de pgcd, factorisation, isolation de racines réelles,...) au travers desquels on apprendra les techniques de base (calcul modulaire, remontée de Hensel).
La seconde partie du cours sera consacrée aux systèmes de polynômes multivariés (bases de Gröbner, ensembles triangulaires, résultants, résolution de systèmes polynomiaux). Nous illustrerons ces méthodes par des applications pour la démonstration automatique en géométrie, en robotique, en vision par ordinateur, en traitement du signal ou en codage.
Bibliographie :
Frédéric Havet (INRIA-MASCOTTE), Nicolas Nisse et Frédéric Giroire
Cours fondamentaux conseillés : combinatoire des graphes
Le but de ce cours est d'étudier divers problèmes se posant en télécommunications :
Bibliographie :
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.
Cette équipe 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.
L'équipe LDP, fondée par Jean-Yves Girard en 1992, é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 :
L'équipe s'intéresse également à certains problèmes de combinatoire des graphes et des structures ordonnées, notamment les problèmes de décomposition et de reconstruction.
Mascotte (anciennement appelé SLOOP) est un projet commun avec le CNRS et l'Université de Nice-Sophia-Antipolis (UNSA) (dans le cadre du laboratoire I3S). L'objectif du projet Mascotte est de développer des méthodes et outils algorithmiques qui s'appliquent en particulier à la conception de réseaux de télécommunications. La réalisation de cet objectif implique la poursuite de recherches de haut niveau dans les domaines de l'algorithmique, de la simulation et des mathématiques discrètes.
Le projet GALAAD est consacré aux algorithmes algèbriques et géométriques et à leurs applications. Il se propose de rechercher des méthodes exactes 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 où apparaissent de tels problèmes, comme les robots parallèles, la vision, le traitement du signal, la géométrie des molécules. L'interaction constante entre algorithmiques, techniques d'implémentation et applications des méthodes est au coeur des activités de l'équipe. Parmi celles-ci, mentionnons :
Le projet MARELLE 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 passe par trois grands thèmes :
Ce groupe dirigé par Jacques Wolfmann est un laboratoire de l'Université de Toulon et du Var. Les thèmes de recherche de l'équipe sont centrés sur les mathématiques discrètes liées à la théorie de l'information et plus particulièrement à la théorie du codage et à la cryptographie. L'équipe aborde aussi bien les aspects théoriques de ces questions en relation avec différentes branches des mathématiques (algèbre finie, arithmétique, combinatoire algébrique, géométrie finie, 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,...).