Algorithmes d'apprentissage pour la recommandation

L'ère numérique dans laquelle nous sommes entrés apporte une quantité importante de nouveaux défis à relever dans une multitude de domaines. Le traitement automatique de l'abondante information à notre disposition est l'un de ces défis, et nous allons ici nous pencher sur des méthodes et techniques adaptées au filtrage et à la recommandation à l'utilisateur d'articles adaptés à ses goûts, dans le contexte particulier et sans précédent notable du jeu vidéo multi-joueurs en ligne. Notre objectif est de prédire l'appréciation des niveaux par les joueurs. Au moyen d'algorithmes d'apprentissage machine modernes tels que les réseaux de neurones profonds avec pré-entrainement non-supervisé, que nous décrivons après une introduction aux concepts nécessaires à leur bonne compréhension, nous proposons deux architectures aux caractéristiques différentes bien que basées sur ce même concept d'apprentissage profond. La première est un réseau de neurones multi-couches pour lequel nous tentons d'expliquer les performances variables que nous rapportons sur les expériences menées pour diverses variations de profondeur, d'heuristique d'entraînement, et des méthodes de pré-entraînement non-supervisé simple, débruitant et contractant. Pour la seconde architecture, nous nous inspirons des modèles à énergie et proposons de même une explication des résultats obtenus, variables eux aussi. Enfin, nous décrivons une première tentative fructueuse d'amélioration de cette seconde architecture au moyen d'un fine-tuning supervisé succédant le pré-entrainement, puis une seconde tentative où ce fine-tuning est fait au moyen d'un critère d'entraînement semi-supervisé multi-tâches. Nos expériences montrent des performances prometteuses, notament avec l'architecture inspirée des modèles à énergie, justifiant du moins l'utilisation d'algorithmes d'apprentissage profonds pour résoudre le problème de la recommandation.

Quantification de la relation séquence-activité de l’ARN par prédiction de structure tridimensionnelle

Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation.

The DPRK in China's post-cold war foreign policy - a neoclassical realist analysis

Avec l’échec des négociations entre les États-Unis et la Corée du Nord, menées depuis le début des années 1990, sur la question du nucléaire, le problème est devenu graduellement l’affaire des pays voisins, tous soucieux de l’avenir de la région du sud-est asiatique. Présentée comme le seul allié de la Corée du Nord, la China a été invitée à participer à des négociations à trois, à quatre (1997-1998), et à six (2003-2007), dans l’espoir de faire entendre raison au régime isolé, mais jusqu’à maintenant, aucune des tentatives n’est parvenue à satisfaire chacun des membres à la table. Alors que la tension monte et que la politique américaine se fait de moins en moins flexible, la Chine quant à elle, continue d’encourager le retour des négociations à six (Six-Party Talks) dans l’optique de dénucléariser la péninsule coréenne, tout en travaillant à maintenir ses liens avec la Corée du Nord. Le fil conducteur de cette présente recherche est d’abord d’essayer de comprendre pourquoi la Chine continue de soutenir la Corée du Nord, fournissant dons alimentaires et financiers. L’idée est donc d’analyser, selon les principes du réalisme néoclassique, la politique étrangère de la Chine. L’hypothèse principale de cette théorie renvoie à l’idée que la distribution du pouvoir dans le système international influence la politique étrangère des États, mais que des variables au niveau de l’état et/ou de l’individu interviennent dans la formulation et l’application de celle-ci. Il est proposé ici que le lien entre l’unipolarité du système international et la politique nord-coréenne de la Chine, est façonné par des variables intermédiaires telles que : a) la perception des leaders de la distribution du pouvoir et de leur place dans le système international; b) l’idéologie du régime politique, et; c) le type d’unité responsable de la prise de décision en politique étrangère. L’analyse de chacune des variables permettra de faire la lumière sur les intérêts politiques et économiques de la Chine dans l’entretien de cette relation avec la Corée du Nord.

Sécurité polynomiale en cryptographie

Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2).

Amorçage cognitif pour amélioration de l’acquisition de la connaissance dans un système tutoriel intelligent

Cette thèse vise à définir une nouvelle méthode d’enseignement pour les systèmes tutoriels intelligents dans le but d’améliorer l’acquisition des connaissances. L’apprentissage est un phénomène complexe faisant intervenir des mécanismes émotionnels et cognitifs de nature consciente et inconsciente. Nous nous intéressons à mieux comprendre les mécanismes inconscients du raisonnement lors de l’acquisition des connaissances. L’importance de ces processus inconscients pour le raisonnement est bien documentée en neurosciences, mais demeure encore largement inexplorée dans notre domaine de recherche. Dans cette thèse, nous proposons la mise en place d’une nouvelle approche pédagogique dans le domaine de l’éducation implémentant une taxonomie neuroscientifique de la perception humaine. Nous montrons que cette nouvelle approche agit sur le raisonnement et, à tour de rôle, améliore l’apprentissage général et l’induction de la connaissance dans un environnement de résolution de problème. Dans une première partie, nous présentons l’implémentation de notre nouvelle méthode dans un système tutoriel visant à améliorer le raisonnement pour un meilleur apprentissage. De plus, compte tenu de l’importance des mécanismes émotionnels dans l’apprentissage, nous avons également procédé dans cette partie à la mesure des émotions par des capteurs physiologiques. L’efficacité de notre méthode pour l’apprentissage et son impact positif observé sur les émotions a été validée sur trente et un participants. Dans une seconde partie, nous allons plus loin dans notre recherche en adaptant notre méthode visant à améliorer le raisonnement pour une meilleure induction de la connaissance. L’induction est un type de raisonnement qui permet de construire des règles générales à partir d’exemples spécifiques ou de faits particuliers. Afin de mieux comprendre l’impact de notre méthode sur les processus cognitifs impliqués dans ce type de raisonnement, nous avons eu recours à des capteurs cérébraux pour mesurer l’activité du cerveau des utilisateurs. La validation de notre approche réalisée sur quarante-trois volontaires montre l’efficacité de notre méthode pour l’induction de la connaissance et la viabilité de mesurer le raisonnement par des mesures cérébrales suite à l’application appropriée d’algorithmes de traitement de signal. Suite à ces deux parties, nous clorons la thèse par une discussion applicative en décrivant la mise en place d’un nouveau système tutoriel intelligent intégrant les résultats de nos travaux.

Étude numérique des origines hémodynamiques des oscillations dans des réseaux de capillaires

En simulant l’écoulement du sang dans un réseau de capillaires (en l’absence de contrôle biologique), il est possible d’observer la présence d’oscillations de certains paramètres comme le débit volumique, la pression et l’hématocrite (volume des globules rouges par rapport au volume du sang total). Ce comportement semble être en concordance avec certaines expériences in vivo. Malgré cet accord, il faut se demander si les fluctuations observées lors des simulations de l’écoulement sont physiques, numériques ou un artefact de modèles irréalistes puisqu’il existe toujours des différences entre des modélisations et des expériences in vivo. Pour répondre à cette question de façon satisfaisante, nous étudierons et analyserons l’écoulement du sang ainsi que la nature des oscillations observées dans quelques réseaux de capillaires utilisant un modèle convectif et un modèle moyenné pour décrire les équations de conservation de masse des globules rouges. Ces modèles tiennent compte de deux effets rhéologiques importants : l’effet Fåhraeus-Lindqvist décrivant la viscosité apparente dans un vaisseau et l’effet de séparation de phase schématisant la distribution des globules rouges aux points de bifurcation. Pour décrire ce dernier effet, deux lois de séparation de phase (les lois de Pries et al. et de Fenton et al.) seront étudiées et comparées. Dans ce mémoire, nous présenterons une description du problème physiologique (rhéologie du sang). Nous montrerons les modèles mathématiques employés (moyenné et convectif) ainsi que les lois de séparation de phase (Pries et al. et Fenton et al.) accompagnés d’une analyse des schémas numériques implémentés. Pour le modèle moyenné, nous employons le schéma numérique explicite traditionnel d’Euler ainsi qu’un nouveau schéma implicite qui permet de résoudre ce problème d’une manière efficace. Ceci est fait en utilisant une méthode de Newton- Krylov avec gradient conjugué préconditionné et la méthode de GMRES pour les itérations intérieures ainsi qu’une méthode quasi-Newton (la méthode de Broyden). Cette méthode inclura le schéma implicite d’Euler et la méthode des trapèzes. Pour le schéma convectif, la méthode explicite de Kiani et al. sera implémentée ainsi qu’une nouvelle approche implicite. La stabilité des deux modèles sera également explorée. À l’aide de trois différentes topologies, nous comparerons les résultats de ces deux modèles mathématiques ainsi que les lois de séparation de phase afin de déterminer dans quelle mesure les oscillations observées peuvent être attribuables au choix des modèles mathématiques ou au choix des méthodes numériques.

Analyse de la distribution des génotypes du virus du papillome humain dans les néoplasies anogénitales et de la tête et du cou en Afrique comparativement au reste du monde

Le virus du papillome humain (HPV) est l’infection sexuellement transmise la plus fréquente au monde. Plusieurs études ont établi son implication dans l’étiologie de pratiquement tous les cancers du col de l’utérus, une maladie qui constitue un problème de santé majeur dans les pays pauvres. Le HPV est également responsable de 90% des cancers de l’anus, 40-50% des cancers du pénis, de la vulve et du vagin, et 30% des cancers de la tête et du cou. L’objectif général de cette thèse est de combler les lacunes relatives aux connaissances sur la distribution génotypique du HPV dans les lésions néoplasiques cervicales utérines et de la tête et du cou, plus particulièrement en Afrique. Les objectifs spécifiques sont les suivants: 1) analyser la distribution génotypique du HPV dans les cancers du col de l’utérus et faire une analyse comparative de cette distribution dans cinq pays africains en fonction de la prévalence du VIH; 2) évaluer la présence du HPV dans les cancers de la tête et du cou au Sénégal; 3) faire une revue de la littérature et une méta-analyse sur la distribution du HPV dans les cancers de la tête et du cou dans toutes les régions du monde. Pour le premier et le second objectifs, qui découlent d’un large projet international coordonné par l’Institut Catalan d’Oncologie pour l’Organisation Mondiale de la Santé (OMS), une étude transversale multicentrique a été menée au Mali et au Sénégal pour collecter des blocs de paraffine de patientes diagnostiquées entre 2001 et 2010 du cancer invasif du col et des cancers de la tête et du cou. Pour le troisième objectif, une revue exhaustive de la littérature a permis d’identifier tous les articles qui ont été publiés sur les cancers de la tête et du cou dans tous les pays du monde et d’effectuer une méta-analyse sur la prévalence de l’ADN du HPV selon le site du cancer et la région géographique. Notre analyse montre que les principaux types de HPV ciblés dans les vaccins prophylactiques (HPV16/18) représentent la majorité des types de HPV détectés dans le cancer invasif du col de l’utérus en Afrique subsaharienne. Par contre, le HPV45 vient au second rang dans certains pays d’Afrique, dont le Mali et le Sénégal. Nos données suggèrent également que le VIH aurait un rôle dans la contribution relative du HPV18 et HPV45 dans le développement du cancer du col de l’utérus. Au Sénégal, notre étude montre que la prévalence du HPV dans les cancers de la tête et du cou est très faible et ne semble pas jouer un rôle important dans l’oncogenèse. Finalement, la méta-analyse a mesuré la prévalence des HPV dans les cancers de la cavité orale, de l’oropharynx, du larynx et de l’hypopharynx, et confirme l’importante contribution relative du HPV16 dans ces cancers. Globalement, cette thèse permet de mieux comprendre l’impact potentiel des vaccins prophylactiques sur l’incidence des cancers associés au HPV.

Du Roman au théâtre : le motif du Graal réactualisé dans les textes de théâtre de Jean Cocteau, Julien Gracq et Jacques Roubaud/Florence Delay

Ce travail analyse les transformations du Graal en comparant sa représentation dans les romans médiévaux et dans trois textes de théâtre modernes. Le Graal, apparu dans la littérature au Moyen Âge, reste une source d'inspiration pour les écrivains modernes au point de gagner, avec le temps, un statut légendaire. L'objet de prédilection de la littérature arthurienne a évolué de façon significative dès le Moyen Âge, où il reste cependant confiné aux formes narratives. Après le « festival scénique sacré » (Bühnenweihfestspiel), Parsifal, de Wagner présenté en 1882 à Bayreuth, des œuvres plus récentes réactualisent le mythe en cherchant à l'adapter au théâtre. Jean Cocteau, en 1937, dans Les Chevaliers de la Table Ronde, présente un Graal inaccessible, immatériel. En 1948, Julien Gracq, dans Le Roi Pêcheur, inscrit le Graal dans l'opposition entre le profane et le sacré. Jacques Roubaud et Florence Delay, dans les éditions de 1977 et 2005 de Graal Théâtre, optent pour une récriture où les représentations du mythe se côtoient et se confrontent. Ces textes de théâtre modernes, où la représentation du Graal se situe au cœur du projet d'écriture, entrent ainsi en relation directe avec les œuvres médiévales. Ils s'inscrivent dans une redéfinition de l'objet qui se renouvelle sans cesse depuis Le Conte du Graal de Chrétien de Troyes. Dans les trois cas, la représentation du Graal entretient des relations contradictoires de filiation et de rupture avec la littérature arthurienne de l'époque médiévale. L'hypothèse principale de cette recherche se situe dans la problématique de la récriture comme transformation d'un héritage. Plus précisément, il sera question de comprendre comment la représentation du Graal dans les textes de théâtre pose problème et comment cette question est modulée, travaillée par les auteurs en termes rhétoriques, stylistiques et dramaturgiques. L'utilisation de la parodie, d'anachronismes et de voix dramatiques nouvelles, par exemple, permet aux auteurs modernes de revisiter et de changer le rapport à l'objet. Le Graal se redéfinit dans des contextes historiques et dans un genre distincts de leur source du Moyen Âge.

Le rôle et la régulation du pyroglutamylated RF-amide peptide dans le tissu adipeux lors de l’obésité

L’obésité est définie comme un surplus de masse adipeuse. Cette condition représente un problème de santé publique devenu pandémique dans les pays industrialisés. Elle prédispose à des maladies potentiellement mortelles comme le diabète de type 2, les maladies cardiovasculaires et la stéatose hépatique non-alcoolique. L’accumulation du tissu adipeux intra-abdominal, formé d’adipocytes, est corrélée avec la résistance à l’insuline. L’augmentation de la masse adipeuse se fait par l’hyperplasie des préadipocytes, la différenciation des préadipocytes en adipocytes et l’hypertrophie des adipocytes. La différenciation des préadipocytes se fait selon l’adipogenèse qui est régulée par une multitude de facteurs, mais qui est inhibée pas les stimuli inflammatoires qui sont aussi responsables de la résistance à l’insuline et de l’apparition des problèmes de santé liés à l’obésité. Nous avons identifié un nouveau système de régulation autocrine/paracrine de l’adipogenèse dans les cellules du tissu adipeux. Le pyroglutamylated RF-amide peptide (QRFP), qui était connu pour son rôle dans la régulation de l’appétit, est un activateur de l’adipogenèse par l’activation de son récepteur, le G protein-coupled receptor 103 (GPR103). Le QRFP est exprimé dans les macrophages et les adipocytes alors que le GPR103 de sous-type b est exprimé dans les adipocytes seulement. Un traitement des adipocytes avec le QRFP augmente le captage des acides gras, l’accumulation de lipides ainsi que l’expression et l’activité de l’enzyme LPL. Le QRFP augmente aussi l’expression des gènes des transporteurs d’acides gras CD36 et FATP1, de l’enzyme activatrice d’acides gras ACSL1 et des facteurs de transcription PPAR-γ et C/EBP-α, qui sont tous impliqués dans l’adipogenèse. En plus de ses effets sur l’adipogenèse, le QRFP possède aussi un effet inhibiteur sur l’activité lipolytique induite par les catécholamines. Nous avons montré que l’expression du QRFP est diminuée dans le tissu adipeux des souris obèses. Selon nos résultats, cette diminution pourrait être expliquée par une augmentation des endotoxines circulantes chez les obèses, appelée endotoxémie métabolique, qui agirait, entre autres, par l’induction des interférons dans les macrophages. Les voies de signalisation de ces effets ont aussi été identifiées. Nous avons montré un autre exemple de stimulus inflammatoire qui régule les signaux adipogènes à la baisse.

Représentation et identification des hypersurfaces

L’objectif à moyen terme de ce travail est d’explorer quelques formulations des problèmes d’identification de forme et de reconnaissance de surface à partir de mesures ponctuelles. Ces problèmes ont plusieurs applications importantes dans les domaines de l’imagerie médicale, de la biométrie, de la sécurité des accès automatiques et dans l’identification de structures cohérentes lagrangiennes en mécanique des fluides. Par exemple, le problème d’identification des différentes caractéristiques de la main droite ou du visage d’une population à l’autre ou le suivi d’une chirurgie à partir des données générées par un numériseur. L’objectif de ce mémoire est de préparer le terrain en passant en revue les différents outils mathématiques disponibles pour appréhender la géométrie comme variable d’optimisation ou d’identification. Pour l’identification des surfaces, on explore l’utilisation de fonctions distance ou distance orientée, et d’ensembles de niveau comme chez S. Osher et R. Fedkiw ; pour la comparaison de surfaces, on présente les constructions des métriques de Courant par A. M. Micheletti en 1972 et le point de vue de R. Azencott et A. Trouvé en 1995 qui consistent à générer des déformations d’une surface de référence via une famille de difféomorphismes. L’accent est mis sur les fondations mathématiques sous-jacentes que l’on a essayé de clarifier lorsque nécessaire, et, le cas échéant, sur l’exploration d’autres avenues.

Problèmes de premier passage et de commande optimale pour des chaînes de Markov à temps discret.

Nous considérons des processus de diffusion, définis par des équations différentielles stochastiques, et puis nous nous intéressons à des problèmes de premier passage pour les chaînes de Markov en temps discret correspon- dant à ces processus de diffusion. Comme il est connu dans la littérature, ces chaînes convergent en loi vers la solution des équations différentielles stochas- tiques considérées. Notre contribution consiste à trouver des formules expli- cites pour la probabilité de premier passage et la durée de la partie pour ces chaînes de Markov à temps discret. Nous montrons aussi que les résultats ob- tenus convergent selon la métrique euclidienne (i.e topologie euclidienne) vers les quantités correspondantes pour les processus de diffusion. En dernier lieu, nous étudions un problème de commande optimale pour des chaînes de Markov en temps discret. L’objectif est de trouver la valeur qui mi- nimise l’espérance mathématique d’une certaine fonction de coût. Contraire- ment au cas continu, il n’existe pas de formule explicite pour cette valeur op- timale dans le cas discret. Ainsi, nous avons étudié dans cette thèse quelques cas particuliers pour lesquels nous avons trouvé cette valeur optimale.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Reliable Solid Modelling Using Subdivision Surfaces

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Le rapport Displaced Persons and Their Resettlement in the United States et le début des politiques d’accueil aux États-Unis

RÉSUMÉ : Avec le dénouement de la Deuxième Guerre mondiale, le problème des réfugiés en Europe devient un enjeu international. Plusieurs millions de personnes, que l’on nomme les Displaced Persons (DP), sont sans refuge et doivent recevoir une aide immédiate pour survivre. Même si la majorité de ces gens retourneront dans leurs pays d’origine, il reste encore des centaines de milliers de réfugiés en 1948. La seule solution concrète pour régler cette problématique est l’émigration des réfugiés dans des pays prêts à les accepter. Les Américains jouent un rôle crucial en acceptant 415 000 DP entre 1948 et 1952 grâce au Displaced Persons Act de 1948 et ses amendements en 1950 et 1951. Après d’âpres discussions entre les restrictionnistes et ceux qui défendent la libéralisation des lois d’immigration, naîtra le Displaced Persons Act (DP Act) signé avec beaucoup de réticence, le 25 juin 1948, par le président Harry S. Truman. Cette loi qui prévoit la venue de 202 000 DP en deux ans, contient des mesures jugées discriminatoires à l'endroit de certaines ethnies. Afin d'améliorer le DP Act, le Congrès effectue des recherches sur la situation des réfugiés toujours dans les camps en 1949 tout en étudiant l’impact de la venue des DP aux États-Unis entre 1948 et 1950. Cette étude est soumise sous forme de rapport, le Displaced Persons and Their Resettlement in the United States, le 20 janvier 1950. Ce mémoire propose une analyse minutieuse du rapport et de son contexte politique afin de démontrer le rôle important de cette étude dans le processus décisionnel du Congrès américain visant à accueillir un plus grand nombre de DP tout en posant les bases pour une politique d’accueil en matière de refugiés.