Journée de formation, 17 janvier 2017

" L'interface mathématiques/informatique "

Cette journée de formation, organisée à l'UPEM en collaboration avec l'académie de Créteil, a eu lieu le 17 janvier 2017. Une journée similaire sera organisée cette année.

Résumés des conférences et ateliers

Cliquer sur les titres pour accéder aux transparents ou aux documents d'accompagnement.

Une balade mathématico-informatique

Notre voyage commencera en Angleterre à la rencontre d'un cartographe qui n'aura aucun scrupules à donner du travail aux mathématiciens pour plus d'un siècle! Nous le suivrons en France, où il sympathisera avec un voyageur de commerce perdu! Ils iront ensemble à New-York trouver une solution quelque peu hasardeuse, mais commune, à leurs problèmes respectifs . Et nous finirons par nous détendre en faisant avec eux une partie de go au Japon!

Intervenant : T. Jeantheau

Le problème du partage du collier

Deux voleurs ont dérobé un magnifique collier formé de perles de types variés. Comme ils ignorent la valeur de ces types et qu’ils veulent être équitables, les voleurs souhaitent partager le collier de manière à ce que, pour chaque type, chacun d’eux reçoive le même nombre de perles. Un théorème d’Alon, Goldberg et West de 1985 assure que si chaque type est présent un nombre pair de fois sur le collier, il existe un tel partage équitable ne requérant pas plus de coupes qu’il n’y a de types (on suppose les perles fermement fixées sur la chaînette, ce qui implique bien qu’il faut couper le collier pour partager les perles).

Curieusement, la preuve traditionnelle de ce théorème est non-constructive : elle assure l’existence de ce partage équitable, mais ne donne pas de méthode pour le trouver. La question de savoir s’il existe un algorithme efficace pour trouver un tel partage, faisant beaucoup mieux que l’énumération « brute-force » de tous les partages possibles, est toujours ouverte.

Cet exposé présentera un panorama des résultats connus et des questions ouvertes relatifs à ce problème de partage de collier.

Intervenant : F. Meunier

Articulations preuves-algorithmes-programmes : questions didactiques à l'interface math-info

Nous proposerons dans cet exposé quelques réflexions sur les liens entre preuves, algorithmes et programmes à l'interaction entre mathématiques et informatique. Ces liens seront illustrés par plusieurs exemples, notamment autour du principe de dichotomie. Ce travail est lié à un projet initié récemment autour de questions de didactique et épistémologie des interactions mathématiques-informatique. Travail en commun avec Simon Modeste (Université de Montpellier).

Intervenant : A. Meyer

Comment choisir un système de vote ? Paradoxe de Condorcet et transformée de Fourier discrète.

Dans son Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, publié en 1785, Condorcet a mis en évidence le paradoxe d'une élection démocratique ayant au moins trois candidats: il arrive souvent que l’élu finalement choisi n’aurait pas gagné dans un duel contre chacun des autres candidats. C’est le paradoxe de Condorcet. En 1951, le prix nobel d’économie, Kenneth Arrow, a démontré que ce paradoxe pouvait arriver dans tout système électoral non dictatorial. Nous exposerons ces problèmes et la démonstration de 2002, par l’informaticien théorique Gil Kalai utilisant la transformation de Fourier discrète.

Intervenant : M. Fradelizi

Pour aller plus loin~: des notes d'E. Mossel, disponibles sur sa page.

L'aléatoire et l'informatique

Que l'on cherche à étudier numériquement des modèles complexes, à calculer le prix de produits financiers ou à échanger des informations de manière sécurisée, on doit trouver une façon de simuler de l'aléatoire à partir des machines déterministes que sont les ordinateurs. Après avoir montré que les êtres humains sont bien peu performants pour cette tâche, nous verrons deux exemples classiques de «générateurs aléatoires» informatiques, en illustrant leurs qualités et leurs défauts.

Intervenant : P.-A. Zitt

Fractales et systèmes de fonctions itérées

Atelier en salle informatique.

Les ensembles fractals sont des objets mathématiques fascinants : la fois simples à définir et complexes d'un point de vue combinatoire. Ce sont des ensembles auto-similaires, un même motif se répète une infinité de fois à différentes échelles.

Dans cet atelier on se concentrera sur les fractales obtenus par des systèmes de fonctions itérés (IFS en anglais ). Nous présenterons leurs principales propriétés ainsi que différentes façons de les dessiner. Nous proposerons à la fin de l'atelier des programmes en python permettant d'obtenir ces fractales sur un ordinateur. Cet atelier ne nécessite aucune connaissance préalable de Python.

Intervenant : O. Sester

Big Data : une première approche

Lors de cette séance, nous commencerons par nous familiariser avec une méthode statistique récente mais incontournable à présent nommée LASSO. Nous en présenterons les avantages aux travers d'applications dites en grande dimension. Ce type d'applications est l'un des premiers challenges du big data. Nous nous intéressons aux problèmes en grande dimension car ils ont largement été étudiés du point de vue théorique ces 15 dernières années. Par la suite, nous présenterons brièvement plus d'applications de la sphère "big data" et en nous expliquerons les nuances par rapport au problème spécifique de grande dimension.

Intervenant : M. Hebiri

Fichier annexe : les données.

Un algorithme parallèle en mathématiques : la décomposition de domaine

Atelier en salle informatique.

Depuis plusieurs années, l'augmentation de la puissance des ordinateurs, qu'il s'agisse d'ordinateurs personnels ou de super-calculateurs, se fait par la mise en parallèle de plusieurs processeurs. Pour tirer profit de ces architectures parallèles, les algorithmes doivent être adaptés. Il faut diviser la tâche effectuée par l'algorithme en plusieurs sous-tâches qui pourront être effectuées simultanément sur plusieurs processeurs. Cette nécessité de «paralléliser» les algorithmes concerne aussi les algorithmes de résolution numérique de problèmes mathématiques. Dans cet atelier, nous présenterons un exemple d'algorithme parallèle pour la résolution des équations aux dérivées partielles : la méthode de décomposition de domaine. Nous ferons une analyse mathématique simplifiée de cette méthode et nous effectuerons quelques tests pratiques en Python (aucune connaissance préalable de Python n'est nécessaire).

Intervenant : D. Doyen

Types d'ordres, entre géométrie, combinatoire et algorithmique

Pour travailler informatiquement sur un nuage de points (manipuler des triangulations, des enveloppes convexes, des dessins de graphes…), on peut souvent oublier les coordonnées des points et ne travailler que sur des informations combinatoires très succintes. C'est ce que propose la notion de "type d'ordre", qui ne retient que la position mutuelle des points.

Cet atelier se veut une introduction à la géométrie algorithmique et combinatoire et ne supposera connues que des notions très basiques de géométrie.

Intervenant : X. Goaoc