Jeux de policiers et voleurs, Modèles et applications

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound.

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Dynamically balanced and plausible trajectory planning for human-like characters

International audience

The Descent of Pluto: Interactive dynamics, specialisation and reciprocity of roles in a Wikipedia debate

International audience

Introduction to geodesics in sub-Riemannian geometry

International audience

Vocabulary and language model adaptation using information retrieval

International audience

Using Kullback-Leibler Distance for Text Categorization

International audience

Développement d'une librairie de code et d'outils bio-informatiques faciliant l'analyse de grandes quantités de données génomiques

Thèse décrivant l'écriture d'outils spécialisés facilitant l'analyse de grandes quantités de données provenant de technologie de séquencage haut débit.

Amélioration de la technique des anneaux piézoélectriques (P-RAT) à l'aide des simulations 3D

La vitesse des ondes de cisaillement est généralement mesurée en laboratoire en utilisant des éléments piézoélectriques comme les bender elements (BE). Cependant, ces techniques présentent certains problèmes au niveau de l’émission à la fois des ondes primaires et de cisaillement, les effets de champ proche, les effets de bords, et l’incertitude au niveau de l’interprétation du signal. Une nouvelle technique, baptisée technique des anneaux piézoélectriques (P-RAT) a été développée dans le laboratoire géotechnique de l'Université de Sherbrooke afin de minimiser / éliminer les difficultés associées aux autres techniques, en particulier, la pénétration des échantillons, obligatoire pour la technique BE. Cette étude présente une description de la technique P-RAT ainsi que les résultats des simulations numériques réalisées avec le code informatique COMSOL afin d'étudier l'interaction entre les composantes du P-RAT et l'échantillon testé (sol ou solide). L’étude démontre l’efficacité du concept de la méthode P-RAT et présente des modifications pour améliorer la fiabilité et la performance de la méthode P-RAT afin d’étendre son applicabilité dans le domaine du génie civil. L’implémentation de la dernière génération de P-RAT dans une cellule triaxiale et une autre œdométrique était l’aboutissement de cette étude.

Analyse prospective jusqu'en 2025 de la demande en recherche des pays du sud dans le domaine des "ressources vivantes" - Rapport final

L'accélération des changements dans tous les domaines, qu'il s'agisse d'environnement, de technologies ou de la vie des sociétés humaines, est une donnée majeure de notre temps. Jusqu'au XIXe siècle, les hommes gardaient une relative maîtrise des révolutions, qu'elles soient techniques (la vapeur, l'électricité, l'atome, ... ) ou sociales (la démocratie, le communisme, etc). A la fin du XXe siècle, la complexité des sociétés humaines, le foisonnement des découvertes scientifiques rapidement exploitées par l'industrie à des fins économiques et l'interdépendance croissante de toutes les activités dans des écosystèmes fragilisés ont conduit les communautés humaines à davantage subir les révolutions: mondialisation d'une économie de plus en plus immatérielle, explosion de l'informatique dans tous les secteurs, évolution du climat, bouleversement des modes de vie et de la vie même (actions sur les génomes animaux, voire humains) ... Aussi, cette accélération des changements rend d'autant plus indispensable une capacité d'anticiper les tendances et les enjeux qui déterminent l'avenir afin de disposer d'une liberté de réflexion et d'action indépendante de la stricte contrainte des évènements.

On the fly type specialization without type analysis

Les langages de programmation typés dynamiquement tels que JavaScript et Python repoussent la vérification de typage jusqu’au moment de l’exécution. Afin d’optimiser la performance de ces langages, les implémentations de machines virtuelles pour langages dynamiques doivent tenter d’éliminer les tests de typage dynamiques redondants. Cela se fait habituellement en utilisant une analyse d’inférence de types. Cependant, les analyses de ce genre sont souvent coûteuses et impliquent des compromis entre le temps de compilation et la précision des résultats obtenus. Ceci a conduit à la conception d’architectures de VM de plus en plus complexes. Nous proposons le versionnement paresseux de blocs de base, une technique de compilation à la volée simple qui élimine efficacement les tests de typage dynamiques redondants sur les chemins d’exécution critiques. Cette nouvelle approche génère paresseusement des versions spécialisées des blocs de base tout en propageant de l’information de typage contextualisée. Notre technique ne nécessite pas l’utilisation d’analyses de programme coûteuses, n’est pas contrainte par les limitations de précision des analyses d’inférence de types traditionnelles et évite la complexité des techniques d’optimisation spéculatives. Trois extensions sont apportées au versionnement de blocs de base afin de lui donner des capacités d’optimisation interprocédurale. Une première extension lui donne la possibilité de joindre des informations de typage aux propriétés des objets et aux variables globales. Puis, la spécialisation de points d’entrée lui permet de passer de l’information de typage des fonctions appellantes aux fonctions appellées. Finalement, la spécialisation des continuations d’appels permet de transmettre le type des valeurs de retour des fonctions appellées aux appellants sans coût dynamique. Nous démontrons empiriquement que ces extensions permettent au versionnement de blocs de base d’éliminer plus de tests de typage dynamiques que toute analyse d’inférence de typage statique.

Is phraseology the third articulation of language? Fresh insights into a theoretical conundrum

Is phraseology the third articulation of language? Fresh insights into a theoretical conundrum Jean-Pierre Colson University of Louvain (Louvain-la-Neuve, Belgium) Although the notion of phraseology is now used across a wide range of linguistic disciplines, its definition and the classification of phraseological units remain a subject of intense debate. It is generally agreed that phraseology implies polylexicality, but this term is problematic as well, because it brings us back to one of the most controversial topics in modern linguistics: the definition of a word. On the other hand, another widely accepted principle of language is the double articulation or duality of patterning (Martinet 1960): the first articulation consists of morphemes and the second of phonemes. The very definition of morphemes, however, also poses several problems, and the situation becomes even more confused if we wish to take phraseology into account. In this contribution, I will take the view that a corpus-based and computational approach to phraseology may shed some new light on this theoretical conundrum. A better understanding of the basic units of meaning is necessary for more efficient language learning and translation, especially in the case of machine translation. Previous research (Colson 2011, 2012, 2013, 2014), Corpas Pastor (2000, 2007, 2008, 2013, 2015), Corpas Pastor & Leiva Rojo (2011), Leiva Rojo (2013), has shown the paramount importance of phraseology for translation. A tentative step towards a coherent explanation of the role of phraseology in language has been proposed by Mejri (2006): it is postulated that a third articulation of language intervenes at the level of words, including simple morphemes, sequences of free and bound morphemes, but also phraseological units. I will present results from experiments with statistical associations of morphemes across several languages, and point out that (mainly) isolating languages such as Chinese are interesting for a better understanding of the interplay between morphemes and phraseological units. Named entities, in particular, are an extreme example of intertwining cultural, statistical and linguistic elements. Other examples show that the many borrowings and influences that characterize European languages tend to give a somewhat blurred vision of the interplay between morphology and phraseology. From a statistical point of view, the cpr-score (Colson 2016) provides a methodology for adapting the automatic extraction of phraseological units to the morphological structure of each language. The results obtained can therefore be used for testing hypotheses about the interaction between morphology, phraseology and culture. Experiments with the cpr-score on the extraction of Chinese phraseological units show that results depend on how the basic units of meaning are defined: a morpheme-based approach yields good results, which corroborates the claim by Beck and Mel'čuk (2011) that the association of morphemes into words may be similar to the association of words into phraseological units. A cross-linguistic experiment carried out for English, French, Spanish and Chinese also reveals that the results are quite compatible with Mejri’s hypothesis (2006) of a third articulation of language. Such findings, if confirmed, also corroborate the notion of statistical semantics in language. To illustrate this point, I will present the PhraseoRobot (Colson 2016), a computational tool for extracting phraseological associations around key words from the media, such as Brexit. The results confirm a previous study on the term globalization (Colson 2016): a significant part of sociolinguistic associations prevailing in the media is related to phraseology in the broad sense, and can therefore be partly extracted by means of statistical scores. References Beck, D. & I. Mel'čuk (2011). Morphological phrasemes and Totonacan verbal morphology. Linguistics 49/1: 175-228. Colson, J.-P. (2011). La traduction spécialisée basée sur les corpus : une expérience dans le domaine informatique. In : Sfar, I. & S. Mejri, La traduction de textes spécialisés : retour sur des lieux communs. Synergies Tunisie n° 2. Gerflint, Agence universitaire de la Francophonie, p. 115-123. Colson, J.-P. (2012). Traduire le figement en langue de spécialité : une expérience de phraséologie informatique. In : Mogorrón Huerta, P. & S. Mejri (dirs.), Lenguas de especialidad, traducción, fijación / Langues spécialisées, figement et traduction. Encuentros Mediterráneos / Rencontres Méditerranéennes, N°4. Universidad de Alicante, p. 159-171. Colson, J.-P. (2013). Pratique traduisante et idiomaticité : l’importance des structures semi-figées. In : Mogorrón Huerta, P., Gallego Hernández, D., Masseau, P. & Tolosa Igualada, M. (eds.), Fraseología, Opacidad y Traduccíon. Studien zur romanischen Sprachwissenschaft und interkulturellen Kommunikation (Herausgegeben von Gerd Wotjak). Frankfurt am Main, Peter Lang, p. 207-218. Colson, J.-P. (2014). La phraséologie et les corpus dans les recherches traductologiques. Communication lors du colloque international Europhras 2014, Association Européenne de Phraséologie. Université de Paris Sorbonne, 10-12 septembre 2014. Colson, J-P. (2016). Set phrases around globalization : an experiment in corpus-based computational phraseology. In: F. Alonso Almeida, I. Ortega Barrera, E. Quintana Toledo and M. Sánchez Cuervo (eds.), Input a Word, Analyse the World: Selected Approaches to Corpus Linguistics. Newcastle upon Tyne: Cambridge Scholars Publishing, p. 141-152. Corpas Pastor, G. (2000). Acerca de la (in)traducibilidad de la fraseología. In: G. Corpas Pastor (ed.), Las lenguas de Europa: Estudios de fraseología, fraseografía y traducción. Granada: Comares, p. 483-522. Corpas Pastor, G. (2007). Europäismen - von Natur aus phraseologische Äquivalente? Von blauem Blut und sangre azul. In: M. Emsel y J. Cuartero Otal (eds.), Brücken: Übersetzen und interkulturelle Kommunikationen. Festschrift für Gerd Wotjak zum 65. Geburtstag, Fráncfort: Peter Lang, p. 65-77. Corpas Pastor, G. (2008). Investigar con corpus en traducción: los retos de un nuevo paradigma [Studien zur romanische Sprachwissenschaft und interkulturellen Kommunikation, 49], Fráncfort: Peter Lang. Corpas Pastor, G. (2013). Detección, descripción y contraste de las unidades fraseológicas mediante tecnologías lingüísticas. In Olza, I. & R. Elvira Manero (eds.) Fraseopragmática. Berlin: Frank & Timme, p. 335-373. Leiva Rojo, J. (2013). La traducción de unidades fraseológicas (alemán-español/español-alemán) como parámetro para la evaluación y revisión de traducciones. In: Mellado Blanco, C., Buján, P, Iglesias N.M., Losada M.C. & A. Mansilla (eds), La fraseología del alemán y el español: lexicografía y traducción. ELS, Etudes Linguistiques / Linguistische Studien, Band 11. München: Peniope, p. 31-42. Leiva Rojo, J. & G. Corpas Pastor (2011). Placing Italian idioms in a foreign milieu: a case study. In: Pamies Bertrán, A., Luque Nadal, L., Bretana, J. &; M. Pazos (eds), (2011). Multilingual phraseography. Second Language Learning and Translation Applications. Baltmannsweiler: Schneider Verlag (Colección: Phraseologie und Parömiologie, 28), p. 289-298. Martinet, A. (1966). Eléments de linguistique générale. Paris: Colin. Mejri, S. (2006). Polylexicalité, monolexicalité et double articulation. Cahiers de Lexicologie 2: 209-221.