La present memòria estudia l'estabilitat estructural de ternes de matrius. Es ben conegut que els sistemes dinàmic lineals amb coeficients constants poden venir definits per ternes de matrius, d'aquí l'interès d'aquest estudi. En particular es donen a la memòria diferents condicions necessàries i suficients per que una terna de matrius sigui estructuralment estable respecte d'una relació d'equivalència prèviament introduïda en l'espai de ternes de matrius, bé a partir de la seva forma reduïda canònica, bé per altres mètodes. En aquest estudi s'utilitzen de forma bàsica les deformacions miniversals de ternes de matrius, la qual cosa és possible ja que es veu la relació d'equivalència considerada en l'espai de ternes de matrius com l'induïda per l'acció d'un grup de LIE en la varietat diferenciable del espai de ternes de matrius. L'estudi dels casos de ternes de matrius no estructuralment estables per a les quals la dimensió de la deformació miniversal és inferior o igual a tres suggereix una nova partició de l'espai de ternes de matrius (que es demostra que és una estratificació) i una nova relació d'equivalència, l'associada a aquesta darrera partició. Es caracteritzen també les ternes de matrius estructuralment estables respecte d'aquesta nova relació d'equivalència. Finalment, s'estudien els casos de les ternes que no són estructuralment estables respecte d'aquesta darrera relació en els casos que la dimensió d'una família minitransversal a l'estrat té dimensió inferior o igual a tres, família que ha estat prèviament trobada. A tot l'estudi realitzat s'utilitza un nou sistema complet d'invariants per a una terna de matrius, la principal característica dels quals és tot els invariants discrets del sistema venen donats en funció del rang d'unes certes matrius associades a les matrius que composen la terna. La definició d'aquestes matrius i la demostració de que és una sistema complet d'invariants constitueix la primera part de la memòria. / -RESUMEN La presente memoria estudia la estabilidad estructural de ternas de matrices. Es bien conocido que los sistemas dinamicos lineales con coeficientes constantes pueden venir definidos por ternas de matrices, de ahi el interes de este estudio. En particular, se dan en la memoria distintas condiciones necesarias y suficientes para que una terna de matrices sea estructuralmente estable con respecto de una relacion de equivalencia previamente introducida en el espacio de ternas de matrices, bien a partir de su forma reducida canonica, bien por otros metodos. En este estudio se utilizan de forma basica las deformaciones miniversales de ternas de matrices, lo cual es posible puesto que se ve la relacion de equivalencia considerada en el espacio de ternas de matrices como la inducida por la accion de un grupo de lie en la variedad diferenciable del espacio de ternas de matrices. El estudio de los casos de ternas de matrices no estructuralmente estables para las cuales la dimension de la deformacion miniversal es inferior o igual a tres sugiere una nueva particion del espacio de ternas de matrices (que se demuestra que es una estratificacion) y una nueva relacion de equivalencia, la asociada a esta ultima particion. Se caracterizan tambien las ternas de matrices estructuralmente estables respecto de esta nueva relacion de equivalencia. Finalmente, se estudian los casos de las ternas que no son estructuralmente estables respecto de esta ultima relacion en los casos en que la dimension de una familia minitransversal al estrato tiene dimension inferior o igual a tres, familia que ha sido previamente encontrada. En todo el estudio realizado se utiliza un nuevo sistema completo de invariantes para una terna de matrices, cuya principal caracteristica es que todos los invariantes discretos del sistema vienen dados en funcion del rango de unas ciertas matrices asociadas a las matrices que componen la terna. La definicion de estas matrices y la demostracion de que es un sistema completo de invariantes constituye la primera parte de la memoria.

La descripció qualitativa dels colors que composen una imatge digital és una tasca molt senzilla pel sistema visual humà. Per un ordinador aquesta tasca involucra una gran quantitat de qüestions i de dades que la converteixen en una operació de gran complexitat. En aquesta tesi desenvolupam un mètode automàtic per a la construcció d'una paleta de colors d'una imatge digital, intentant respondre a les diferents qüestions que se'ns plantegen quan treballam amb colors a dins el món computacional. El desenvolupament d'aquest mètode suposa l'obtenció d'un algorisme automàtic de segmentació d'histogrames, el qual és construït en detall a la tesi i diferents aplicacions del mateix son donades. Finalment, també s'explica el funcionament de CProcess, un 'software' amigable desenvolupat per a la fàcil comprensió del color.

This work concerns some problems in the area of survival analysis that arise in real clinical or epidemiological studies. In particular, we approach the problem of estimating the survival function based on interval-censored data or doubly-censored data. We will start defining these concepts and presenting a brief review of different methodologies to deal with this kind of censoring patterns.Survival analysis is the term used to describe the analysis of data that correspond to the time from a well defined origin time until the occurrence of some particular event of interest. This event need not necessarily be death, but could, for example, be the response to a treatment, remission from a disease, or the occurrence of a symptom

The present thesis addresses several machine learning problems on generative and predictive models on sequential data. All the models considered have in common that they can be de ned in terms of nite-state machines. On one line of work we study algorithms for learning the probabilistic analog of Deterministic Finite Automata (DFA). This provides a fairly expressive generative model for sequences with very interesting algorithmic properties. State-merging algorithms for learning these models can be interpreted as a divisive clustering scheme where the "dependency graph" between clusters is not necessarily a tree. We characterize these algorithms in terms of statistical queries and a use this characterization for proving a lower bound with an explicit dependency on the distinguishability of the target machine. In a more realistic setting, we give an adaptive state-merging algorithm satisfying the stringent algorithmic constraints of the data streams computing paradigm. Our algorithms come with strict PAC learning guarantees. At the heart of state-merging algorithms lies a statistical test for distribution similarity. In the streaming version this is replaced with a bootstrap-based test which yields faster convergence in many situations. We also studied a wider class of models for which the state-merging paradigm also yield PAC learning algorithms. Applications of this method are given to continuous-time Markovian models and stochastic transducers on pairs of aligned sequences. The main tools used for obtaining these results include a variety of concentration inequalities and sketching algorithms. In another line of work we contribute to the rapidly growing body of spectral learning algorithms. The main virtues of this type of algorithms include the possibility of proving nite-sample error bounds in the realizable case and enormous savings on computing time over iterative methods like Expectation-Maximization. In this thesis we give the rst application of this method for learning conditional distributions over pairs of aligned sequences de ned by probabilistic nite-state transducers. We also prove that the method can learn the whole class of probabilistic automata, thus extending the class of models previously known to be learnable with this approach. In the last two chapters we present works combining spectral learning with methods from convex optimization and matrix completion. Respectively, these yield an alternative interpretation of spectral learning and an extension to cases with missing data. In the latter case we used a novel joint stability analysis of matrix completion and spectral learning to prove the rst generalization bound for this type of algorithms that holds in the non-realizable case. Work in this area has been motivated by connections between spectral learning, classic automata theory, and statistical learning; tools from these three areas have been used.

El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequeños, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio o se minimice la pérdida del material sobrante. En esta Tesis se han abordado dos problemas concretos de corte en dos dimensiones. En ellos suponemos que las piezas a cortar y los tableros son rectangulares y que se permiten cortes que no sean de tipo guillotina. El primer problema tratado ha sido aquél en el que se dispone de un tablero del que se ha de cortar el máximo número de piezas de un solo tipo. Este problema es conocido como el Pallet Loading Problem, ya que su aplicación más habitual surge cuando un pallet rectangular se ha de llenar en la fábrica con el mayor número posible de cajas de un solo producto.. Nuestro trabajo ha consistido, en primer lugar, en el desarrollo de un algoritmo exacto, basado en procedimientos Branch and Cut, que no habían sido aplicados hasta ahora a este problema. Este algoritmo ha permitido resolver óptimamente problemas de hasta 100 cajas que no habían sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heurístico basado en Tabu Search que resuelve de forma eficiente problemas de hasta 150 cajas.El segundo problema tratado es el problema en el que se dispone de un tablero, del que se ha de cortar un subconjunto de las piezas demandadas. Este problema admite, a su vez, cuatro subproblemas, dependiendo de la función objetivo (maximizar el valor de las piezas cortadas o minimizar el área no utilizada del tablero) y de la existencia o no de cotas superiores en el número de piezas a cortar de cada tipo. Se han desarrollado algoritmos heurísticos que resuelven las cuatro versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rápidos, que pueden servir como subrutinas de algoritmos más complejos. En una segunda fase, se ha diseñado un algoritmo metaheurístico más complejo, GRASP, para obtener soluciones, que superan en calidad y menor tiempo de computación a las de los mejores algoritmos publicados. / The constrained two-dimensional cutting problem consists of satisfying the demands of small pieces from a set of large stock sheets with the objective of maximizing the total value of the pieces cut. In this work we have studied two particular two-dimensional cutting problems in which both pieces and stock sheets are rectangular and non-guillotine cuts are allowed. The Pallet Loading Problem (PLP) arises whenever identical rectangular boxes have to be packed on a rectangular pallet. Though the problem is initially three-dimensional, practical considerations usually mean that the boxes must be placed orthogonally with respect to the edges of the pallet, and in layers in which the vertical orientation of the boxes is fixed. With these restrictions the problem becomes the two-dimensional problem of packing a large rectangle, pallet, with the maximum number of small identical rectangles, boxes. The problem has many practical applications in distribution and logistics. We have developed a branch and cut algorithm for that problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes) which .had not been previously solved. In a second phase, we have developed a heuristic algorithm, based on Tabu Search, that solves efficiently problems with up to 150 boxes. In the second problem studied several types of pieces can be cut from the large stock rectangle. For this problem we have developed a greedy randomized adaptive search procedure (GRASP). We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well known instances previously reported, which show that our algorithm improves the best known results in terms of quality and computing time.

This dissertation addresses three different problems in the study of discrete dynamical systems. Firstly, this work dynamically classifies a 9−parametric family of planar birational maps f : C2 → C2 that is f(x, y) = α0 + α1x + α2y, β0 + β1x + β2y γ0 + γ1x + γ2y , where the parameters are complex numbers. This is done by finding the dynamical degree δ for the degenerate and non degenerate cases of F that is the extended map of f in projective space. The dynamical degree δ defined as δ(F) := lim n→∞ (deg(Fn)) 1 n , indicates the subfamilies which are chaotic, that is when δ > 1, and otherwise. The study of the sequence of degrees dn of F shows the degree growth rate of all the subfamilies of f. This gives the families which have bounded growth , or they grow linearly, quadratically or grow exponentially. The family f includes the birational maps studied by Bedford and Kim in [18] as one of its subfamily. The second problem includes the study of the subfamilies of f with zero entropy that is for δ = 1. These includes the families with bounded (in particular periodic), linear or quadratic growth rate. Two transverse fibrations are found for the families with bounded growth. In the periodic case the period of the families is indicated. It is observed that there exist infinite periodic subfamilies of f, depending on the parameter region. The families with linear growth rate preserve rational fibration and the quadratic growth rate families preserve elliptic fibration that is unique depending on the parameters. In all the cases with zero entropy all the mappings are found up to affine conjugacy. Thirdly, it deals with non-autonomous Lyness type recurrences of the form xn+2 = an + xn+1 xn , where {an}n is a k-periodic sequence of complex numbers with minimal period k. We treat such non-autonomous recurrences via the autonomous dynamical system generated by the birational mapping Fak ◦ Fak−1 ◦ · · · ◦ Fa1 where Fa is defined by Fa(x, y) = (y, a + y x ). For the cases k ∈ {1, 2, 3, 6} the corresponding mappings have a rational first integral. By calculating the dynamical degree we show that for k = 4 and for k = 5 generically the dynamical system is no longer rationally integrable. We also prove that the only values of k for which the corresponding dynamical system is rationally integrable for all the values of the involved parameters, are k ∈ {1, 2, 3, 6}.

Esta monografía presenta un marco de trabajo para el aprendizaje en un escenario de datos distribuidos y con control descentralizado. Hemos basado nuestro marco de trabajo en Sistemas Multi-Agente (MAS) para poder tener control descentralizado, y en Razonamiento Basado en Casos (CBR), dado que su naturaleza de aprendizaje perezoso lo hacen adecuado para sistemas multi-agentes dinámicos. Además, estamos interesados en agentes autónomos que funcionen como ensembles. Un ensemble de agentes soluciona problemas de la siguiente manera: cada agente individual soluciona el problema actual individualmente y hace su predicción, entonces todas esas predicciones se agregan para formar una predicción global. Así pues, en este trabajo estamos interesados en desarrollar estrategias de aprendizaje basadas en casos y en ensembles para sistemas multi-agente.Concretamente, presentaremos un marco de trabajo llamado Razonamiento Basado en Casos Multi-Agente (MAC), una aproximación al CBR basada en agentes. Cada agente individual en un sistema MAC es capaz de aprender y solucionar problemas individualmente utilizando CBR con su base de casos individual. Además, cada base decasos es propiedad de un agente individual, y cualquier información de dicha base de casos será revelada o compartida únicamente si el agente lo decide así. Por tanto, este marco de trabajo preserva la privacidad de los datos y la autonomía de los agentes para revelar información.Ésta tesis se centra en desarrollar estrategias para que agentes individuales con capacidad de aprender puedan incrementar su rendimiento tanto cuando trabajan individualmente como cuando trabajan como un ensemble. Además, las decisiones en un sistema MAC se toman de manera descentralizada, dado que cada agente tiene autonomía de decisión. Por tanto, las técnicas desarrolladas en este marco de trabajo consiguen un incremento del rendimiento como resultado de decisiones individuales tomadas de manera descentralizada. Concretamente, presentaremos tres tipos de estrategias: estrategias para crear ensembles de agentes, estrategias para realizar retención de casos en sistemas multi-agente, y estrategias para realizar redistribución de casos. / This monograph presents a framework for learning in a distributed data scenario with decentralized decision making. We have based our framework in Multi-Agent Systems (MAS) in order to have decentralized decision making, and in Case-Based Reasoning (CBR), since the lazy learning nature of CBR is suitable for dynamic multi-agent systems. Moreover, we are interested in autonomous agents that collaborativelywork as ensembles. An ensemble of agents solves problems in the following way: each individual agent solves the problem at hand individually and makes its individual prediction, then all those predictions are aggregated to form a global prediction. Therefore, in this work we are interested in developing ensemble case basedlearning strategies for multi-agent systems.Specifically, we will present the Multi-Agent Case Based Reasoning (MAC) framework, a multi-agent approach to CBR. Each individual agent in a MAC system is capable of individually learn and solve problems using CBR with an individual case base. Moreover, each case base is owned and managed by an individual agent, and any information is disclosed or shared only if the agent decides so. Thus, this framework preserves the privacy of data, and the autonomy to disclose data.The focus of this thesis is to develop strategies so that individual learning agents improve their performance both individually and as an ensemble. Moreover, decisions in the MAC framework are made in a decentralized way since each individual agent has decision autonomy. Therefore, techniques developed in this framework achieve an improvement of individual and ensemble performance as a result of individual decisions made in a decentralized way. Specifically, we will present three kind of strategies: strategies to form ensembles of agents, strategies to perform case retention in multi-agent systems, and strategies to perform case redistribution.

SISTEMAS DE INSERCIÓN Y BORRADO: COMPLEJIDAD Y CAPACIDAD DE MODELADO El objetivo central de la tesis es el estudio de los sistemas de inserción y borrado y su capacidad computacional. Más concretamente, estudiamos algunos modelos de generación de lenguaje que usan operaciones de reescritura de dos cadenas. También consideramos una variante distribuida de los sistemas de inserción y borrado en el sentido de que las reglas se separan entre un número finito de nodos de un grafo. Estos sistemas se denominan sistemas controlados mediante grafo, y aparecen en muchas áreas de la Informática, jugando un papel muy importante en los lenguajes formales, la lingüística y la bio-informática. Estudiamos la decidibilidad/ universalidad de nuestros modelos mediante la variación de los parámetros de tamaño del vector. Concretamente, damos respuesta a la cuestión más importante concerniente a la expresividad de la capacidad computacional: si nuestro modelo es equivalente a una máquina de Turing o no. Abordamos sistemáticamente las cuestiones sobre los tamaños mínimos de los sistemas con y sin control de grafo. / COMPLEXITY AND MODELING POWER OF INSERTION-DELETION SYSTEMS The central object of the thesis are insertion-deletion systems and their computational power. More specifically, we study language generating models that use two string rewriting operations: contextual insertion and contextual deletion, and their extensions. We also consider a distributed variant of insertion-deletion systems in the sense that rules are separated among a finite number of nodes of a graph. Such systems are refereed as graph-controlled systems. These systems appear in many areas of Computer Science and they play an important role in formal languages, linguistics, and bio-informatics. We vary the parameters of the vector of size of insertion-deletion systems and we study decidability/universality of obtained models. More precisely, we answer the most important questions regarding the expressiveness of the computational model: whether our model is Turing equivalent or not. We systematically approach the questions about the minimal sizes of the insertiondeletion systems with and without the graph-control.

Uno de los principales objetivos de la Estadística es la comparación de variables aleatorias. Estas comparaciones están principalmente basadas en mediadas asociadas a dichas variables como las medias, medianas o varianzas. En muchas situaciones, estas comparaciones no resultan muy informativas, por lo que sería de interés establecer criterios de comparación más elaborados, lo que ha motivado el desarrollo de la teoría de ordenaciones estocásticas. Dicha teoría esta formada por diversos criterios que comparan distintas características asociadas a las variables, las cuáles se miden mediante funciones de interés en fiabilidad, riesgos y economía. Estas funciones están definidas en términos de ciertas integrales incompletas de las funciones cuantiles o de supervivencia. Desafortunadamente, dichas integrales no siempre tiene expresión explícita, lo cuál dificulta el estudio. A pesar de poder verificar otras ordenaciones, así como condiciones más fuertes, hay muchos casos que no están cubiertos por ninguna herramienta existente en la literatura, puesto que todas las ordenaciones son parciales. Por esta razón, una de las principales líneas de investigación dentro de este tópico es el estudio de condiciones suficientes para los distintos criterios que sean fáciles de verificar cuando las variables no se ordenen en ningún criterio más fuerte. Por ejemplo, el conocido orden creciente convexo se verifica cuando las integrales incompletas de las funciones de supervivencia están ordenadas. Sin embargo, existen muchas situaciones en las que estas integrales no tiene expresión analítica. En este caso, se puede verificar el orden estocástico, que es el criterio de comparación de localización más fuerte, el cuál se cumple cuando se ordenan las funciones de supervivencia. Este criterio es fácil de verificar siempre que las funciones de supervivencia tengan expresión explícita, pero incluso en los casos en los que no la tienen, existen condiciones suficientes en términos de las funciones de densidad. El problema es que, como ya hemos dicho, las variables no tienen por qué estar ordenadas estocásticamente. Afortunadamente, para el orden creciente convexo existen las conocidas condiciones de Karlin-Novikov que siempre se pueden verificar, ya que se establecen en términos de los puntos de corte entre las funciones de supervivencia, cuantiles o de densidad. Nuestro principal objetivo es continuar esta línea de investigación para algunos de los órdenes más importantes en la literatura: el vida media residual, el total time on test transform, el excess wealth y el expected proportional shortfall. En detalle, lo que hacemos es estudiar condiciones suficientes para estos criterios en aquellas situaciones en las que no se verifican los órdenes más fuertes (el razón de fallo, el estocástico, el dispersivo y el estrella). Menos el estocástico, como ya hemos mencionado, estos criterios más fuertes están definidos en términos de la monotonía del cociente (o la diferencia) de las funciones de supervivencia (o cuantiles). Nuestro objetivo es establecer condiciones suficientes para los criterios mencionados en términos de los extremos relativos de dichas funciones, lo cuál es menos restrictivo que la monotonía de las mismas. Otro logro es la ordenación de distintas familias paramétricas conocidas de interés en fiabilidad, riesgos y economía, las cuáles se ordenan aplicando los distintos resultados establecidos en la tesis. Por otro lado, la comparación estocástica de datos ordenados es también un área de investigación importante dentro de este tópico y establecemos varios resultados en esta línea. Por último, trabajamos en los órdenes estocásticos conjuntos. Estos criterios tienen en cuenta la estructura de dependencia entre las variables, lo cuál es de interés, por ejemplo, en situaciones en las que se quieren comparar los tiempos de vida de dos individuos o mecanismos que envejecen en el mismo ambiente y además dependen de dicho ambiente. También hacemos aportaciones en este área. / One of the main objectives of statistics is the comparison of random quantities. These comparisons are mainly based on measures associated to these random quantities, like the means, medians or variances. In some situations, the comparisons based only on two single measures are not very informative. The necessity of providing more elaborate comparisons of two random quantities has motivated the development of the theory of the stochastic orders. This theory is composed of different criteria which compare different characteristics measured by several functions of interest in reliability, risks and economy. Such functions are defined in terms of certain incomplete integrals of the survival or quantile functions. Unfortunately, these integrals can not be given in an explicit way in most cases, therefore we can not check directly these orders by their definitions. Even though we can verify some stronger orders or conditions, there are lots of cases which are not covered by any tool in the literature. Due to this fact, one of the main direction of research on this topic is the exploration of sufficient conditions, easy to verify, for these orders when the strongest ones do not hold. For instance, the well-known increasing convex order holds when the incomplete integrals of the survival functions are ordered. However, there are loads of situations where this integrals do not have analytical expression, which makes difficult to verify the order. In this case, we can check the stochastic order, since it is widely known that it is the strongest order to compare location and holds when the survival functions are ordered, which is a simple condition to verify, as long as the survival functions have an explicit expression; but also if this does not occurs, there exists a sufficient condition in terms of the density functions. However, there are lots of situations where the random variables are not ordered in the stochastic order. Luckily, to check the increasing convex order in this cases, there exist the renowned Karlin-Novikov conditions established in terms of the crossing among the survival, quantile and density functions, therefore these conditions can be always verified. Our main purpose in this thesis is to continue this line of research for some of the main orders in the literature: the mean residual life, the total time on test transform, the excess wealth and the expected proportional shortfall order. Down to the last detail, we consider the situation where the strongest orders are not verified (the hazard rate, the stochastic, the dispersive and the star shaped orders, respectively), which are mainly defined in terms of the monotonicity of the ratio (or the difference) of the survival or the quantile functions. We seek an intermediate condition between the strongest order and the corresponding weaker order. Principally, we consider the situations where they have a relative extreme, a property less restrictive than being monotone, to establish several sets of sufficient conditions. Furthermore, a relevant goal of this thesis is to apply the provided results to order several well-known parametric families, which have particular interest to fit data in reliability, risks and economy. The stochastic comparison of ordered data is another of the most important areas of research in this topic and we also provide some results in this direction. Finally, we work on the joint stochastic orders, which take into account the dependence structure among the random variables. This is of interest, for example, if we are interested in comparing two units which are aging in the same environment and both depend on this environment. We also provide some contributions to this area.

Resum pendent