Este trabalho trata de pesquisa de soluções para a síntese física de circuitos integrados menos susceptíveis aos efeitos de variabilidade decorrentes do uso de tecnologias de fabricação com dimensões nanométricas. Também apresenta a pesquisa e o desenvolvimento de uma ferramenta para a geração de leiautes regulares denominada R-CAT. A regularidade geométrica é explorada pela repetição de padrões básicos de leiaute ao longo de uma matriz. A regularidade é apontada como uma das melhores alternativas para lidar com os atuais problemas de fabricação em tecnologias submicrônicas. Projetos regulares são menos suscetíveis aos problemas de litografia, aumentam o yield e diminuem o tempo gasto em re-projeto. Além disso, circuitos regulares apresentam maior previsibilidade de resultados de potência, atraso e yield, principalmente pelo fato das células estarem pré-caracterizadas. A ferramenta desenvolvida visa o trabalho com dois tipos de síntese física para leiautes regulares, produzindo circuitos integrados personalizáveis por todas as máscaras ou circuitos personalizáveis por algumas máscaras. O principal objetivo deste gerador é a facilidade de conversão e adaptação dependendo da abordagem de matriz escolhida. Isso facilitará a comparação entre diferentes alternativas de matrizes, a adoção de blocos lógicos diversos e de novas tecnologias. O gerador de leiautes R-CAT identifica células adjacentes com conexões em comum entre elas e realiza a conexão entre essas células em metal 1, reduzindo o número de conexões a ser realizado pelo roteador em até 10%. A ferramenta R-CAT está inserida em um fluxo de projeto e depende do método de síntese lógica adotado. Duas ferramentas de síntese lógica foram utilizadas: SIS e OrBDDs, oferecendo duas linhas de projeto: a primeira priorizando a área e a segunda priorizando timing e interconexões curtas. Ambas respeitando a mesma regularidade geométrica imposta pela matriz. Os resultados obtidos demonstram que as matrizes SIS ocupam 53% menos área do que a estratégia orBDD e reduzem o wire length em 30%. Uma área menor é obtida devido ao fato da ferramenta SIS gerar descrições com a metade de células lógicas e nets. Entretanto, as matrizes R-CAT OrBDD apresentam menor wire length médio, menor fan-out (redução de 15%), menor delay e maior roteabilidade. As sínteses OrBDD apresentam poucas nets não roteadas sem a inserção de trilhas extras. Além disso, as matrizes R-CAT atingiram resultados até 40% menores em wire length e reduções de área de até 46% em relação às matrizes MARTELO. / This work presents a research for physical synthesis of integrated circuits, which are less susceptible to the effects of variability observed in fabrication technologies using nanometers scale. Moreover, it presents a CAD tool developed to generate regular layouts, which is called R-CAT. The geometric regularity is achieved using basic patterns repeated along one matrix structure. Regularity is pointed like one of the best alternatives to deal with submicron technologies issues. Regular designs are less susceptible to lithographic problems, improve the yield and decrease the time to re-spin. Furthermore, regular circuits improve predictability of power consumption, timing and yield results, because the cells are pre-characterized. The developed tool focuses on two types of physical synthesis for regular layouts, producing either integrated circuit customized using all masks or integrated circuits customized using some masks. The main goal is the facility of conversion and adaptation depending on the chosen matrix approach. This will make easier the comparison of different matrix approaches, besides the adoption of several logic blocks and new technologies. R-CAT layout generator identifies adjacent cells that are placed in a same row and have common connections between them. In this case, the generator can make these connections in Metal 1. This technique reduces the number of connections to be done by the router. The experiments showed that this technique is able to reduce about 10% the number of connections to be done. This tool is inserted into a design flow and it is dependent of the logic synthesis methodology adopted. Two logical syntheses tools were used in the flow: SIS and OrBDDs. R-CAT SIS and R-CAT orBDD Matrices were generated for a set of circuits. The use of R-CAT tool with SIS and orBDD logical synthesis offers two design lines: the first one highlights area and the second one emphasize timing and short connections. Both of them respect the same geometric regularity. The results demonstrate that SIS matrices present 53% less area than orBDD approach and reduce the wire length by 30%. The area reduction is achieved because the SIS tool generates descriptions with the half of logic cells and nets. Nevertheless, the R-CAT orBDD matrices decreased the medium wire length, reduced the fan-out in 15%, reduced the delay and improved the routability. orBDD synthesis presents few non-routed nets without extra tracks insertion. Moreover, the R-CAT matrices obtained about 40% better results in wire length and they reduced area in 46% when compared to MARTELO matrices.

Les problèmes d'optimisation de forme sont présents naturellement en physique, ingénierie, biologie, etc. Ils visent à répondre à différentes questions telles que:-A quoi une aile d'avion parfaite pourrait ressembler?-Comment faire pour réduire la résistance d'un objet en mouvement dans un gaz ou un fluide?-Comment construire une structure élastique de rigidité maximale?-Quel est le comportement d'un système de cellules en interaction?Pour des exemples précis et autres applications de l'optimisation de forme nous renvoyons à [20] et [69]. Ici, nous traitons les aspects mathématiques théoriques de l'optimisation de forme, concernant l'existence d'ensembles optimaux ainsi que leur régularité. Dans toutes les situations que l'on considère, la fonctionnelle dépend de la solution d'une certaine équation aux dérivées partielles posée sur la forme inconnue. Nous allons parfois se référer à cette fonction comme une fonction d'état.Les fonctions d'état les plus simples, mais qui apparaissent dans beaucoup de problèmes, sont données par les solutions des équations -Δw = 1 et -Δu = λu,qui sont liées à la torsion et aux modes d'oscillation d'un objet donné. Notre étude se concentrera principalement sur ces fonctionnelles de formes, impliquant la torsion et le spectre.[20] D. Bucur, G. Buttazzo: Variational Methods in Shape Optimization Problems. Progress in Nonlinear Differential Equations 65, Birkhauser Verlag, Basel (2005).[69] A. Henrot, M. Pierre: Variation et optimisation de formes: une analyse geometrique. Springer-Berlag, Berlin, 2005. / The shape optimization problems naturally appear in engineering and biology. They aim to answer questions as:-What a perfect wing may look like?-How to minimize the resistance of a moving object in a gas or a fluid?-How to build a rod of maximal rigidity?-What is the behaviour of a system of cells?The shape optimization appears also in physics, mainly in electrodynamics and in the systems presenting both classical and quantum mechanics behaviour. For explicit examples and furtheraccount on the applications of the shape optimization we refer to the books [20] and [69]. Here we deal with the theoretical mathematical aspects of the shape optimization, concerning existence of optimal sets and their regularity. In all the practical situations above, the shape of the object in study is determined by a functional depending on the solution of a given partial differential equation. We will sometimes refer to this function as a state function.The simplest state functions are provided by solutions of the equations−∆w = 1 and −∆u = λu,which usually represent the torsion rigidity and the oscillation modes of a given object. Thus our study will be concentrated mainly on the situations, in which these state functions appear,i.e. when the optimality is intended with respect to energy and spectral functionals. [20] D. Bucur, G. Buttazzo: Variational Methods in Shape Optimization Problems. Progress in Nonlinear Differential Equations 65, Birkhauser Verlag, Basel (2005).[69] A. Henrot, M. Pierre: Variation et optimisation de formes: une analyse geometrique. Springer-Berlag, Berlin, 2005.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / In this paper we provide a universal solution for continuity module in the direction of the viscosity of fully nonlinear elliptic equations considering properties of the function f integrable in different situations. Established inner estimate for the solutions of these equations based on some conditions the norm of the function f. To obtain regularity in solutions of these inhomogeneous equations and coefficients of variables we use a method of compactness, which consists essentially of approximating solutions of inhomogeneous equations for a solution of a homogeneous equation in order to "inherit" the regularity that those equations possess. / Neste trabalho fornecemos mÃdulo de continuidade universal para soluÃÃes, no sentido da viscosidade,de equaÃÃes elÃpticas totalmente nÃo lineares, considerando propriedades de integrabilidade da funÃÃo f em diferentes situaÃÃes. Estabelecemos estimativa interior para as soluÃÃes dessas equaÃÃes baseadas em algumas condiÃÃes da norma da funÃÃo f. Para se obter regularidade nas soluÃÃes dessas equacÃes nÃo homogÃneas e de coeficientes variÃveis usamos um mÃtodo de compacidade, o qual consiste, essencialmente, em aproximar soluÃÃes de equaÃÃes nÃo homogÃneas por uma soluÃÃo de uma equaÃÃo homogÃnea com o objetivo de âherdarâ a regularidade que essas equaÃÃes possuem.

Este trabalho trata de pesquisa de soluções para a síntese física de circuitos integrados menos susceptíveis aos efeitos de variabilidade decorrentes do uso de tecnologias de fabricação com dimensões nanométricas. Também apresenta a pesquisa e o desenvolvimento de uma ferramenta para a geração de leiautes regulares denominada R-CAT. A regularidade geométrica é explorada pela repetição de padrões básicos de leiaute ao longo de uma matriz. A regularidade é apontada como uma das melhores alternativas para lidar com os atuais problemas de fabricação em tecnologias submicrônicas. Projetos regulares são menos suscetíveis aos problemas de litografia, aumentam o yield e diminuem o tempo gasto em re-projeto. Além disso, circuitos regulares apresentam maior previsibilidade de resultados de potência, atraso e yield, principalmente pelo fato das células estarem pré-caracterizadas. A ferramenta desenvolvida visa o trabalho com dois tipos de síntese física para leiautes regulares, produzindo circuitos integrados personalizáveis por todas as máscaras ou circuitos personalizáveis por algumas máscaras. O principal objetivo deste gerador é a facilidade de conversão e adaptação dependendo da abordagem de matriz escolhida. Isso facilitará a comparação entre diferentes alternativas de matrizes, a adoção de blocos lógicos diversos e de novas tecnologias. O gerador de leiautes R-CAT identifica células adjacentes com conexões em comum entre elas e realiza a conexão entre essas células em metal 1, reduzindo o número de conexões a ser realizado pelo roteador em até 10%. A ferramenta R-CAT está inserida em um fluxo de projeto e depende do método de síntese lógica adotado. Duas ferramentas de síntese lógica foram utilizadas: SIS e OrBDDs, oferecendo duas linhas de projeto: a primeira priorizando a área e a segunda priorizando timing e interconexões curtas. Ambas respeitando a mesma regularidade geométrica imposta pela matriz. Os resultados obtidos demonstram que as matrizes SIS ocupam 53% menos área do que a estratégia orBDD e reduzem o wire length em 30%. Uma área menor é obtida devido ao fato da ferramenta SIS gerar descrições com a metade de células lógicas e nets. Entretanto, as matrizes R-CAT OrBDD apresentam menor wire length médio, menor fan-out (redução de 15%), menor delay e maior roteabilidade. As sínteses OrBDD apresentam poucas nets não roteadas sem a inserção de trilhas extras. Além disso, as matrizes R-CAT atingiram resultados até 40% menores em wire length e reduções de área de até 46% em relação às matrizes MARTELO. / This work presents a research for physical synthesis of integrated circuits, which are less susceptible to the effects of variability observed in fabrication technologies using nanometers scale. Moreover, it presents a CAD tool developed to generate regular layouts, which is called R-CAT. The geometric regularity is achieved using basic patterns repeated along one matrix structure. Regularity is pointed like one of the best alternatives to deal with submicron technologies issues. Regular designs are less susceptible to lithographic problems, improve the yield and decrease the time to re-spin. Furthermore, regular circuits improve predictability of power consumption, timing and yield results, because the cells are pre-characterized. The developed tool focuses on two types of physical synthesis for regular layouts, producing either integrated circuit customized using all masks or integrated circuits customized using some masks. The main goal is the facility of conversion and adaptation depending on the chosen matrix approach. This will make easier the comparison of different matrix approaches, besides the adoption of several logic blocks and new technologies. R-CAT layout generator identifies adjacent cells that are placed in a same row and have common connections between them. In this case, the generator can make these connections in Metal 1. This technique reduces the number of connections to be done by the router. The experiments showed that this technique is able to reduce about 10% the number of connections to be done. This tool is inserted into a design flow and it is dependent of the logic synthesis methodology adopted. Two logical syntheses tools were used in the flow: SIS and OrBDDs. R-CAT SIS and R-CAT orBDD Matrices were generated for a set of circuits. The use of R-CAT tool with SIS and orBDD logical synthesis offers two design lines: the first one highlights area and the second one emphasize timing and short connections. Both of them respect the same geometric regularity. The results demonstrate that SIS matrices present 53% less area than orBDD approach and reduce the wire length by 30%. The area reduction is achieved because the SIS tool generates descriptions with the half of logic cells and nets. Nevertheless, the R-CAT orBDD matrices decreased the medium wire length, reduced the fan-out in 15%, reduced the delay and improved the routability. orBDD synthesis presents few non-routed nets without extra tracks insertion. Moreover, the R-CAT matrices obtained about 40% better results in wire length and they reduced area in 46% when compared to MARTELO matrices.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-19T12:25:23Z No. of bitstreams: 2 Dissertação - Gean Carlos Sousa Gonzaga - 2015.pdf: 2479646 bytes, checksum: d85220319554b1544933aa25ea2c672c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-19T12:27:30Z (GMT) No. of bitstreams: 2 Dissertação - Gean Carlos Sousa Gonzaga - 2015.pdf: 2479646 bytes, checksum: d85220319554b1544933aa25ea2c672c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-19T12:27:30Z (GMT). No. of bitstreams: 2 Dissertação - Gean Carlos Sousa Gonzaga - 2015.pdf: 2479646 bytes, checksum: d85220319554b1544933aa25ea2c672c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-08-06 / This paper addresses the theorem of Napoleon on historical, conceptual perspectives, and focusing on demonstrations and applications properties as well. In the rst chapter, are discussed aspects of the history and Napoleon Bonaparte biography. In the second chapter are addressed notions of Plane Geometry, Linear Algebra, of Rigid Transformation of Complex Numbers and Related Transformations. In the third chapter, statements are presented, generalizations (especially the so-called Barlotti Theorem), properties and applications in exercises. / O presente trabalho aborda o teorema de Napoleão em perspectivas históricas e conceituais, enfocando demonstrações e propriedades. No primeiro capítulo, são abordados aspectos da biogra a de Napoleão Bonaparte. No segundo capítulo são abordadas no- ções de Geometria Plana, de Álgebra Linear, de Transformações Rígidas, de Números Complexos e Transformações A ns. No terceiro capítulo, são apresentadas demonstra ções, generalizações (em especial, o chamado Teorema de Barlotti), propriedades e aplicações em exercícios.

Chez les humains et les animaux, l’exposition répétée à une séquence de stimulus conduit à la création de représentations mentales isomorphes aux régularités statistiques de cette séquence. Cette thèse étudie la dynamique avec laquelle les unités et sous-unités sont extraites, s’influencent et s’organisent lors de l’apprentissage séquentiel chez l’humain et le primate non-humain (babouin Papio papio). Nos résultats montrent que lors de l’apprentissage d’une séquence régulière ABC, la sous-unité finale BC est apprise plus rapidement que la sous-unité initiale AB chez les humains comme les primates non- humains. Avec une séquence plus longue ABCD, cet effet ne s’étend pas au-delà des deux termes précédents celui à prédire lors des 2000 essais d’apprentissage. Une seconde étude montre que les humains sont capables d’utiliser la prédictibilité des éléments à différents niveaux de complexité, alors que les singes sont limités aux dépendances locales. Enfin notre dernière étude montre que les humains comme les singes ne bénéficient pas d’un contexte d’homogénéité de longueurs des unités par rapport à un contexte d’hétérogénéité de longueurs des unités. Ensemble, ces études montrent des continuités et discontinuités entre les primates humains et non-humains dans l’extraction, l’influence et l’organisation des unités de différents niveaux. Elles donnent des informations d’une finesse nécessaires pour contraindre les différents modèles computationnels qui ont été proposés pour décrire l’apprentissage de régularités. / In humans and animals, the repeated exposure to a sequence of stimulus creates mental representations which have the same statistical regularities as that sequence. This thesis investigates the dynamics, influence and organization of units and sub-units during sequence learning, in humans and non-human primates (Guinea baboons, Papio papio).Our results show an advantage of the final sub- unit BC over the initial sub-unit AB during learning of sequences with the form ABC in both humans and baboons. We interpret this effect as resulting from the richer contextual information AB predicting C compared to the single term A predicting B. This effect is limited to the 2 previous terms before the one term to be predicted, across 2000 learning trials. A second finding shows that in learning sequences of 3 units (i.e. ABC, DEF, HGI), humans are able to use the predictability of elements at both local (within units) and global (within sequence) levels, whereas monkeys are limited to local dependencies. A third section investigates the extraction of regularities in homogeneous (i.e., units of the same length) and heterogeneous contexts (units of different lengths). Results in humans and monkeys showed no advantage for either of these contexts.Considered together, our studies show continuities and discontinuities between human and non-human primates in the extraction, influence and organization of units of different levels. This fine-grained level of information is necessary to constrain the computational models proposed to describe the mechanisms underlying regularity extraction.

The thesis studies homogenization of Dirichlet boundary value problems for divergence type elliptic operators, and the associated boundary layer issues. This type of problems for operators with periodically oscillating coeffcients, and fixed boundary data are by now a classical topic largely due to the celebrated work by Avellaneda and Lin from late 80's. The case when the operator and the Dirichlet boundary data exhibit periodic oscillations simultaneously was a longstanding open problem, and a progress in this direction has been achieved only very recently, in 2012, by Gerard-Varet and Masmoudi who proved a homogenization result for the simultaneously oscillating case with an algebraic rate of convergence in L2. Aimed at understanding the homogenization process of oscillating boundary data, in the first part of the thesis we introduce and develop Fourier-analytic ideas into the study of homogenization of Dirichlet boundary value problems for elliptic operators in divergence form. In smooth and bounded domains, for fixed operator and periodically oscillating boundary data we prove pointwise, as well as Lp convergence results the homogenization problem. We then investigate the optimality (sharpness) of our Lp upper bounds. Next, for the above mentioned simultaneously oscillating problem studied by Gerard-Varet and Masmoudi, we establish optimal Lp bounds for homogenization in some class of operators. For domains with non smooth boundary, we study similar boundary value homogenization problems for scalar equations set in convex polygonal domains. In the vein of smooth boundaries, here as well for problems with fixed operator and oscillating Dirichlet data we prove pointwise, and Lp convergence results, and study the optimality of our Lp bounds. Although the statements are somewhat similar with the smooth setting, challenges for this case are completely different due to a radical change in the geometry of the domain. The second part of the work is concerned with the analysis of boundary layers arising in periodic homogenization. A key difficulty toward the homogenization of Dirichlet problem for elliptic systems in divergence form with periodically oscillating coefficients and boundary condition lies in identification of the limiting Dirichlet data corresponding to the effective problem. This question has been addressed in the aforementioned work by Gerard-Varet and Masmoudi on the way of proving their main homogenization result. Despite the progress in this direction, some very basic questions remain unanswered, for instance the regularity of this effective data on the boundary. This issue is directly linked with the up to the boundary regularity of homogenized solutions, but perhaps more importantly has a potential to cast light on the homogenization process. We initiate the study of this regularity problem, and prove certain Lipschitz continuity result. The work also comprises a study on asymptotic behaviour of solutions to boundary layer systems set in halfspaces. By a new construction we show that depending on the normal direction of the hyperplane, convergence of the solutions toward their tails far away from the boundaries can be arbitrarily slow. This last result, combined with the previous studies gives an almost complete picture of the situation.

Le contrôle et à la maîtrise de l’état des surfaces est un besoin majeur pour les industriels. De nombreuses études sur les interactions entre la morphologie de surface et les mécanismes physiques, chimiques ou mécaniques, ont été réalisées. Cependant une caractérisation plus précise en fonction des domaines et des besoins est nécessaire. Elle consiste à chercher les paramètres de rugosité les plus pertinents qui relient la topographie d’une surface aux phénomènes physiques qu’elle subit ou aux propriétés du matériau dont elle composé.Dans ce travail, un logiciel pour caractériser l’état de surface a été développé. Cet outil nommé « MesRug » permet de calculer des paramètres de rugosité et d’extraire les plus pertinents ainsi que de définir l’échelle la plus adéquate pour une application donnée. La recherche des paramètres les plus pertinent se fait par une approche statistique (l'analyse de la variance ‘ANOVA’ combinée avec la théorie du Bootstrap).Une caractérisation a été effectuée en utilisant des données de mesures (2D) sur des surfaces abrasives. L’influence de la forme des ondelettes discrètes et continues sur la détection de l’échelle pertinente du mécanisme d’abrasion a été testée. On déduit que la décomposition en ondelettes permet de quantifier et de localiser les échelles de l'abrasion des processus d'usinage pour tous les paramètres du processus. Cependant, la pertinence de caractériser les échelles appropriées d'abrasion ne dépend pas de la forme de l'ondelette.Dans ce travail, un nouveau paramètre de rugosité 3D est proposé pour quantifier la régularité d'une surface indépendamment de l'amplitude et des unités de longueur de balayage. L'efficacité de ce paramètre est testée sur des surfaces périodiques bruitées avec différents degrés d'anisotropie. La valeur de ce paramètre est comprise entre zéro (bruit parfait) et 100% (surface sinusoïdale parfaite). Il nous a permis de détecter les directions d'anisotropie de régularité pour une surface donnée. / Monitoring and control of the state of the surfaces is a major need for industry. Numerous studies on the interactions between the surface morphology and the physical, chemical or mechanical mechanisms have been conducted. However, a more precise characterization related to industrial domains and needs is necessary. It consists in finding the most relevant roughness parameters that connect the topography of a surface with the physical phenomena which it undergoes or in the properties of the material of which it consisted.In this work, a software designed to characterize the surface condition was developed. This tool named "MesRug" allows to calculate roughness parameters then extract the most relevant ones and to define the most appropriate scale for a given application. The search for the most relevant parameters is done by a statistical approach (analysis of variance ANOVA combined with the theory of Bootstrap).A characterization was performed using (2D) data of measurement on abrasive surfaces. The influence of the form of discrete and continuous wavelet on the detection on the relevant scale mechanism of the abrasion was tested. We conclude that the wavelet decomposition allows to quantify and localize the scales of abrasion of the machining process for all process parameters. However, the relevance of appropriate scales to characterize abrasion does not depend on the shape of the wavelet.In this work, a new 3D roughness parameter is proposed to quantify the smoothness of a surface, independently of the amplitude and the scanning length units of the surface. The efficiency of this parameter is tested on noisy periodic surfaces with varying degrees of anisotropy. The value of this parameter is between zero (perfect sound) and 100 % (sine perfect surface). It enables us to identify the anisotropy directions of regularity for a given surface.

Dans le cadre de l’aide à l’analyse de dialogues, un corpus de dialogues peut être représenté par un ensemble de tableaux d’annotations encodant les différents énoncés des dialogues. Afin d’identifier des schémas dialogiques mis en oeuvre fréquemment, nous définissons une méthodologie en deux étapes : extraction de motifs récurrents, puis partitionnement de ces motifs en classes homogènes constituant ces régularités. Deux méthodes sont développées afin de réaliser l’extraction de motifs récurrents : LPCADC et SABRE. La première est une adaptation d’un algorithme de programmation dynamique tandis que la seconde est issue d’une modélisation formelle du problème d’extraction d’alignements locaux dans un couple de tableaux d’annotations.Le partitionnement de motifs récurrents est réalisé par diverses heuristiques de la littérature ainsi que deux formulations originales du problème de K-partitionnement sous la forme de programmes linéaires en nombres entiers. Lors d’une étude polyèdrale, nous caractérisons des facettes d’un polyèdre associé à ces formulations (notamment les inégalités de 2-partitions, les inégalités 2-chorded cycles et les inégalités de clique généralisées). Ces résultats théoriques permettent la mise en place d’un algorithme de plans coupants résolvant efficacement le problème.Nous développons le logiciel d’aide à la décision VIESA, mettant en oeuvre ces différentes méthodes et permettant leur évaluation au cours de deux expérimentations réalisées par un expert psychologue. Des régularités correspondant à des stratégies dialogiques que des extractions manuelles n’avaient pas permis d’obtenir sont ainsi identifiées. / In the context of dialogue analysis, a corpus of dialogues can be represented as a set of arrays of annotations encoding the dialogue utterances. In order to identify the frequently used dialogue schemes, we design a two-step methodology in which recurrent patterns are first extracted and then partitioned into homogenous classes constituting the regularities. Two methods are developed to extract recurrent patterns: LPCA-DC and SABRE. The former is an adaptation of a dynamic programming algorithm whereas the latter is obtained from a formal modeling of the extraction of local alignment problem in annotations arrays.The partitioning of recurrent patterns is realised using various heuristics from the literature as well as two original formulations of the K-partitioning problem in the form of mixed integer linear programs. Throughout a polyhedral study of a polyhedron associated to these formulations, facets are characterized (in particular: 2-chorded cycle inequalities, 2-partition inequalities and general clique inequalities). These theoretical results allow the establishment of an efficient cutting plane algorithm.We developed a decision support software called VIESA which implements these different methods and allows their evaluation during two experiments realised by a psychologist. Thus, regularities corresponding to dialogical strategies that previous manual extractions failed to identify are obtained.

Dans cette thèse on aborde deux problèmes. Dans la première partie on considère des diffusions hypoelliptiques, à la fois sur une condition d'Hormander forte et faible. On trouve des estimations gaussiennes pour la densité de la loi de la solution à un temps court fixé. Un outil fondamental pour prouver ces estimations est le calcul de Malliavin, et en particulier on utilise des techniques développées récemment pour faire face à des problèmes de dégénérescence. Ensuite, grâce à ces estimations en temps court, on trouve des bornes inférieures et supérieures exponentielles sur la probabilité que la diffusion reste dans un petit tube autour d'une trajectoire déterministe jusqu'à un moment fixé. Dans ce cadre hypoelliptique, la forme du tube doit tenir compte du fait que la diffusion se déplace avec une vitesse différente dans les directions du coefficient de diffusion et dans les directions des crochets de Lie. Pour cette raison, on introduit une norme qui prend en compte ce comportement anisotrope, qui peut être adaptée aux cas d'Hormander fort et faible. Dans le cas Hormander fort on établit un lien entre cette norme et la distance de contrôle classique. Dans le cas Hormander faible on introduit une distance de contrôle équivalente appropriée. Dans la deuxième partie de la thèse, on travaille avec des modèles à volatilité stochastique avec retour à la moyenne, oú la volatilité est dirigée par un processus de saut. On suppose d'abord que les sauts suivent un processus de Poisson, et on considère la décroissance des corrélations croisées, théoriquement et empiriquement. Ceci nous amène à étudier un algorithme pour la détection de sauts de la volatilité. On considère ensuite un phénomène plus subtil largement observé dans les indices financiers: le "multiscaling" des moments, c'est-à-dire le fait que les moments d'ordre q des log-incréments du prix sur un temps h, ont une amplitude d'ordre h à une certaine puissance, qui est non linéaire dans q. On travaille avec des modèles oú la volatilité suit une EDS avec retour à la moyenne dirigée par un subordinateur de Lévy. On montre que le multiscaling se produit si la mesure caractéristique du Lévy a des queues de loi de puissance et le retour à la moyenne est superlinéaire à l'infini. Dans ce cas l'exposant de scaling est linéaire par morceaux / In this thesis we address two problems. In the first part we consider hypoelliptic diffusions, under both strong and weak Hormander condition. We find Gaussian estimates for the density of the law of the solution at a fixed, short time. A main tool to prove these estimates is Malliavin Calculus, in particular some techniques recently developed to deal with degenerate problems. We then use these short-time estimates to show exponential two-sided bounds for the probability that the diffusion remains in a small tube around a deterministic path up to a given time. In our hypoelliptic framework, the shape of the tube must reflect the fact the diffusion moves with a different speed in the direction of the diffusion coefficient and in the direction of the Lie brackets. For this reason we introduce a norm accounting of this anisotropic behavior, which can be adapted to both the strong and weak Hormander framework. We establish a connection between this norm and the standard control distance in the strong Hormander case. In the weak Hormander case, we introduce a suitable equivalent control distance. In the second part of the thesis we work with mean reverting stochastic volatility models, with a volatility driven by a jump process. We first suppose that the jumps follow a Poisson process, and consider the decay of cross asset correlations, both theoretically and empirically. This leads us to study an algorithm for the detection of jumps in the volatility profile. We then consider a more subtle phenomenon widely observed in financial indices: the multiscaling of moments, i.e. the fact that the q-moment of the log-increment of the price on a time lag of length h scales as h to a certain power of q, which is non-linear in q. We work with models where the volatility follows a mean reverting SDE driven by a Lévy subordinator. We show that multiscaling occurs if the characteristic measure of the Lévy has power law tails and the mean reversion is super-linear at infinity. In this case the scaling function is piecewise linear