La necessitat d'executar aplicacions en ambients heterogenis és un obstacle que la programació paral·lela vol superar. Per aquesta raó, hem dissenyat una metodologia d'execució eficient que permeti gestionar les heterogeneïtats de comunicació i còmput en sistemes jeràrquics de comunicacions com el presentat en un Cluster Multicore. Per tant, es busca millorar l'eficiència del sistema i determinar el màxim speedup (escalabilidad de l'aplicació en el sistema) amb una eficiència definida. La metodologia està composta per quatre fases: la de caracterització, un model de distribució de tasques, una estratègia de mapping i la política de scheduling. La nostra metodologia s'enfoca en les aplicacions Single Program Multiple Data (SPMD) que estan dissenyades amb llibreria de pas de missatges per realitzar el procés de comunicació. Així mateix, van ser seleccionades a causa que són aplicacions amb alt volum de comunicació i sincronisme, punts que genera desafiaments als programadors quan aquests desitgen executar-les en entorns de comunicacions heterogènies de manera ràpida i eficient. La principal contribució d'aquesta metodologia és determinar el nombre aproximat de cores necessaris i el nombre de tiles que han de ser assignades per complir el nostre objectiu, d'obtenir el màxim speedup mentre l'eficiència és manté per sobre d'un llindar definit per l'usuari. La metodologia ha estat avaluada amb un conjunt d'aplicacions científiques i el resultats mostren en el millor dels casos millores que aconsegueixen fins a 39% en la mètrica de l'eficiència. / La necesidad de ejecutar aplicaciones en ambientes heterogéneos es un obstáculo que la programación paralela quiere superar. Por esta razón, hemos diseñado una metodología de ejecución eficiente que permita gestionar las heterogeneidades de comunicación y cómputo en sistemas jerárquico de comunicaciones como el presentado en un clústeres con procesadores multicore. Por lo tanto, se busca mejorar la eficiencia del sistema y determinar el máximo speedup (escalabilidad de la aplicación en el sistema) con una eficiencia definida. La metodología está compuesta por cuatro fases: la de caracterización, un modelo de distribución de tareas, una estrategia de mapping y la política de Scheduling. Nuestra metodología se enfoca en las aplicaciones Single Program Multiple Data (SPMD) que están diseñadas con librería de paso de mensajes para realizar el proceso de comunicación. Asimismo, fueron seleccionadas debido a que son aplicaciones con alto volumen de comunicación y sincronismo, puntos que genera desafíos a los programadores cuando éstos desean ejecutarlas en entornos de comunicaciones heterogéneas de manera rápida y eficiente. La principal contribución de ésta metodología es determinar el número aproximado de cores necesarios y el número de tiles que deben ser asignadas para cumplir nuestro objetivo, de obtener el máximo speedup mientras la eficiencia es mantenida por encima de un umbral definido por el usuario. La metodología ha sido evaluada con un conjunto de aplicaciones científicas y lo resultados muestran en el mejor de los casos mejoras que alcanzan hasta 39% en la métrica de la eficiencia. / The need to efficiently execute applications in heterogeneous environments is an obstacle parallel computing wants to overcome. The communication heterogeneities present on Multicore clusters ought to be handled carefully for improving efficiency and speedup. For this reason, executions on Multicore environments become a challenge that parallel application programmers must be prepared to deal with. This work proposes an execution methodology centered on controlling communication heterogeneities and improving system efficiency on Multicore clústers. Such methodology is composed by four phases: characterization, a tile distribution model, mapping strategy, and scheduling policy. This method has been developed for Single Program Multiple Data (SPMD) applications with high communication synchronism. We will focus on SPMD applications which are designed through a message-passing library for communication, and selected according to their synchronicity and communications volume. The main contribution of this methodology is to determine the approximate number of cores necessary to achieve a suitable solution in obtaining a good execution time, while the efficiency level is maintained over a threshold defined by users and. Our results show an improvement around 39% in the best case of efficiency on SPMD applications tested when our methodology is applied.

pendent

Los sistemas RFID permiten la identificación rápida y automática de etiquetas RFID a través de un canal de comunicación inalámbrico. Dichas etiquetas son dispositivos con cierto poder de cómputo y capacidad de almacenamiento de información. Es por ello que los objetos que contienen una etiqueta RFID adherida permiten la lectura de una cantidad rica y variada de datos que los describen y caracterizan, por ejemplo, un código único de identificación, el nombre, el modelo o la fecha de expiración. Además, esta información puede ser leída sin la necesidad de un contacto visual entre el lector y la etiqueta, lo cual agiliza considerablemente los procesos de inventariado, identificación, o control automático. Para que el uso de la tecnología RFID se generalice con éxito, es conveniente cumplir con varios objetivos: eficiencia, seguridad y protección de la privacidad. Sin embargo, el diseño de protocolos de identificación seguros, privados, y escalables es un reto difícil de abordar dada las restricciones computacionales de las etiquetas RFID y su naturaleza inalámbrica. Es por ello que, en la presente tesis, partimos de protocolos de identificación seguros y privados, y mostramos cómo se puede lograr escalabilidad mediante una arquitectura distribuida y colaborativa. De este modo, la seguridad y la privacidad se alcanzan mediante el propio protocolo de identificación, mientras que la escalabilidad se logra por medio de novedosos métodos colaborativos que consideran la posición espacial y temporal de las etiquetas RFID. Independientemente de los avances en protocolos inalámbricos de identificación, existen ataques que pueden superar exitosamente cualquiera de estos protocolos sin necesidad de conocer o descubrir claves secretas válidas ni de encontrar vulnerabilidades en sus implementaciones criptográficas. La idea de estos ataques, conocidos como ataques de “relay”, consiste en crear inadvertidamente un puente de comunicación entre una etiqueta legítima y un lector legítimo. De este modo, el adversario usa los derechos de la etiqueta legítima para pasar el protocolo de autenticación usado por el lector. Nótese que, dada la naturaleza inalámbrica de los protocolos RFID, este tipo de ataques representa una amenaza importante a la seguridad en sistemas RFID. En esta tesis proponemos un nuevo protocolo que además de autenticación realiza un chequeo de la distancia a la cual se encuentran el lector y la etiqueta. Este tipo de protocolos se conocen como protocolos de acotación de distancia, los cuales no impiden este tipo de ataques, pero sí pueden frustrarlos con alta probabilidad. Por último, afrontamos los problemas de privacidad asociados con la publicación de información recogida a través de sistemas RFID. En particular, nos concentramos en datos de movilidad que también pueden ser proporcionados por otros sistemas ampliamente usados tales como el sistema de posicionamiento global (GPS) y el sistema global de comunicaciones móviles. Nuestra solución se basa en la conocida noción de k-anonimato, alcanzada mediante permutaciones y microagregación. Para este fin, definimos una novedosa función de distancia entre trayectorias con la cual desarrollamos dos métodos diferentes de anonimización de trayectorias. / Els sistemes RFID permeten la identificació ràpida i automàtica d’etiquetes RFID a través d’un canal de comunicació sense fils. Aquestes etiquetes són dispositius amb cert poder de còmput i amb capacitat d’emmagatzematge de informació. Es per això que els objectes que porten una etiqueta RFID adherida permeten la lectura d’una quantitat rica i variada de dades que els descriuen i caracteritzen, com per exemple un codi únic d’identificació, el nom, el model o la data d’expiració. A més, aquesta informació pot ser llegida sense la necessitat d’un contacte visual entre el lector i l’etiqueta, la qual cosa agilitza considerablement els processos d’inventariat, identificació o control automàtic. Per a que l’ús de la tecnologia RFID es generalitzi amb èxit, es convenient complir amb diversos objectius: eficiència, seguretat i protecció de la privacitat. No obstant això, el disseny de protocols d’identificació segurs, privats i escalables, es un repte difícil d’abordar dades les restriccions computacionals de les etiquetes RFID i la seva naturalesa sense fils. Es per això que, en la present tesi, partim de protocols d’identificació segurs i privats, i mostrem com es pot aconseguir escalabilitat mitjançant una arquitectura distribuïda i col•laborativa. D’aquesta manera, la seguretat i la privacitat s’aconsegueixen mitjançant el propi protocol d’identificació, mentre que l’escalabilitat s’aconsegueix per mitjà de nous protocols col•laboratius que consideren la posició espacial i temporal de les etiquetes RFID. Independentment dels avenços en protocols d’identificació sense fils, existeixen atacs que poden passar exitosament qualsevol d’aquests protocols sense necessitat de conèixer o descobrir claus secretes vàlides, ni de trobar vulnerabilitats a les seves implantacions criptogràfiques. La idea d’aquestos atacs, coneguts com atacs de “relay”, consisteix en crear inadvertidament un pont de comunicació entre una etiqueta legítima i un lector legítim. D’aquesta manera, l’adversari utilitza els drets de l’etiqueta legítima per passar el protocol d’autentificació utilitzat pel lector. Es important tindre en compte que, dada la naturalesa sense fils dels protocols RFID, aquests tipus d’atacs representen una amenaça important a la seguretat en sistemes RFID. En aquesta dissertació proposem un nou protocol que, a més d’autentificació, realitza una revisió de la distància a la qual es troben el lector i l’etiqueta. Aquests tipus de protocols es coneixen com a “distance-boulding protocols”, els quals no prevenen aquests tipus d’atacs, però si que poden frustrar-los amb alta probabilitat. Per últim, afrontem els problemes de privacitat associats amb la publicació de informació recol•lectada a través de sistemes RFID. En concret, ens concentrem en dades de mobilitat, que també poden ser proveïdes per altres sistemes àmpliament utilitzats tals com el sistema de posicionament global (GPS) i el sistema global de comunicacions mòbils. La nostra solució es basa en la coneguda noció de privacitat “k-anonymity” i parcialment en micro-agregació. Per a aquesta finalitat, definim una nova funció de distància entre trajectòries amb la qual desenvolupen dos mètodes diferents d’anonimització de trajectòries. / Radio Frequency Identification (RFID) is a technology aimed at efficiently identifying and tracking goods and assets. Such identification may be performed without requiring line-of-sight alignment or physical contact between the RFID tag and the RFID reader, whilst tracking is naturally achieved due to the short interrogation field of RFID readers. That is why the reduction in price of the RFID tags has been accompanied with an increasing attention paid to this technology. However, since tags are resource-constrained devices sending identification data wirelessly, designing secure and private RFID identification protocols is a challenging task. This scenario is even more complex when scalability must be met by those protocols. Assuming the existence of a lightweight, secure, private and scalable RFID identification protocol, there exist other concerns surrounding the RFID technology. Some of them arise from the technology itself, such as distance checking, but others are related to the potential of RFID systems to gather huge amount of tracking data. Publishing and mining such moving objects data is essential to improve efficiency of supervisory control, assets management and localisation, transportation, etc. However, obvious privacy threats arise if an individual can be linked with some of those published trajectories. The present dissertation contributes to the design of algorithms and protocols aimed at dealing with the issues explained above. First, we propose a set of protocols and heuristics based on a distributed architecture that improve the efficiency of the identification process without compromising privacy or security. Moreover, we present a novel distance-bounding protocol based on graphs that is extremely low-resource consuming. Finally, we present two trajectory anonymisation methods aimed at preserving the individuals' privacy when their trajectories are released.

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.

Aquesta tesi tracta de les possibles aplicacions que puguin tenir els sistemes de simulació física en el camp de l'arquitectura. Aquests mecanismes s'han fet servir profusament en la informàtica ja sigui per a generar animacions, per a càlcul estructural, per investigació etc. Però només recentment s'ha plantejat la possibilitat de fer-les servir com una eina de modelat per als programes de CAD. En aquest sentit la tesi tracta aquesta possibilitat de manera extensa investigant la viabilitat de la idea des de diferents punts de vista i buscant aplicacions per a la mateixa. Es fa una breu exploració dels diferents tipus de models de simulacions físiques. A partir d'aquest estudi i basant-se en els plantejaments teòrics es va generar un software destinat a comprovar tots els aspectes que es van esmentant. El fet de generar un programa va resultar de molta utilitat a l'hora de verificar les idees i estructurar-les correctament. Amb aquest programa es van poder generar models de tota mena, des de arcs funiculars fins a sistemes de malles de pannells que més endavant van poder-se exportar a altres plataformes de CAD amb les que estudiar els resultats. Les simulacions es basen en les formules de Newton aplicades sobre un model de partícules en el que es tenen en compte forces que fan que interactuïn entre elles. A partir d'aquestes interaccions es defineixen o s'optimitzen models tridimensionals conferint-los una sèrie de propietats que s'analitzen mes endavant. Per altra banda les transformacions que pateix aquest model poden ser controlades des de menús de manera que modificant un paràmetre el model es modifiqui automàticament sense la intervenció directa de l'usuari. A nivell de càlcul el programa fa servir sistemes iteratius per a generar transformacions en un model. Seria doncs un procés equivalent a generar una maqueta física del nostre projecte però en el que a més podem controlar la física del model de manera que les possibilitats d'ús siguin més amplies. Es troben doncs tres possibles camps en els que la tesi pot tenir aplicació directa que seria per a processos generatius en arquitectura, per a pannel•lització i per a generar sistemes tènsils. També apareixen altres possibles aplicacions secundaries per a facilitar la modificació d'estructures complexes o simular el control paramètric d'elements arquitectònics. A més de tot això també sorgeixen aspectes inesperats que durant la tesi no s'havien tingut en compte i que al crear un programa s'han pogut apreciar, com certs processos subliminals d'ajust de la forma que tenen lloc en un segon terme o similituds amb certs elements i processos naturals. Així doncs es presenta un anàlisi complet del que significarien els sistemes dinàmics un cop fossin aplicats a l'arquitectura tenint en compte la seva possible repercussió en el disseny. Un aspecte rellevant de la tesi es la relació que s'estableix entre les funcions dinàmiques i la geometria ja que es pretén que els sistemes de forces serveixin, entre altres coses, d'eina de resolució geomètrica. Estudiant els casos en que es poden aplicar i les característiques geomètriques que confereixen als models es pot establir quins possibles usos generals poden tenir en els projectes. Tot això s'emmarca en un context en el que les eines digitals estan en un clar procés de creixement i en el que hi ha una tendència creixent variar la relació amb l'usuari i la manera de com es controlen els processos interns, avançant cada cop més cap a sistemes visuals de programació i cap a un ús més complet de la capacitat de computació que actualment es fa servir només de forma puntual. / This Thesis analyzes the role of physics based algorithms in architectural applications as a generative tool and problem solver mechanism. While physics simulations in digital media had been used for animations, structural calculations or scientific research, there is a lack of studies about the possible uses that it poses for CAD programs. This Thesis tries to fill this gap studying possible applications of this mechanism, from different view points, and trying to extract global rules for their use. In the Thesis we could find an exploration of different methods used in physics simulations, based on this study and some theoretical ideas a software was developed allowing me to test all the theoretical concepts previously exposed. The development of this software was essential to verify that the exposed ideas were correct and also helped to reshape the theoretical structure. All sort of models, ranging from funicular arches to panel meshes were generated using this software and were exported to other platforms to study the results. Physics simulations are based on Newton's formulas applied on particle systems that interact using force fields. These interactions give rise to new 3d shapes and multiple optimization processes that are studied in the thesis. On the other hand the software also allows the user to control the transformations of the model using a parametric tool. The program uses iterative algorithms to modify the model because it is a robust and simple method that could be tested on any computer. The final process is similar to a real physical model of our project but giving the opportunity to control the physics that rule our model allowing more uses than a conventional physical model. There are three areas in which physics based methods could be applied: Generative methods, panelization and tensile structures. There are also other less defined applications as control methods for complex structures and parametric-like control methods of conventional models. Moreover unexpected phenomena takes place in the research process like subliminal long term optimization or natural-like processes. And important issue in this study is the relation between geometry and force fields because there is an interest in solve geometrical problems using forces. Studying the geometric properties that this method gives to the model we can point out which kind of uses is could have. It is also important to look for similarities between geometric shapes and forces to associate both in concepts that could be easily understand by users. This study takes place in a moment when digital tools are growing and the relationship between users and machines is changing continuously in the direction of visual programming. So this study is also trying to make a closer relationship between advanced digital methods and architectural needs to update the current practice. Barcelona

En los experimentos con DNA microarrays se genran dos imágenes monocromo, las cuales es conveniente almacenar para poder realizar análisis más precisos en un futuro. Por tanto, la compresión de imágenes surge como una herramienta particularmente útil para minimizar los costes asociados al almacenamiento y la transmisión de dichas imágenes. Esta tesis tiene por objetivo mejorar el estado del arte en la compresión de imágenes de DNA microarrays. Como parte de esta tesis, se ha realizado una detallada investigación de las características de las imágenes de DNA microarray. Los resultados experimentales indican que los algoritmos de compresión no adaptados a este tipo de imágenes producen resultados más bien pobres debido a las características de estas imágenes. Analizando las entropías de primer orden y condicionales, se ha podido determinar un límite aproximado a la compresibilidad sin pérdida de estas imágenes. Aunque la compresión basada en contexto y en segmentación proporcionan mejoras modestas frente a algoritmos de compresión genéricos, parece necesario realizar avances rompedores en el campo de compresión de datos para superar los ratios 2:1 en la mayor parte de las imágenes. Antes del comienzo de esta tesis se habían propuesto varios algoritmos de compresión sin pérdida con rendimientos cercanos al límite óptimo anteriormente mencionado. Sin embargo, ninguno es compatible con los estándares de compresión existentes. Por tanto, la disponibilidad de descompresores compatibles en plataformas futuras no está garantizado. Además, la adhesión a dichos estándares se require normalmente en escenarios clínicos. Para abordar estos problemos, se propone una transformada reversible compatible con el standard JPEG2000: la Histogram Swap Transform (HST). La HST mejora el rendimiento medio de JPEG2000 en todos los corpora entre 1.97% y 15.53%. Además, esta transformada puede aplicarse incurriendo en un sobrecoste de tiempo negligible. Con la HST, JPEG2000 se convierte en la alternativa estándard más competitiva a los compresores no estándard. Las similaridades entre imágenes del mismo corpus también se han estudiado para mejorar aún más los resultados de compresión de imágenes de DNA microarrays. En concreto, se ha encontrado una agrupación óptima de las imágenes que maximiza la correlación dentro de los grupos. Dependiendo del corpus observado, pueden observarse resultados de correlación medios de entre 0.75 y 0.92. Los resultados experimentales obtenidos indican que las técnicas de decorrelación espectral pueden mejorar los resultados de compresión hasta en 0.6 bpp, si bien ninguna de las transformadas es efectiva para todos los corpora utilizados. Por otro lado, los algoritmos de compresión con pérdida permiten obtener resultados de compresión arbitrarios a cambio de modificar las imágenes y, por tanto, de distorsionar subsiguientes procesos de análisis. Si la distorsión introducida es más pequeña que la variabilidad experimental inherente, dicha distorsión se considera generalmente aceptable. Por tanto, el uso de técnicas de compresión con pérdida está justificado. En esta tesis se propone una métrica de distorsión para imágenes de DNA microarrays capaz de predecir la cantidad de distorsión introducida en el análisis sin necesitar analizar las imágenes modificadas, diferenciando entre cambios importantes y no importantes. Asimismo, aunque ya se habían propuesto algunos algoritmos de compresión con pérdida para estas imágenes antes del comienzo de la tesis, ninguno estaba específicamente diseñado para minimizar el impacto en los procesos de análisis para un bitrate prefijado. En esta tesis, se propone un compresor con pérdida (el Relative Quantizer (RQ) coder) que mejora los resultados de todos los métodos anteriormente publicados. Los resultados obtenidos sugieren que es posible comprimir con ratios superiores a 4.5:1 mientras se introducen distorsiones en el análisis inferiores a la mitad de la variabilidad experimental inherente. Además, se han propuesto algunas mejoras a dicho compresor, las cuales permiten realizar una codificación lossy-to-lossless (el Progressive RQ (PRQ) coder), pudiéndose así reconstruir una imagen comprimida con diferentes niveles de calidad. Cabe señalar que los resultados de compresión anteriormente mencionados se obtienen con una complejidad computacional ligeramente inferior a la del mejor compresor sin pérdida para imágenes de DNA microarrays. / In DNA microarray experiments, two grayscale images are produced. It is convenient to save these images for future, more accurate re-analysis. Thus, image compression emerges as a particularly useful tool to alleviate the associated storage and transmission costs. This dissertation aims at improving the state of the art of the compression of DNA microarray images. A thorough investigation of the characteristics of DNA microarray images has been performed as a part of this work. Results indicate that algorithms not adapted to DNA microarray images typically attain only mediocre lossless compression results due to the image characteristics. By analyzing the first-order and conditional entropy present in these images, it is possible to determine approximate limits to their lossless compressibility. Even though context-based coding and segmentation provide modest improvements over generic-purpose algorithms, conceptual breakthroughs in data coding are arguably required to achieve compression ratios exceeding 2:1 for most images. Prior to the start of this thesis, several lossless coding algorithms that have performance results close to the aforementioned limit were published. However, none of them is compliant with existing image compression standards. Hence, the availability of decoders in future platforms -a requisite for future re-analysis- is not guaranteed. Moreover, the adhesion to standards is usually a requisite in clinical scenarios. To address these problems, a fast reversible transform compatible with the JPEG2000 standard -the Histogram Swap Transform (HST)- is proposed. The HST improves the average compression performance of JPEG2000 for all tested image corpora, with gains ranging from 1.97% to 15.53%. Furthermore, this transform can be applied with only negligible time complexity overhead. With the HST, JPEG2000 becomes arguably the most competitive alternatives to microarray-specific, non-standard compressors. The similarities among sets of microarray images have also been studied as a means to improve the compression performance of standard and microarray-specific algorithms. An optimal grouping of the images which maximizes the inter-group correlation is described. Average correlations between 0.75 and 0.92 are observed for the tested corpora. Thorough experimental results suggest that spectral decorrelation transforms can improve some lossless coding results by up to 0.6bpp, although no single transform is effective for all copora. Lossy coding algorithms can yield almost arbitrary compression ratios at the cost of modifying the images and, thus, of distorting subsequent analysis processes. If the introduced distortion is smaller than the inherent experimental variability, it is usually considered acceptable. Hence, the use of lossy compression is justified on the assumption that the analysis distortion is assessed. In this work, a distortion metric for DNA microarray images is proposed to predict the extent of this distortion without needing a complete re-analysis of the modified images. Experimental results suggest that this metric is able to tell apart image changes that affect subsequent analysis from image modifications that do not. Although some lossy coding algorithms were previously described for this type of images, none of them is specifically designed to minimize the impact on subsequent analysis for a given target bitrate. In this dissertation, a lossy coder -the Relative Quantizer (RQ) coder- that improves upon the rate- distortion results of previously published methods is proposed. Experiments suggest that compression ratios exceeding 4.5:1 can be achieved while introducing distortions smaller than half the inherent experimental variability. Furthermore, a lossy-to-lossless extension of this coder -the Progressive RQ (PRQ) coder- is also described. With the PRQ, images can be compressed once and then reconstructed at different quality levels, including lossless reconstruction. In addition, the competitive rate-distortion results of the RQ and PRQ coders can be obtained with computational complexity slightly smaller than that of the best-performing lossless coder of DNA microarray images.

Es va realitzar una investigació amb la finalitat d'estimar l'impacte que tenen la Data Warehouse (DW) i la Intel•ligència de Negocis (BI) en l'acompliment de les empreses en un país en vies de desenvolupament. Es van establir les preguntes d'investigació i es van utilitzar dos models per resoldre aquestes. El primer un model Qualitatiu Explorador, mitjançant entrevistes semi-estructurades, i el segon un model Quantitativa, mitjançant qüestionaris. El model Qualitatiu Explorador va utilitzar 23 entrevistes en 16 empreses de diversos segments de negocis, que utilitzen la DW i BI. Es van entrevistar Gerents d'Intel•ligència de Negocis d'empreses que desenvolupen el sistema de DW i BI, després a Gerents de DW i BI d'empreses que utilitzen el sistema ja usuaris directes del sistema de DW i BI. Es van gravar totes les entrevistes, després van ser transcrites i codificades, de manera obtenir la informació més important. D'aquesta manera es van establir quines eren les variables més rellevants i els seus components en el cas de la DW i BI, i es va obtenir addicionalment informació molt rellevant. El model Quantitatiu utilitzar 110 qüestionaris de 13 empreses de diversos segments de negocis que utilitzen la DW i BI. Es va utilitzar el model de l'èxit de IS de DeLone i McLean de 2003, amb les variables verificades en l'estudi qualitatiu. Aquest té els constructes independents, Qualitat de la Informació, Qualitat del Sistema i Qualitat del Servei. Després els constructes mediadors, Ús del Sistema i satisfacció de l’usuari, i finalment el constructe dependent, l'Impacte Individual. Com s'indica el constructe dependent, la unitat d'anàlisi va ser l'usuari individual, atès el nombre limitat d'empreses que fan servir el sistema de DW i BI, la qual cosa no permetia treballar amb les empreses com a unitat d'anàlisi. Per a la resolució del model es van utilitzar les Equacions Estructurals, les quals són una eina d'anàlisi multivariable d'última generació que permet treballar amb diversos ítems per a cada constructe i solucionar el model amb tots els constructes alhora. D'aquesta manera es van establir les variables o constructes més rellevants, per grau d'importància, i els seus components, i després es va determinar la significació de cada un d'ells, responent d'aquesta manera les preguntes de recerca i confirmant les hipòtesis més rellevants de l'estudi quantitatiu . Es va determinar addicionalment aspectes com l'ús que li donen les empreses a la Intel•ligència de Negocis. Es va aconseguir explicar àmpliament al constructe dependent, l'Impacte Individual, i es va determinar també un constructe que no va funcionar bé en el model, l'Ús del Sistema. Es van establir igualment les limitacions de l'estudi i es van donar les recomanacions per a estudis futurs, de manera d'aprofitar el trobat en aquest estudi. / Se realizó una investigación con la finalidad de estimar el impacto que tienen la Data Warehouse (DW) y la Inteligencia de Negocios (BI) en el desempeño de las empresas en un país en vías de desarrollo. Se establecieron las preguntas de investigación y se utilizaron dos modelos para resolver las mismas. El primero un modelo Cualitativo Exploratorio, mediante entrevistas semi-estructuradas, y el segundo un modelo Cuantitativo, mediante cuestionarios. El modelo Cualitativo Exploratorio utilizó 23 entrevistas en 16 empresas de diversos segmentos de negocios, que utilizan la DW y BI. Se entrevistaron a Gerentes de Inteligencia de Negocios de empresas que desarrollan el sistema de DW y BI, luego a Gerentes de DW y BI de empresas que utilizan el sistema y a usuarios directos del sistema de DW y BI. Se grabaron todas las entrevistas, luego fueron transcritas y codificadas, de manera obtener la información más importante. De esta manera se establecieron cuales eran las variables más relevantes y sus componentes en el caso de la DW y BI, y se obtuvo adicionalmente información muy relevante. El modelo Cuantitativo utilizó 110 cuestionarios de 13 empresas de diversos segmentos de negocios que utilizan la DW y BI. Se utilizó el modelo del éxito de IS de DeLone y McLean de 2003, con las variables verificadas en el estudio cualitativo. Éste tiene los constructos independientes, Calidad de la Información, Calidad del Sistema y Calidad del Servicio. Luego los constructos mediadores, Uso del Sistema y Satisfacción del Usuario, y finalmente el constructo dependiente, el Impacto Individual. Como se indica el constructo dependiente, la unidad de análisis fue el usuario individual, dado el número limitado de empresas que usan el sistema de DW y BI, lo cual no permitía trabajar con las empresas como unidad de análisis. Para la resolución del modelo se utilizaron las Ecuaciones Estructurales, las cuales son una herramienta de análisis multivariable de última generación que permite trabajar con varios ítems para cada constructo y solucionar el modelo con todos los constructos a la vez. De esta manera se establecieron las variables o constructos más relevantes, por grado de importancia, y sus componentes, y luego se determino la significancia de cada uno de ellos, respondiéndose de esta manera las preguntas de investigación y confirmándose las hipótesis más relevantes del estudio cuantitativo. Se determinó adicionalmente aspectos como el uso que le dan las empresas a la Inteligencia de Negocios. Se logró explicar ampliamente al constructo dependiente, el Impacto Individual, y se determinó también un constructo que no funcionó bien en el modelo, el Uso del Sistema. Se establecieron igualmente las limitaciones del estudio y se dieron las recomendaciones para estudios futuros, de manera de aprovechar lo encontrado en el presente estudio. / The research was made with the purpose of assess the impact that the Data Warehouse (DW) and Business Intelligence (BI) have on the business performance of enterprises in a developing country. Two research questions were established, and two models were used to answer them. The first was a Qualitative exploratory model, using semi- structured interviews, and the second was a Quantitative model, using questionnaires. The Qualitative Exploratory model utilized 23 interviews in 16 enterprises of several business sectors that utilize de DW and BI. Managers of BI of companies that develop systems of DW and BI were interviewed, then managers of DW and BI of companies that use the system, and finally, users of the systems of DW and BI. The interviews were digitally recorded, and then transcribed and coded for analysis. In this way, the main variables and their components that impact in the DW and BI were established, and some complementary information was obtained. The Quantitative model used 110 questionnaires of 13 companies of different business sectors that utilize the DW and BI. The DeLone and McLean model of 2003 with constructs verified in the qualitative model. The model has three independent constructs, Information Quality, System Quality and Service Quality. Then two mediated constructs, Use of the system and User Satisfaction, and finally, the Dependent construct, the Individual Impact. As indicated in the dependent construct, the individual user was the unit of analysis, because of the limited number of enterprises that utilize the system of DW and BI. To solve the quantitative model, structural equations were used, which are tools of multivariate analysis that permit to work with several items per construct and solve the model with all constructs at the same time. In this way, using both models the more relevant constructs and their components were established, determining their importance and significance, and both research questions were answered, and the main hypothesis were confirmed. The dependent construct, the Individual Impact, was well explained, and one construct, the Use of the system, did not work at all. Besides that, some additional information of the DW and BI was gotten, as the specific use of BI that the companies realized. Finally, the limitations and recommendations of the study were presented in order to help to futures studies of DW and BI.

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

The present thesis aims at developing a basis for the numerical simulation of multiphase flows of immiscible fluids. This approach, although limited by the computational power of the present computers, is potentially very important, since most of the physical phenomena of these flows often happen on space and time scales where experimental techniques are impossible to be utilized in practice. In particular, this research is focused on developing numerical discretizations suitable for three-dimensional (3-D) unstructured meshes. In detail, the first chapter delimits the considered multiphase flows to the case in which the components are immiscible fluids. In particular, the focus is placed on those cases where two or more continuous streams of different fluids are separated by interfaces, and hence, correspondingly named separated flows. Additionally, once the type of flow is determined, the chapter introduces the physical characteristics and the models available to predict its behavior, as well as the mathematical formulation that sustains the numerical techniques developed within this thesis. The second chapter introduces and analyzes a new geometrical Volume-of-Fluid (VOF) method for capturing interfaces on 3-D Cartesian and unstructured meshes. The method reconstructs interfaces as first- and second-order piecewise planar approximations (PLIC), and advects volumes in a single unsplit Lagrangian-Eulerian (LE) geometrical algorithm based on constructing flux polyhedrons by tracing back the Lagrangian trajectories of the cell-vertex velocities. In this way, the situations of overlapping between flux polyhedrons are minimized. Complementing the previous chapter, the third one proposes a parallelization strategy for the VOF method. The main obstacle is that the computing costs are concentrated in the interface between fluids. Consequently, if the interface is not homogeneously distributed, standard domain decomposition (DD) strategies lead to imbalanced workload distributions. Hence, the new strategy is based on a load balancing process complementary to the underlying domain decomposition. Its parallel efficiency has been analyzed using up to 1024 CPU-cores, and the results obtained show a gain with respect to the standard DD strategy up to 12x, depending on the size of the interface and the initial distribution. The fourth chapter describes the discretization of the single-phase Navier-Stokes equations to later extend it to the case of multiphase immiscible flow. One of the most important characteristics of the discretization schemes, aside from accuracy, is their capacity to discretely conserve kinetic energy, specially when solving turbulent flow. Hence, this chapter analyzes the accuracy and conservation properties of two particular collocated and staggered mesh schemes. The extension of the numerical schemes suitable for the single-phase Navier-Stokes equations to the case of multiphase immiscible flow is developed in the fifth chapter. Particularly, while the numerical techniques for the simulation of turbulent flow have evolved to discretely preserve mass, momentum and, specially, kinetic energy, the mesh schemes for the discretization of multiphase immiscible flow have evolved to improve their stability and robustness. Therefore, this chapter presents and analyzes two particular collocated and staggered mesh discretizations, able to simulate multiphase immiscible flow, which favor the discrete conservation of mass, momentum and kinetic energy. Finally, the sixth chapter numerically simulates the Richtmyer-Meshkov (RM) instability of two incompressible immiscible liquids. This chapter is a general assessment of the numerical methods developed along this thesis. In particular, the instability has been simulated by means of a VOF method and a staggered mesh scheme. The corresponding numerical results have shown the capacity of the discrete system to obtain accurate results for the RM instability. / Aquesta tesi té com a objectiu desenvolupar una base per a la simulació numèrica de fluids multi-fase immiscibles. Aquesta estratègia, encara que limitada per la potència computacional dels computadors actuals, és potencialment molt important, ja que la majoria de la fenomenologia d'aquests fluids sovint passa en escales temporals i especials on les tècniques experimentals no poden ser utilitzades. En particular, aquest treball es centra en desenvolupar discretitzacions numèriques aptes per a malles no-estructurades en tres dimensions (3-D). En detall, el primer capítol delimita els casos multifásics considerats al cas en que els components són fluids immiscibles. En particular, la tesi es centra en aquells casos en que dos o més fluids diferents són separats per interfases, i per tant, corresponentment anomenats fluxos separats. A més a més, un cop el tipus de flux es determinat, el capítol introdueix les característiques físiques i els models disponibles per predir el seu comportament, així com també la formulació matemàtica i les tècniques numèriques desenvolupades en aquesta tesi. El segon capítol introdueix i analitza un nou mètode "Volume-of-Fluid" (VOF) apte per a capturar interfases en malles Cartesianes i no-estructurades 3-D. El mètode reconstrueix les interfases com aproximacions "piecewise planar approximations" (PLIC) de primer i segon ordre, i advecciona els volums amb un algoritme geomètric "unsplit Lagrangian-Eulerian" (LE) basat en construïr els poliedres a partir de les velocitats dels vèrtexs de les celdes. D'aquesta manera, les situacions de sobre-solapament entre poliedres són minimitzades. Complementant el capítol anterior, el tercer proposa una estratègia de paral·lelització pel mètode VOF. L'obstacle principal és que els costos computacionals estan concentrats en les celdes de l'interfase entre fluids. En conseqüència, si la interfase no està ben distribuïda, les estratègies de "domain decomposition" (DD) resulten en distribucions de càrrega desequilibrades. Per tant, la nova estratègia està basada en un procés de balanceig de càrrega complementària a la DD. La seva eficiència en paral·lel ha sigut analitzada utilitzant fins a 1024 CPU-cores, i els resultats obtinguts mostren uns guanys respecte l'estratègia DD de fins a 12x, depenent del tamany de la interfase i de la distribució inicial. El quart capítol descriu la discretització de les equacions de Navier-Stokes per a una sola fase, per després estendre-ho al cas multi-fase. Una de les característiques més importants dels esquemes de discretització, a part de la precisió, és la seva capacitat per conservar discretament l'energia cinètica, específicament en el cas de fluxos turbulents. Per tant, aquest capítol analitza la precisió i propietats de conservació de dos esquemes de malla diferents: "collocated" i "staggered". L'extensió dels esquemes de malla aptes per els casos de una sola fase als casos multi-fase es desenvolupa en el cinquè capítol. En particular, així com en el cas de la simulació de la turbulència les tècniques numèriques han evolucionat per a preservar discretament massa, moment i energia cinètica, els esquemes de malla per a la discretització de fluxos multi-fase han evolucionat per millorar la seva estabilitat i robustesa. Per lo tant, aquest capítol presenta i analitza dos discretitzacions de malla "collocated" i "staggered" particulars, aptes per simular fluxos multi-fase, que afavoreixen la conservació discreta de massa, moment i energia cinètica. Finalment, el capítol sis simula numèricament la inestabilitat de Richtmyer-Meshkov (RM) de dos fluids immiscibles i incompressibles. Aquest capítol es una prova general dels mètodes numèrics desenvolupats al llarg de la tesi. En particular, la inestabilitat ha sigut simulada mitjançant un mètode VOF i un esquema de malla "staggered". Els resultats numèrics corresponents han demostrat la capacitat del sistema discret en obtenir bons resultats per la inestabilitat RM.