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.

La protection de la jeunesse, la place de l'enfant et sa représentation par avocat

Pris dans l'engrenage de la pratique, comme avocat, depuis maintenant 17 ans, le retour aux études représentait un moment de réflexion et une occasion de faire le point sur l'évolution du judiciaire en matière de protection et la place qu'occupe l'enfant. Certes, la présente démarche n'est pas la solution qui liera le législateur, mais elle s'inscrit dans le cadre de l'évolution de la pratique en matière de protection qui devrait intéresser les intervenants du monde judiciaire et social. Bien que la protection des enfants constitue, pour la société, une action importante, il nous semble que l'analyse et la réflexion sur le sujet aient souvent été faites de façon hermétique en ce sens que les intervenants des différents secteurs se sont souvent ignorés et que le discours de chacun a été peu accessible pour les autres. Le présent travail s'adresse donc aux principaux intervenants en protection de l'enfance, soit les intervenants sociaux et les juristes. Bien sûr, il est possible que certaines parties du travail intéressent davantage les juristes alors que d'autres parties intéresseront plus les intervenants sociaux. Cependant, l'objectif visé est d'amorcer une réflexion qui soit accessible à tous les intervenants. Certains avis et prises de position sur les rôles ou aspects de la pratique intéresseront davantage les juristes, dans certains cas, et, plus indirectement les intervenants sociaux, alors que l'inverse se produira sur d'autres aspects. Le présent travail comporte certaines limites qu'il est nécessaire de signaler. Dans un premier temps, précisons qu'il n'y a pas de présentation ou d'étude systématique de loi, si ce n'est l'utilisation de certains articles de la Loi sur la protection de la jeunesse que nous avons cru nécessaire de citer. Dans un deuxième temps, signalons que l'objectif du travail n'est pas de proposer une réforme, mais qu'il s'agit plutôt d'une réflexion de la part d'un praticien sur certains éléments difficiles de la pratique en matière de protection de l'enfance. Dans un troisième temps, il est important de souligner que le présent travail a été préparé et rédigé avant que ne soient rendus publics les résultats de l'enquête Jasmin concernant la Loi sur la protection de la jeunesse. Les textes, recherches et commentaires déposés auprès de cette Commission n'ont pas été portés à notre connaissance.

Analyse critique des services policiers en tant que "services sociaux" : proposition de complémentarité

Si j'ai choisi comme sujet d'étude "Comment les services sociaux sont appliqués dans le système policier", c'est qu'à plusieurs niveaux cette institution sociale, "la police", constitue un champ privilégié d'étude pour les spécialistes des sciences sociales comme pour ceux de l'administration publique. En effet, parmi les organisations sociales ayant des buts et intérêts précis, dans des rôles spécifiques, la police est de celles qui ont été étudiées tardivement et ce, d'une manière moins approfondie que d'autres organisations comme par exemple, le scolaire, le judiciaire, et aussi le sanitaire. Cet état de choses réside dans de multiples raisons, mais l'une des plus importantes est probablement le peu de priorité accordée dans l'échelle des préoccupations sociales aux problèmes liés au fonctionnement de la police. Il est certain qu'à côté d'un intérêt purement théorique et académique, j'ai également une préoccupation pratique, car, ayant servi plus de huit ans dans les forces policières, il n'y a aucun doute que je fais passer la police dans un ordre de haute priorité dans mes préoccupations de travailleur social, comme dans celles du grand public. Je suis convaincu que les agents de contrôle social, en particulier la police et les services sociaux, exercent par leur diplomatie et par leur jugement, un pouvoir discrétionnaire indispensable qui permet d'aérer un appareil juridique surchargé. Ils deviennent, par le fait même, les pivots d'un appareil de protection sociale. C'est pourquoi, avec une prise de conscience de la police et des services sociaux face aux problèmes qui sont liés au rôle de chacun d'eux, ainsi qu'à l'exercice de leurs fonctions, on pourra peut-être rendre conscients les promoteurs de l'ordre social des valeurs qui sont en cause dans l'action policière. Il serait souhaitable qu'une évolution redéfinisse le rôle de la police dans une société démocratique, afin que de nouvelles solutions puissent apparaître dans l'intérêt du grand public. […]

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.

Mística y seducción : el affaire Cadière-Girard y el triunfo de la racionalidad ilustrada en Thérèse philosophe

[en] This article aims at examining the theoretic and literary models of sexuality offered in the libertine novel Thérèse philosophe, focusing on its representation of the Cadière-Girard affair. During this scandalous trial that took place in the Parliament of Aix-en-Provence in 1731, Jean-Baptiste Girard (Jesuit priest) was accused by Marie-Catherine Cadière (penitent) of sorcery and sexual abuse, while he claimed these charges were calumnies. We seek to show the development of a rationalist, demystifying, scientific perspective on this affair, characteristic of Enlightenment in the eighteenth century, which tended to neutralize and obliterate charismatic religiosity. [fr] Cet article a pour but d’examiner les modèles théoriques et littéraires de la sexualité offerts par le roman libertin Thérèse philosophe, en se concentrant sur la façon dont l’affaire Cadière-Girard y est représentée. Pendant ce procès judiciaire qui a eu lieu au Parlement d’Aix-en-Provence en 1731, Jean-Baptiste Girard (père jésuite) a été accusé par Marie-Catherine Cadière (pénitente) de sorcellerie et abus, ayant reçu elle-même une dénonciation pour calomnies. On cherche à montrer le développement, autour de cette affaire, d’une perspective rationaliste, démystifiante et scientifique, propre des Lumières au XVIIIe siècle, à partir de laquelle la religiosité charismatique se neutralise au point de l’oblitération.

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

Analyse du mouvement social Coule pas chez nous!

Face à la multiplication des projets de transport de pétrole brut envisagés par l’industrie pétrolière pour désenclaver les sables bitumineux, de nombreux mouvements d’opposition se sont mis en branle. On retrouve parmi eux notamment des organisations environnementales, des syndicats, des agriculteurs, des municipalités, mais aussi plusieurs groupes citoyens qui témoignent de la mobilisation citoyenne grandissante face à ces projets. Au Québec, l’un des groupes citoyens les plus en vue est la Fondation Coule pas chez nous. Ce groupe est en voie de devenir un acteur politique influent pour ce qui est de son opposition aux projets de transport de pétrole brut touchant le Québec. L’objectif principal de cet essai est donc d’analyser la Fondation Coule pas chez nous pour contribuer à comprendre quels sont les éléments qui ont mené aux succès obtenus par le groupe et quelle est l’influence du groupe sur le monde politique et sur la société. L’analyse de la Fondation Coule pas chez nous démontre tout d’abord que l’organisation et la mobilisation citoyenne qu’elle engendre répondent à la définition de ce qui est un mouvement social. L’analyse met aussi en évidence les forces du groupe, soit l’étendue du réseau sur lequel il s’appuie, la qualité des liens qu’il a pu tisser avec d’autres acteurs influents et son choix de structure d’organisation. À ceci s’ajoutent le pragmatisme de son argumentaire, sa présence sur le terrain et sa capacité à tirer avantage des opportunités qui s’offrent à lui, notamment à l’échelle municipale. Le groupe a aussi su tirer profit de plusieurs événements symboliques, notamment pour le lancement de sa campagne initiale et pour sa participation à diverses manifestations. Ses actions les plus importantes ont été son implication dans un recours judiciaire mené par le Centre québécois du droit de l’environnement et sa collaboration pour la publication du livre Le Piège Énergie Est d’Éric Pineault, paru sous les Éditions Écosociété. La Fondation Coule pas chez nous utilise principalement le discours du développement durable et les variantes de conscience et politique verte du discours de radicalisme vert. L’utilisation de ces discours pourrait lui avoir permis de contribuer à étendre la mobilisation citoyenne et à placer les enjeux des projets d’expansion du complexe des sables bitumineux sur l'agenda politique à l’échelle municipale, provinciale et fédérale. Le groupe pourrait également avoir eu un impact sur le changement de culture des gens, en les rendant plus actifs au sein de leur communauté. Plusieurs pistes et suggestions sont lancées en fin d’essai pour les suites du mouvement. Entre autres, il est conseillé d’impliquer le citoyen le plus possible, de s’assurer de construire une solidarité au sein du groupe et d’orienter le discours vers des émotions mobilisatrices et un ton positif. Il est également suggéré de développer davantage de partenariats avec les communautés autochtones et les mouvements à l’extérieur du Québec.

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.