Quantum nonlocality, cryptography and complexity

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Reliable computation for geometric models

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Développement d’une méthode de simulation multi-échelle pour l’étude des grandes transformations dans les protéines

Les films de simulations qui accompagnent le document ont été réalisés avec Pymol.

L’éradication du fléau de la pauvreté en Tunisie: acquis et défis

Sur le plan conceptuel, un consensus s’est dégagé depuis quelques années arguant que la pauvreté est un phénomène multidimensionnel. Vu que, la pauvreté en Tunisie est traitée dans la plupart des rapports suivant une approche monétaire et que cette dernière témoigne d'une diminution très appréciable de la pauvreté, nous élargissons la notion de la pauvreté en adoptant une approche multidimensionnelle et en se référant, dans un premier temps, aux réalisations du pays en termes de satisfaction aux Objectifs du Millénaire pour le Développement (OMD). En second lieu, nous procédons, en utilisant la méthode ACP, au calcul d’un indice composite de bien-être pour chaque gouvernorat. Les résultats dégagés à partir de la construction dudit indice montrent une forte disparité entre les régions et une persistance de la pauvreté dans nombre de gouvernorats. Une analyse plus approfondie au niveau de chaque gouvernorat caractérisé comme pauvre nous a permis de localiser, avec précision, les poches de pauvreté persistantes.

Impact du sexe et du profil génétique sur la sécrétion d’insuline dans une cohorte de patients atteints de fibrose kystique

Introduction : La Fibrose Kystique (FK) est la maladie autosomique récessive la plus fréquente chez les Caucasiens et est due à une mutation du gène Cystic Fibrosis Transmembrane Regulator (CFTR), codant pour un canal chlore. La principale mutation est la délétion de l'acide aminé phénylalanine en position 508. En raison de l’augmentation de l'espérance de vie, de nouvelles complications telles que le diabète associé à la FK (DAFK) ont vu le jour. Le DAFK semble principalement dû à un défaut de sécrétion d'insuline. Des études ont montré que les femmes et les personnes homozygotes ΔF508 ont un risque plus élevé de développer le DAFK. Objectifs : Comparer la sécrétion d'insuline entre les hommes et les femmes FK selon leur génotype CFTR. Notre hypothèse était que les femmes FK présentaient une sécrétion d'insuline moins élevée que des hommes. Méthodes : Deux cents sujets adultes sans diabète connu ont été recrutés dans la clinique de FK du CHUM et inclus dans cette étude. Cent seize ont été revus après un suivi de 24 ± 10 mois. Leur génotype CFTR a été extrait à partir des dossiers médicaux. Tous les sujets ont subi une hyperglycémie provoquée par voie orale de 2-h (HGPO) afin de déterminer leur tolérance au glucose : normale (NGT), intolérance (IGT) ou DAFK. Des échantillons de sang ont été prélevés aux temps 0, 30, 60, 90, et 120 min de l’HGPO. À partir de ces derniers, la sécrétion d'insuline et la sensibilité à l’insuline des sujets ont été évaluées en utilisant les indices de Stumvoll et les aires sous la courbe de l’insuline durant l’HGPO. Résultats : Pour une excursion glycémique comparable, il y avait des différences significatives dans les concentrations d'insuline entre les hommes et les femmes et selon le génotype CFTR. Ainsi, les femmes et les sujets hétérozygotes avaient des concentrations d’insuline plus élevées que les hommes et les sujets homozygotes. Cela restait significatif quelle que soit leur tolérance au glucose. Le calcul du disposition index représentant la sécrétion d'insuline ajustée pour le degré de sensibilité à l’insuline a suggéré une sécrétion d'insuline plus élevée chez les femmes que les hommes. Le suivi prospectif nous a permis de déterminer que cette sécrétion plus élevée d’insuline était associée à une évolution plus favorable pour la tolérance au glucose. Fait intéressant, cette constatation n'était vraie que pour les femmes. Conclusion : Dans une vaste cohorte prospective observationnelle de patients FK sans diabète connu, nous avons démontré qu’en dépit d’un âge et d’une fonction pulmonaire semblables, les femmes présentaient une sécrétion d'insuline supérieure à celle des hommes et que cela pourrait avoir un effet protecteur, à court terme, chez celles-ci pour le développement du DAFK.

Effets de la croissance des capacités respiratoires sur la longueur des énoncés et sur la diversité lexicale

Brown (1973) a proposé la « longueur moyenne des énoncés » (LME) comme indice standard du développement langagier. La LME se calcule selon le nombre moyen de morphèmes dans 100 énoncés de parole spontanée. L’hypothèse sous-jacente à cet indice est que la complexité syntaxique croît avec le nombre de morphèmes dans les énoncés. Selon Brown, l’indice permet d’estimer le développement d’une « compétence grammaticale » jusqu’à environ quatre morphèmes. Certains auteurs ont toutefois critiqué le manque de fiabilité de la LME et la limite de quatre morphèmes. Des rapports démontrent des variations de la LME avec l’âge, ce qui suggère que des facteurs comme la croissance des capacités respiratoires peuvent influencer l’indice de Brown. La présente étude fait état de ces problèmes et examine comment la LME et certaines mesures de diversité lexicale varient selon le développement des capacités respiratoires. On a calculé la LME et la diversité lexicale dans la parole spontanée de 50 locuteurs mâles âgés de 5 à 27 ans. On a également mesuré, au moyen d’un pneumotachographe, la capacité vitale (CV) des locuteurs. Les résultats démontrent que la LME et des mesures de diversité lexicale corrèlent fortement avec la croissance de la CV. Ainsi, la croissance des fonctions respiratoires contraint le développement morphosyntaxique et lexical. Notre discussion fait valoir la nécessité de réévaluer l’indice de la LME et la conception « linguistique » du développement langagier comme une compétence mentale qui émerge séparément de la croissance des structures de performance.

Développement d'un indice de vulnérabilité à l'érosion éolienne à partir d'images satellitales, dans le Bassin arachidier du Sénégal : cas de la région de Thiès.

L’érosion éolienne est un problème environnemental parmi les plus sévères dans les régions arides, semi-arides et les régions sèches sub-humides de la planète. L’érosion des sols accélérée par le vent provoque des dommages à la fois localement et régionalement. Sur le plan local, elle cause la baisse des nutriments par la mobilisation des particules les plus fines et de la matière organique. Cette mobilisation est une des causes de perte de fertilité des sols avec comme conséquence, une chute de la productivité agricole et une réduction de la profondeur de la partie arable. Sur le plan régional, les tempêtes de poussières soulevées par le vent ont un impact non négligeable sur la santé des populations, et la déposition des particules affecte les équipements hydrauliques tels que les canaux à ciel ouvert ainsi que les infrastructures notamment de transport. Dans les régions où les sols sont fréquemment soumis à l’érosion éolienne, les besoins pour des études qui visent à caractériser spatialement les sols selon leur degré de vulnérabilité sont grands. On n’a qu’à penser aux autorités administratives qui doivent décider des mesures à prendre pour préserver et conserver les potentialités agropédologiques des sols, souvent avec des ressources financières modestes mises à leur disposition. Or, dans certaines de ces régions, comme notre territoire d’étude, la région de Thiès au Sénégal, ces études font défaut. En effet, les quelques études effectuées dans cette région ou dans des contextes géographiques similaires ont un caractère plutôt local et les approches suivies (modèles de pertes des sols) nécessitent un nombre substantiel de données pour saisir la variabilité spatiale de la dynamique des facteurs qui interviennent dans le processus de l’érosion éolienne. La disponibilité de ces données est particulièrement problématique dans les pays en voie de développement, à cause de la pauvreté en infrastructures et des problèmes de ressources pour le monitoring continu des variables environnementales. L’approche mise de l’avant dans cette recherche vise à combler cette lacune en recourant principalement à l’imagerie satellitale, et plus particulièrement celle provenant des satellites Landsat-5 et Landsat-7. Les images Landsat couvrent la presque totalité de la zone optique du spectre exploitable par télédétection (visible, proche infrarouge, infrarouge moyen et thermique) à des résolutions relativement fines (quelques dizaines de mètres). Elles permettant ainsi d’étudier la distribution spatiale des niveaux de vulnérabilité des sols avec un niveau de détails beaucoup plus fin que celui obtenu avec des images souvent utilisées dans des études environnementales telles que AVHRR de la série de satellites NOAA (résolution kilométrique). De plus, l’archive complet des images Landsat-5 et Landsat-7 couvrant une période de plus de 20 ans est aujourd’hui facilement accessible. Parmi les paramètres utilisés dans les modèles d’érosion éolienne, nous avons identifiés ceux qui sont estimables par l’imagerie satellitale soit directement (exemple, fraction du couvert végétal) soit indirectement (exemple, caractérisation des sols par leur niveau d’érodabilité). En exploitant aussi le peu de données disponibles dans la région (données climatiques, carte morphopédologique) nous avons élaboré une base de données décrivant l’état des lieux dans la période de 1988 à 2002 et ce, selon les deux saisons caractéristiques de la région : la saison des pluies et la saison sèche. Ces données par date d’acquisition des images Landsat utilisées ont été considérées comme des intrants (critères) dans un modèle empirique que nous avons élaboré en modulant l’impact de chacun des critères (poids et scores). À l’aide de ce modèle, nous avons créé des cartes montrant les degrés de vulnérabilité dans la région à l’étude, et ce par date d’acquisition des images Landsat. Suite à une série de tests pour valider la cohérence interne du modèle, nous avons analysé nos cartes afin de conclure sur la dynamique du processus pendant la période d’étude. Nos principales conclusions sont les suivantes : 1) le modèle élaboré montre une bonne cohérence interne et est sensible aux variations spatiotemporelles des facteurs pris en considération 2); tel qu’attendu, parmi les facteurs utilisés pour expliquer la vulnérabilité des sols, la végétation vivante et l’érodabilité sont les plus importants ; 3) ces deux facteurs présentent une variation importante intra et inter-saisonnière de sorte qu’il est difficile de dégager des tendances à long terme bien que certaines parties du territoire (Nord et Est) aient des indices de vulnérabilité forts, peu importe la saison ; 4) l’analyse diachronique des cartes des indices de vulnérabilité confirme le caractère saisonnier des niveaux de vulnérabilité dans la mesure où les superficies occupées par les faibles niveaux de vulnérabilité augmentent en saison des pluies, donc lorsque l’humidité surfacique et la végétation active notamment sont importantes, et décroissent en saison sèche ; 5) la susceptibilité, c’est-à-dire l’impact du vent sur la vulnérabilité est d’autant plus forte que la vitesse du vent est élevée et que la vulnérabilité est forte. Sur les zones où la vulnérabilité est faible, les vitesses de vent élevées ont moins d’impact. Dans notre étude, nous avons aussi inclus une analyse comparative entre les facteurs extraits des images Landsat et celles des images hyperspectrales du satellite expérimental HYPERION. Bien que la résolution spatiale de ces images soit similaire à celle de Landsat, les résultats obtenus à partir des images HYPERION révèlent un niveau de détail supérieur grâce à la résolution spectrale de ce capteur permettant de mieux choisir les bandes spectrales qui réagissent le plus avec le facteur étudié. Cette étude comparative démontre que dans un futur rapproché, l’amélioration de l’accessibilité à ce type d’images permettra de raffiner davantage le calcul de l’indice de vulnérabilité par notre modèle. En attendant cette possibilité, on peut de contenter de l’imagerie Landsat qui offre un support d’informations permettant tout de même d’évaluer le niveau de fragilisation des sols par l’action du vent et par la dynamique des caractéristiques des facteurs telles que la couverture végétale aussi bien vivante que sénescente.

Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

Parallel metaheuristics for stochastic capacitated multicommodity network design

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Effet d'une approche par le jeu sur l'apprentissage du répertoire mémorisé chez des élèves de deuxième année primaire

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Étude pilote des effets du Tandem Forsus Maxillary Corrector sur la croissance des maxillaires

Objectif : Récemment, un nouvel appareil issu de la technologie du Forsus™ et visant à corriger les malocclusions de classe III a été mis sur le marché et se popularise dans la pratique orthodontique : le Tandem Forsus Maxillary Corrector (TFMC). L’objectif de la présente étude est de mesurer les effets squelettiques, l’influence réelle sur la croissance, et les effets dento-alvéolaires du port du TFMC. Matériel et méthodes : 14 patients présentant une malocclusion de classe III (âge moyen de 9 ans 6 mois) traités par le même orthodontiste ont participé à cette étude prospective. Le groupe consiste en 10 garçons et 4 filles. Le Tandem Forsus Maxillary Corrector est porté de 12 à 14 heures par jour jusqu’à l’obtention d’une surcorrection du surplomb horizontal et une relation dentaire de classe I. Le traitement est généralement d’une durée de 8 à 9 mois. Des radiographies céphalométriques latérales prises avant (T1) et après (T2) le traitement ont été analysées afin de déterminer les changements dentaires et squelettiques. Les résultats ont été comparés à un groupe contrôle composé de 42 enfants provenant du Centre de croissance de l’Université de Montréal. Les radiographies ont été tracées et analysées de manière aveugle à l’aide du logiciel Dolphin Imaging (ver 11.0, Patterson Dental, Chatsworth, California). L’erreur sur la méthode a été évaluée avec la formule de Dahlberg, le coefficient de corrélation intra-classe et l’indice de Bland-Altman. L’effet du traitement a été évalué à l’aide du test t pour échantillons appariés. L’effet de la croissance pour le groupe contrôle a été calculé à l’aide d’un test t pour échantillons indépendants. Résultats : L’utilisation du TFMC produit un mouvement antérieur et une rotation antihoraire du maxillaire. De plus, il procline les incisives supérieures et rétrocline les incisives inférieures. Une rotation antihoraire du plan occlusal contribue aussi à la correction de la malocclusion de classe III. Par contre, le TFMC ne semble pas avoir pour effet de restreindre la croissance mandibulaire. Conclusion : La présente étude tend à démontrer que le port de l’appareil TFMC a un effet orthopédique et dento-alvéolaire significatif lors du traitement correctif des malocclusions modérées de classe III.

Rendu de matériaux semi-transparents hétérogènes en temps réel

On retrouve dans la nature un nombre impressionnant de matériaux semi-transparents tels le marbre, le jade ou la peau, ainsi que plusieurs liquides comme le lait ou les jus. Que ce soit pour le domaine cinématographique ou le divertissement interactif, l'intérêt d'obtenir une image de synthèse de ce type de matériau demeure toujours très important. Bien que plusieurs méthodes arrivent à simuler la diffusion de la lumière de manière convaincante a l'intérieur de matériaux semi-transparents, peu d'entre elles y arrivent de manière interactive. Ce mémoire présente une nouvelle méthode de diffusion de la lumière à l'intérieur d'objets semi-transparents hétérogènes en temps réel. Le coeur de la méthode repose sur une discrétisation du modèle géométrique sous forme de voxels, ceux-ci étant utilisés comme simplification du domaine de diffusion. Notre technique repose sur la résolution de l'équation de diffusion à l'aide de méthodes itératives permettant d'obtenir une simulation rapide et efficace. Notre méthode se démarque principalement par son exécution complètement dynamique ne nécessitant aucun pré-calcul et permettant une déformation complète de la géométrie.

Reconstruction des structures magnéto-convectives solaires sous une région active, par l’utilisation conjointe d’un modèle de convection anélastique et d’une méthode d’assimilation de données.

L’utilisation d’une méthode d’assimilation de données, associée à un modèle de convection anélastique, nous permet la reconstruction des structures physiques d’une partie de la zone convective située en dessous d’une région solaire active. Les résultats obtenus nous informent sur les processus d’émergence des tubes de champ magnétique au travers de la zone convective ainsi que sur les mécanismes de formation des régions actives. Les données solaires utilisées proviennent de l’instrument MDI à bord de l’observatoire spatial SOHO et concernent principalement la région active AR9077 lors de l’ ́évènement du “jour de la Bastille”, le 14 juillet 2000. Cet évènement a conduit à l’avènement d’une éruption solaire, suivie par une importante éjection de masse coronale. Les données assimilées (magnétogrammes, cartes de températures et de vitesses verticales) couvrent une surface de 175 méga-mètres de coté acquises au niveau photosphérique. La méthode d’assimilation de données employée est le “coup de coude direct et rétrograde”, une méthode de relaxation Newtonienne similaire à la méthode “quasi-linéaire inverse 3D”. Elle présente l’originalité de ne pas nécessiter le calcul des équations adjointes au modèle physique. Aussi, la simplicité de la méthode est un avantage numérique conséquent. Notre étude montre au travers d’un test simple l’applicabilité de cette méthode à un modèle de convection utilisé dans le cadre de l’approximation anélastique. Nous montrons ainsi l’efficacité de cette méthode et révélons son potentiel pour l’assimilation de données solaires. Afin d’assurer l’unicité mathématique de la solution obtenue nous imposons une régularisation dans tout le domaine simulé. Nous montrons enfin que l’intérêt de la méthode employée ne se limite pas à la reconstruction des structures convectives, mais qu’elle permet également l’interpolation optimale des magnétogrammes photosphériques, voir même la prédiction de leur évolution temporelle.

La structure de Jordan des matrices de transfert des modèles de boucles et la relation avec les hamiltoniens XXZ

Les modèles sur réseau comme ceux de la percolation, d’Ising et de Potts servent à décrire les transitions de phase en deux dimensions. La recherche de leur solution analytique passe par le calcul de la fonction de partition et la diagonalisation de matrices de transfert. Au point critique, ces modèles statistiques bidimensionnels sont invariants sous les transformations conformes et la construction de théories des champs conformes rationnelles, limites continues des modèles statistiques, permet un calcul de la fonction de partition au point critique. Plusieurs chercheurs pensent cependant que le paradigme des théories des champs conformes rationnelles peut être élargi pour inclure les modèles statistiques avec des matrices de transfert non diagonalisables. Ces modèles seraient alors décrits, dans la limite d’échelle, par des théories des champs logarithmiques et les représentations de l’algèbre de Virasoro intervenant dans la description des observables physiques seraient indécomposables. La matrice de transfert de boucles D_N(λ, u), un élément de l’algèbre de Temperley- Lieb, se manifeste dans les théories physiques à l’aide des représentations de connectivités ρ (link modules). L’espace vectoriel sur lequel agit cette représentation se décompose en secteurs étiquetés par un paramètre physique, le nombre d de défauts. L’action de cette représentation ne peut que diminuer ce nombre ou le laisser constant. La thèse est consacrée à l’identification de la structure de Jordan de D_N(λ, u) dans ces représentations. Le paramètre β = 2 cos λ = −(q + 1/q) fixe la théorie : β = 1 pour la percolation et √2 pour le modèle d’Ising, par exemple. Sur la géométrie du ruban, nous montrons que D_N(λ, u) possède les mêmes blocs de Jordan que F_N, son plus haut coefficient de Fourier. Nous étudions la non diagonalisabilité de F_N à l’aide des divergences de certaines composantes de ses vecteurs propres, qui apparaissent aux valeurs critiques de λ. Nous prouvons dans ρ(D_N(λ, u)) l’existence de cellules de Jordan intersectorielles, de rang 2 et couplant des secteurs d, d′ lorsque certaines contraintes sur λ, d, d′ et N sont satisfaites. Pour le modèle de polymères denses critique (β = 0) sur le ruban, les valeurs propres de ρ(D_N(λ, u)) étaient connues, mais les dégénérescences conjecturées. En construisant un isomorphisme entre les modules de connectivités et un sous-espace des modules de spins du modèle XXZ en q = i, nous prouvons cette conjecture. Nous montrons aussi que la restriction de l’hamiltonien de boucles à un secteur donné est diagonalisable et trouvons la forme de Jordan exacte de l’hamiltonien XX, non triviale pour N pair seulement. Enfin nous étudions la structure de Jordan de la matrice de transfert T_N(λ, ν) pour des conditions aux frontières périodiques. La matrice T_N(λ, ν) a des blocs de Jordan intrasectoriels et intersectoriels lorsque λ = πa/b, et a, b ∈ Z×. L’approche par F_N admet une généralisation qui permet de diagnostiquer des cellules intersectorielles dont le rang excède 2 dans certains cas et peut croître indéfiniment avec N. Pour les blocs de Jordan intrasectoriels, nous montrons que les représentations de connectivités sur le cylindre et celles du modèle XXZ sont isomorphes sauf pour certaines valeurs précises de q et du paramètre de torsion v. En utilisant le comportement de la transformation i_N^d dans un voisinage des valeurs critiques (q_c, v_c), nous construisons explicitement des vecteurs généralisés de Jordan de rang 2 et discutons l’existence de blocs de Jordan intrasectoriels de plus haut rang.

Apprentissage machine efficace : théorie et pratique

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique.