No description available.

Es presenta una experiència de modelització realitzada en alumnes de primers cursos d'enginyeria tècnica. La investigació neix arran de la insatisfacció proporcionada per l'ensenyament tradicional de les matemàtiques. En concret la manca d'aplicacions en els currículums de matemàtiques i l'excessiu formalisme.En aquest context, s'analitza l'evolució del procés d'aprenentatge d'un grup d'alumnes sotmesos a experiències de modelatge. L'experiència, desenvolupada a l'Escola Universitària Politècnica de Vilanova i la Geltrú (UPC), es concreta en el disseny i aplicació del que anomenem unitats didàctiques i projectes. Les unitats didàctiques són treballs dirigits i desenvolupats a les aules, siguent els projectes activitats desenvolupades fóra de les aules i una component important de recerca per part de l'alumne.La tesi planteja una articulació del contingut de la matemàtica que afavoreixi la perspectiva interdisciplinària i el pensament creatiu, utilitzant i descobrint coneixements matemàtics fonamentals per a un enginyer, mitjançant el plantejament de problemes reals. També implica un canvi substancial en la metodologia, que adquireix una vessant heurística alhora que fa servir tècniques de modelatge matemàtic, utilitza nous recursos i replanteja els processos d'avaluació. Es demostra que la metodologia es una eina d'aprenentatge eficient, els alumnes aprenen d'una manera dirigida i espontània, veuen la utilitat del que aprenen i els estudiants adquireixen una actitud creativa. La metodologia pressuposa un canvi fonamental en la concepció del rol del professor i del seu perfil formatiu, i la preparació conceptual i emergent de material. / We present a modelling experience developed with first year students of technical engineering. Our investigation is motivated by the unsatisfactory state of affairs produced by the traditional way of teaching mathematics, namely the lack of applications and the excessive level of formalism. In this context, we analyse the learning process of a group of students exposed to modelling experiences.The work, developed at the Escola Universitària Politècnica de Vilanova i la Geltrú of the Universitat Politècnica de Catalunya, consists in the design and implementation of what we call didactic units and projects. The didactic units are exercises supervised and performed in the classroom, while the projects are developed outside the classroom and imply an important level of research activity for the student.This thesis presents a proposal for the teaching of mathematics directed to the interdisciplinary work and the creative thought, using and discovering the mathematical contents that are most fundamental for an engineer, analysing real life problems. It implies a substantial change in methodology, using more heuristic reasoning and mathematical modelling techniques, taking advantage of the new resources available today and rethinking the evaluation process.We show that our methodology is an efficient learning tool: the students learn in a natural way, realise the usefulness of what they learn and develop a creative attitude. The methodology requires a fundamental change in the role of the instructor and his formative career, and the conceptual and continuously evolving preparation of the teaching materials.

Different types of regulated grammars have been introduced in order to supplement shortcomings of context-free grammars in applications preserving their elegant mathematical properties. However, the rapid developments in present day industry, biology, and other areas challenge to deal with various tasks which need suitable tools for their modelling and investigation. We propose Petri net controlled grammars as models for representing and analyzing of metabolic pathways in living cells where Petri nets are responsible for the structure and communication of the pathways, and grammars represent biochemical processes. On the other hand, the control by Petri nets has also theoretical interest: it extends possibilities to introduce and investigate concurrent control mechanisms in formal language theory. The thesis introduces various variants of Petri net controlled grammars using different types of Petri nets and investigates their mathematical properties such as computational power and closure properties. / Los diferentes tipos de gramáticas con reescritura regulada han sido introducidas para complementar las deficiencias de las gramáticas libres del contexto en las aplicaciones, preservando sus propiedades matemáticas. Por otro lado, la rápida evolución la biología, y otras áreas actuales supone un reto para tratar de las tareas varias que necesitan las herramientas adecuadas para la elaboración de modelos e investigación. Proponemos gramáticas controladas por redes de Petri como modelos para representar y analizar los procesos bioquímicos en las células vivas donde redes de Petri son responsables de la estructura, y gramáticas representan los procesos generativos. Además, el control de redes de Petri también tiene interés teórico: amplía las posibilidades de investigar los mecanismos de control concurrente en la teoría de lenguajes formales. La tesis presenta distintas variantes de gramáticas controladas por redes de Petri e investiga sus propiedades matemáticas.

One of the main challenges in Robotics is to develop robots that can interact with humans in a natural way, sharing the same dynamic and unstructured environments. Such an interaction may be aimed at assisting, helping or collaborating with a human user. To achieve this, the robot must be endowed with a cognitive system that allows it not only to learn new skills from its human partner, but also to refine or improve those already learned. In this context, learning from demonstration appears as a natural and userfriendly way to transfer knowledge from humans to robots. This dissertation addresses such a topic and its application to an unexplored field, namely force-based manipulation tasks learning. In this kind of scenarios, force signals can convey data about the stiffness of a given object, the inertial components acting on a tool, a desired force profile to be reached, etc. Therefore, if the user wants the robot to learn a manipulation skill successfully, it is essential that its cognitive system is able to deal with force perceptions. The first issue this thesis tackles is to extract the input information that is relevant for learning the task at hand, which is also known as the what to imitate? problem. Here, the proposed solution takes into consideration that the robot actions are a function of sensory signals, in other words the importance of each perception is assessed through its correlation with the robot movements. A Mutual Information analysis is used for selecting the most relevant inputs according to their influence on the output space. In this way, the robot can gather all the information coming from its sensory system, and the perception selection module proposed here automatically chooses the data the robot needs to learn a given task. Having selected the relevant input information for the task, it is necessary to represent the human demonstrations in a compact way, encoding the relevant characteristics of the data, for instance, sequential information, uncertainty, constraints, etc. This issue is the next problem addressed in this thesis. Here, a probabilistic learning framework based on hidden Markov models and Gaussian mixture regression is proposed for learning force-based manipulation skills. The outstanding features of such a framework are: (i) it is able to deal with the noise and uncertainty of force signals because of its probabilistic formulation, (ii) it exploits the sequential information embedded in the model for managing perceptual aliasing and time discrepancies, and (iii) it takes advantage of task variables to encode those force-based skills where the robot actions are modulated by an external parameter. Therefore, the resulting learning structure is able to robustly encode and reproduce different manipulation tasks. After, this thesis goes a step forward by proposing a novel whole framework for learning impedance-based behaviors from demonstrations. The key aspects here are that this new structure merges vision and force information for encoding the data compactly, and it allows the robot to have different behaviors by shaping its compliance level over the course of the task. This is achieved by a parametric probabilistic model, whose Gaussian components are the basis of a statistical dynamical system that governs the robot motion. From the force perceptions, the stiffness of the springs composing such a system are estimated, allowing the robot to shape its compliance. This approach permits to extend the learning paradigm to other fields different from the common trajectory following. The proposed frameworks are tested in three scenarios, namely, (a) the ball-in-box task, (b) drink pouring, and (c) a collaborative assembly, where the experimental results evidence the importance of using force perceptions as well as the usefulness and strengths of the methods.

Even though the transition to turbulence has been studied for over a century, its complete comprehension still remains unclear even for the simplest flows and continues to be a daunting challenge for the scientific community. Among these, there is the transition from the von K\'arm\'an vortex street to turbulent wakes. The complexity of this problem poses a series of difficulties that leaves little room for manoeuvre, so other ways to tackle this question have to be sought. A reasonable option is the analysis of the instability phenomena that other flows with the same symmetry group undergo. Despite being really different, an example of such flow is the one generated in a cylindrical cavity subjected to an oscillatory shear. The purpose of the present thesis has been to provide a deeper understanding of the mechanisms that are responsible for the transition in oscillatory cylindrical cavities. Besides the potential implications of studying such systems for the transitions in wake flows, the system under consideration might be useful for any investigation involving a periodic forcing. Accurate spectral computations of the incompressible Navier-Stokes equations have been combined with equivariant bifurcation and normal form theories in an attempt to achieve our goal from different, yet complementary, perspectives. The utilisation of these techniques has produced positive results in the field under consideration. The linear stability analysis has resulted in three types of different bifurcations expected by normal form theory and previous results. The evolution in time of these bifurcating modes yield the non-linear saturated states, which can be synchronous with the forcing or acquire an additional frequency (quasiperiodic). Furthermore, the exploration of regions where two synchronous modes become unstable at the same time, has provided a wide variety of novel states that are not necessarily synchronous. The description of these phenomena via bifurcation theory and dynamical systems techniques is in accordance with the numerical simulations, despite not having an absolute quantitative agreement between them. The research focused on the study of viscoelastic fluids in periodically driven cylindrical cavities is a natural extension of the main topic of this thesis. Although this part has to be considered in a preliminary stage, there are some evidences suggesting that the system is always linearly stable and the only possibility to break the basic state is via a subcritical finite-amplitude bifurcation. The transition recalls in a great deal the instabilities in Newtonian plane Couette and pipe Poiseuille, thus resulting in a much more difficult instability scenario that the one that was initially expected. / Encara que la transició a la turbulència s'ha estat estudiant durant més d'un segle, la comprensió completa d'aquesta, encara roman poc clara ,fins i tot en els fluxos més senzills, i contínua sent un repte d'enormes proporcions per a la comunitat científica. La complexitat d'aquest problema planteja una sèrie de dificultats que deixen poc marge de maniobra i, per tant, s'han de cercar altres mètodes per atacar aquesta qüestió. Una opció molt raonable és l'anàlisi dels fenòmens d'inestabilitats en altres sistemes amb el mateix grup de simetries. Malgrat ser molt diferents, un exemple d'aquest tipus de flux seria el que es genera en una cavitat cilíndrica sotmesa a un esforç de cisalla oscil·latori. L'objectiu de la present tesi ha estat proporcionar un coneixement més profund dels mecanismes responsables en la transició en cavitats cilíndriques. Deixant de banda les possibles implicacions d'estudiar aquests sistemes pel que fa a les transicions dels fluxos en les esteles, el sistema que s'està considerant pot resultar útil en qualsevol investigació que involucri un forçament periòdic. En un intent d'arribar a bon port des de diferents punts de vista, càlculs espectrals precisos de les equacions de Navier-Stokes s'han combinat amb la teoria de formes normals. La utilització f'aquestes tècniques ha produït resultats positius en aquest camp. L'anàlisi d'estabilitat lineal ha revelat tres tipus diferents de bifurcacions, les quals s'esperaven a causa de la teoria de formes normals i resultats anteriors. L'evolució temporal d'aquests modes que bifurquen han proporcionar estats saturats no-lineals, els quals poden ser síncrons amb el forçament o poden adquirir una freqüència addicional (quasiperiòdic). A més a més, l'exploració de les regions on dos modes síncrons esdevenen inestables a la vegada, ha proporcionat una gran varietat de nous estats que no han de ser necessàriament síncrons. La descripció d'aquest fenomen per mitjà de la teoria de bifurcacions i les tècniques de sistemes dinàmics, es troben en acord amb les simulacions numèriques, malgrat que no hi ha una concordància absoluta entre ells. La recerca focalitzada en l'estudi de fluids viscoelàstics en cavitats cilíndriques forçades perioòdicament, és una extensió natural de la temàtica principal d'aquesta tesi. Tot i que aquesta part ha de ser considerada com un estudi preliminar, hi ha algunes evidències que suggereixen que el sistema és sempre linealment estable i l'única manera de desestabilitzar l'estat bàsic és per mitjà d'una bifurcació subcrítica d'amplitud finita. La transició ens recorda en gran mesura el cas de les inestabilitats en el Couette pla i el Poiseuille cilíndric de fluids Newtonian, obtenint així un escenari per la transició molt més difícil dels que ens esperàvem.

Quantum mechanics was developed as a response to the inadequacy of classical physics in explaining certain physical phenomena. While it has proved immensely successful, it also presents several features that severely challenge our classicality based intuition. Randomness in quantum theory is one such and is the central theme of this dissertation. Randomness is a notion we have an intuitive grasp on since it appears to abound in nature. It a icts weather systems and nancial markets and is explicitly used in sport and gambling. It is used in a wide range of scienti c applications such as the simulation of genetic drift, population dynamics and molecular motion in fluids. Randomness (or the lack of it) is also central to philosophical concerns such as the existence of free will and anthropocentric notions of ethics and morality. The conception of randomness has evolved dramatically along with physical theory. While all randomness in classical theory can be fully attributed to a lack of knowledge of the observer, quantum theory qualitatively departs by allowing the existence of objective or intrinsic randomness. It is now known that intrinsic randomness is a generic feature of hypothetical theories larger than quantum theory called the non-signalling theories. They are usually studied with regards to a potential future completion of quantum mechanics or from the perspective of recognizing new physical principles describing nature. While several aspects have been studied to date, there has been little work in globally characterizing and quantifying randomness in quantum and non-signalling theories and the relationship between them. This dissertation is an attempt to ll this gap. Beginning with the unavoidable assumption of a weak source of randomness in the universe, we characterize upper bounds on quantum and non-signalling randomness. We develop a simple symmetry argument that helps identify maximal randomness in quantum theory and demonstrate its use in several explicit examples. Furthermore, we show that maximal randomness is forbidden within general non-signalling theories and constitutes a quantitative departure from quantum theory. We next address (what was) an open question about randomness ampli cation. It is known that a single source of randomness cannot be ampli ed using classical resources alone. We show that using quantum resources on the other hand allows a full ampli cation of the weakest sources of randomness to maximal randomness even in the presence of supra-quantum adversaries. The signi cance of this result spans practical cryptographic scenarios as well as foundational concerns. It demonstrates that conditional on the smallest set of assumptions, the existence of the weakest randomness in the universe guarantees the existence of maximal randomness. The next question we address is the quanti cation of intrinsic randomness in non-signalling correlations. While this is intractable in general, we identify cases where this can be quanti ed. We nd that in these cases all observed randomness is intrinsic even relaxing the measurement independence assumption. We nally turn to the study of the only known resource that allows generating certi able intrinsic randomness in the laboratory i.e. entanglement. We address noisy quantum systems and calculate their entanglement dynamics under decoherence. We identify exact results for several realistic noise models and provide tight bounds in some other cases. We conclude by putting our results into perspective, pointing out some drawbacks and future avenues of work in addressing these concerns.

The thesis deals with the theoretical and practical study of mathematical programming methodologies to the analysis complex networks and their application in economic and social problems. More specifically, it applies models and methods for solving linear and integer programming problems to network models exploiting the matrix structure of such models, resulting in efficient computational procedures and small processing time. As a consequence, it allows the study of larger and more complex networks models that arise in many economical and sociological applications. The main efforts have been addressed to the development of a rigorous mathematical programming based framework, which is able to capture many classes of complex network problems. Such a framework involves a general and flexible modeling approach, based on linear and integer programmin, as well as a collection of efficient probabilistic procedures to deal with these models. The computer implementation has been carried out by high level programming languages, such as Java, MatLab, R and AMPL. The final chapter of the thesis introduced an extension of the analyzed model to the case of microeconomic interaction, providing a fruitful mathematical linkage between its optimization-like properties and its multi-agents properties. The theoretical and practical use of optimization methods represents the trait-de-union of the different chapters. The overall structure of the thesis manuscript contains three parts: Part I: The fine-grained structure of complex networks: theories, models and methods; Chapter 1 and Chapter 2. Part II: Mathematical Programming based approaches for random models of network formation; Chapter 3, Chapter 4 and Chapter 5. Part III: Strategic models of network formation. Chapter 6. Results of this research have generated four working papers in quality scientific journals: one has been accepted and three are under review. Some results have been also presented in four international conferences. / La tesis aborda el estudio teórico y práctico de las metodologías de programación matemática para el análisis de redes complejas y su aplicación a problemas económicos y sociales. Más específicamente, se aplica modelos y métodos para resolver problemas de programación lineal y de programación lineal entera explotando las estructuras matriciales de tales modelos, lo que resulta en procedimientos computacionales eficientes y bajo coste de procesamiento. Como consecuencia de ello, las metodologías propuestas permiten el estudio de modelos complejos de gran dimensión, para redes complejas que surgen en muchas aplicaciones económicas y sociológicas. Los principales esfuerzos se han dirigido al desarrollo de un marco teórico basado en la programación matemática, que es capaz de capturar muchas clases de problemas de redes complejas. Dicho marco teórico envuelve un sistema general y flexible de modelado y una colección de procedimientos probabilísticos para solucionar eficientemente dichos modelos, basados en la programación linear y entera. Las implementaciones informáticas se han llevado a cabo mediante lenguajes de programación de alto nivel, como Java, Matlab, R y AMPL. El último capítulo de la tesis introduce una extensión de los modelos analizados, para el caso de la interacción microeconómica, con el objetivo de establecer un nexo metodológico entre sus propiedades de optimización y sus propiedades multi-agentes. El uso teórico y práctico de los métodos de optimización representa el elemento de conjunción de los distintos capítulos. Parte I: The fine-grained structure of complex networks: theories, models and methods; - Capitulo 1 y Capitulo 2. Parte II: Mathematical Programming based approaches for random models of network formation; - Capitulo 3, Capitulo 4 y Capitulo 5. Parte III: Strategic models of network formation. - Capitulo 6. Los resultados de esta investigación han generado cuatro papers en revistas científicas indexadas: uno ha sido aceptado, tres están en revisión. Algunos resultados han sido también presentados en cuatro conferencias internacionales

This thesis aims at developing numerical methods based on level-set techniques suitable for the direct numerical simulation (DNS) of free surface and interfacial flows, in order to be used on basic research and industrial applications. First, the conservative level-set method for capturing the interface between two fluids is combined with a variable density projection scheme in order to simulate incompressible two-phase flows on unstructured meshes. All equations are discretized by using a finite-volume approximation on a collocated grid arrangement. A high order scheme based on a flux limiter formulation, is adopted for approximating the convective terms, while the diffusive fluxes are centrally differenced. Gradients are computed by the least-squares approach, whereas physical properties are assumed to vary smoothly in a narrow band around the interface to avoid numerical instabilities. Surface tension force is calculated according to the continuous surface force approach. The numerical method is validated against experimental and numerical data reported in the scientific literature. Second, the conservative level-set method is applied to study the gravity-driven bubbly flow. Unlike the cases presented in the first part, a periodic boundary condition is applied in the vertical direction, in order to mimic a channel of infinite length. The shape and terminal velocity of a single bubble which rises in a quiescent liquid are calculated and validated against experimental results reported in the literature. In addition, different initial arrangements of bubble pairs were considered to study its hydrodynamic interaction, and, finally the interaction of multiple bubbles is explored in a periodic vertical duct, allowing their coalescence. In the third part of this thesis, a new methodology is presented for simulation of surface-tension-driven interfacial flows by combining volume-of-fluid with level-set methods. The main idea is to benefit from the advantage of each strategy, which is to minimize mass loss through the volume-of-fluid method, and to keep a fine description of the interface curvature using a level-set function. With the information of the interface given by the volume-of-fluid method, a signed distance function is reconstructed following an iterative geometric algorithm, which is used to compute surface tension force. This numerical method is validated on 2D and 3D test cases well known in the scientific literature. The simulations reveal that numerical schemes afford qualitatively similar results to those obtained by the conservative level-set method. Mass conservation is shown to be excellent, while geometrical accuracy remains satisfactory even for the most complex cases involving topology changes. In the fourth part of the thesis a novel multiple marker level-set method is presented. This method is deployed to perform numerical simulation of deformable fluid particles without numerical coalescence of their interfaces, which is a problem inherent to standard interface tracking methodologies (e.g. level-set and volume of fluid). Each fluid particle is described by a separate level-set function, thus, different interfaces can be solved in the same control volume, avoiding artificial and potentially unphysical coalescence of fluid particles. Therefore, bubbles or droplets are able to approach each other closely, within the size of one grid cell, and can even collide. The proposed algorithm is developed in the context of the conservative levelset method, whereas, surface tension is modeled by the continuous surface force approach. The pressure-velocity coupling is solved by the fractional-step projection method. For validation of the proposed numerical method, the gravity-driven impact of a droplet on a liquid-liquid interface is studied; then, the binary droplet collision with bouncing outcome is examined, and finally, it is applied on simulation of gravity-driven bubbly flow in a vertical column. The study of these cases contributed to shed some light into physics present in bubble and droplet flows. / Ésta tesis se enfoca en el desarrollo de métodos numéricos basados en la aplicación de técnicas level-set para la Simulación Numérica Directa (DNS) de flujos interfaciales y flujos de superficie libre, con el objetivo de ser usados tanto en investigación básica como en aplicaciones industriales. Primero, el método level-set conservativo desarrollado para la captura de interfaces entre dos fluidos, es combinado con un esquema de proyección adaptado para un fluido de densidad variable, con el objetivo de simular flujos de dos fases en mallas no estructuradas. Todas las ecuaciones son discretizadas mediante una aproximación de volúmenes finitos sobre un arreglo de malla colocada. Un esquema de alto orden cuya formulación se basa en el uso de limitadores de flujo, es usado para la discretización de los términos convectivos, mientras que los flujos difusivos son calculados mediante diferencias centradas. Los gradientes son calculados mediante el método de los mínimos cuadrados, en tanto que se asume que las propiedades físicas varían suavemente en una zona estrecha alrededor de la interface con el objetivo de evitar inestabilidades numéricas. La tensión superficial es incorporada mediante el enfoque de la fuerza superficial continua. El método numérico es validado con respecto a los datos experimentales y numéricos reportados en la literatura científica. Segundo, el método level-set conservativo es aplicado en el estudio del flujo de burbujas conducidas por la gravedad. A diferencia de los casos precedentes, se aplica una condición de frontera periódica en la dirección vertical, con el objetivo de simular un canal de longitud infinita. La forma y velocidad terminal de una burbuja ascenciendo en un líquido inicialmente en reposo son calculadas y contrastadas con los resultados reportados en la literatura. Adicionalmente se estudia la interacción hidrodinámica de un par de burbujas para diferentes configuraciones, y finalmente se explora la interacción de un emjambre de burbujas ascendiendo en un canal vertical. En la tercera parte de ésta tesis, se presenta una nueva metodología para la simulación de flujos interfaciales conducidos por la tensión superficial, mediante la combinación de los métodos volume-of-fluid y level-set. La idea principal se basa en usar el método volume-of-fluid para advectar la interface, minimizando las pérdidas de masa, mientras que las propiedades geométricas de la interface se calculan a partir de una función level-set obtenida mediante un algoritmo geométrico iterativo. La propiedades geométricas así calculadas son usadas para el cómputo de la tensión superficial. El método numérico es validado mediante casos bi y tri-dimensionales bien conocidos en la literatura científica. La conservación de la masa es excelente en tanto que la precisión del método es altamente satisfactoria incluso en los casos más complejos. En la cuarta parte de ésta tesis se presenta un nuevo método level-set de múltiples marcadores. Éste método es diseñado para llevar a cabo simulaciones numéricas de partículas de fluido deformables, evitando la coalescencia numérica de las interfaces. Cada partícula de fluido es capturada por una función level-set distinta, así, diferentes interfaces pueden ser resueltas en el mismo volumen de control, evitando la coalescencia artificial y potencialmente no-física de las partículas fluidas. Por lo tanto, las burbujas (o gotas) pueden acercarce y colisionar. El algoritmo es propuesto en el contexto del método level-set conservativo, mientras que la tensión superficial se resuelve mediante una adaptación del enfoque de la fuerza superficial continua. Para su validación, se estudia el impacto conducido por la gravedad de una gota sobre una interface líquido-líquido; luego, se estudia la collisión de dos gotas con salida rebotante, y finalmente el método numérico es aplicado para la simulación de un enjambre de burbujas sin coalescencia numérica.

Term unification is a basic operation in several areas of computer science, specially in those related to logic. Generally speaking, it consists on solving equations over expressions called terms. Depending on the kind of variables allowed to occur in the terms and under which conditions two terms are considered to be equal, several frameworks of unification such as first-order unification, higher-order unification, syntactic unification, and unification modulo theories can be distinguished. Moreover, other variants of term unification arise when we consider nontrivial representations for terms. In this thesis we study variants of the classic first-order syntactic term unification problem resulting from the introduction of context variables, i.e. variables standing for contexts, and/or assuming that the input is given in some kind of compressed representation. More specifically, we focus on two of such compressed representations: the well-known Directed Acyclic Graphs (DAGs) and Singleton Tree Grammars (STGs). Similarly as DAGs allow compression by exploiting the reusement of repeated instances of a subterm in a term, STGs are a grammar-based compression mechanism based on the reusement of repeated (multi)contexts. An interesting property of the STG formalism is that many operations on terms can be efficiently performed directly in their compressed representation thus taking advantage of the compression also when computing with the represented terms. Although finding a minimal STG representation of a term is computationally difficult, this limitation has been successfully overcome is practice, and several STG-compressors for terms are available. The STG representation has been applied in XML processing and analysis of Term Rewrite Systems. Moreover, STGs are a very useful concept for the analysis of unification problems since, roughly speaking, allow to represent solutions in a succinct but still efficiently verifiable form. / La unificació de termes és una operación básica en diverses àrees de la informática, especialment en aquelles relacionades amb la lógica. En termes generals, consisteix en resoldre equacions sobre expressions anomenades termes. Depenent del tipus de variables que apareguin en els termes i de sota quines condicions dos termes són considerats iguals, podem definir diverses variants del problema d'unificació de termes. A més a més, altres variants del problema d'unificació de termes sorgeixen quan considerem representacions no trivials per als termes. S'estudia variants del problema clàssic d'unificació sintáctica de primer ordre resultants de la introducció de variables de context i/o de l'assumpció de que l'entrada és donada en format comprimit. Ens centrem en l'estudi de dues representacions comprimides: els grafs dirigits acíclics i les gramàtiques d'arbre singletó. Similarment a com els grafs dirigits acíclics permeten compressió mitjançant el reús d'instàncies repetides d'un mateix subterme, les gramàtiques d'arbres singletó són un sistema de compressió basat en el reús de (multi)contexts. Una propietat interessant d'aquest formalisme és que moltes de les operacions comuns sobre termes es poden realizar directament sobre la versió comprimida d'aquests de forma eficient, sense cap mena de descompressió prèvia. Tot i que trobar una representació minimal d'un terme amb una gramática singletó és una tasca computacionalment difícil, aquesta limitació ha estat resolta de forma satisfactòria en la pràctica, hi ha disponibles diversos compressors per a termes. La representació de termes amb gramàtiques singletó ha estat útil per al processament de documents XML i l'anàlisi de sistemes de reescriptura de termes. Les gramàtiques singletó són concepte molt útil per a l'anàlisi de problemas d'unificació, ja que permeten representar solucions de forma comprimida sense renunciar a que puguin ser verificades de forma eficient. A la primera part d'aquesta tesi s'estudien els problemas d'unificació i matching de primer ordre sota l'assumpció de que els termes de l'entrada són representats fent servir gramàtiques singletó. Presentem algorismes de temps polinòmic per a aquests problemas, així com propostes d'implementacions i resultats experimentals. Aquests resultats s'utilitzen més endevant en aquesta tesi per a l'anàlisi de problemes d'unificació i matching amb variables de contexte i entrada comprimida. A la resta d'aquesta tesi ens centrem en variants d'unificació amb variables de contexte, que són un cas particular de variables d'ordre superior. Més concretament, a la segona part d'aquesta tesi, ens centrem en un cas particular d'unificació de contextes on nomès es permet una sola variable de context en l'entrada. Aquest problema s'anomena "one context unification". Mostrem que aquest problema es pot resoldre en temps polinòmic indeterminista, no només quan els termes de l'entrada són representats de forma explícita, sino també quan es representen fent servir grafs dirigits acíclics i gramàtiques singletó. També presentem un resultat parcial recent en la tasca de trobar un algorisme de temps polinòmic per a one context unification. Al final de la tesi, estudiem el problema de matching per a entrades amb variables de contexte, que és un cas particular d'unificació on només un dels dos termes de cada equació té variables. En contrast amb el problema general, matching de contextes ha estat classificat com a problema NP-complet. Mostrem que matching de contextes és NP-complet fins i tot quan es fan servir gramàtiques com a formalisme de representació de termes. Això implica que afegir compressió no ens porta a un augment dràstic de la complexitat del problema. També demostrem que la restricció de matching de contextes on el nombre de variables de contexte està afitat per una constant fixa del problema es pot resoldre en temps polinòmic, fins i tot quan es fan servir grafs dirigits acíclics com formalisme de representació de termes

En aquesta tesi presentem una metodologia sistemàtica la qual permet caracteritzar sistemes biològics dinàmics a partir de dades de series temporals. Del treball desenvolupat se’n desprenen tres publicacions. En la primera desenvolupem un mètode d’optimització global determinista basat en l’outer approximation per a la estimació de paràmetres en sistemes biològics dinàmics. El nostre mètode es basa en la reformulació d’un conjunt d’equacions diferencials ordinàries al seu equivalent algebraic mitjançant l’ús de mètodes de col•locació ortogonal, donant lloc a un problema no convex programació no lineal (NLP). Aquest problema no convex NLP es descompon en dos nivells jeràrquics: un problema master de programació entera mixta (MILP) que proporciona una cota inferior rigorosa al solució global, i una NLP esclau d’espai reduït que dóna un límit superior. L’algorisme itera entre aquests dos nivells fins que un criteri de terminació es satisfà. En les publicacions segona i tercera vam desenvolupar un mètode que és capaç d’identificar l’estructura regulatòria amb els corresponents paràmetres cinètics a partir de dades de series temporals. En la segona publicació vam definir un problema d’optimització dinàmica entera mixta (MIDO) on minimitzem el criteri d’informació d’Akaike. En la tercera publicació vam adoptar una perspectiva MIDO multicriteri on minimitzem l’ajust i complexitat simultàniament mitjançant el mètode de l’epsilon constraint on un dels objectius es tracta com la funció objectiu mentre que la resta es converteixen en restriccions auxiliars. En ambdues publicacions els problemes MIDO es reformulen a programació entera mixta no lineal (MINLP) mitjançant la col•locació ortogonal en elements finits on les variables binàries s’utilitzem per modelar l’existència d’interaccions regulatòries. / En esta tesis presentamos una metodología sistemática que permite caracterizar sistemas biológicos dinámicos a partir de datos de series temporales. Del trabajo desarrollado se desprenden tres publicaciones. En la primera desarrollamos un método de optimización global determinista basado en el outer approximation para la estimación de parámetros en sistemas biológicos dinámicos. Nuestro método se basa en la reformulación de un conjunto de ecuaciones diferenciales ordinarias a su equivalente algebraico mediante el uso de métodos de colocación ortogonal, dando lugar a un problema no convexo de programación no lineal (NLP). Este problema no convexo NLP se descompone en dos niveles jerárquicos: un problema master de programación entera mixta (MILP) que proporciona una cota inferior rigurosa al solución global, y una NLP esclavo de espacio reducido que da un límite superior. El algoritmo itera entre estos dos niveles hasta que un criterio de terminación se satisface. En las publicaciones segunda y tercera desarrollamos un método que es capaz de identificar la estructura regulatoria con los correspondientes parámetros cinéticos a partir de datos de series temporales. En la segunda publicación definimos un problema de optimización dinámica entera mixta (MIDO) donde minimizamos el criterio de información de Akaike. En la tercera publicación adoptamos una perspectiva MIDO multicriterio donde minimizamos el ajuste y complejidad simultáneamente mediante el método del epsilon constraint donde uno de los objetivos se trata como la función objetivo mientras que el resto se convierten en restricciones auxiliares. En ambas publicaciones los problemas MIDO se reformulan a programación entera mixta no lineal (MINLP) mediante la colocación ortogonal en elementos finitos donde las variables binarias se utilizan para modelar la existencia de interacciones regulatorias. / In this thesis we present a systematic methodology to characterize dynamic biological systems from time series data. From the work we derived three publications. In the first we developed a deterministic global optimization method based on the outer approximation for parameter estimation in dynamic biological systems. Our method is based on reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. In the second and third publications we developed a method that is able to identify the regulatory structure and its corresponding kinetic parameters from time series data. In the second publication we defined a mixed integer dynamic optimization problem (MIDO) which minimize the Akaike information criterion. In the third publication, we adopted a multi-criteria MIDO which minimize complexity and fit simultaneously using the epsilon constraint method in which one objective is treated as the objective function while the rest are converted to auxiliary constraints. In both publications MIDO problems were reformulated to mixed integer nonlinear programming (MINLP) through the use of orthogonal collocation on finite elements where binary variables are used to model the existence of regulatory interactions.