 |
Journées Nationales 2018 Du 3 au 6 avril 2018 |
|
|
|
Navigation
SUPPORT
|
Présentation Les journées JNIM (Journées Nationales de l’Informatique Mathématique) sont organisées chaque année par le GDR IM (Informatique Mathématique). C’est un lieu d'information et d'échange annuel entre chercheurs de la discipline et, tout particulièrement, entre chercheurs du GDR. Les journées 2018 sont organisées par le LIX et se tiendront à l'École Polytechnique, du 3 au 6 avril 2018. La journée du 6 avril est consacrée à un hommage à Maurice Nivat. Elles comprendront des présentations longues d’orateur·e·s invite·e·s, de présentations plus courtes de membres des GT du GDR, et de posters de jeunes docteur·e·s ou doctorant·e·s de l’IM. Pour toute question, merci de contacter les organisateurs.
Conférenciers invités, du 3 au 5 avril
L'interrogation de données en présence d'ontologies : Exploiter les connaissances pour mieux tirer parti des données Ces dernières années ont vu un intérêt grandissant pour l’interrogation de données en présence d'ontologies ("ontology-mediated query answering", ou OMQA, en anglais), un nouveau paradigme en gestion de données qui vise à exploiter des connaissances sémantiques décrites par une ontologie afin d'améliorer la réponse aux requêtes. Les ontologies ont plusieurs avantages : elles permettent d'enrichir le vocabulaire d’interrogation des données, de relier les vocabulaires de différentes sources de données, et à pallier l’incomplétude des données en permettant l’inférence de nouveaux faits. Par contre, cette expressivité accrue complexifie la tâche de calculer les réponses aux requêtes. Dans ce contexte, la réécriture de requêtes, qui réduit OMQA à la réponse aux requêtes classique (sans ontologies), est une technique algorithmique particulièrement intéressante, car elle permet de bénéficier des bonnes performances et maturité des systèmes de gestion de bases de données. Dans cet exposé, je commencerai par donner une courte introduction à OMQA, un sujet de recherche très actif à la croisée des domaines de l’intelligence artificielle et des bases de données. Ensuite, je considérerai deux questions naturelles en lien avec la réécriture de requêtes (concernant l'existence et la taille des réécritures) et présenterai des solutions obtenues grâce à des techniques issues de différents champs de l'informatique théorique (complexité de circuits, automates, problèmes de satisfaction de contraintes).
Modélisation expressive des mondes virtuels : Nouvelles avancées en informatique graphique L'informatique graphique a vu récemment émerger des systèmes d'aide à la création 3D qui combinent des modèles géométriques contraints, exprimant des connaissances a priori, avec un contrôle gestuel inspiré du dessin ou de la sculpture. Etendre cette "modélisation expressive" à la synthèse de mondes virtuels complets - typiquement des terrains parcourus de cours d'eau et peuplés de myriades d'éléments comme des rochers ou des plantes, avec les contraintes de cohérence que cela implique - demande un passage à l'échelle difficile. Nous montrerons à travers une série d'exemples comment un contrôle interactif peut être entrelacé avec le maintien de la cohérence, et comment des outils issus de l'apprentissage statistique et de l'interpolation de distributions d'éléments peuvent être exploités pour peupler les paysages.
Joint Complexity with suffix and hyper-suffix trees The joint complexity has been introduced for DNA comparison and has been successfully applied to natural text sampling and clustering. It consists into enumerating the common factors between two texts without taking into consideration languages, grammars and vocabularies. Therefore it is extremely fast to compute via the use of suffix trees. The larger is the joint complexity the closer are the texts in meanings. It provides results at least as accurate as machine learning but without any training and at unprecedented speed. It has been successfully experimented on Twitter flows. Furthermore, it can be precisely analysed via combinatorics and generating functions when the text generation process are Markovian with finite memory. The process of text clustering can even again been accelerated via the use of hyper-suffix trees which have been recently invented. We have called this new branch of Artificial Intelligence which uses combinatorics and fast algorithms, the "accelerated AI". (The talk is based on joint work with Gerard Burnside.)
Recherche exhaustive des pentagones convexes pavant le plan Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties: la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus.
The true concurrency of Herbrand's theorem The brilliant French mathematician Jacques Herbrand died in 1931 in a mountaineering accident at the age of 23. Despite his youth he has two major theorems to his name. One is a foundational result in logic. Herbrand's Theorem is perhaps the first example of information being extracted from a formula in predicate calculus from the bare fact of its provability. In its simplest form his theorem states that if an existential formula of predicate calculus is provable then so is a disjunction got by instantiating its body with finitely many witnesses. More generally, Herbrand showed how an arbitrary formula in the predicate calculus is provable only if a quantifier-free disjunctive formula is provable. Herbrand's proof didn't work directly off the composition of the original formula. Indeed, it seems to be folklore that there is a problem in giving a compositional proof of Herbrand's Theorem. This is made precise by Kohlenbach who shows that one cannot hope directly to use collections of Herbrand witnesses for provable A and (A implies B) to give a collection for B. That leaves open the possibility of making some richer data compositional. In this talk I will sketch how it is useful to regard a classical proof as a distributed strategy. In this way we can obtain a compositional proof of Herbrand's theorem. The `true concurrency' in the title refers to the approach to distributed computation initiated by Carl Adam Petri; in modelling a proof as distributed computation we shall take careful account of the causal dependencies between events intrinsic to the proof. In effect, we exhibit the computational content of a classical proof as a distributed computation. (The talk is based on joint work with Aurore Alcolei and Pierre Clairambault at ENS Lyon, and Martin Hyland at the University of Cambridge.)
Journée du 6 avril en hommage à Maurice Nivat Maurice Nivat, professeur à l'Université Paris-Diderot et pionnier de l'informatique fondamentale en France et dans le monde, nous a quitté le 21 septembre 2017. Sa personnalité exceptionnelle et son rôle fondateur dans de nombreuses structures de l’informatique fondamentale — l’association EATCS, le journal TCS, les conférences ICALP, les écoles EPIT — ont marqué toute une génération d’informaticiens. Le GDR IM lui rend hommage en organisant une journée scientifique.
Maurice : ses travaux, son action, sa marque
Regular transducer expressions for two-way deterministic transducers Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. We show that every regular function, either on finite words or on infinite words, captured by a deterministic two-way transducer, can be described with a regular transducer expression (RTE). RTEs are constructed from constant functions using the combinators if-then-else (deterministic choice), Hadamard product, and unambiguous versions of the Cauchy product, the 2-chained Kleene-iteration and the 2-chained omega-iteration.
Differential Privacy and Applications to Location Privacy In this talk, we review the notion of Differential Privacy, its implications in terms of Bayesian Adversary, and we discuss typical implementations from the point of view of their optimality with respect to utility. Then, we consider an extension of differential privacy to general metric domains, and the consequences for the optimality results. Finally, we show an instantiation to the case of location privacy, leading to the notion of geo-indistinguishability.
Comment nous avons formalisé le parallélisme à travers la théorie des langages
Une approche informatique théorique des nombres de Markoff Nous allons revenir dans la première partie de l'exposé sur l'apport de Maurice Nivat aux pavages du plan et à la géométrie discrète. Nous évoquerons, bien sûr, le théorème de Beauquier-Nivat et ses nombreux prolongements en informatique théorique et algorithmique. Nous montrerons, ainsi, que Maurice aimait beaucoup faire de la recherche en géométrie discrète et en particulier coder des objets géométriques par des mots. Dans cet esprit et dans la seconde partie de l'exposé, nous montrerons comment le codage de segments discrets de la grille Z2 et l'informatique théorique donnent de nouveaux outils pour attaquer la conjecture plus que centenaire de Frobenius sur les nombres de Markoff.
Remerciements Le comité d'organisation des Journées Nationales de l’Informatique Mathématique 2018 remercie les organismes suivants pour leurs soutiens :
Éditions précédentes
|
| Personnes connectées : 1 |
|
