Métodos numéricos para resolução de equações diferenciais ordinárias lineares baseados em interpolação por spline

In this work we have elaborated a spline-based method of solution of inicial value problems involving ordinary differential equations, with emphasis on linear equations. The method can be seen as an alternative for the traditional solvers such as Runge-Kutta, and avoids root calculations in the linear time invariant case. The method is then applied on a central problem of control theory, namely, the step response problem for linear EDOs with possibly varying coefficients, where root calculations do not apply. We have implemented an efficient algorithm which uses exclusively matrix-vector operations. The working interval (till the settling time) was determined through a calculation of the least stable mode using a modified power method. Several variants of the method have been compared by simulation. For general linear problems with fine grid, the proposed method compares favorably with the Euler method. In the time invariant case, where the alternative is root calculation, we have indications that the proposed method is competitive for equations of sifficiently high order.

Modelo numérico do terreno obtido por diferentes métodos em cartas planialtimétricas

The digital elevation model is important to determine the slope and land use capability, therefore, a proposal of methodology for acquisition of elevation data contemplating an efficient algorithm to generate a slope map was developed. Thus, it was aimed to obtain and evaluate a digital elevation model without the vetorization of the contours on planialtimetric charts. The area for acquisition of elevation data was Sao Manuel, SP. The data were collected by two methods: level contour vetorization and the gathering of elevation points on the level contour with maximum elevation points. The elevation data were analyzed by geostatistical techniques. Inspite of wide difference in the number of collected points between two methods, the variograms were adjusted to the exponential model and showed a range of approximately 1500 m, which does not justify the wide difficulty in vetorization of the planialtimetric charts, once the data points collected in the area were appropriately distributed, they represented rightly the terrain surface.

Evolutionary heuristic to determine future land use

In the spatial electric load forecasting, the future land use determination is one of the most important tasks, and one of the most difficult, because of the stochastic nature of the city growth. This paper proposes a fast and efficient algorithm to find out the future land use for the vacant land in the utility service area, using ideas from knowledge extraction and evolutionary algorithms. The methodology was implemented into a full simulation software for spatial electric load forecasting, showing a high rate of success when the results are compared to information gathered from specialists. The importance of this methodology lies in the reduced set of data needed to perform the task and the simplicity for implementation, which is a great plus for most of the electric utilities without specialized tools for this planning activity. © 2008 IEEE.

Tomografia eletromagnética para caracterização de reservatórios de hidrocarbonetos

Na produção de petróleo é importante o monitoramento dos parâmetros do reservatório (permeabilidade, porosidade, saturação, pressão, etc) para o seu posterior gerenciamento. A variação dos parâmetros dinâmicos do reservatório induz variações na dinâmica do fluxo no reservatório, como por exemplo, perdas na pressão, dificultando o processo de extração do óleo. A injeção de fluidos aumenta a energia interna do reservatório e incrementa a pressão, estimulando o movimento do óleo em direção aos poços de extração. A tomografia eletromagnética poço-a-poço pode se tomar em uma técnica bastante eficaz no monitoramento dos processos de injeção, considerando-se o fato de ser altamente detectável a percolação de fluidos condutivos através das rochas. Esta tese apresenta o resultado de um algoritmo de tomografia eletromagnética bastante eficaz aplicado a dados sintéticos. O esquema de imageamento assume uma simetria cilíndrica em torno de uma fonte constituída por um dipolo magnético. Durante o processo de imageamento foram usados 21 transmissores e 21 receptores distribuídos em dois poços distanciados de 100 metros. O problema direto foi resolvido pelo método dos elementos finitos aplicado à equação de Helmhotz do campo elétrico secundário. O algoritmo resultante é válido para qualquer situação, não estando sujeito às restrições impostas aos algoritmos baseados nas aproximações de Born e Rytov. Por isso, pode ser aplicado eficientemente em qualquer situação, como em meios com contrastes de condutividade elétrica variando de 2 a 100, freqüências de 0.1 a 1000.0 kHz e heterogeneidades de qualquer dimensão. O problema inverso foi resolvido por intermédio do algoritmo de Marquardt estabilizado. A solução é obtida iterativamente. Os dados invertidos, com ruído Gaussiano aditivo, são as componentes em fase e em quadratura do campo magnético vertical. Sem o uso de vínculos o problema é totalmente instável, resultando em imagens completamente borradas. Duas categorias de vínculos foram usadas: vínculos relativos, do tipo suavidade, e vínculos absolutos. Os resultados obtidos mostram a eficiência desses dois tipos de vínculos através de imagens nítidas de alta resolução. Os tomogramas mostram que a resolução é melhor na direção vertical do que na horizontal e que é também função da freqüência. A posição e a atitude da heterogeneidade é bem recuperada. Ficou também demonstrado que a baixa resolução horizontal pode ser atenuada ou até mesmo eliminada por intermédio dos vínculos.

Uma abordagem híbrida e semiautomática para estimativa de regiões cobertas por nuvens e sombras em imagens de satélite: análise e avaliação

Os principais objetivos deste trabalho são propor um algoritmo eficiente e o mais automático possível para estimar o que está coberto por regiões de nuvens e sombras em imagens de satélite; e um índice de confiabilidade, que seja aplicado previamente à imagem, visando medir a viabilidade da estimação das regiões cobertas pelos componentes atmosféricos usando tal algoritmo. A motivação vem dos problemas causados por esses elementos, entre eles: dificultam a identificação de objetos de imagem, prejudicam o monitoramento urbano e ambiental, e desfavorecem etapas cruciais do processamento digital de imagens para extrair informações ao usuário, como segmentação e classificação. Através de uma abordagem híbrida, é proposto um método para decompor regiões usando um filtro passa-baixas não-linear de mediana, a fim de mapear as regiões de estrutura (homogêneas), como vegetação, e de textura (heterogêneas), como áreas urbanas, na imagem. Nessas áreas, foram aplicados os métodos de restauração Inpainting por suavização baseado em Transformada Cosseno Discreta (DCT), e Síntese de Textura baseada em modelos, respectivamente. É importante salientar que as técnicas foram modificadas para serem capazes de trabalhar com imagens de características peculiares que são obtidas por meio de sensores de satélite, como por exemplo, as grandes dimensões e a alta variação espectral. Já o índice de confiabilidade, tem como objetivo analisar a imagem que contém as interferências atmosféricas e daí estimar o quão confiável será a redefinição com base no percentual de cobertura de nuvens sobre as regiões de textura e estrutura. Tal índice é composto pela combinação do resultado de algoritmos supervisionados e não-supervisionados envolvendo 3 métricas: Exatidão Global Média (EGM), Medida De Similaridade Estrutural (SSIM) e Confiança Média Dos Pixels (CM). Finalmente, verificou-se a eficácia destas metodologias através de uma avaliação quantitativa (proporcionada pelo índice) e qualitativa (pelas imagens resultantes do processamento), mostrando ser possível a aplicação das técnicas para solucionar os problemas que motivaram a realização deste trabalho.

Estimation of croplands using indicator kriging and fuzzy classification

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Implementation of a non ground meta interpreter for defeasible logic

Human reasoning is a fascinating and complex cognitive process that can be applied in different research areas such as philosophy, psychology, laws and financial. Unfortunately, developing supporting software (to those different areas) able to cope such as complex reasoning it’s difficult and requires a suitable logic abstract formalism. In this thesis we aim to develop a program, that has the job to evaluate a theory (a set of rules) w.r.t. a Goal, and provide some results such as “The Goal is derivable from the KB5 (of the theory)”. In order to achieve this goal we need to analyse different logics and choose the one that best meets our needs. In logic, usually, we try to determine if a given conclusion is logically implied by a set of assumptions T (theory). However, when we deal with programming logic we need an efficient algorithm in order to find such implications. In this work we use a logic rather similar to human logic. Indeed, human reasoning requires an extension of the first order logic able to reach a conclusion depending on not definitely true6 premises belonging to a incomplete set of knowledge. Thus, we implemented a defeasible logic7 framework able to manipulate defeasible rules. Defeasible logic is a non-monotonic logic designed for efficient defeasible reasoning by Nute (see Chapter 2). Those kind of applications are useful in laws area especially if they offer an implementation of an argumentation framework that provides a formal modelling of game. Roughly speaking, let the theory is the set of laws, a keyclaim is the conclusion that one of the party wants to prove (and the other one wants to defeat) and adding dynamic assertion of rules, namely, facts putted forward by the parties, then, we can play an argumentative challenge between two players and decide if the conclusion is provable or not depending on the different strategies performed by the players. Implementing a game model requires one more meta-interpreter able to evaluate the defeasible logic framework; indeed, according to Göedel theorem (see on page 127), we cannot evaluate the meaning of a language using the tools provided by the language itself, but we need a meta-language able to manipulate the object language8. Thus, rather than a simple meta-interpreter, we propose a Meta-level containing different Meta-evaluators. The former has been explained above, the second one is needed to perform the game model, and the last one will be used to change game execution and tree derivation strategies.

Simulations of physics and chemistry of polar stratospheric clouds with a general circulation model

A polar stratospheric cloud submodel has been developed and incorporated in a general circulation model including atmospheric chemistry (ECHAM5/MESSy). The formation and sedimentation of polar stratospheric cloud (PSC) particles can thus be simulated as well as heterogeneous chemical reactions that take place on the PSC particles. For solid PSC particle sedimentation, the need for a tailor-made algorithm has been elucidated. A sedimentation scheme based on first order approximations of vertical mixing ratio profiles has been developed. It produces relatively little numerical diffusion and can deal well with divergent or convergent sedimentation velocity fields. For the determination of solid PSC particle sizes, an efficient algorithm has been adapted. It assumes a monodisperse radii distribution and thermodynamic equilibrium between the gas phase and the solid particle phase. This scheme, though relatively simple, is shown to produce particle number densities and radii within the observed range. The combined effects of the representations of sedimentation and solid PSC particles on vertical H2O and HNO3 redistribution are investigated in a series of tests. The formation of solid PSC particles, especially of those consisting of nitric acid trihydrate, has been discussed extensively in recent years. Three particle formation schemes in accordance with the most widely used approaches have been identified and implemented. For the evaluation of PSC occurrence a new data set with unprecedented spatial and temporal coverage was available. A quantitative method for the comparison of simulation results and observations is developed and applied. It reveals that the relative PSC sighting frequency can be reproduced well with the PSC submodel whereas the detailed modelling of PSC events is beyond the scope of coarse global scale models. In addition to the development and evaluation of new PSC submodel components, parts of existing simulation programs have been improved, e.g. a method for the assimilation of meteorological analysis data in the general circulation model, the liquid PSC particle composition scheme, and the calculation of heterogeneous reaction rate coefficients. The interplay of these model components is demonstrated in a simulation of stratospheric chemistry with the coupled general circulation model. Tests against recent satellite data show that the model successfully reproduces the Antarctic ozone hole.

Exact computation of the adjacency graph of an arrangement of quadrics

Präsentiert wird ein vollständiger, exakter und effizienter Algorithmus zur Berechnung des Nachbarschaftsgraphen eines Arrangements von Quadriken (Algebraische Flächen vom Grad 2). Dies ist ein wichtiger Schritt auf dem Weg zur Berechnung des vollen 3D Arrangements. Dabei greifen wir auf eine bereits existierende Implementierung zur Berechnung der exakten Parametrisierung der Schnittkurve von zwei Quadriken zurück. Somit ist es möglich, die exakten Parameterwerte der Schnittpunkte zu bestimmen, diese entlang der Kurven zu sortieren und den Nachbarschaftsgraphen zu berechnen. Wir bezeichnen unsere Implementierung als vollständig, da sie auch die Behandlung aller Sonderfälle wie singulärer oder tangentialer Schnittpunkte einschließt. Sie ist exakt, da immer das mathematisch korrekte Ergebnis berechnet wird. Und schließlich bezeichnen wir unsere Implementierung als effizient, da sie im Vergleich mit dem einzigen bisher implementierten Ansatz gut abschneidet. Implementiert wurde unser Ansatz im Rahmen des Projektes EXACUS. Das zentrale Ziel von EXACUS ist es, einen Prototypen eines zuverlässigen und leistungsfähigen CAD Geometriekerns zu entwickeln. Obwohl wir das Design unserer Bibliothek als prototypisch bezeichnen, legen wir dennoch größten Wert auf Vollständigkeit, Exaktheit, Effizienz, Dokumentation und Wiederverwendbarkeit. Über den eigentlich Beitrag zu EXACUS hinaus, hatte der hier vorgestellte Ansatz durch seine besonderen Anforderungen auch wesentlichen Einfluss auf grundlegende Teile von EXACUS. Im Besonderen hat diese Arbeit zur generischen Unterstützung der Zahlentypen und der Verwendung modularer Methoden innerhalb von EXACUS beigetragen. Im Rahmen der derzeitigen Integration von EXACUS in CGAL wurden diese Teile bereits erfolgreich in ausgereifte CGAL Pakete weiterentwickelt.

Automatic Deployment of Applications in the Cloud

In distributed systems like clouds or service oriented frameworks, applications are typically assembled by deploying and connecting a large number of heterogeneous software components, spanning from fine-grained packages to coarse-grained complex services. The complexity of such systems requires a rich set of techniques and tools to support the automation of their deployment process. By relying on a formal model of components, a technique is devised for computing the sequence of actions allowing the deployment of a desired configuration. An efficient algorithm, working in polynomial time, is described and proven to be sound and complete. Finally, a prototype tool implementing the proposed algorithm has been developed. Experimental results support the adoption of this novel approach in real life scenarios.

Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.

TRIO LOGIC REGRESSION - DETECTION OF SNP - SNP INTERACTIONS IN CASE-PARENT TRIOS

Statistical approaches to evaluate higher order SNP-SNP and SNP-environment interactions are critical in genetic association studies, as susceptibility to complex disease is likely to be related to the interaction of multiple SNPs and environmental factors. Logic regression (Kooperberg et al., 2001; Ruczinski et al., 2003) is one such approach, where interactions between SNPs and environmental variables are assessed in a regression framework, and interactions become part of the model search space. In this manuscript we extend the logic regression methodology, originally developed for cohort and case-control studies, for studies of trios with affected probands. Trio logic regression accounts for the linkage disequilibrium (LD) structure in the genotype data, and accommodates missing genotypes via haplotype-based imputation. We also derive an efficient algorithm to simulate case-parent trios where genetic risk is determined via epistatic interactions.

Mejora de la calidad de los electrocardiogramas recogidos por terminales móviles

Inicio del desarrollo de un algoritmo eficiente orientado a dispositivos con baja capacidad de proceso, que ayude a personas sin necesariamente una preparación adecuada a llevar a cabo un proceso de toma de una señal biológica, como puede ser un electrocardiograma. La aplicación deberá, por tanto, asesorar en la toma de la señal al usuario, evaluar la calidad de la grabación obtenida, y en tiempo seudo real, comprobar si la calidad de la señal obtenida es suficientemente buena para su posterior diagnóstico, de tal modo que en caso de que sea necesaria una repetición de la prueba médica, esta pueda realizarse de inmediato. Además, el algoritmo debe extraer las características más relevantes de la señal electrocardiográfica, procesarlas, y obtener una serie de patrones significativos que permitan la orientación a la diagnosis de algunas de las patologías más comunes que se puedan extraer de la información de las señales cardíacas. Para la extracción, evaluación y toma de decisiones de este proceso previo a la generación del diagnóstico, se seguirá la arquitectura clásica de un sistema de detección de patrones, definiendo las clases que sean necesarias según el número de patologías que se deseen identificar. Esta información de diagnosis, obtenida mediante la identificación del sistema de reconocimiento de patrones, podría ser de ayuda u orientación para la posterior revisión de la prueba por parte de un profesional médico cualificado y de manera remota, evitando así el desplazamiento del mismo a zonas donde, por los medios existentes a día de hoy, es muy remota la posibilidad de presencia de personal sanitario. ABTRACT Start of development of an efficient algorithm designed to devices with low processing power, which could help people without adequate preparation to undertake a process of taking a biological signal, such as an electrocardiogram. Therefore, the application must assist the user in taking the signal and evaluating the quality of the recording. All of this must to be in live time. It must to check the quality of the signal obtained, and if is it necessary a repetition of the test, this could be done immediately. Furthermore, the algorithm must extract the most relevant features of the ECG signal, process it, and get meaningful patterns that allow to a diagnosis orientation of some of the more common diseases that can be drawn from the cardiac signal information. For the extraction, evaluation and decision making in this previous process to the generation of diagnosis, we will follow the classic architecture of a pattern recognition system, defining the necessary classes according to the number of pathologies that we wish to identify. This diagnostic information obtained by identifying the pattern recognition system could be for help or guidance for further review of the signal by a qualified medical professional, and it could be done remotely, thus avoiding the movements to areas where nowadays it is extremely unlikely to place any health staff, due to the poor economic condition.

Simulación numérica de un problema de contaminación atmosférica

La ecuación en derivadas parciales de advección difusión con reacción química es la base de los modelos de dispersión de contaminantes en la atmósfera, y los diferentes métodos numéricos empleados para su resolución han sido objeto de amplios estudios a lo largo de su desarrollo. En esta Tesis se presenta la implementación de un nuevo método conservativo para la resolución de la parte advectiva de la ecuación en derivadas parciales que modela la dispersión de contaminantes dentro del modelo mesoescalar de transporte químico CHIMERE. Este método está basado en una técnica de volúmenes finitos junto con una interpolación racional. La ventaja de este método es la conservación exacta de la masa transportada debido al empleo de la ley de conservación de masas. Para ello emplea una formulación de flujo basado en el cálculo de la integral ponderada dentro de cada celda definida para la discretización del espacio en el método de volúmenes finitos. Los resultados numéricos obtenidos en las simulaciones realizadas (implementando el modelo conservativo para la advección en el modelo CHIMERE) se han comparado con los datos observados de concentración de contaminantes registrados en la red de estaciones de seguimiento y medición distribuidas por la Península Ibérica. Los datos estadísticos de medición del error, la media normalizada y la media absoluta normalizada del error, presentan valores que están dentro de los rangos propuestos por la EPA para considerar el modelo preciso. Además, se introduce un nuevo método para resolver la parte advectivadifusiva de la ecuación en derivadas parciales que modeliza la dispersión de contaminantes en la atmósfera. Se ha empleado un método de diferencias finitas de alto orden para resolver la parte difusiva de la ecuación de transporte de contaminantes junto con el método racional conservativo para la parte advectiva en una y dos dimensiones. Los resultados obtenidos de la aplicación del método a diferentes situaciones incluyendo casos académicos y reales han sido comparados con la solución analítica de la ecuación de advección-difusión, demostrando que el nuevo método proporciona un resultado preciso para aproximar la solución. Por último, se ha desarrollado un modelo completo que contempla los fenómenos advectivo y difusivo con reacción química, usando los métodos anteriores junto con una técnica de diferenciación regresiva (BDF2). Esta técnica consiste en un método implícito multipaso de diferenciación regresiva de segundo orden, que nos permite resolver los problemas rígidos típicos de la química atmosférica, modelizados a través de sistemas de ecuaciones diferenciales ordinarias. Este método hace uso de la técnica iterativa Gauss- Seidel para obtener la solución de la parte implícita de la fórmula BDF2. El empleo de la técnica de Gauss-Seidel en lugar de otras técnicas comúnmente empleadas, como la iteración por el método de Newton, nos proporciona rapidez de cálculo y bajo consumo de memoria, ideal para obtener modelos operativos para la resolución de la cinética química atmosférica. ABSTRACT Extensive research has been performed to solve the atmospheric chemicaladvection- diffusion equation and different numerical methods have been proposed. This Thesis presents the implementation of an exactly conservative method for the advection equation in the European scale Eulerian chemistry transport model CHIMERE based on a rational interpolation and a finite volume algorithm. The advantage of the method is that the cell-integrated average is predicted via a flux formulation, thus the mass is exactly conserved. Numerical results are compared with a set of observation registered at some monitoring sites in Spain. The mean normalized bias and the mean normalized absolute error present values that are inside the range to consider an accurate model performance. In addition, it has been introduced a new method to solve the advectiondiffusion equation. It is based on a high-order accurate finite difference method to solve de diffusion equation together with a rational interpolation and a finite volume to solve the advection equation in one dimension and two dimensions. Numerical results obtained from solving several problems include academic and real atmospheric problems have been compared with the analytical solution of the advection-diffusion equation, showing that the new method give an efficient algorithm for solving such problems. Finally, a complete model has been developed to solve the atmospheric chemical-advection-diffusion equation, adding the conservative method for the advection equation, the high-order finite difference method for the diffusion equation and a second-order backward differentiation formula (BDF2) to solve the atmospheric chemical kinetics. The BDF2 is an implicit, second order multistep backward differentiation formula used to solve the stiff systems of ordinary differential equations (ODEs) from atmospheric chemistry. The Gauss-Seidel iteration is used for approximately solving the implicitly defined BDF solution, giving a faster tool than the more commonly used iterative modified Newton technique. This method implies low start-up costs and a low memory demand due to the use of Gauss-Seidel iteration.

A framework for mixed-criticality partitioned real-time embedded systems

Los sistemas empotrados son cada día más comunes y complejos, de modo que encontrar procesos seguros, eficaces y baratos de desarrollo software dirigidos específicamente a esta clase de sistemas es más necesario que nunca. A diferencia de lo que ocurría hasta hace poco, en la actualidad los avances tecnológicos en el campo de los microprocesadores de los últimos tiempos permiten el desarrollo de equipos con prestaciones más que suficientes para ejecutar varios sistemas software en una única máquina. Además, hay sistemas empotrados con requisitos de seguridad (safety) de cuyo correcto funcionamiento depende la vida de muchas personas y/o grandes inversiones económicas. Estos sistemas software se diseñan e implementan de acuerdo con unos estándares de desarrollo software muy estrictos y exigentes. En algunos casos puede ser necesaria también la certificación del software. Para estos casos, los sistemas con criticidades mixtas pueden ser una alternativa muy valiosa. En esta clase de sistemas, aplicaciones con diferentes niveles de criticidad se ejecutan en el mismo computador. Sin embargo, a menudo es necesario certificar el sistema entero con el nivel de criticidad de la aplicación más crítica, lo que hace que los costes se disparen. La virtualización se ha postulado como una tecnología muy interesante para contener esos costes. Esta tecnología permite que un conjunto de máquinas virtuales o particiones ejecuten las aplicaciones con unos niveles de aislamiento tanto temporal como espacial muy altos. Esto, a su vez, permite que cada partición pueda ser certificada independientemente. Para el desarrollo de sistemas particionados con criticidades mixtas se necesita actualizar los modelos de desarrollo software tradicionales, pues estos no cubren ni las nuevas actividades ni los nuevos roles que se requieren en el desarrollo de estos sistemas. Por ejemplo, el integrador del sistema debe definir las particiones o el desarrollador de aplicaciones debe tener en cuenta las características de la partición donde su aplicación va a ejecutar. Tradicionalmente, en el desarrollo de sistemas empotrados, el modelo en V ha tenido una especial relevancia. Por ello, este modelo ha sido adaptado para tener en cuenta escenarios tales como el desarrollo en paralelo de aplicaciones o la incorporación de una nueva partición a un sistema ya existente. El objetivo de esta tesis doctoral es mejorar la tecnología actual de desarrollo de sistemas particionados con criticidades mixtas. Para ello, se ha diseñado e implementado un entorno dirigido específicamente a facilitar y mejorar los procesos de desarrollo de esta clase de sistemas. En concreto, se ha creado un algoritmo que genera el particionado del sistema automáticamente. En el entorno de desarrollo propuesto, se han integrado todas las actividades necesarias para desarrollo de un sistema particionado, incluidos los nuevos roles y actividades mencionados anteriormente. Además, el diseño del entorno de desarrollo se ha basado en la ingeniería guiada por modelos (Model-Driven Engineering), la cual promueve el uso de los modelos como elementos fundamentales en el proceso de desarrollo. Así pues, se proporcionan las herramientas necesarias para modelar y particionar el sistema, así como para validar los resultados y generar los artefactos necesarios para el compilado, construcción y despliegue del mismo. Además, en el diseño del entorno de desarrollo, la extensión e integración del mismo con herramientas de validación ha sido un factor clave. En concreto, se pueden incorporar al entorno de desarrollo nuevos requisitos no-funcionales, la generación de nuevos artefactos tales como documentación o diferentes lenguajes de programación, etc. Una parte clave del entorno de desarrollo es el algoritmo de particionado. Este algoritmo se ha diseñado para ser independiente de los requisitos de las aplicaciones así como para permitir al integrador del sistema implementar nuevos requisitos del sistema. Para lograr esta independencia, se han definido las restricciones al particionado. El algoritmo garantiza que dichas restricciones se cumplirán en el sistema particionado que resulte de su ejecución. Las restricciones al particionado se han diseñado con una capacidad expresiva suficiente para que, con un pequeño grupo de ellas, se puedan expresar la mayor parte de los requisitos no-funcionales más comunes. Las restricciones pueden ser definidas manualmente por el integrador del sistema o bien pueden ser generadas automáticamente por una herramienta a partir de los requisitos funcionales y no-funcionales de una aplicación. El algoritmo de particionado toma como entradas los modelos y las restricciones al particionado del sistema. Tras la ejecución y como resultado, se genera un modelo de despliegue en el que se definen las particiones que son necesarias para el particionado del sistema. A su vez, cada partición define qué aplicaciones deben ejecutar en ella así como los recursos que necesita la partición para ejecutar correctamente. El problema del particionado y las restricciones al particionado se modelan matemáticamente a través de grafos coloreados. En dichos grafos, un coloreado propio de los vértices representa un particionado del sistema correcto. El algoritmo se ha diseñado también para que, si es necesario, sea posible obtener particionados alternativos al inicialmente propuesto. El entorno de desarrollo, incluyendo el algoritmo de particionado, se ha probado con éxito en dos casos de uso industriales: el satélite UPMSat-2 y un demostrador del sistema de control de una turbina eólica. Además, el algoritmo se ha validado mediante la ejecución de numerosos escenarios sintéticos, incluyendo algunos muy complejos, de más de 500 aplicaciones. ABSTRACT The importance of embedded software is growing as it is required for a large number of systems. Devising cheap, efficient and reliable development processes for embedded systems is thus a notable challenge nowadays. Computer processing power is continuously increasing, and as a result, it is currently possible to integrate complex systems in a single processor, which was not feasible a few years ago.Embedded systems may have safety critical requirements. Its failure may result in personal or substantial economical loss. The development of these systems requires stringent development processes that are usually defined by suitable standards. In some cases their certification is also necessary. This scenario fosters the use of mixed-criticality systems in which applications of different criticality levels must coexist in a single system. In these cases, it is usually necessary to certify the whole system, including non-critical applications, which is costly. Virtualization emerges as an enabling technology used for dealing with this problem. The system is structured as a set of partitions, or virtual machines, that can be executed with temporal and spatial isolation. In this way, applications can be developed and certified independently. The development of MCPS (Mixed-Criticality Partitioned Systems) requires additional roles and activities that traditional systems do not require. The system integrator has to define system partitions. Application development has to consider the characteristics of the partition to which it is allocated. In addition, traditional software process models have to be adapted to this scenario. The V-model is commonly used in embedded systems development. It can be adapted to the development of MCPS by enabling the parallel development of applications or adding an additional partition to an existing system. The objective of this PhD is to improve the available technology for MCPS development by providing a framework tailored to the development of this type of system and by defining a flexible and efficient algorithm for automatically generating system partitionings. The goal of the framework is to integrate all the activities required for developing MCPS and to support the different roles involved in this process. The framework is based on MDE (Model-Driven Engineering), which emphasizes the use of models in the development process. The framework provides basic means for modeling the system, generating system partitions, validating the system and generating final artifacts. The framework has been designed to facilitate its extension and the integration of external validation tools. In particular, it can be extended by adding support for additional non-functional requirements and support for final artifacts, such as new programming languages or additional documentation. The framework includes a novel partitioning algorithm. It has been designed to be independent of the types of applications requirements and also to enable the system integrator to tailor the partitioning to the specific requirements of a system. This independence is achieved by defining partitioning constraints that must be met by the resulting partitioning. They have sufficient expressive capacity to state the most common constraints and can be defined manually by the system integrator or generated automatically based on functional and non-functional requirements of the applications. The partitioning algorithm uses system models and partitioning constraints as its inputs. It generates a deployment model that is composed by a set of partitions. Each partition is in turn composed of a set of allocated applications and assigned resources. The partitioning problem, including applications and constraints, is modeled as a colored graph. A valid partitioning is a proper vertex coloring. A specially designed algorithm generates this coloring and is able to provide alternative partitions if required. The framework, including the partitioning algorithm, has been successfully used in the development of two industrial use cases: the UPMSat-2 satellite and the control system of a wind-power turbine. The partitioning algorithm has been successfully validated by using a large number of synthetic loads, including complex scenarios with more that 500 applications.