Displaying similar documents to “The second-order monadic theory of the free inverse monoid is undecidable. (La théorie monadique du second ordre du monoïde inversif libre est indécidable.)”

Groupes aléatoires

Étienne Ghys (2002-2003)

Séminaire Bourbaki

Similarity:

Quelles sont les propriétés d’un groupe de présentation finie “tiré au hasard” ? La réponse à cette question dépend bien entendu de la méthode choisie pour le tirage au sort. On peut par exemple fixer n générateurs et choisir p relations aléatoirement parmi les mots de longueur L , puis faire tendre L vers l’infini. On peut aussi choisir un graphe fini, étiqueter aléatoirement ses arêtes par des générateurs, et considérer le groupe engendré par ces générateurs, soumis aux relations lues...

Perspective historique sur les rapports entre la théorie des modèles et l’algèbre. Un point de vue tendancieux

Daniel Lascar (1998)

Revue d'histoire des mathématiques

Similarity:

Je vais traiter, d’un point de vue personnel, la naissance et les premiers développements de la théorie des modèles pendant la période qui s’étend de sa naissance vers 1870, avec les travaux de Peirce, jusqu’au théorème de Morley vers 1965. J’insisterai particulièrement sur l’aspect « algèbre universelle » et j’essaierai de dégager comment la notion de définissabilité a fait évoluer cette théorie jusqu’à une science complexe pouvant apporter de nouvelles idées au reste des mathématiques. ...

Des explications pour reconnaître et exploiter les structures cachées d’un problème combinatoire

Hadrien Cambazard, Narendra Jussien (2006)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

L’identification de structures propres à un problème est souvent une étape clef pour la conception d’heuristiques de recherche comme pour la compréhension de la complexité du problème. De nombreuses approches en Recherche Opérationnelle emploient des stratégies de relaxation ou de décomposition dès lors que certaines struc- tures idoines ont été identifiées. L’étape suivante est la conception d’algorithmes de résolution qui puissent intégrer à la volée, pendant la résolution, ce type...

Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances

Marc Demange, Vangelis Paschos (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement...

Exploration d’un mode d’écriture de la généralité : l’article de Poincaré sur les lignes géodésiques des surfaces convexes (1905)

Anne Robadey (2004)

Revue d'histoire des mathématiques

Similarity:

L’analyse de l’article de Poincaré sur les géodésiques fait apparaître qu’il entretient des liens complexes avec les travaux antérieurs de Poincaré en mécanique céleste. Nous montrerons que le problème des géodésiques des surfaces convexes est traité comme un paradigme grâce auquel Poincaré explicite une méthode qui n’était présentée qu’à l’état d’ébauche dans ses ouvrages de mécanique céleste. Cette étude de cas permet ainsi de mettre en évidence l’utilisation par Poincaré d’une technique...

La différentiation automatique et son utilisation en optimisation

Jean-Pierre Dussault (2008)

RAIRO - Operations Research

Similarity:

In this work, we present an introduction to automatic differentiation, its use in optimization software, and some new potential usages. We focus on the potential of this technique in optimization. We do not dive deeply in the intricacies of automatic differentiation, but put forward its key ideas. We sketch a survey, as of today, of automatic differentiation software, but warn the reader that the situation with respect to software evolves rapidly. In the last part of the paper, we present...

Configuration des lignes d'usinage à boîtiers multibroches : une approche mixte

Olga Guschinskaya, Alexandre Dolgui (2009)

RAIRO - Operations Research

Similarity:

Ce travail porte sur l'optimisation des lignes d'usinage pour la grande série. Une telle ligne comporte plusieurs postes de travail, chacun étant équipé avec boîtiers multibroches. Un boîtier multibroche exécute plusieurs opérations en parallèle. Lors de la conception en avant-projet, il est nécessaire d'affecter toutes les opérations à des boîtiers et des postes de travail de sorte à minimiser le nombre de postes et de boîtiers utilisés. Pour ce nouveau problème d'équilibrage des...

Une nouvelle transformation des réseaux de Petri généralisés : l’abstraction généralisée

Christophe Haro, Patrick Martineau, Christian Proust (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Cet article introduit une nouvelle transformation des réseaux de Petri généralisés appelée l’abstraction généralisée. C’est une réduction dont nous montrons qu’elle conserve les invariants du réseau de départ et les propriétés structurelles les plus importantes. Une fonction de transformation de marquages nous permet d’introduire l’étude de la conservation des propriétés comportementales.

Capacité analytique et le problème de Painlevé

Hervé Pajot (2003-2004)

Séminaire Bourbaki

Similarity:

Le problème de Painlevé consiste à trouver une caractérisation géométrique des sous-ensembles du plan complexe qui sont effaçables pour les fonctions holomorphes bornées. Ce problème d’analyse complexe a connu ces dernières années des avancées étonnantes, essentiellement grâce au dévelopement de techniques fines d’analyse réelle et de théorie de la mesure géométrique. Dans cet exposé, nous allons présenter et discuter une solution proposée par X. Tolsa en termes de courbure de Menger...