Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Le cannabis, le tabac et le changement d’adiposité chez les jeunes hommes et femmes : une étude longitudinale 2005-2012

Exposé de la situation : Des études menées sur les animaux démontrent que le système endocannabinoide est important dans le maintien de l’homéostasie de l’énergie et que les effets de sa modulation sont différents selon le sexe et l’exposition à la nicotine. Deux études longitudinales ont étudié l’association entre l’usage du cannabis (UC) et le changement de poids et ont obtenus des résultats contradictoires. L’objectif de ce mémoire est de décrire la modification de l’association entre l’UC et le changement de poids par la cigarette chez les jeunes hommes et femmes. Méthodes : Des donnés de 271 hommes et 319 femmes ont été obtenues dans le cadre de l’étude NICO, une cohorte prospective (1999-2013). L’indice de masse corporelle (IMC) et la circonférence de taille (CT) ont été mesurés à l’âge de 17 et 25 ans. L’UC dans la dernière année et de cigarette dans les derniers trois mois ont été auto-rapportées à 21 ans. Les associations entre l’UC et le changement d’IMC et de CT ont été modélisées dans une régression polynomiale stratifiée par sexe avec ajustement pour l’activité physique, la sédentarité et la consommation d’alcool. Résultats : Uniquement, chez les hommes, l’interaction de l’UC et cigarettes était statistiquement significative dans le model de changement IMC (p=0.004) et celui de changement de CT (p=0.043). L’UC était associé au changement d’adiposité dans une association en forme de U chez les homes non-fumeurs et chez les femmes, et dans une association en forme de U-inversé chez les hommes fumeurs. Conclusion : La cigarette semble modifier l’effet du cannabis sur le changement d’IMC et CT chez les hommes, mais pas chez les femmes.

Certain problems concerning polynomials and transcendental entire functions of exponential type

Soit $\displaystyle P(z):=\sum_{\nu=0}^na_\nu z^{\nu}$ un polynôme de degré $n$ et $\displaystyle M:=\sup_{|z|=1}|P(z)|.$ Sans aucne restriction suplémentaire, on sait que $|P'(z)|\leq Mn$ pour $|z|\leq 1$ (inégalité de Bernstein). Si nous supposons maintenant que les zéros du polynôme $P$ sont à l'extérieur du cercle $|z|=k,$ quelle amélioration peut-on apporter à l'inégalité de Bernstein? Il est déjà connu [{\bf \ref{Mal1}}] que dans le cas où $k\geq 1$ on a $$(*) \qquad |P'(z)|\leq \frac{n}{1+k}M \qquad (|z|\leq 1),$$ qu'en est-il pour le cas où $k < 1$? Quelle est l'inégalité analogue à $(*)$ pour une fonction entière de type exponentiel $\tau ?$ D'autre part, si on suppose que $P$ a tous ses zéros dans $|z|\geq k \, \, (k\geq 1),$ quelle est l'estimation de $|P'(z)|$ sur le cercle unité, en terme des quatre premiers termes de son développement en série entière autour de l'origine. Cette thèse constitue une contribution à la théorie analytique des polynômes à la lumière de ces questions.

Dénombrement des polynômes irréductibles unitaires dans les corps finis avec différentes contraintes sur les coefficients.

Le but de ce mémoire est de dénombrer les polynômes irréductibles unitaires dans les corps finis avec certaines conditions sur les coefficients. Notre première condition sera de fixer la trace du polynôme. Par la suite, nous choisirons la cotrace lorsque la trace sera déjà fixée à zéro. Finalement, nous discuterons du cas où la trace et le terme constant sont fixés en même temps.

Énergie des vortex dans un modèle abélien de Higgs en 2+1 dimensions avec un potentiel d’ordre six

Dans ce travail, j’étudierai principalement un modèle abélien de Higgs en 2+1 dimensions, dans lequel un champ scalaire interagit avec un champ de jauge. Des défauts topologiques, nommés vortex, sont créés lorsque le potentiel possède un minimum brisant spontanément la symétrie U(1). En 3+1 dimensions, ces vortex deviennent des défauts à une dimension. Ils ap- paraissent par exemple en matière condensée dans les supraconducteurs de type II comme des lignes de flux magnétique. J’analyserai comment l’énergie des solutions statiques dépend des paramètres du modèle et en particulier du nombre d’enroulement du vortex. Pour le choix habituel de potentiel (un poly- nôme quartique dit « BPS »), la relation entre les masses des deux champs mène à deux types de comportements : type I si la masse du champ de jauge est plus grande que celle du champ sca- laire et type II inversement. Selon le cas, la dépendance de l’énergie au nombre d’enroulement, n, indiquera si les vortex auront tendance à s’attirer ou à se repousser, respectivement. Lorsque le flux emprisonné est grand, les vortex présentent un profil où la paroi est mince, permettant certaines simplifications dans l’analyse. Le potentiel, un polynôme d’ordre six (« non-BPS »), est choisi tel que le centre du vortex se trouve dans le vrai vide (minimum absolu du potentiel) alors qu’à l’infini le champ scalaire se retrouve dans le faux vide (minimum relatif du potentiel). Le taux de désintégration a déjà été estimé par une approximation semi-classique pour montrer l’impact des défauts topologiques sur la stabilité du faux vide. Le projet consiste d’abord à établir l’existence de vortex classi- quement stables de façon numérique. Puis, ma contribution fut une analyse des paramètres du modèle révélant le comportement énergétique de ceux-ci en fonction du nombre d’enroulement. Ce comportement s’avèrera être différent du cas « BPS » : le ratio des masses ne réussit pas à décrire le comportement observé numériquement.

Croissance et ensemble nodal de fonctions propres du laplacien sur des surfaces

Dans cette thèse, nous étudions les fonctions propres de l'opérateur de Laplace-Beltrami - ou simplement laplacien - sur une surface fermée, c'est-à-dire une variété riemannienne lisse, compacte et sans bord de dimension 2. Ces fonctions propres satisfont l'équation $\Delta_g \phi_\lambda + \lambda \phi_\lambda = 0$ et les valeurs propres forment une suite infinie. L'ensemble nodal d'une fonction propre du laplacien est celui de ses zéros et est d'intérêt depuis les expériences de plaques vibrantes de Chladni qui remontent au début du 19ème siècle et, plus récemment, dans le contexte de la mécanique quantique. La taille de cet ensemble nodal a été largement étudiée ces dernières années, notamment par Donnelly et Fefferman, Colding et Minicozzi, Hezari et Sogge, Mangoubi ainsi que Sogge et Zelditch. L'étude de la croissance de fonctions propres n'est pas en reste, avec entre autres les récents travaux de Donnelly et Fefferman, Sogge, Toth et Zelditch, pour ne nommer que ceux-là. Notre thèse s'inscrit dans la foulée du travail de Nazarov, Polterovich et Sodin et relie les propriétés de croissance des fonctions propres avec la taille de leur ensemble nodal dans l'asymptotique $\lambda \nearrow \infty$. Pour ce faire, nous considérons d'abord les exposants de croissance, qui mesurent la croissance locale de fonctions propres et qui sont obtenus à partir de la norme uniforme de celles-ci. Nous construisons ensuite la croissance locale moyenne d'une fonction propre en calculant la moyenne sur toute la surface de ces exposants de croissance, définis sur de petits disques de rayon comparable à la longueur d'onde. Nous montrons alors que la taille de l'ensemble nodal est contrôlée par le produit de cette croissance locale moyenne et de la fréquence $\sqrt{\lambda}$. Ce résultat permet une reformulation centrée sur les fonctions propres de la célèbre conjecture de Yau, qui prévoit que la mesure de l'ensemble nodal croît au rythme de la fréquence. Notre travail renforce également l'intuition répandue selon laquelle une fonction propre se comporte comme un polynôme de degré $\sqrt{\lambda}$. Nous généralisons ensuite nos résultats pour des exposants de croissance construits à partir de normes $L^q$. Nous sommes également amenés à étudier les fonctions appartenant au noyau d'opérateurs de Schrödinger avec petit potentiel dans le plan. Pour de telles fonctions, nous obtenons deux résultats qui relient croissance et taille de l'ensemble nodal.

Approche bayésienne de la construction d'intervalles de crédibilité simultanés à partir de courbes simulées

Ce mémoire porte sur la simulation d'intervalles de crédibilité simultanés dans un contexte bayésien. Dans un premier temps, nous nous intéresserons à des données de précipitations et des fonctions basées sur ces données : la fonction de répartition empirique et la période de retour, une fonction non linéaire de la fonction de répartition. Nous exposerons différentes méthodes déjà connues pour obtenir des intervalles de confiance simultanés sur ces fonctions à l'aide d'une base polynomiale et nous présenterons une méthode de simulation d'intervalles de crédibilité simultanés. Nous nous placerons ensuite dans un contexte bayésien en explorant différents modèles de densité a priori. Pour le modèle le plus complexe, nous aurons besoin d'utiliser la simulation Monte-Carlo pour obtenir les intervalles de crédibilité simultanés a posteriori. Finalement, nous utiliserons une base non linéaire faisant appel à la transformation angulaire et aux splines monotones pour obtenir un intervalle de crédibilité simultané valide pour la période de retour.

Désintégration du faux vide médiée par des kinks en 1+1 dimensions

Dans ce mémoire, on étudie la désintégration d’un faux vide, c’est-à-dire un vide qui est un minimum relatif d’un potentiel scalaire par effet tunnel. Des défauts topologiques en 1+1 dimension, appelés kinks, apparaissent lorsque le potentiel possède un minimum qui brise spontanément une symétrie discrète. En 3+1 dimensions, ces kinks deviennent des murs de domaine. Ils apparaissent par exemple dans les matériaux magnétiques en matière condensée. Un modèle à deux champs scalaires couplés sera étudié ainsi que les solutions aux équations du mouvement qui en découlent. Ce faisant, on analysera comment l’existence et l’énergie des solutions statiques dépend des paramètres du modèle. Un balayage numérique de l’espace des paramètres révèle que les solutions stables se trouvent entre les zones de dissociation, des régions dans l’espace des paramètres où les solutions stables n’existent plus. Le comportement des solutions instables dans les zones de dissociation peut être très différent selon la zone de dissociation dans laquelle une solution se trouve. Le potentiel consiste, dans un premier temps, en un polynôme d’ordre six, auquel on y rajoute, dans un deuxième temps, un polynôme quartique multiplié par un terme de couplage, et est choisi tel que les extrémités du kink soient à des faux vides distincts. Le taux de désintégration a été estimé par une approximation semi-classique pour montrer l’impact des défauts topologiques sur la stabilité du faux vide. Le projet consiste à déterminer les conditions qui permettent aux kinks de catalyser la désintégration du faux vide. Il appert qu’on a trouvé une expression pour déterminer la densité critique de kinks et qu’on comprend ce qui se passe avec la plupart des termes.

Scoliosis curve type classification from 3D trunk image

Adolescent idiopathic scoliosis (AIS) is a deformity of the spine manifested by asymmetry and deformities of the external surface of the trunk. Classification of scoliosis deformities according to curve type is used to plan management of scoliosis patients. Currently, scoliosis curve type is determined based on X-ray exam. However, cumulative exposure to X-rays radiation significantly increases the risk for certain cancer. In this paper, we propose a robust system that can classify the scoliosis curve type from non invasive acquisition of 3D trunk surface of the patients. The 3D image of the trunk is divided into patches and local geometric descriptors characterizing the surface of the back are computed from each patch and forming the features. We perform the reduction of the dimensionality by using Principal Component Analysis and 53 components were retained. In this work a multi-class classifier is built with Least-squares support vector machine (LS-SVM) which is a kernel classifier. For this study, a new kernel was designed in order to achieve a robust classifier in comparison with polynomial and Gaussian kernel. The proposed system was validated using data of 103 patients with different scoliosis curve types diagnosed and classified by an orthopedic surgeon from the X-ray images. The average rate of successful classification was 93.3% with a better rate of prediction for the major thoracic and lumbar/thoracolumbar types.

Influvence of Alloying Additions on the Structure and Properties of Ai-7Si-0.3Mg Alloy

Cast Ai-Si alloys are widely used in the automotive, aerospace and general engineering industries due to their excellent combination of properties such as good castability, low coefficient of thermal expansion, high strength-to-weight ratio and good corrosion resistance. The present investigation is on the influence of alloying additions on the structure and properties of Ai-7Si-0.3Mg alloy. The primary objective of this present investigation is to study these beneficial effects of calcium on the structure and properties of Ai-7Si-0.3Mg-xFe alloys. The second objective of this work is to study the effects of Mn,Be and Sr addition as Fe neutralizers and also to study the interaction of Mn,Be,Sr and Ca in Ai-7Si-0.3Mg-xFe alloys. In this study the duel beneficial effects of Ca viz;modification and Fe-neutralization, comparison of the effects of Ca and Sr with common Fe neutralizers. The casting have been characterized with respect to their microstructure, %porosity and electrical conductivity, solidification behaviour and mechanical properties. One of the interesting observations in the present work is that a low level of calcium reduces the porosity compared to the untreated alloy. However higher level of calcium addition lead to higher porosity in the casting. An empirical analysis carried out for comparing the results of the present work with those of the other researchers on the effect of increasing iron content on UTS and % elongation of Ai-Si-Mg and Ai-Si-Cu alloys has shown a linear and an inverse first order polynomial relationships respectively.

Field Equilibrium Finite Elements for Structural Analysis

Many finite elements used in structural analysis possess deficiencies like shear locking, incompressibility locking, poor stress predictions within the element domain, violent stress oscillation, poor convergence etc. An approach that can probably overcome many of these problems would be to consider elements in which the assumed displacement functions satisfy the equations of stress field equilibrium. In this method, the finite element will not only have nodal equilibrium of forces, but also have inner stress field equilibrium. The displacement interpolation functions inside each individual element are truncated polynomial solutions of differential equations. Such elements are likely to give better solutions than the existing elements.In this thesis, a new family of finite elements in which the assumed displacement function satisfies the differential equations of stress field equilibrium is proposed. A general procedure for constructing the displacement functions and use of these functions in the generation of elemental stiffness matrices has been developed. The approach to develop field equilibrium elements is quite general and various elements to analyse different types of structures can be formulated from corresponding stress field equilibrium equations. Using this procedure, a nine node quadrilateral element SFCNQ for plane stress analysis, a sixteen node solid element SFCSS for three dimensional stress analysis and a four node quadrilateral element SFCFP for plate bending problems have been formulated.For implementing these elements, computer programs based on modular concepts have been developed. Numerical investigations on the performance of these elements have been carried out through standard test problems for validation purpose. Comparisons involving theoretical closed form solutions as well as results obtained with existing finite elements have also been made. It is found that the new elements perform well in all the situations considered. Solutions in all the cases converge correctly to the exact values. In many cases, convergence is faster when compared with other existing finite elements. The behaviour of field consistent elements would definitely generate a great deal of interest amongst the users of the finite elements.

Some problems of discrete function theory

An attempt is made by the researcher to establish a theory of discrete functions in the complex plane. Classical analysis q-basic theory, monodiffric theory, preholomorphic theory and q-analytic theory have been utilised to develop concepts like differentiation, integration and special functions.

Median filtering: structure analysis and application

Median filtering is a simple digital non—linear signal smoothing operation in which median of the samples in a sliding window replaces the sample at the middle of the window. The resulting filtered sequence tends to follow polynomial trends in the original sample sequence. Median filter preserves signal edges while filtering out impulses. Due to this property, median filtering is finding applications in many areas of image and speech processing. Though median filtering is simple to realise digitally, its properties are not easily analysed with standard analysis techniques,

On the generalized obnoxious center problem: antimedian subsets

The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered.

Enhancement of Calcifications in Mammograms using Volterra Series based Quadratic Filter

The paper summarizes the design and implementation of a quadratic edge detection filter, based on Volterra series, for enhancing calcifications in mammograms. The proposed filter can account for much of the polynomial nonlinearities inherent in the input mammogram image and can replace the conventional edge detectors like Laplacian, gaussian etc. The filter gives rise to improved visualization and early detection of microcalcifications, which if left undetected, can lead to breast cancer. The performance of the filter is analyzed and found superior to conventional spatial edge detectors