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.

Étude du comportement des piles de pont confinées de PRFC par écoute acoustique

Une structure en béton armé est sujette à différents types de sollicitations. Les tremblements de terre font partie des événements exceptionnels qui induisent des sollicitations extrêmes aux ouvrages. Pour faire face à cette problématique, les codes de calcul des ponts routiers font appel à une approche basée sur des niveaux de performance qui sont rattachés à des états limites. Actuellement, les états limites d'une pile de ponts en béton armé (BA) confinée à l'aide de polymères renforcés de fibres de carbone (PRFC) proposés dans la littérature ne prennent pas en compte le confinement lié au chemisage de PRFC en combinaison avec celui des spirales d'acier. Ce projet de recherche était la suite du volet de contrôle non destructif d'une étude réalisée en 2012 qui comprenait un volet expérimental [Carvalho, 2012] et un volet numérique [Jean, 2012]. L'objectif principal était de compléter l'étude du comportement des poteaux en BA renforcés de PRFC soumis à un chargement cyclique avec les données acoustiques recueillies par St-Martin [2014]. Plus précisément, les objectifs spécifiques étaient de déterminer les états limites reliés aux niveaux de performance et de caractériser la signature acoustique de chaque état limite (p. ex. fissuration du béton, plastification de l'acier et rupture du PRFC). Une méthodologie d'analyse acoustique basée sur l'état de l'art de Behnia et al. [2014] a été utilisée pour quantifier la gravité, localiser et caractériser le type de dommages. Dans un premier temps, les données acoustiques provenant de poutres de 550 mm x 150 mm x 150 mm ont permis de caractériser la signature acoustique des états limites. Puis, des cinq spécimens d'essai construits en 2012, les données acoustiques de trois spécimens, soient des poteaux circulaires d'un diamètre de 305 mm et d'une hauteur de 2000 mm ont été utilisée pour déterminer les états limites. Lors de ces essais, les données acoustiques ont été recueillies avec 14 capteurs de résonances qui étaient reliés à un système multicanal et au logiciel AEwin SAMOS 5.23 de Physical Acoustics Corporation (PAC) [PAC, 2005] par St-Martin [2014]. Une analyse de la distribution des paramètres acoustiques (nbr. de comptes et énergie absolue) combiné à la localisation des événements et le regroupement statistique, communément appelé clustering, ont permis de déterminer les états limites et même, des signes précurseurs à l'atteinte de ces états limites (p. ex. l'initiation et la propagation des fissures, l'éclatement de l'enrobage, la fissuration parallèle aux fibres et l'éclatement du PRFC) qui sont rattachés aux niveaux de performances des poteaux conventionnels et confinés de PRFC. Cette étude a permis de caractériser la séquence d'endommagement d'un poteau en BA renforcé de PRFC tout en démontrant l'utilité de l'écoute acoustique pour évaluer l'endommagement interne des poteaux en temps réel. Ainsi, une meilleure connaissance des états limites est primordiale pour intégrer les PRFC dans la conception et la réhabilitation des ouvrages.

Génération de squelettes des contrats de classes et des tests unitaires en Java

Le logiciel est devenu omniprésent dans nos vies de sorte qu'on le retrouve dans plusieurs domaines de la vie courante. Cependant cette omniprésence, n'est pas sans conséquences. Les bogues de logiciel peuvent causer de vrais désastres, économiques, écologiques voire sanitaires. Vu la forte omniprésente du logiciel dans nos vies, le fonctionnement de nos sociétés dépend fortement de sa qualité. La programmation par contrat a pour but de produire des logiciels fiables, c'est-à-dire corrects et robustes. En effet, ce paradigme de programmation vise à introduire des assertions qui sont des spécifications de services. Ces spécifications représentent une forme de contrat. Les contrats définissent les responsabilités entre le client et le fournisseur. Le respect des contrats permet de garantir que le logiciel ne fait ni plus ni moins que ce que l'on attend de lui qu'il fasse. Le test unitaire est un test qui permet de s'assurer du bon fonctionnement d'une partie précise d'un logiciel. C'est un test dont la vérification se fait en exécutant une petite unité de code. En somme, un test unitaire est un code qui exécute de manière indirecte le code d'une classe pour vérifier que le code fonctionne bien. L'outil Génération de Squelettes des Contrats de classes et des tests unitaires (GACTUS) permet la génération automatique de squelettes de contrats de classes et celles des classes des tests unitaires d'un projet Java. La génération automatique du code source permet d'obtenir un code uniforme. GACTUS est un plug-in pour l'environnement de développement Eclipse écrit en Java. L'objectif principal de GACTUS est de faciliter la réalisation de logiciel de qualité grâce à la génération automatique des squelettes de contrats de classe et celui des tests unitaires et aussi d'accroître la productivité des développeurs. Pour faciliter son utilisation, GACTUS dispose d'une interface graphique permettant de guider l'utilisateur.

Modélisation et analyse d'une machine à absorption/compression hybride fonctionnant à partir de rejets thermiques basse température

Les applications de réfrigération sont aujourd’hui majoritairement réalisées par des machines à compression alimentées en électricité. Animées à partir d’une source chaude, l’utilisation de machines à absorption permet d’utiliser très peu d’électricité comparée à une machine à compression et d’utiliser des réfrigérants écologiques. Le faible coefficient de performance et le coût élevé de ces machines est compensé par l’utilisation de rejets thermiques industriels destinés à être rejeté dans l’environnement et donc considérés comme gratuits. Le but de cette étude est de modéliser une machine à absorption hybride, utilisant le couple de fluide eau et ammoniac, en y ajoutant un compresseur ou booster dans la zone haute pression du circuit et d’évaluer ses performances. Cette modification crée une pression intermédiaire au désorbeur permettant de diminuer la température des rejets thermiques exploitables. Une température de rejets réutilisable de 50°C, contre 80°C actuellement, ouvrirait alors la voie à de nouvelles sources communes d’énergie. Le logiciel ASPEN Plus de simulation des procédés a été choisi afin de modéliser en régime permanent le système. Le modèle est en partie validé par l’étude expérimentale d’une machine à absorption commerciale de 10kW pour des applications de climatisation. Cette machine est située au Laboratoire des Technologies de l’Énergie d’Hydro-Québec. Ensuite, une étude de design permet de montrer, à puissance de réfrigération constante, les impacts bénéfiques de la technologie hybride sur le rendement exergétique, mais également sur la taille globale des échangeurs nécessaires. La technologie hybride est alors analysée économiquement face à une machine à absorption chauffée au gaz pour montrer sa rentabilité.

Génération de patrons de conception et restructuration de code vers un patron de conception pour Java

(POO) est l’utilisation de patrons de conception (PC). Un PC est un arrangement caractéristique de classes permettant d’offrir une solution éprouvée, tout en obtenant un code réutilisable et compréhensible. Plusieurs PC sont définis, dont 24 par la GoF [12] et plusieurs autres sont apparus par la suite. Le concept de PC est abstrait ce qui peut amener différentes interprétations. Ces différences peuvent aussi causer une mauvaise implémentation qui peut réduire les avantages d’utiliser ce patron. Ce projet consiste à concevoir un outil facilitant l’utilisation des PC. L’outil Génération et Restructuration de Patrons de Conception(GRPC) permet la génération automatique du squelette d’un patron de conception ainsi que la restructuration d’un code en le transformant structure respectant un PC. La génération et la restructuration automatique permettent d’obtenir un code uniforme et de qualité tout en respectant le patron de conception. La compréhension et la maintenance du code sont ainsi améliorées. GRPC est module d’extension pour l’environnement de développement Eclipse écrit en Java. Le code est conçu pour être facilement compréhensible et extensible. Les deux principaux objectifs de GRPC sont de restructurer (refactoring) une section de code vers l’architecture d’un patron de conception et de générer des squelettes de patrons de conception. Une interface graphique permet de guider l’utilisateur et d’aller chercher toutes les informations importantes pour le fonctionnement du logiciel. Elle permet aussi de configurer les éléments du patron de conception. Pour s’assurer de la possibilité d’effectuer une restructuration, chaque patron est associé avec une ou plusieurs règles qui analysent le code pour détecter la présence d’une structure particulière. Des procédures aident les développeurs à ajouter de nouveaux PC dans GRPC. GRPC fournit des fonctionnalités permettant d’implémenter quelques patrons de conception de la POO définis dans le livre Design Patterns : Elements of Reusable Object-Oriented Software.

Conception d’un simulateur de conduite pour véhicule Spyder

Le Spyder conçu par BRP est un véhicule complexe, original et peu connu du grand public à travers le monde. Par conséquent, on souhaite développer un outil facile d’accès pour la découverte, la formation au pilotage et l’aide à la conception du roadster. Le sujet de ce projet de maîtrise est le développement du modèle dynamique du véhicule et l’intégration à une plateforme de simulation existante. Pour y parvenir, on élabore un modèle réaliste du véhicule sous deux versions, sport et tourisme. Après avoir recherché les différents paramètres et caractéristiques du véhicule, on se concentre d’abord sur un modèle simple puis sur un modèle plus complexe comportant différents modules, comme la motorisation et les aides à la conduite. En vue de valider le modèle, on utilisera les résultats de tests et des mesures expérimentales. Après validation, le modèle doit être intégré à la nouvelle plateforme de simulation. Le logiciel, développé en langage C++, est élaboré à partir de la plateforme de base. Des modèles 3D détaillés du Spyder offrent un rendu graphique réaliste pour une meilleure immersion. Le modèle est capable de répondre en temps réel et de manière réaliste et précise sous le contrôle de l’utilisateur. On a donc un outil polyvalent à objectifs multiples : faire connaître le véhicule, aider l’ingénieur dans l’étude du véhicule et former les futurs pilotes de manière plus efficace et moins coûteuse. L’outil de simulation peut être également un moyen d’évaluer facilement des paramètres dont l’appréciation est subjective comme la signature sonore du véhicule.

Amélioration des propriétés pharmacocinétiques de peptides par différentes alkylations N-terminales

Modélisations moléculaires réalisés avec le logiciel HyperChem 8.

La rivière Seudre : intégration des données relatives au bassin versant de la Seudre dans un système d'information géographique

La préparation du S.A.G.E. Seudre se poursuit. Il doit permettre dans un premier temps d'informer, de communiquer, de faire un état des lieux de l'existant concernant les aspects environnementaux et socio-économique, la gestion de l'eau, de sa qualité ou d'autres points. L'IFREMER, qui a récemment acquis un logiciel de système d'information géographique l'a exploité pour réaliser un «début d'atlas» sur la Seudre. Cet atlas est donc mis à disposition des utilisateurs potentiels par l'IFREMER, comme base de réflexion. Un stage de D.E.S.S. a été proposé à l'Université de Montpellier, qui forme des étudiants en aménagement du littoral. C'était une bonne occasion de confier cette pré-étude de S.A.G.E. Seudre à une stagiaire qui connaissait déjà la Seudre pour avoir fait un stage de maîtrise au laboratoire Environnement Littoral de l'IFREMER à La Tremblade et, de surcroît, dont le nom évoque la déesse de la SAGEsse.

Transfert de connaissances et politiques publiques : le cas de la politique de gratuité des soins au Niger

Au Niger, le taux de mortalité maternelle est estimé à 535 décès pour 100 000 naissances vivantes (INS, 2013) et la probabilité pour un nouveau-né de mourir avant l’âge d’un mois est de 33 ‰. Depuis 2006, le Niger a mis en place une politique de gratuité des soins pour les femmes enceintes et les enfants de 0 à 5 ans, ce qui a contribué à une amélioration significative de la fréquentation des centres de santé. En mars 2012, un processus délibératif fut organisé pendant une conférence de trois jours pour échanger sur les acquis, limites et perspectives de cette nouvelle politique avec 160 participants dont des chercheurs, des humanitaires, des décideurs politiques et des intervenants sur le terrain. L’objectif de cette recherche est de comprendre les effets de cette conférence ainsi que d’explorer les activités du comité de suivi de la feuille de route. La recherche a été réalisée durant deux mois en été 2014 à Niamey et à N’guiguimi. Elle a reposé sur l’utilisation du cadre conceptuel de Boyko et al., (2012) qui permet de décrire les principales caractéristiques et les effets attendus des dialogues délibératifs et comprendre comment les dialogues délibératifs peuvent contribuer à l’élaboration de politiques sur la base de données probantes. Nous avons mis un accent particulier sur les trois formes d’utilisation des connaissances présentées par Dagenais et al., (2013) : instrumentale, conceptuelle et persuasive. Des entretiens semi-directifs ont été effectués avec 22 acteurs impliqués dans la mise en oeuvre des recommandations. Ils ont été enregistrés, retranscrits intégralement et traités avec le logiciel QDA Miner. Les résultats de l’analyse des discours recueillis révèlent une utilisation instrumentale des recommandations et plus visible chez les humanitaires que les décideurs et les acteurs de la société civile. Il ressort aussi de cette analyse une utilisation conceptuelle et persuasive des recommandations à un degré plus faible parmi tous les acteurs. Le comité de suivi de la feuille route de la conférence n’a pratiquement pas fonctionné, par conséquent, le processus n’a pas eu l’impact souhaité. Les principales raisons de cet échec sont liées au contexte de mise en oeuvre des recommandations (arrestation de plusieurs agents du ministère de la Santé publique qui sont des membres clés du comité de suivi à cause du détournement des fonds GAVI, manque de volonté technique et politique) et/ou aux conditions financières (absence de primes pour les membres du comité et de budget de fonctionnement.). Les iv résultats obtenus ont permis de comprendre les énormes défis (contextuels, financiers notamment) qui restent à relever en matière de transfert de connaissance dans le secteur de santé publique au Niger. En ce qui concerne la suite de la conférence, il faudrait accélérer la redynamisation du comité de suivi en le dotant d’un fonds de fonctionnement et en créant une agence autonome de gestion de la gratuité des soins; et renforcer le soutien politique autour de l’Initiative Santé Solidarité Sahel.

Évolution de la métacognition de trois étudiants du niveau collégial présentant un trouble du spectre de l’autisme

Cette recherche s’intéresse à l’évolution de la conception des stratégies d’apprentissage d’étudiants ou d’étudiantes de niveau collégial présentant un trouble du spectre de l’autisme (TSA). Nous souhaitons analyser la perception que ces étudiants ont de ces stratégies avant notre intervention proprement dite et à la suite de celle-ci, c’est-à-dire de suivre son évolution. Si notre hypothèse de travail se vérifie, l’étudiant ou l’étudiante aux prises avec cette condition devrait se responsabiliser et modifier ses stratégies en fonction des informations que nous lui fournirons. C’est dans le cadre d’interventions éducatives formelles avec l’étudiante ou l’étudiant que nous agirons sur la prise de conscience d’abord, puis sur la modification de ses habitudes et de ses croyances en matière d’apprentissage. Nos interventions prendront la forme d’ateliers individualisés basés sur certains concepts béhavioraux et des théories du courant constructiviste qui tiendront compte, bien entendu, des caractéristiques de la personne ayant un TSA. Dans la présente étude, nous explorerons les stratégies que les étudiants ou les étudiantes présentant un TSA utilisent lors des rédactions dans leurs cours de français, langue d’enseignement et littérature. Nous avons recensé des auteurs pour qui les stratégies d’apprentissage prennent la forme d’actions que l’étudiant ou l’étudiante autiste sera capable de reconnaitre. Nous aimerions savoir si une intervention sur la métacognition auprès d’étudiants ou d’étudiantes ayant un TSA favoriserait chez eux la mise en place de stratégies d’apprentissage efficaces pour la rédaction de l’analyse littéraire, la compétence demandée au terme du premier cours de la séquence des cours de français, langue d’enseignement et littérature. Afin de répondre à cette interrogation, notre recherche vise les objectifs suivants: 1) inventorier les stratégies d’apprentissage utilisées lors de la phase du travail individuel; 2) informer l’étudiant ou l’étudiante du profil d’apprentissage élaboré pour lui ou pour elle par le logiciel Étudiant Plus et ainsi l’aider à prendre conscience de ses stratégies; 3) selon les stratégies identifiées par le questionnaire Étudiant Plus, élaborer deux ou trois ateliers qui tiennent compte des pratiques à modifier lors du travail individuel; 4) appliquer le processus d’encadrement auprès de tous lors de la phase du travail individuel; 5) évaluer les effets de l’expérimentation du processus d’encadrement sur les stratégies d’apprentissage en fonction des changements apportés. Cette recherche est réalisée auprès de trois étudiants. Elle propose une approche méthodologique qui réunit le rôle de la chercheuse et des participants ou des participantes à la recherche. L’analyse des données met en valeur les stratégies d’apprentissage communes utilisées par les étudiants et les étudiantes présentant un TSA. Cette recherche soutient l'adoption d’un processus d’encadrement auprès des étudiants ou des étudiantes ayant un TSA. Notre étude ne vise pas à généraliser les résultats, mais elle favorise une approche éducative centrée sur les besoins d’apprentissage des étudiants ou des étudiantes présentant un TSA.

Facteurs susceptibles d’influencer l'implantation de l'Échelle québécoise des niveaux de compétence en français des personnes immigrantes adultes et du Programme-cadre de français pour les personnes immigrantes adultes au Québec

La coexistence des services de francisation au Québec pour les personnes immigrantes adultes a fait l'objet de divers enjeux liés notamment au passage des apprenants d'un lieu de formation à un autre (Québec, MICC, 2011a). Dans le but de répondre à ces enjeux et d’harmoniser l'offre de services gouvernementaux en matière de francisation des adultes, le ministère de l'Immigration et des Communautés culturelles (MICC) a élaboré en collaboration avec le ministère de l'Éducation, du Loisir et du Sport (MELS), une innovation pédagogique, soit un référentiel commun québécois composé de deux instruments : l’Échelle québécoise des niveaux de compétence en français des personnes immigrantes adultes et le Programme-cadre de français pour les personnes immigrantes adultes au Québec. Le but de notre étude était de mieux comprendre l'implantation du référentiel commun québécois, de faire état des représentations du personnel enseignant en francisation vis-à-vis de cette innovation pédagogique et d’identifier les principaux facteurs qui structurent son implantation. Pour atteindre ces objectifs de recherche, nous avons mené une étude qualitative dans laquelle nous nous sommes appuyée sur le modèle d'implantation de Vince-Whitman (2009) qui identifie douze facteurs facilitant l’implantation d’une politique et d’une pratique. Nous avons accédé aux représentations de douze enseignantes et enseignants en francisation qui œuvrent au MICC et au MELS lors d’entretiens de groupe en leur permettant de s'exprimer sur leurs pratiques pédagogiques et sur leurs impressions du référentiel commun québécois. À l’aide du logiciel QSF NVivo 8, nous avons analysé le contenu des propos de nos participants de recherche. Nos résultats démontrent que le manque appréhendé de ressources – humaines, matérielles et financières, et un manque de temps, de formation et de collaboration professionnelle pourraient représenter des obstacles et nuire à une éventuelle implantation du référentiel commun québécois. À la lumière de ces résultats, nous proposons un cadre de référence composé de sept facteurs d’implantation d’une innovation pédagogique afin de mieux rendre compte d’une réalité spécifique et contemporaine, celle de l'implantation du référentiel commun québécois pour la francisation des immigrants adultes scolarisés. Les écrits scientifiques et nos résultats de recherche démontrent que de diverses formes de soutien, principalement du matériel pédagogique approprié et suffisant, peuvent constituer un facteur-clé dans la réussite de l’implantation d’une innovation pédagogique.

Étude de quelques populations structurées : processus de coalescence et abondance d’une stratégie

Le fichiers qui accompagnent mon document ont été réalisés avec le logiciel Mathematica

La loi applicable aux transferts de biens virtuels

Thèse réalisée en cotutelle avec l'université Paris1-Sorbonne