| Proposé par : | Julieng |
| Résumé : | Récemment un papier clamait sur arXiv avoir reprouvé le théorème des quatre couleurs en mélangeant le polynôme de Tutte et les séries génératrices. Bon, bien sûr, le papier s'est avéré faux comme le visage d'Isabelle Adjani, mais une interrogation apparut au sein de l'équipe : c'est quoi le polynôme de Tutte au fait ? Il se trouve que pendant ma thèse, j'ai travaillé sur ce polynôme ! Incroyable. Pour la reprise de ce GLT, je vous dirai ce qu'il faut retenir sur ces polynômes, sans trop rentrer dans les détails. |
| Objectifs : | Comprendre le polynôme de Tutte |
| Prérequis : | walou |
| Intéressés : | Julien (2), Julien D (3), Pascal (3), Paul (4) |
| Proposé par : | Julieng |
| Résumé : | Quand j'étais bébé Julieng, j'avais lu un article sur "Pour la Science" qui parlait de cette fameuse suite de Goodstein. La lecture de cet article m'avait fait l'effet d'un petit Big Bang dans mon cerveau, me confortant mon goût et mon amour pour les mathématiques. Qu'est-il question ? Une suite mathématique qui se définit très facilement et dont on a l'impression qu'elle diverge vers l'infini à la vitesse d'un photon sous hormones. Mais en vrai, elle converge vers 0 ! Comment le prouve-t-on ? La preuve est à la fois simple et complexe, mais d'une élégance qui n'a d'égal que M. Akhavi. Elle est forcément un peu complexe vu qu'on peut prouver qu'elle ne peut pas se montrer avec l'arithmétique basique, dite de Peano. Mais ça reste élémentaire. On va parler de ça et si je suis motivé, je lirai l'article qui démontre l'incomplétude de la convergence de la suite de Goodstein pour vous en donner l'idée. |
| Objectifs : | Comprendre la preuve de la convergence de la suite de Goodstein. Un apport de culture G informatique qui parle d'incomplétude et d'ordinaux. |
| Prérequis : | Pas grand chose. |
| Intéressés : | Pascal (5), Paul (4), Rémi P. (4) |
| Proposé par : | Matthieu |
| Résumé : | Les auteurs caractérisent PTIME en terme d'équations différentielles. Ils montrent ainsi que le "General Purpose Analog Computer" de Turing est équivalent à une machine de Turing. L'article est disponible là : https://arxiv.org/abs/1601.05360 |
| Objectifs : | Lire l'article |
| Prérequis : | aucun |
| Intéressés : |
| Proposé par : | Matthieu |
| Résumé : | Je vous propose de lire l'article de L. Valiant qui introduit les algorithmes holographiques. Dans cet article il introduit un nouveau type de réduction "many-to-many" dite holographique. Ces réductions servent notamment à démontrer des résultats de #P-complétude mais aussi en tant qu'outils algorithmiques. L'article est disponible ici : https://epubs.siam.org/doi/10.1137/070682575 |
| Objectifs : | Comprendre l'article |
| Prérequis : | aucun |
| Intéressés : | Julieng (3), Matthieu (4) |
| Proposé par : | Matthieu |
| Résumé : | Le Coupling from the past (CFTP) est une méthode générique permettant d’échantillonner la distribution stationnaire d'une chaîne de Markov. L'idée de ce GLT est de lire plusieurs articles et/ou chapitres de livre pour arriver à l'implémentation de cet algorithme dans un cas concret issu de la littérature ou proposé par les participants. |
| Objectifs : | Comprendre le CFTP L'implémenter sur un cas concret |
| Prérequis : | Aucun |
| Intéressés : | Henri (2), Matthieu (4) |
| Proposé par : | Matthieu |
| Résumé : | Pendant ce groupe de travail nous apprendrons le fonctionnement général du gestionnaire de version git et son utilisation basique pour travailler à plusieurs sur des fichiers communs. Inscription sur https://evento.renater.fr/survey/glt-git-f7z7e8wp |
| Objectifs : | Comprendre et utiliser git |
| Prérequis : | un ordinateur |
| Intéressés : |
| Proposé par : | Julien Clément |
| Résumé : | A border u of a word w = w[0 . . n − 1] of length n is a word (distinct from w) which is both a prefix and a suffix of w. The border array associated with a word w is an array storing for all prefixes of w the length of the maximal border of this prefix. Border arrays are fundamental objects for text algorithms: for instance it is used to compute a good efficient for the classical Morris-Pratt pattern matching algorithm. See pdf: https://clementj01.users.greyc.fr/border-project.pdf |
| Objectifs : | Essayer de compter les tables de bords. Eventuellement si plus simple, pour les mots sur un alphabet de 3 lettres, ou sinon sur un alphabet quelconque. |
| Prérequis : | |
| Intéressés : | Julien (4), Julieng (4), Matthieu (4) |
| Proposé par : | Gaétan Richard |
| Résumé : | L’objectif est de confronter les notions de complexité de Kolmogorov et celle d’entropie (topologique ou métrique) en particulier dans le cadre de système dynamique. Ces deux notions parlent, à quelque part, de choses similaire mais sont rarement étudiées ensemble. Je donnerai les définitions, exemples et propriétés coté complexité de Kolmogorov. J’en appelle aussi un peu à l’aide de l’assistance pour la partie entropie. |
| Objectifs : | Réussir a poser toutes les définitions dans un cadre commun et voir les relations ou différences simples. |
| Prérequis : | |
| Intéressés : | Ali (3), Brigitte (3), Etienne (3), Jerzy (3), Julien Clément (3), Julien Courtiel (1), Loïck (3), Matthieu (1), Paul (2), Théo (3), Véronique (3) |
| Proposé par : | Paul Dorbec |
| Résumé : | Plutot mode groupe de lecture sur l'article récent de Babai pour les isomorphismes de graphes (cf cf https://arxiv.org/abs/1512.03547). Je pense que ça peut aussi être utile pour de possibles interactions avec des collègues de fouilles (notamment sur les projets d'application en pharmacologie). |
| Objectifs : | Etudier et comprendre l'algorithme de l'isomorphisme de graphe récent par Babai. |
| Prérequis : | Savoir ce qu'est un isomorphisme de graphe |
| Intéressés : | Ali (3), Brigitte (3), Etienne (3), Gaétan (4), Julien le Vieux (3), Juliengue (1), Loïck (3), Matthieu (3), stevekhiedi (3), Théo (3), Véronique (3) |
| Proposé par : | Paul Dorbec |
| Résumé : | L'idée de ce projet est de regarder un peu ce qui peut être fait sur cette fameuse conjecture sur les jeux octaux, en sachant bien que le problème est difficile. |
| Objectifs : | Ceci peut être l'occasion d'identifier des sujets de collaboration autour des jeux. |
| Prérequis : | Peut-être le séminaire d'Eric Duchene en décembre |
| Intéressés : | Etienne (3), Gaétan (4), Juliengue (1), Loïck (3), Matthieu (3), Théo (4), Véronique (3) |
| Proposé par : | Matthieu Dien |
| Résumé : | je présenterai brièvement l'analyse de singularité (méthode de combinatoire analytique introduite par Flajolet et Odlyzko dans les années 80/90) et son application aux calculs de lois limites de certains paramètres combinatoires (degré à la racine d'un arbre non-étiqueté ou croissant, "core-size" de cartes ou graphes aléatoires, etc) |
| Objectifs : | présenter cette méthode pour travailler sur les lois limites des objets qui vous intéressent |
| Prérequis : | |
| Intéressés : | Ali (3), Brigitte (3), Julien le Vieux (3), Juliengue (3), Loïck (3), Paul (1) |
| Proposé par : | Matthieu Dien |
| Résumé : | l'article parle de génération aléatoire de lois discrètes en proposant des algorithmes élémentaires |
| Objectifs : | lire l'article, explorer les perspectives présentées dedans |
| Prérequis : | avoir lu l'article (un peu en diagonal) pour pouvoir en discuter après un rappel de 15/20 minutes |
| Intéressés : | Ali (3), Étienne (3), Brigitte (3), Etienne (3), Julien le Vieux (3), Juliengue (3), Loïck (3), Matthieu (5), Paul (3), Véronique (3) |
| Proposé par : | Julien Courtiel |
| Résumé : | Je présenterai une bijection qui voit les cartes planaires de manières arborescente. La bijection est jolie, et pourrait donner lieu à une collaboration sur ce qui concerne la génération aléatoire desdites cartes. |
| Objectifs : | rappeler ce qu'est une carte planaire, présenter la bijection et ses variantes/généralisations. |
| Prérequis : | |
| Intéressés : | Etienne (3), Gaétan (2), Julien Clément (3), Julien Courtiel (5), Loïck (3), Matthieu (4), Paul (2), Théo (2) |