Дисертації з теми "[519.1"

La visión por computador y más específicamente el reconocimiento de objetos han demostrado en los últimos años un impresionante progreso que ha llevado a la aparición de nuevas y útiles tecnologías que facilitan nuestras actividades diarias y mejoran ciertos procesos industriales. Actualmente, nosotros podemos encontrar algoritmos para el reconocimiento de objetos en computadores, videocámaras, teléfonos móviles, tablets o sitios web para la realización de ciertas tareas específicas tales como la detección de caras, el reconocimiento de gestos y escenas, la detección de peatones, la realidad aumentada, etc. No obstante, estas aplicaciones siguen siendo problemas abiertos que cada año reciben más atención por parte de la comunidad de visión por computador. Esto se demuestra por el hecho de que cientos de artículos abordando estos problemas son publicados en congresos internacionales y revistas anualmente. Desde una perspectiva general, los trabajos más recientes intentan mejorar el desempeño de clasificadores, hacer frente a nuevos y más desafiantes problemas de detección, y a aumentar la eficiencia computacional de los algoritmos resultantes con el objetivo de ser implementados comercialmente en diversos dispositivos electrónicos. Aunque actualmente, existen enfoques robustos y confiables para la detección de objetos, la mayoría de estos métodos tienen un alto coste computacional que hacen imposible su aplicación en tareas en tiempo real. En particular, el coste computacional y el desempeño de cualquier sistema de reconocimiento está determinado por el tipo de características, método de reconocimiento y la metodología utilizada para localizar los objetos dentro de las imágenes. El principal objetivo de estos métodos es obtener sistemas de detección eficaces pero también eficientes. A través de esta tesis diferentes enfoques son presentados para abordar de manera eficiente y discriminante la detección de objetos en condiciones de imagen diversas y difíciles. Cada uno de los enfoques propuestos ha sido especialmente diseñado y enfocado para la detección de objetos en circunstancias distintas, tales como la categorización de objetos, la detección bajo rotaciones en el plano o la detección de objetos a partir de múltiples vistas. Los métodos propuestos combinan varias ideas y técnicas para la obtención de detectores de objetos que son tanto altamente discriminantes como eficientes. Esto se demuestra experimentalmente en varias bases de datos del estado del arte donde los resultados alcanzados son competitivos al ser contrastados con otros métodos recientes. En concreto, esta tesis estudia y desarrolla características rápidas, algoritmos de aprendizaje, métodos para reducir el coste computacional de los clasificadores y representaciones de imagen integral que permiten un mejor cálculo de las características.
Computer vision and more specifically object recognition have demonstrated in recent years an impressive progress that has led to the emergence of new and useful technologies that facilitate daily activities and improve some industrial processes. Currently, we can find algorithms for object recognition in computers, video cameras, mobile phones, tablets or websites, for the accomplishment of specific tasks such as face detection, gesture and scene recognition, detection of pedestrians, augmented reality, etc. However, these applications are still open problems that each year receive more attention in the computer vision community. This is demonstrated by the fact that hundreds of articles addressing these problems are published in international conferences and journals annually. In a broader view, recent work attempts to improve the performance of classifiers, to face new and more challenging problems of detection and to increase the computational efficiency of the resulting algorithms in order to be implemented commercially in diverse electronic devices. Although nowadays there are robust and reliable approaches for detecting objects, most of these methods have a high computational cost that make impossible their application for real-time tasks. In particular, the computational cost and performance of any recognition system is determined by the type of features, the method of recognition and the methodology used for localizing objects within images. The main objective of these methods is to produce not only effective but also efficient detection systems. Through this dissertation different approaches are presented for addressing efficiently and discriminatively the detection of objects in diverse and difficult imaging conditions. Each one of the proposed approaches are especially designed and focus on different detection problems, such as object categorization, detection under rotations in the plane or the detection of objects from multiple views. The proposed methods combine several ideas and techniques for obtaining object detectors that are both highly discriminative and efficient. This is demonstrated experimentally in several state-of-the-art databases where our results are competitive with other recent and successful methods. In particular, this dissertation studies and develops fast features, learning algorithms, methods for reducing the computational cost of the classifiers and integral image representations for speeding up feature computation.

Two general goals were raised in this thesis: First, to establish a PLS model for patent value and to investigate causality relationships among variables that determine the patent value; second, to investigate the performance of Partial Least Squares (PLS) Path Modelling with Mode C inthe context of patent value models. This thesis is organized in 10 chapters. Chapter 1 presents an introduction to the thesis that includes the objectives, research scope and the document’s structure. Chapter 2 gives an overview of the different approaches for patent value from the perspective of technological change. Definitions related to patent documents and patent indicators are provided. Chaper 3 reports on patent sample descriptions. We present criteria to retrieve data, the procedure for calculating patent indicators, and a statistical data description. Chapter 4 provides an introduction to structural equation models (SEMs) including origins, basic background and recent developments. In addition, it provides guidelines for model specification and modelling process for SEMs. Special emphasis is placed on determining the reflective or formative nature of measurement models. Chapter 5 puts forward the main PLS algorithms: NIPALS, PLS Regression and PLS Path Modelling. We present two path modelling implementations: Lohmöller and Wold’s procedures. Additionally, insights are given on procedure sensitivity to starting weight values and weighting schemes; algorithm properties, such as consistency and consistency at large; and convergence. We briefly review some PLS Path Modelling extensions and relationships with other procedures. The chapter ends by describing validation techniques. Chapter 6 provides evidence about the accuracy and precision of PLS Path Modelling with Mode C to recover true values in SEMs with few indicators per construct. Monte Carlo simulations and computational experiments are carried out to study the performance of the algorithm. Chapter 7 addresses the formulation and estimation of patent value models. This entails the identification and definition of observable and unobservable variables, the determination of blocks of manifest variables and structural relationships, the specification of a first- and a second-order models of patent value, and the models’ estimation by PLS Path Modelling. In Chapter 8, the evolution of patent value over time using longitudinal SEMs is investigated. Two set-ups are explored. The first longitudinal model includes time-dependent manifest variables and the second includes time-dependent unobservable variables. The SEMs are estimated using PLS Path Modelling. In Chapter 9, there is a description of a Two-Step PLS Path Modelling with Mode C (TsPLS) procedure to study nonlinear and interaction effects among formative constructs. Monte Carlo simulations are performed to generate data and to determine the accuracy and precision of this approach to recover true values. This chapter includes an application of the TsPLS algorithm to patent value models. Finally, in Chapter 10, we provide a summary of conclusions and future researchs. The main contribution of this thesis is to set-up a PLS model for patent value, and around this issue, we have also contributed in two main areas: Contributions to the field of Technological Change are comprised of: (1) Evidence on the role of the knowledge stock, technological scope and international scope as determinants of patent value and technological usefulness. A stable pattern of path coefficients was found across samples in different time periods. (2) To conceptualize the patent value as a potential and a recognized value for intangible assets. It was also shown that the potential value of patent is small compared to the value that is given later. (3) Evidence for the importance of considering the longitudinal nature of the indicators in the patent value problem, especially for forward citations, which are the most widely used indicator of patent value. (4) To introduce a multidimensional perspective of the patent valuation problem. This novel approach may offer a robust understanding of the different varia bles that determine patent value. Contributions to the field of PLS Path Modelling are comprised of: (5) Empirical evidence on the performance of PLS Path Modelling with Mode C. If properly implemented, the procedure can adequately capture some of the complex dynamic relationships involved in models. Our research shows that PLS Path Modelling with Mode C performs according to the theoretical framework established for PLS procedures and PLS-models (Wold, 1982; Krämer, 2006; Hanafi, 2007; Dijkstra, 2010). (6) Empirical evidence for the consistency at large of the PLS Path Modelling with Mode A. (7) Empirical evidence for formative outer models with few manifest variables. (8) Empirical evidence on the performance of a Two-Step PLS Path Modelling with Mode C procedure to estimate nonlinear and interaction effects among formative constructs.
Dos objetivos general fueron planteados en esta tesis. Primero, establacer un modelo PLS para el valor de las patentes e investigar las relaciones de causalidad entre las variables que determinan el valor de las patentes. Segundo, investigar el desempeño del procedimiento Partial Least Squares (PLS) Path Modelling con Modo C en el contexto de los modelos de valor de las patentes. La tesis es organizada en 10 capítulos. El Capítulo 1 presenta una introducción a la tesis que incluye los objetivos, el alcance de la investigación y la estructura del documento. El Capítulo 2 entrega una presentación general de los diferentes enfoques para valoración de patentes desde una perspectiva del cambio tecnológico. También se entregan las definiciones necesarias relacionadas con los documentos e indicadores de patentes. El Capítulo 3 describe la muestra de patentes usada en esta investigación. Se presentan los criterios utilizados para recuperar los datos, el procedimiento seguido para calcular los indicadores de patentes y la descripción estadística de la muestra. El Capítulo 4 provee una introducción a los modelos de ecuaciones estructurales (SEMs) incluyendo orígenes, antecedentes básicos y desarrollos recientes. Además se entregan los lineamientos para la especificación de los modelos y el proceso de modelamiento para SEMs. Este capítulo discute con especial énfasis la determinación de la naturaleza reflectiva o formativa de los modelos de medida. El Capítulo 5 presenta los principales algoritmos PLS: NIPALS, Regresión PLS y PLS Path Modelling. Se presentan dos implementaciones de PLS Path Modelling: los procedimientos de Lohmöller y Wold. Adicionalmente, se analyzan resultados previos relacionados con: la sensibilidad del procedimiento al valor inicial de los vectores de pesos y el esquema de ponderación, y las propiedades del algoritmo, tales como consistencia, consistencia “at large” y convergencia. También brevemente se revisan algunas extensiones del procedimiento y su relación con otros métodos. El capítulo termina describiendo las técnicas de validación. El Capítulo 6 provee evidencia acerca de la exactitud y precisión con que PLS Path Modelling con Modo C recupera valores verdaderos en SEMs con pocos indicadores por constructo. Simulaciones Monte Carlo y experimentos computacionales son llevados a cabo para estudiar el rendimiento del algoritmo. El Capítulo 7 trata la formulación y estimación de los modelos de valoración de patentes. Esto comprende la identificación y definición de las variables observables y no observables, la determinación de los bloques de variables manifiestas y las relaciones estructurales, la especificación de los modelos de primer y segundo orden del valor de las patentes y la estimación de los mismos con PLS Path Modelling. En el Capítulo 8, la evolución del valor de las patentes a través del tiempo es investigado usando SEMs longitudinales. Dos set-ups son explorados. El primer modelo longitudinal considera variables manifiestas dependientes del tiempo y el segundo incluye variables latentes dependientes del tiempo. Los SEMs son estimados usando PLS Path Modelling. En el Capítulo 9, el procedimiento Two-Step PLS Path Modelling con Modo C (TsPLS) es implementado para estudiar los efectos no lineales y de interacción entre constructos formativos. Simulaciones Monte Carlo son llevadas a cabo para generar datos y determinar la exactitud y precisión con que este enfoque recupera valores verdaderos. Este capítulo incluye una aplicación del procedimiento a los modelos de patentes. Finalmente, el Capítulo 10 provee un resumen de las conclusiones y lineamientos para futuras investigaciones. La principal contribución de esta tesis es proponer modelos PLS para el valor de las patentes, y alrededor de este objetivo, nosotros hemos también contribuido en dos áreas principales: Contribuciones en el área del Cambio Tecnológico comprenden: (1) Evidencia empírica del rol del stock de conocimiento, el alcance tecnológico y el alcance internacional como determinantes del valor de las patentes y la utilidad tecnológica. Un patrón estable de coeficientes de trayectoria fue encontrado al estimar los modelos con muestras en diferentes periodos de tiempo. (2) Conceptualizar el valor de las patentes en un valor potencial y uno reconocido. También proveer evidencia acerca de que el valor potencial es pequeño al compararlo con el valor que las patentes adquieren con posterioridad. (3) Evidencia acerca de la importancia de considerar la naturaleza longitudinal de los indicatores en el problema de valorización de patentes, especialmente de las citas recibidas, el indicador de valor más utilizado. (4) Introducir una perspectiva multidimensional en el problema de valoración de patentes. Este nuevo enfoque puede ofrecer un entendimiento robusto de las diferentes variables que determinar el valor de las patentes. Contribuciones en el área del PLS PLS Path Modelling comprenden: (5) Evidencia empírica acerca del desempeño de PLS Path Modelling con Modo C. Apropiadamente implemetado, el procedimiento puede adecuadamente capturar algunas de las complejas relaciones dinámicas en los modelos. Nuestra investigación muestra que PLS Path Modelling con Modo C se comporta de acuerdo al marco teórico establecido para los procedimientos PLS y los modelos PLS (Wold, 1982; Krämer, 2006; Hanafi, 2007; Dijkstra, 2010). Es decir, (a) las estimaciones PLS estan siempre sesgadas, (b) las relaciones internas son subestimadas, (c) las relaciones externas son sobrestimadas, (d) el Modo A carece de la propiedad de convergencia monótona, (3) el Modo B tiene la propiedad de convergencia monótona. (6) Evidencia empírica acerca de la convergencia “at large” de PLS Path Modelling con Modo A. (7) Evidencia empírica para los modelos formativos con pocos indicadores (8) Evidencia empírica del desempeño del procedimiento Two-Step PLS Path Modelling con Modo C para estimar efectos no lineales y de interacción entre constructos formativos.

En aquesta tesi s'estudien diferents problemes en el camp de la combinatòria i la teoria de grafs, utilitzant el mètode probabilístic. Aquesta tècnica, introduïda per Erdős , ha esdevingut una eina molt potent per tal de donar proves existencials per certs problemes en diferents camps de les matemàtiques on altres mètodes no ho han aconseguit. Un dels seus principals objectius és l'estudi del comportament de les variables aleatòries. El cas en que aquestes variables compten el nombre d'esdeveniments dolents que tenen lloc en una estructura combinatòria és de particular interès. La idea del Paradigma de Poisson és estimar la probabilitat que tots aquests esdeveniments dolents no succeeixin a la vegada, quan les dependències entre ells són febles o escasses. En tal cas, aquesta probabilitat s'hauria de comportar de forma similar al cas on tots els esdeveniments són independents. El Lema Local de Lovász o la Desigualtat de Suen són exemples d'aquesta idea. L'objectiu de la tesi és estudiar aquestes tècniques ja sigui proveint-ne noves versions, refinant-ne les existents per casos particulars o donant-ne noves aplicacions. A continuació s'enumeren les principals contribucions de la tesi. La primera part d'aquesta tesi estén un resultat d' Erdős i Spencer sobre transversals llatins. Els autors proven que qualsevol matriu d'enters on cap nombre apareix massa vegades, admet un transversal on tots els nombres són diferents. Això equival a estudiar els aparellaments multicolors en aresta-coloracions de grafs complets bipartits. Sota les mateixes hipòtesis que, es donen resultats sobre el nombre d'aquests aparellaments. Les tècniques que s'utilitzen estan basades en l'estratègia desenvolupada per Lu i Székely. En la segona part d'aquesta tesi s'estudien els codis identificadors. Un codi identificador és un conjunt de vèrtexs tal que tots els vèrtexs del graf tenen un veïnatge diferent en el codi. Aquí s'estableixen cotes en la mida d'un codi identificador mínim en funció dels graus i es resol parcialment una conjectura de Foucaud et al.. En un altre capítol, es mostra que qualsevol graf suficientment dens conté un subgraf que admet un codi identificador òptim. En alguns casos, provar l'existència d'un cert objecte és trivial. Tot i així, es poden utilitzar les mateixes tècniques per obtenir resultats d'enumeració. L'estudi de patrons en permutacions n'és un bon exemple. A la tercera part de la tesi es desenvolupa una nova tècnica per tal d'estimar el nombre de permutacions d'una certa llargada que eviten còpies consecutives d'un patró donat. En particular, es donen cotes inferiors i superiors per a aquest nombre. Una de les conseqüències és la prova de la conjectura CMP enunciada per Elizalde i Noy així com nous resultats en el comportament de la majoria dels patrons. En l'última part de la tesi s'estudia la Conjectura Lonely Runner, enunciada independentment per Wills i Cusick i que té múltiples aplicacions en diferents camps de les matemàtiques. Aquesta coneguda conjectura diu que per qualsevol conjunt de corredors que corren al llarg d'un cercle unitari, hi ha un moment on tots els corredors estan suficientment lluny de l'origen. Aquí, es millora un resultat de Chen ampliant la distància de tots els corredors a l'origen. També s'estén el teorema del corredor invisible de Czerwiński i Grytczuk .
In this thesis we study different problems in combinatorics and in graph theory by means of the probabilistic method. This method, introduced by Erdös, has become an extremely powerful tool to provide existential proofs for certain problems in different mathematical branches where other methods had failed utterly. One of its main concerns is to study the behavior of random variables. In particular, one common situation arises when these random variables count the number of bad events that occur in a combinatorial structure. The idea of the Poisson Paradigm is to estimate the probability of these bad events not happening at the same time when the dependencies among them are weak or rare. If this is the case, this probability should behave similarly as in the case where all the events are mutually independent. This idea gets reflected in several well-known tools, such as the Lovász Local Lemma or Suen inequality. The goal of this thesis is to study these techniques by setting new versions or refining the existing ones for particular cases, as well as providing new applications of them for different problems in combinatorics and graph theory. Next, we enumerate the main contributions of this thesis. The first part of this thesis extends a result of Erdös and Spencer on latin transversals [1]. They showed that an integer matrix such that no number appears many times, admits a latin transversal. This is equivalent to study rainbow matchings of edge-colored complete bipartite graphs. Under the same hypothesis of, we provide enumerating results on such rainbow matchings. The second part of the thesis deals with identifying codes, a set of vertices such that all vertices in the graph have distinct neighborhood within the code. We provide bounds on the size of a minimal identifying code in terms of the degree parameters and partially answer a question of Foucaud et al. On a different chapter of the thesis, we show that any dense enough graph has a very large spanning subgraph that admits a small identifying code. In some cases, proving the existence of a certain object is trivial. However, the same techniques allow us to obtain enumerative results. The study of permutation patterns is a good example of that. In the third part of the thesis we devise a new approach in order to estimate how many permutations of given length avoid a consecutive copy of a given pattern. In particular, we provide upper and lower bounds for them. One of the consequences derived from our approach is a proof of the CMP conjecture, stated by Elizalde and Noy as well as some new results on the behavior of most of the patterns. In the last part of this thesis, we focus on the Lonely Runner Conjecture, posed independently by Wills and Cusick and that has multiple applications in different mathematical fields. This well-known conjecture states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a moment where all of them are far enough from the origin. We improve the result of Chen on the gap of loneliness by studying the time when two runners are close to the origin. We also show an invisible runner type result, extending a result of Czerwinski and Grytczuk.

L'objectiu d'aquesta tesi és aprofondir en l'estudi d'una certa família de dígrafs, els dígrafs de prefix-cicle, donant nous detalls sobre la seva estructura, noves maneres d'enfocar el seu estudi, i dissenyant bons esquemes de comunicació. Es completa d'aquesta forma l'estudi iniciat per altres autors i s'en refoça el seu interès com a bon model de xarxa d'interconnexió.

The objective of this thesis is to study cages, constructions and properties of such families of graphs. For this, the study of graphs without short cycles plays a fundamental role in order to develop some knowledge on their structure, so we can later deal with the problems on cages. Cages were introduced by Tutte in 1947. In 1963, Erdös and Sachs proved that (k, g) -cages exist for any given values of k and g. Since then, large amount of research in cages has been devoted to their construction. In this work we study structural properties such as the connectivity, diameter, and degree regularity of graphs without short cycles. In some sense, connectivity is a measure of the reliability of a network. Two graphs with the same edge-connectivity, may be considered to have different reliabilities, as a more refined index than the edge-connectivity, edge-superconnectivity is proposed together with some other parameters called restricted connectivities. By relaxing the conditions that are imposed for the graphs to be cages, we can achieve more refined connectivity properties on these families and also we have an approach to structural properties of the family of graphs with more restrictions (i.e., the cages). Our aim, by studying such structural properties of cages is to get a deeper insight into their structure so we can attack the problem of their construction. By way of example, we studied a condition on the diameter in relation to the girth pair of a graph, and as a corollary we obtained a result guaranteeing restricted connectivity of a special family of graphs arising from geometry, such as polarity graphs. Also, we obtained a result proving the edge superconnectivity of semiregular cages. Based on these studies it was possible to develop the study of cages. Therefore obtaining a relevant result with respect to the connectivity of cages, that is, cages are k/2-connected. And also arising from the previous work on girth pairs we obtained constructions for girth pair cages that proves a bound conjectured by Harary and Kovács, relating the order of girth pair cages with the one for cages. Concerning the degree and the diameter, there is the concept of a Moore graph, it was introduced by Hoffman and Singleton after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth (bipartite Moore graphs) as well as odd girth, and again these graphs are cages. Thus, Moore graphs give a lower bound for the order of cages, but they are known to exist only for very specific values of k, therefore it is interesting to study how far a cage is from this bound, this value is called the excess of a cage. We studied the excess of graphs and give a contribution, in the sense of the work of Biggs and Ito, relating the bipartition of girth 6 cages with their orders. Entire families of cages can be obtained from finite geometries, for example, the graphs of incidence of projective planes of order q a prime power, are (q+1, 6)-cages. Also by using other incidence structures such as the generalized quadrangles or generalized hexagons, it can be obtained families of cages of girths 8 and 12. In this thesis, we present a construction of an entire family of girth 7 cages that arises from some combinatorial properties of the incidence graphs of generalized quadrangles of order (q,q).

En el entorno actual, diversas ramas de las ciencias, tienen la necesidad de auxiliarse de la computación de altas prestaciones para la obtención de resultados a relativamente corto plazo. Ello es debido fundamentalmente, al alto volumen de información que necesita ser procesada y también al costo computacional que demandan dichos cálculos. El beneficio al realizar este procesamiento de manera distribuida y paralela, logra acortar de manera notable los tiempos de espera en la obtención de los resultados. Para soportar ello, existen fundamentalmente dos modelos de programación ampliamente extendidos: el modelo de paso de mensajes a través de librerías basadas en el estándar MPI, y el de memoria compartida con la utilización de OpenMP. Las aplicaciones híbridas son aquellas que combinan ambos modelos con el fin de aprovechar en cada caso, las potencialidades específicas del paralelismo en cada uno. Lamentablemente, la práctica ha demostrado que la utilización de esta combinación de modelos, no garantiza necesariamente una mejoría en el comportamiento de las aplicaciones. Existen varios parámetros que deben ser considerados a determinar la configuración de la aplicación que proporciona el mejor tiempo de ejecución. El número de proceso que se debe utilizar, el número de hilos en cada nodo, la distribución de datos entre procesos e hilos, y así sucesivamente, son parámetros que afectan seriamente elrendimiento de la aplicación. El valor apropiado de tales parámetros depende, por una parte, de las características de arquitectura del sistema (latencia de las comunicaciones, el ancho de banda de comunicación, el tamaño y la distribución de los niveles de memoria cache, la capacidad de cómputo, etc.) y, por otro lado, de la características propias del comportamiento de la aplicación. La contribución fundamental de esta tesis radica en la utilización de una técnica novedosa para la predicción del rendimiento y la eficiencia de aplicaciones híbridas de tipo Master/Worker. En particular, dentro del mundo del aprendizaje automatizado, este método de predicción es conocido como arboles de regresión basados en modelos análiticos. Los resultados experimentales obtenidos permiten ser optimista en cuanto al uso de este algoritmo para la predicción de ambas métricas o para la selección de la mejor configuración de parámetros de ejecución de la aplicación.
In the current environment, various branches of science are in need of auxiliary high-performance computing to obtain relatively short-term results. This is mainly due to the high volume of information that needs to be processed and the computational cost demanded by these calculations. The benefit to performing this processing using distributed and parallel programming mechanisms is that it achieves shorter waiting times in obtaining the results. To support this, there are basically two widespread programming models: the model of message passing based on the standard libraries MPI and the shared memory model with the use of OpenMP. Hybrid applications are those that combine both models in order to take the specific potential of parallelism of each one in each case. Unfortunately, experience has shown that using this combination of models does not necessarily guarantee an improvement in the behavior of applications. There are several parameters that must be considered to determine the configuration of the application that provides the best execution time. The number of process that must be used,the number of threads on each node, the data distribution among processes and threads, and so on, are parameters that seriously affect the performance of the application. On the one hand, the appropriate value of such parameters depends on the architectural features of the system (communication latency, communication bandwidth, cache memory size and architecture, computing capabilities, etc.), and, on the other hand, on the features of the application. The main contribution of this thesis is a novel technique for predicting the performance and efficiency of parallel hybrid Master/Worker applications. This technique is known as model-based regression trees into the field of machine learning. The experimental results obtained allow us to be optimistic about the use of this algorithm for predicting both metrics and to select the best application execution parameters.

Gone are the days when engineers and scientists conducted most of their experiments empirically. During these decades, actual tests were carried out in order to assess the robustness and reliability of forthcoming product designs and prove theoretical models. With the advent of the computational era, scientific computing has definetely become a feasible solution compared with empirical methods, in terms of effort, cost and reliability. Large and massively parallel computational resources have reduced the simulation execution times and have improved their numerical results due to the refinement of the sampled domain. Several numerical methods coexist for solving the Partial Differential Equations (PDEs). Methods such as the Finite Element (FE) and the Finite Volume (FV) are specially well suited for dealing with problems where unstructured meshes are frequent. Unfortunately, this flexibility is not bestowed for free. These schemes entail higher memory latencies due to the handling of irregular data accesses. Conversely, the Finite Difference (FD) scheme has shown to be an efficient solution for problems where the structured meshes suit the domain requirements. Many scientific areas use this scheme due to its higher performance. This thesis focuses on improving FD schemes to leverage the performance of large scientific computing simulations. Different techniques are proposed such as the Semi-stencil, a novel algorithm that increases the FLOP/Byte ratio for medium- and high-order stencils operators by reducing the accesses and endorsing data reuse. The algorithm is orthogonal and can be combined with techniques such as spatial- or time-blocking, adding further improvement. New trends on Symmetric Multi-Processing (SMP) systems -where tens of cores are replicated on the same die- pose new challenges due to the exacerbation of the memory wall problem. In order to alleviate this issue, our research is focused on different strategies to reduce pressure on the cache hierarchy, particularly when different threads are sharing resources due to Simultaneous Multi-Threading (SMT). Several domain decomposition schedulers for work-load balance are introduced ensuring quasi-optimal results without jeopardizing the overall performance. We combine these schedulers with spatial-blocking and auto-tuning techniques, exploring the parametric space and reducing misses in last level cache. As alternative to brute-force methods used in auto-tuning, where a huge parametric space must be traversed to find a suboptimal candidate, performance models are a feasible solution. Performance models can predict the performance on different architectures, selecting suboptimal parameters almost instantly. In this thesis, we devise a flexible and extensible performance model for stencils. The proposed model is capable of supporting multi- and many-core architectures including complex features such as hardware prefetchers, SMT context and algorithmic optimizations. Our model can be used not only to forecast execution time, but also to make decisions about the best algorithmic parameters. Moreover, it can be included in run-time optimizers to decide the best SMT configuration based on the execution environment. Some industries rely heavily on FD-based techniques for their codes. Nevertheless, many cumbersome aspects arising in industry are still scarcely considered in academia research. In this regard, we have collaborated in the implementation of a FD framework which covers the most important features that an HPC industrial application must include. Some of the node-level optimization techniques devised in this thesis have been included into the framework in order to contribute in the overall application performance. We show results for a couple of strategic applications in industry: an atmospheric transport model that simulates the dispersal of volcanic ash and a seismic imaging model used in Oil & Gas industry to identify hydrocarbon-rich reservoirs.
Atrás quedaron los días en los que ingenieros y científicos realizaban sus experimentos empíricamente. Durante esas décadas, se llevaban a cabo ensayos reales para verificar la robustez y fiabilidad de productos venideros y probar modelos teóricos. Con la llegada de la era computacional, la computación científica se ha convertido en una solución factible comparada con métodos empíricos, en términos de esfuerzo, coste y fiabilidad. Los supercomputadores han reducido el tiempo de las simulaciones y han mejorado los resultados numéricos gracias al refinamiento del dominio. Diversos métodos numéricos coexisten para resolver las Ecuaciones Diferenciales Parciales (EDPs). Métodos como Elementos Finitos (EF) y Volúmenes Finitos (VF) están bien adaptados para tratar problemas donde las mallas no estructuradas son frecuentes. Desafortunadamente, esta flexibilidad no se confiere de forma gratuita. Estos esquemas conllevan latencias más altas debido al acceso irregular de datos. En cambio, el esquema de Diferencias Finitas (DF) ha demostrado ser una solución eficiente cuando las mallas estructuradas se adaptan a los requerimientos. Esta tesis se enfoca en mejorar los esquemas DF para impulsar el rendimiento de las simulaciones en la computación científica. Se proponen diferentes técnicas, como el Semi-stencil, un nuevo algoritmo que incrementa el ratio de FLOP/Byte para operadores de stencil de orden medio y alto reduciendo los accesos y promoviendo el reuso de datos. El algoritmo es ortogonal y puede ser combinado con técnicas como spatial- o time-blocking, añadiendo mejoras adicionales. Las nuevas tendencias hacia sistemas con procesadores multi-simétricos (SMP) -donde decenas de cores son replicados en el mismo procesador- plantean nuevos retos debido a la exacerbación del problema del ancho de memoria. Para paliar este problema, nuestra investigación se centra en estrategias para reducir la presión en la jerarquía de cache, particularmente cuando diversos threads comparten recursos debido a Simultaneous Multi-Threading (SMT). Introducimos diversos planificadores de descomposición de dominios para balancear la carga asegurando resultados casi óptimos sin poner en riesgo el rendimiento global. Combinamos estos planificadores con técnicas de spatial-blocking y auto-tuning, explorando el espacio paramétrico y reduciendo los fallos en la cache de último nivel. Como alternativa a los métodos de fuerza bruta usados en auto-tuning donde un espacio paramétrico se debe recorrer para encontrar un candidato, los modelos de rendimiento son una solución factible. Los modelos de rendimiento pueden predecir el rendimiento en diferentes arquitecturas, seleccionando parámetros suboptimos casi de forma instantánea. En esta tesis, ideamos un modelo de rendimiento para stencils flexible y extensible. El modelo es capaz de soportar arquitecturas multi-core incluyendo características complejas como prefetchers, SMT y optimizaciones algorítmicas. Nuestro modelo puede ser usado no solo para predecir los tiempos de ejecución, sino también para tomar decisiones de los mejores parámetros algorítmicos. Además, puede ser incluido en optimizadores run-time para decidir la mejor configuración SMT. Algunas industrias confían en técnicas DF para sus códigos. Sin embargo, no todos los aspectos que aparecen en la industria han sido sometidos a investigación. En este aspecto, hemos diseñado e implementado desde cero una infraestructura DF que cubre las características más importantes que una aplicación industrial debe incluir. Algunas de las técnicas de optimización propuestas en esta tesis han sido incluidas para contribuir en el rendimiento global a nivel industrial. Mostramos resultados de un par de aplicaciones estratégicas para la industria: un modelo de transporte atmosférico que simula la dispersión de ceniza volcánica y un modelo de imagen sísmica usado en la industria del petroleo y gas para identificar reservas ricas en hidrocarburos

An important question that modern societies have to decide is the election of some people who represent them and can also make some decisions. Mechanisms to do it are called Electoral Systems. In fact, there are a lot of them and they are very different. In this work, we present some ideas to carry out a mathematical analysis of them. The first chapter is a global analysis of electoral systems. It begins with the definition of electoral system --helped by Probability Theory-- and the introduction of most important simple examples found in practice. Next we define two operations on electoral systems and, in particular, we obtain two different generalizations of each one of the examples. We also introduce some important properties that electoral systems may have -- superadditivity, monotonicity, increasing and stability-- and we study which examples enjoy them and the behavior of these properties with respect to the operations defined before. Finally, stability give us the possibility to define majority and proportional electoral systems. In the second chapter we study electoral systems individually. In this sense, we introduce the electoral expectatives, obtained when the vote vector of an arbitrary list of candidates is fixed. Then we study their connection with the operations before defined and we finish the chapter by introducing some individual properties that electoral systems may have and analysing what happens when we consider again the operations defined before. The third chapter refers to a parameter introduced to assess whether an arbitrary list of candidates gets profit or not from an electoral system. The way used to do it consists in considering the expected value of electoral expectatives introduced in the second chapter. We obtain in this form the concept of average electoral expectative. And we finish the chapter by studying the behavior of this concept with respect to the operations and examples introduced above. In the fourth chapter we analyse three questions of majority weighted games that we will use in the next chapter: another form to define them, a new operation between them and their convergence. Finally, in the fifth chapter we replace the number of seats of each litst of candidates by its Shapley-Shubik power index and we study the electoral systems using this new indicator. In this form, we obtain the concept of power system and, analogously, the concepts of power expectative and average power expectative. We finish by introducing some new properties of each one of these concepts and we also analyse their relation with the analogous properties of electoral systems.
Una cuestión importante que las sociedades modernas deben decidir es la elección de algunos individuos que los representen y puedan asimismo tomar ciertas decisiones. Los mecanismos encargados de hacer esto se llaman Sistemas Electorales. De hecho, existen muchos y son muy diferentes. En este trabajo, presentamos algunas ideas para analizamos matemáticamente. El primer capítulo es un análisis global de los sistemas electorales. Comienza con la definición de sistema electoral --con la ayuda de la Teoría de Probabilidades-- y la introducción de los ejemplos simples más importantes que hay. Después definimos dos operaciones para los sistemas electorales, con lo que obtenemos dos generalizaciones diferentes de cada uno de los ejemplos. Introducimos también algunas propiedades importantes que pueden poseer los sistemas electorales --superaditividad, monotonía, crecimiento y estabilidad-- y estudiamos cuáles de los ejemplos las poseen y el comportamiento de dichas propiedades respecto de las operaciones anteriormente definidas. Finalmente, la estabilidad nos proporciona la posibilidad de definir los sistemas electorales mayoritarios y proporcionales. En el segundo capítulo estudiamos los sistemas electorales desde el punto de vista individual. En tal sentido, introducimos las expectativas electorales, obtenidas fijando el vector de votos de una candidatura arbitraria. Seguidamente, estudiamos su relación con las operaciones anteriormente definidas y terminamos el capítulo introduciendo algunas propiedades de tipo individual que los sistemas electorales pueden poseer y analizando qué sucede cuando consideramos las operaciones anteriores. El tercer capítulo trata sobre un parámetro introducido para evaluar si una candidatura cualquiera resulta beneficiada o no por un sistema electoral. La forma de hacerlo ha sido considerar la media de las expectativas electorales introducidas en el segundo capítulo. Obtenemos de esta forma el concepto de expectativa electoral media. Y finalizamos el capítulo estudiando de nuevo su comportamiento respecto de las operaciones y los ejemplos introducidos. En el cuarto capítulo analizamos tres cuestiones sobre juegos de mayoría ponderada que serán utilizados en el capítulo siguiente: otra forma de definirlos, una nueva operación entre ellos y su convergencia. Finalmente, en el quinto capítulo substituimos el número de respresentantes de cada candidatura por su índice de poder de Shapley-Shubik y estudiamos los sistemas electorales utilizando este nuevo indicador. De esta forma, obtenemos el concepto de sistema de poder y, análogamente, los de expectativa de poder y expectativa de poder media. E introducimos algunas propiedades nuevas sobre cada uno de los conceptos anteriores y analizamos también su relación con las propiedades análogas de los sistemas electorales.

En esta tesis se desarrolla, siempre con el enfoque bayesiano en mente, una metodología estadística para el análisis de datos discretos en su aplicación en problemas estilometría. El análisis estadístico del estilo literario se ha utilizado para caracterizar el estilo de textos y autores, y para ayudar a resolver problemas de atribución de autoría. Estudios anteriores caracterizaron el estilo usando la longitud de las palabras, la longitud de las oraciones, y la proporción de los sustantivos, artículos, adjetivos o adverbios. Los datos que aquí se utilizan van, desde la frecuencia de frecuencias de palabras, hasta el análisis simultáneo de la frecuencia de longitud de palabra y de las palabras funcionales más frecuentes. Todos estos datos son característicos del estilo de autor y al mismo tiempo independiente del contexto en el que escribe. De esta forma, se introduce un análisis bayesiano de la frecuencia de frecuencias de palabras, que tiene una distribución en forma de J inversa con las colas superiores extraordinariamente largas. Se basa en la extensión de la metodología no bayesiana de Sichel para estos datos utilizando el modelo Poisson inversa gaussiana. Los modelos se comprueban mediante la exploración de la distribución a posteriori de los errores de Pearson y por la implementación de controles de consistencia de la distribución predictiva a posteriori. La distribución a posteriori de la inversa gausiana tiene una interpretación útil, al poder ser vista como una estimación de la distribución vocabulario del autor, de la cual se pueden obtener la riqueza y diversidad de la escritura del autor. Se propone también un análisis alternativo basado en la mixtura inversa gaussiana - poisson truncada en el cero, que se obtiene cambiando el orden de la mezcla y el truncamiento. También se propone un análisis de la heterogeneidad de estilo, que es un compromiso entre el modelo de punto de cambio, que busca un cambio repentino de estilo, y el análisi de conglomerados, que no tiene en cuenta el orden. El análisis incorpora el hecho de que partes próximas de un texto tienen más probabilidades de pertenecer al mismo autor que partes del texto más separadas. El enfoque se ilustra volviendo a revisar la atribución de autoría del Tirant lo Blanc. Para el análisis de la heterogeneidad del estilo literario se propone también un análisis estadístico que utiliza simultáneamente diferentes características estilométricas, como la longitud palabra y la frecuencia de las palabras funcionales más frecuentes. Las filas de todas tablas de contingencia se agrupan simultáneamente basandose en una mezcla finita de conjuntos de modelos multinomiales con un estilo homogéneo. Esto tiene algunas ventajas sobre las heurísticas utilizadas en el análisis de conglomerados, ya que incorpora naturalmente el tamaño del texto, la naturaleza discreta de los datos y la dependencia entre las categorías. Todo ello se ilustra a través del análisis del estilo en las obras de teatro de Shakespeare, el Quijote y el Tirant lo Blanc. Finalmente, los problemas de atribución y verificación de autoría, que se tratan normalmente por separado, son tratados de forma conjunta. Esto se hace asumiendo un escenario abierto de clasificación para el problema de la atribución, contemplando la posibilidad de que ninguno de los autores candidatos, con textos conocidos para aprendijaje, es el autor de los textos en disputa. Entonces, el problema de verificación se convierte en un caso especial de problema de atribución. El modelo multinomial bayesiano propuesto permite obtener una solución exacta y cerrada para este problema de atribución de autoría más general. El enfoque al problema de verificación se ilustra mediante la exploración de si un fallo judicial condenatorio podría haber sido escrito por el juez que lo firma o no, y el enfoque al problema de atribución se ilustra revisando el problema de la autoría de los Federalist Papers.
In this thesis I develop statistical methodology for analyzing discrete data to be applied to stylometry problems, always with the Bayesian approach in mind. The statistical analysis of literary style has long been used to characterize the style of texts and authors, and to help settle authorship attribution problems. Early work in the literature used word length, sentence length, and proportion of nouns, articles, adjectives or adverbs to characterize literary style. I use count data that goes from the frequency of word frequency, to the simultaneous analysis of word length counts and more frequent function words counts. All of them are characteristic features of the style of author and at the same time rather independent of the context in which he writes. Here we intrude a Bayesian Analysis of word frequency counts, that have a reverse J-shaped distribution with extraordinarily long upper tails. It is based on extending Sichel's non-Bayesian methodology for frequency count data using the inverse gaussian Poisson model. The model is checked by exploring the posterior distribution of the Pearson errors and by implementing posterior predictive consistency checks. The posterior distribution of the inverse gaussian mixing density also provides a useful interpretation, because it can be seen as an estimate of the vocabulary distribution of the author, from which measures of richness and of diversity of the author's writing can be obtained. An alternative analysis is proposed based on the inverse gaussian-zero truncated Poisson mixture model, which is obtained by switching the order of the mixing and the truncation stages. An analysis of the heterogeneity of the style of a text is proposed that strikes a compromise between change-point, that analyze sudden changes in style, and cluster analysis, that does not take order into consideration. Here an analysis is proposed that strikes a compromise by incorporating the fact that parts of the text that are close together are more likely to belong to the same author than parts of the text far apart. The approach is illustrated by revisiting the authorship attribution of Tirant lo Blanc. A statistical analysis of the heterogeneity of literary style in a set of texts that simultaneously uses different stylometric characteristics, like word length and the frequency of function words, is proposed. It clusters the rows of all contingency tables simultaneously into groups with homogeneous style based on a finite mixture of sets of multinomial models. That has some advantages over the usual heuristic cluster analysis approaches as it naturally incorporates the text size, the discrete nature of the data, and the dependence between categories. All is illustrated with the analysis of the style in plays by Shakespeare, El Quijote, and Tirant lo Blanc. Finally, authorship attribution and verification problems that are usually treated separately are treated jointly. That is done by assuming an open-set classification framework for attribution problems, contemplating the possibility that neither one of the candidate authors, with training texts known to have been written by them is the author of the disputed texts. Then the verification problem becomes a special case of attribution problems.A formal Bayesian multinomial model for this more general authorship attribution is given and a closed form solution for it is derived. The approach to the verification problem is illustrated by exploring whether a court ruling sentence could have been written by the judge that signs it or not, and the approach to the attribution problem illustrated by exploring whether a court ruling sentence could have been written by the judge that signs it or not, and the approach to the attribution problem is illustrated by revisiting the authority attribution

Los clusters de computadores son una alternativa actual usada para el cómputo de aplicaciones científicas. Sin embargo las aplicaciones crecen en complejidad y necesitan más recursos. Unir estos clusters distribuidos usando Internet en un multi-cluster puede permitir lograrlo.
Un problema que se introduce con esta colaboración es un incremento en la heterogeneidad tanto de cómputo como de comunicación, aumentando la complejidad de dicho sistema lo que dificulta su uso.
El objetivo de esta tesis es lograr la reducción del tiempo de ejecución de aplicaciones, originalmente desarrolladas para un cluster, usando eficientemente un multi-cluster.
Proponemos una arquitectura del sistema para lograr una máquina virtual multi-cluster transparente a la aplicación que además la dota de escalabilidad y robustez tolerando los problemas de la comunicación por Internet. Esta arquitectura propone un master-worker jerárquico en el que se introducen elementos claves como los gestores de comunicación que dotan al sistema de robustez, seguridad y transparencia en las comunicaciones entre clusters a través de Internet.
Desarrollamos un modelo de prestaciones para poder hacer una estimación teórica del tiempo de ejecución y de la eficiencia de una aplicación ejecutándose en un multi-cluster. La precisión de las estimaciones es superior al 90%.
Proponemos una metodología que da un procedimiento que define los pasos para realizar la predicción del tiempo de ejecución, para garantizar un umbral de eficiencia seleccionando los recursos adecuados y para guiar a la sintonización de la aplicación encontrando los cuellos de botella de la ejecución.
Clusters of computers represent an alternative for speeding up scientific applications. Nevertheless applications grow in complexity and need more resources. The joint of distributed clusters, using Internet, in a multi-cluster can allow the resources obtainment.
A problem on reaching an effective collaboration from multiple clusters is the increase on the computation and communication heterogeneity. This factor increases the complexity of such a system bringing difficulties in its use.
The target of this thesis is to attain the reduction of the execution time of applications, originally written for a single cluster, efficiently using a multi-cluster. In order to reach this goal we propose a system architecture, an analytical model and a performance and tuning methodology.
The proposed system architecture aims to obtain a multi-cluster virtual machine, transparent to the application and that provides scalability and robustness, tolerating possible faults in the Internet communication between clusters. This architecture is organized around a hierarchical master-worker with communication managers. Communication managers are a key element responsible for the robustness, security and transparency in the communication between clusters using Internet.
The analytical performance model was developed to estimate the execution time and efficiency of an application executing in a multi-cluster. The precision on the estimations are over 90%.
The proposed performance prediction and application tuning methodology is a procedure that defines the steps to predict the execution time and efficiency, to guarantee an efficiency threshold and to guide on the application tuning, evaluating the execution bottlenecks.

Recientes avances en im agenes t ermicas (LWIR) han permitido su uso en aplicaciones m as all a del ambito militar. Actualmente, esta nueva familia de sensor esta siendo incluida en diversas aplicaciones tanto t ecnicas como cient cas. Este tipo de sensores facilitan tareas tales como: detecci on de peatones, puntos calientes, detecci on de cambios de temperatura, entre otros. Caracter sticas que pueden mejorar signi cativamente el desempeo de un sistema, especialmente cuando hay interacci on con humanos. Por ejemplo, aplicaciones de v deo vigilancia, detecci on de peatones, an alisis de postura. En esta tesis se plantea entre otras la siguiente pregunta de investigaci on: Podr a un par de sensores operando en diferentes bandas del espectro electromagn etico, como el visible e infrarrojo t ermico, proporciona informaci on de profundidad? Si bien es una cuesti on compleja, nosotros demostramos que un sistema de estas caracter sticas es posible. Adem as, de discutir sus posibles ventajas, desventajas y oportunidades potenciales. La fusi on y correspondencia de los datos procedentes de diferentes sensores, como las emisiones registradas en la banda visible e infrarroja, representa un reto atractivo, ya que se ha demostrado que aquellas se~nales est an d ebilmente correlacionadas. Por lo tanto, muchas t ecnicas tradicionales de procesamiento de im agenes y visi on por computadora son inadecuadas, requiriendo ajustes para su correcto funcionamiento. En esta investigaci on se realizo un estudio experimental comparando diferentes funciones de costos multimodal, y t ecnicas de correspondencia, a n de construir un sistema est ereo multimodal. Tambi en, se identi c o el problema com un entre est ereo visible/ visible y infrarrojo/visible, particularmente en ambientes al aire libre. Entre las contribuciones de esta tesis se encuentra; el aislamiento de las diferentes etapas que componen un sistema est ereo multimodal. Esta arquitectura es gen erica a diferentes niveles, tanto computacional, funcional y estructural, permitiendo su extensi on a esquemas mas complejos tales como fusi on de alto nivel (sem antica) y de orden superior (supuestos). El enfoque propuesto est a destinado a explorar nuevos m etodos de correspondencia est ereo, pasando de una soluci on escasa a una densas (tanto en disparidad como en mapas de profundidad). Adem as, se ha incluido informaci on de contexto en forma de asunciones y restricciones. Finalmente, esta disertaci on muestra un promisorio camino hacia la integraci on de m ultiples sensores.
Recent advances in thermal infrared imaging (LWIR) has allowed its use in applications beyond of military domain. Nowadays, this new sensor family is included in diverse technical and scienti c applications. They o er features that facilitate tasks, such as detection of pedestrians, hot spots, di erences in temperature, among others, which can signi cantly improve the performance of a system where the persons are expected to play the principal role. For instance, video surveillance applications, monitoring, and pedestrian detection. During this dissertation is stated the next question: Could a couple of sensors measuring di erent bands of the electromagnetic spectrum, as the visible and thermal infrared, provides depth information? Although is a complex question, we shows that a system of those characteristics is possible as well as their advantages, drawbacks, and potential opportunities. The fusion and matching of data coming from di erent sensors, as the emissions registered at visible and infrared band, represents a special challenge, because it has been showed that theses signals are weak correlated. Indeed, they are uncorrelated. Therefore, many traditional techniques of image processing and computer vision are not helpful, requiring adjustments for their correct performs in every modality. In this research is performed a experimental study that compares di erent cost functions and matching approaches, in order to build a multimodal stereo system. Furthermore, are identi ed the common problem between visible/visible and infrared/visible stereo, special in the outdoor scenes. A contribution of this dissertation is the isolation achieved, between the di erent stage that compose a multimodal stereo system. Our framework summarizes the architecture of a generic stereo algorithm, at di erent levels: computational, functional, and structural, which is successful because this can be extended toward high-level fusion (semantic) and high-order (prior). The proposed framework is intended to explore novel multimodal stereo matching approaches, going from sparse to dense representation (both disparity and depth maps). Moreover, context information is added in form of priors and assumptions. Finally, this dissertation shows a promissory way toward the integration of multiple sensors for recovering three-dimensional information.

Los estudios desarrollados se enmarcan, dentro de la teoría de grafos, en el análisis de condiciones suficientes para obtener algunas medidas de conectividad optima.se han estudiado condiciones de tipo mixto para el caso de dígrafos bipartitos que mejoran los conocidos hasta el momento.se han estudiado la t-distancia conectividad, construyendo dígrafos que muestran la independencia de los parámetros que le definen y obteniendo cotas superiores sobre el diámetro que garantizan valores óptimos para las mismas.se ha introducido el concepto de diámetro condicional que ha permitido la ampliación de las cotas conocidas sobre el diámetro, así como la mejora de algunas de ellas. Por último se han obtenido nuevas condiciones de tipo chartrand para la conectividad y la superconectividad de dígrafos s-geodeticos.

DE LA TESIS
Si un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a l'estudi del conjunt de grafs que admeten etiquetaments super edge magic així com també a desenvolupar relacions entre aquest tipus d'etiquetaments i altres etiquetaments molt estudiats com ara els etiquetaments graciosos i armònics, entre d'altres. De fet, els etiquetaments super edge magic serveixen com nexe d'unió entre diferents tipus d'etiquetaments, i per tant moltes relacions entre etiquetaments poden ser obtingudes d'aquesta forma.
A la tesis també es proposa una nova manera de pensar en la ja famosa conjectura que afirma que tots els arbres admeten un etiquetament super edge magic. Això és, per a cada arbre T trobam un arbre super edge magic T' que conté a T com a subgraf, i l'ordre de T'no és massa gran quan el comparam amb l'ordre de T .
Un problema de naturalesa similar al problema anterior, en el sentit que intentam trobar un graf super edge magic lo més petit possible i que contengui a cert tipus de grafs, i que ha estat completament resolt a la tesis es pot enunciar com segueix.
Problema: Quin és un graf conexe G super edge magic d'ordre més petit que conté al graf complet 
Kn com a subgraf?.
La solució d'aquest problema és prou interessant ja que relaciona els etiquetaments super edge magic amb un concepte clàssic de la teoria aditiva de nombres com són els conjunts de Sidon dèbils, també coneguts com well spread sets.De fet, aquesta no és la única vegada que el concepte de conjunt de Sidon apareix a la tesis. També quan a la tesis es tracta el tema de la deficiència , els conjunts de Sidon són d'una gran utilitat. La deficiencia super edge magic d'un graf és una manera de mesurar quan d'aprop està un graf de ser super edge magic. Tècnicament parlant, la deficiència super edge magic d'un graf 
G es defineix com el mínim número de vèrtexs aillats amb els que hem d'unir
G perque el graf resultant sigui super edge magic. Si d'aquesta manera no aconseguim mai que el graf resultant sigui super edge magic, aleshores deim que la deficiència del graf és infinita. A la tesis, calculam la deficiència super edge magic de moltes families importants de grafs, i a més donam alguns resultats generals, sobre aquest concepte.
Per acabar aquest document, simplement diré que al llarg de la tesis molts d'exemples que completen la tesis, i que fan la seva lectura més agradable i entenible han estat introduits.
OF THESIS
If a graph G admits a super edge magic labeling, then G is called a super edge magic graph. The thesis is mainly devoted to study the set of graphs which admit super edge magic labelings as well as to stablish and study relations with other well known labelings.
For instance, graceful and harmonic labelings, among others, since many relations among labelings can be obtained using super edge magic labelings as the link.
In the thesis we also provide a new approach to the already famous conjecture that claims that every tree is super edge magic. We attack this problem by finding for any given tree T a super edge magic tree T' that contains T as a subgraph, and the order of T'is not too large if we compare it with the order of T .
A similar problem to this one, in the sense of finding small host super edge magic graphs for certain type of graphs, which is completely solved in the thesis, is the following one.
Problem: Find the smallest order of a connected super edge magic graph G that contains the complete graph Kn as a subgraph.
The solution of this problem has particular interest since it relates super edge magic labelings with the additive number theoretical concept of weak Sidon set, also known as well spread set. In fact , this is not the only time that this concept appears in the thesis.
Also when studying the super edge magic deficiency, additive number theory and in particular well spread sets have proven to be very useful. The super edge magic deficiency of graph is a way of measuring how close is graph to be super edge magic.
Properly speaking, the super edge magic deficiency of a graph G is defined to be the minimum number of isolated vertices that we have to union G with, so that the resulting graph is super edge magic. If no matter how many isolated vertices we union G with, the resulting graph is never super edge magic, then the super edge magic deficiency is defined to be infinity. In the thesis, we compute the super edge magic deficiency of may important families of graphs and we also provide some general results, involving this concept.
Finally, and in order to bring this document to its end, I will just mention that many examples that improve the clarity of the thesis and makes it easy to read, can be found along the hole work.

El reconeixement d'objectes és potser la tasca més important que un sistema autònom, ja sigui biològic o artificial, necessita realitzar. En el context de la visió humana, això s'aconsegueix parcialment a través del reconeixement del color de les superfícies malgrat els canvis en la distribució espectral de la llum, propietat anomenada constància de color. El reconeixement correcte del color de les superfícies és pot realitzar adequadament mitjançant la correspondència entre categories de color sense la necessitat d'ajustar exactament els mateixos colors, aleshores la constància de color categòrica juga probablement un paper important per tal d'aconseguir amb èxit el reconeixement d'objectes. El principal objectiu d'aquest treball és estudiar la relació entre la constància de color i la percepció categòrica del color. Estudis anteriors de constància de color han mostrat la influència de factors tals com les propietats espai-cromàtiques de l'entorn, particularitats individuals dels observadors, semàntica, etc... Malgrat tot, aquestes influències només s'han estudiat breument de forma sistemàtica. Per solucionar-ho, hem desenvolupat una nova aproximació a la constància de color, la qual inclou la percepció categòrica dels individus, l'estructura categòrica de l'entorn, i les seves interrelacions, resultant en una caracterització més comprensiva del fenomen. En el nostre estudi, primer hem desenvolupat un nou mètode per tal d'analitzar l'estructura categòrica 3D de l'espai de color, la qual ens ha permès caracteritzar la percepció categòrica de cada individu i també quantificar les variacions entre individus en termes de la forma i la localització dels centroides de les regions 3D categòriques. Seguidament, hem desenvolupat un nou paradigma de constància de color, anomenat "chromatic setting", el qual permet mesurar de forma precisa la localització de nou punts categòricament rellevants en l'espai de color sota una ill.luminació envolvent. Adicionalment, hem derivat a partir d'aquestes mesures un nou índex de constància de color, el qual té en compte la magnitud i la orientació cromàtica de l'il.lumiant, influències de la memòria i les interrelacions entre colors, i també un model d'assignació de noms de color ajustat a l'estat d'adaptació de cada observador. A partir dels nostres resultats concloem: (1) Existeixen àmplies variacions entre individus respecte l'estructura categòrica de l'espai de color, i pertant l'abilitat d'assignar noms de color varia significativament però aquesta no està ben predita per les abilitats discriminatives de baix nivell; (2) L'anàlisi de l'espai mitjà d'assignació de noms de color suggereix la necessitat d'afegir tres nous "basic colour terms" ("turquoise", "lilac" i "lime" ) per tal d'optimitzar la comunicació de color; (3) El "chromatic setting" ha millorat la precisió dels models lineals més complexos de constància de color, així suggerint que altres mecanismes que no pas els d'adaptació al guany dels cons poden ser més adequats per tal d'explicar el fenomen de la constància de color; (4) L'estructura categòrica de l'espai de color és en general estable sota canvis d'il.luminant quan s'usen entorns categòricament balancejats; (5) Existeix inconstància de color per entorns categòricament no balancejats i pertant indicant que la informació categòrica percebuda en les etapes inicials de l'adaptació pot condicionar la percepció categòrica posterior.
To recognise objects is perhaps the most important task an autonomous system, either biological or artificial needs to perform. In the context of human vision, this is partly achieved by recognizing the colour of surfaces despite changes in the wavelength distribution of the illumination, a property called colour constancy. Correct surface colour recognition may be adequately accomplished by colour category matching without the need to match colours precisely, therefore categorical colour constancy is likely to play an important role for object identification to be successful. The main aim of this work is to study the relationship between colour constancy and categorical colour perception. Previous studies of colour constancy have shown the influence of factors such the spatio-chromatic properties of the background, individual observer's performance, semantics, etc. However there is very little systematic study of these influences. To this end, we developed a new approach to colour constancy which includes both individual observers' categorical perception, the categorical structure of the background, and their interrelations resulting in a more comprehensive characterization of the phenomenon. In our study, we first developed a new method to analyse the categorical structure of 3D colour space, which allowed us to characterize individual categorical colour perception as well as quantify inter-individual variations in terms of shape and centroid location of 3D categorical regions. Second, we developed a new colour constancy paradigm, termed chromatic setting, which allows measuring the precise location of nine categorically-relevant points in colour space under immersive illumination. Additionally, we derived from these measurements a new colour constancy index which takes into account the magnitude and orientation of the chromatic shift, memory effects and the interrelations among colours and a model of colour naming tuned to each observer/adaptation state. Our results lead to the following conclusions: (1) There exists large inter-individual variations in the categorical structure of colour space, and thus colour naming ability varies significantly but this is not well predicted by low-level chromatic discrimination ability; (2) Analysis of the average colour naming space suggested the need for an additional three basic colour terms (turquoise, lilac and lime) for optimal colour communication; (3) Chromatic setting improved the precision of more complex linear colour constancy models and suggested that mechanisms other than cone gain might be best suited to explain colour constancy; (4) The categorical structure of colour space is broadly stable under illuminant changes for categorically balanced backgrounds; (5) Categorical inconstancy exists for categorically unbalanced backgrounds thus indicating that categorical information perceived in the initial stages of adaptation may constrain further categorical perception.

Probablement, el sistema-en-xip encastat futur estarà compost per desenes o centenars de nuclis de Propietat Intel·lectual heterogenis que executaran una aplicació paral·lela o fins i tot diverses aplicacions que funcionin en paral·lel. Aquests sistemes seran possible gràcies a l’evolució constant de la tecnologia que segueix la llei de Moore, que ens durà a integrar més transistors en un únic dau, o el mateix nombre de transistors en un dau més petit. En els sistemes MPSoC encastats, les xarxes intenrades (NoC) poden proporcionar una infraestructura de comunicació flexible, en què diversos components, com ara els nuclis microprocessadors, MCU, DSP, GPU, memòries i altres components IP, poden estar interconnectats. En primer lloc, en aquesta tesi presentem un procés de desenvolupament complet creat per desenvolupar MPSoC en clústers reconfigurables tot complementant el procés de desenvolupament SoC actual amb passos addicionals per admetre la programació paral·lela i l’optimització del software. Aquest treball explica de manera sistemàtica els problemes i les solucions per aconseguir un MPSoC basat en FPGA seguint el nostre flux sistemàtic, i s’ofereixen eines i tècniques per desenvolupar aplicacions paral·leles per a aquests sistemes. D’altra banda, descrivim diversos models de programació per a MPSoC encastats i proposem adoptar MPI per a aquests sistemes, i mostrem algunes implementacions creades en aquesta tesi amb arquitectures de memòria compartida i distribuïda. Finalment, ens centrem en la sobrecarrega de temps que produeix la llibreria MPI i intentarem trobar solucions per tal de minimitzar aquesta sobrecàrrega i, per tant, poder accelerar l’execució de l’aplicació, descarregant algunes parts del software stack al controlador d’interfície de la xarxa.
Future embedded System-on-Chip (SoC) will probably be made up of tens or hundreds of heterogeneous Intellectual Properties (IP) cores, which will execute one parallel application or even several applications running in parallel. These systems could be possible due to the constant evolution in technology that follows the Moore’s law, which will lead us to integrate more transistors on a single dice, or the same number of transistors in a smaller dice. In embedded MPSoC systems, NoCs can provide a flexible communication infrastructure, in which several components such as microprocessor cores, MCU, DSP, GPU, memories and other IP components can be interconnected. In this thesis, firstly, we present a complete development process created for developing MPSoCs on reconfigurable clusters by complementing the current SoC development process with additional steps to support parallel programming and software optimization. This work explains systematically problems and solutions to achieve a FPGA-based MPSoC following our systematic flow and offering tools and techniques to develop parallel applications for such systems. Additionally, we show several programming models for embedded MPSoCs and propose the adoption of MPI for such systems and show some implementations created in this thesis over shared and distributed memory architectures. Finally, the focus will be set on the overhead produced by MPI library and on trying to find solutions to minimize this overhead and then be able to accelerate the execution of the application, offloading some parts of the software stack to the Network Interface Controller.

En aquest treball s’explora el reconeixement d’accions humanes i l'estimació de la seva postura en seqüències d'imatges. A diferència de les tècniques tradicionals d’aprenentatge a partir d’imatges 2D o vídeo amb la sortida anotada, en aquesta Tesi abordem aquest objectiu amb la informació de moviment 3D capturat, que ens ajudar a tancar el llaç entre les característiques 2D de la imatge i les interpretacions sobre el moviment humà.
En este trabajo se exploran el reconocimiento de acciones humanas y la estimación de su postura en secuencias de imágenes. A diferencia de las técnicas tradicionales de aprendizaje a partir de imágenes 2D o vídeo con la salida anotada, en esta Tesis abordamos este objetivo con la información de movimiento 3D capturado, que nos ayudar a cerrar el lazo entre las caracteríssticas 2D de la imagen y las interpretaciones sobre el movimiento humano.
In this work, we explore human action recognition and pose estimation problems. Different from traditional works of learning from 2D images or video sequences and their annotated output, we seek to solve the problems with additional 3D motion capture information, which helps to fill the gap between 2D image features and human interpretations.

Puesto que los sistemas informáticos son cada vez más vulnerables a actividades deshonestas, los mecanismos tradicionales de seguridad son todavía necesarios, pero no suficientes. Es necesario elaborar nuevos métodos de detección y de respuesta de manera que sea posible detener acciones de ataque tan pronto como sean realizadas. En esta tesis se presenta el diseño de una arquitectura de carácter general que pretende ser utilizada tanto para la realización de tareas de análisis y verificación de políticas de seguridad en red, como para controlar y configurar -sin anomalias ni errores de confguración- componentes de seguridad preventivos y de vigilancia. Se presenta también en esta tesis un mecanismo de respuesta basado en librerías de contramedidas. El objetivo de este mecanismo es ayudar al administrador a escoger posibles respuesta tan pronto como las acciones de ataque vayan siendo detectadas. Por último, se introduce también en esta tesis el diseño de una infrastructura para la comunicación entre los componentes de nuestra plataforma, y un mecanismo para la protección de dichos componentes. Todas las proposiciones y propuestas han sido implementadas y evaluadas a lo largo de nuestro trabajo. Los resultados obtenidos son presentados en las respectivas secciones de esta disertación.
Esta tesis ha sido principalmente financiada por la Agencia de Gestión y Ayudas Universitarias y de Investigación (AGAUR) del Departamento de Universidades, Investigación y Sociedad de la Información (DURSI) de la Generalitat de Catalunya (num. de referencia 2003FI00126). El trabajo ha sido conjuntamente realizado en la Universitat Autònoma de Barcelona y la Ecole Nationale Superieure des Télécommunications de Bretagne.
Palabras clave: Políticas de seguridad, detección de intrusos, contramedidas, correlación de eventos, comunicación publish/subscribe, control de acceso, protección de componentes.
Since computer infrastructures are currently getting more vulnerable than ever, traditional security mechanisms are still necessary but not suficient. We need to design effective response techniques to circumvent intrusions when they are detected. We present in this dissertation the design of a platform which is intended to act as a central point to analyze and verify network security policies, and to control and configure -without anomalies or errors- both prevention and detection security components. We also present in our work a response mechanism based on a library that implements different types of countermeasures. The objective of such a mechanism is to be a support tool in order to help the administrator to choose, in this library, the appropriate counter-measure when a given intrusion occurs. We finally present an infrastructure for the communication between the components of our platform, as well as a mechanism for the protection of such components. All these approaches and proposals have been implemented and evaluated. We present the obtained results within the respectives sections of this dissertation.
This thesis has mainly been funded by the Agency for Administration of University and Research Grants (AGAUR) of the Ministry of Education and Universities (DURSI) of the Government of Catalonia (reference number 2003FI00126). The research was jointly carried out at the Universitat Autònoma de Barcelona and at the Ecole Nationale Superieure des Télécommunications de Bretagne.
Keywords: Security policies, intrusion detection, response, counter-measures, event correlation, communication publish/subscribe, access control, components protection.

El disseny d'un controlador es un procés que requereix adquirir y processar informació amb la finalitat de dissenyar un sistema de control satisfactori. A més a més és àmpliament reconegut el fet de que si s'afegeix nova informació en el procés de disseny d'un controlador, és possible millorar el funcionament del controlador obtingut. Aquesta és la filosofia existent darrere del control adaptatiu. No obstant el concepte d'informació referit al problema del disseny de reguladors, si bé està molt estes, no disposa d'una formalització clara ni unificadora degut a la mancança d'un marc conceptual.
Aquesta tesi aborda el problema del disseny de controladors des d'un punt de vista de la informació requerida per aconseguir aquesta finalitat. Les aportacions de la tesi es divideixen en dues parts.
En la primera part l'objectiu és caracteritzar el concepte d'informació dins del problema del disseny de controladors, així com analitzar totes les fonts d'informació disponibles. Aquest objectiu s'aconsegueix mitjançant el desenvolupament d'un marc conceptual en el qual es pot establir relacions fonamentals necessàries per augmentar la informació dels elements del problema de control. En un segon pas, aquest marc ja establert s'utilitza par analitzar i comparar les tècniques del control adaptatiu clàssic amb el control iteratiu. El marc permet comparar ambdues tècniques de disseny de controladors en funció de la gestió de la informació que cadascuna d'elles realitza, proporcionant així un punt de referència per comparar diverses maneres de gestionar la informació per al disseny de controladors.
En la segona part de la tesi s'aborda el problema de la validació de la informació existent en un model. L'objectiu és ser capaç de validar un model de manera que el resultat de la validació no sigui simplement un resultat binari de "validat/invalidat", si no que es donen guies de decisió sobre com gestionar la informació dels elements del problema de control amb la finalitat d'augmentar la informació dels models. Per aconseguir aquest fi es desenvolupa l'algorisme de validació FDMV (Frequency Domain Model Validation) que permet que el resultat de la validació d'un model sigui dependent de la freqüència. D'aquest fet es conclou que un mateix model pot ser validat per a un cert rang de freqüències mentre que el mateix model pot ser invalidat per a un altre rang de freqüències diferents. Aquesta validació dependent de la freqüència permet millorar la gestió de la informació en lo referent a 1) disseny experimental per a una nova identificació, 2) selecció de l'ordre del model adequat i, 3) selecció de la amplada de banda del controlador acceptable per l'actual model. L'algorisme FDMV es mostra com una eina especialment apropiada per a ser emprada en tècniques de control iteratiu.
El diseño de un controlador es un proceso que requiere adquirir y procesar información con el fin de diseñar un sistema de control satisfactorio. Además es ampliamente reconocido el hecho de que si se añade nueva información en el proceso de diseño de un controlador, es posible mejorar el desempeño del controlador obtenido. Esta es la filosofía existente detrás del control adaptativo. Sin embargo el concepto de información referido al problema de diseño de reguladores, si bien está muy extendido, no dispone de una formalización clara ni unificada al carecer de un marco conceptual.
En esta tesis se aborda el problema del diseño de controladores desde un punto de vista de la información requerida para tal fin. Las aportaciones de la tesis se dividen en dos partes.
En la primera parte el objetivo es caracterizar el concepto de información cuando hablamos del problema del diseño de controladores, así como analizar todas las fuentes de información disponibles. Esto se consigue mediante el desarrollo de un marco conceptual en el cual se pueden establecer relaciones fundamentales necesarias para aumentar la información de los elementos del problema de control. En un segundo paso, dicho marco ya establecido se utiliza para analizar y comparar las técnicas del control adaptativo clásico con el control iterativo. El marco permite comparar ambas técnicas de diseño de controladores en función de la gestión de la información que cada una de ellas realiza, proporcionando así un punto de referencia para comparar diversas maneras de gestionar la información para el diseño de controladores.
En la segunda parte de la tesis se aborda el problema de la validación de la información existente en un modelo. El objetivo es ser capaz de validar un modelo de manera tal que el resultado de la validación no sea simplemente un resultado binario de "validado/invalidado", si no que aporte guías de decisión sobre como gestionar la información de los elementos del problema de control con el fin de aumentar la información del modelo. Para tal fin se desarrolla el algoritmo de validación FDMV (Frequency Domain Model Validation) que permite que el resultado de la validación de un modelo sea dependiente de la frecuencia. De ello se sigue que un mismo modelo puede ser validado para cierto rango de frecuencias mientras que el mismo modelo puede ser invalidado para otro rango de frecuencias diferentes. Esta validación dependiente de la frecuencia permite mejorar la gestión de la información en lo referente al i) diseño experimental para una nueva identificación, ii) selección del orden del modelo adecuado y iii) selección del ancho de banda del controlador aceptable por el modelo a mano. El algoritmo FDMV se muestra como una herramienta especialmente apropiada para ser empleada en técnicas de control iterativo.

Aquesta tesi analitza diversos aspectes de les motivacions individuals i de les seves implicacions en processos econòmics. Específicament, analitzo en detall criteris normatius que poden aplicar els individus com són els de justícia i reciprocitat. En la Introducció defineixo l'ús que en faig de conceptes com la reciprocitat, la justícia, la "dependència del menú" i els "punts de referència" donat que s'empren en el desenvolupament dels diferents capítols. També es descriu la metodologia emprada, que consisteix en alguns models teòrics sobre el comportament dels individus en situacions estratègiques, incorporant elements de la Teoria dels Jocs i l'ús de la metodologia experimental. En el segon capítol, " El concepte de justícia de Rabin i la provisió privada de béns públics", analitzo en detall les implicacions de la teoria de Rabin (1993) sobre el comportament estratègic d'individus. Aquest model introdueix en la funció d'utilitat , a més dels pagaments econòmics que un individu obté, aspectes psicològics com el sentit de justícia en les relacions econòmiques amb altres individus. En aquest capítol examino les implicacions d'una extensió de la teoria a un camp a on existeix una acumulació de resultats experimentals en contradicció amb el comportament predit pels models estàndard de la teoria dels jocs. Mostro que la teoria d'en Rabin és consistent amb el que s'anomena "splitting" però inconsistent amb el que es coneix com a "efecte MPCR". El tercer capítol, "Punts de referència i reciprocitat negativa en jocs seqüencials simples", analitza la influència que poden tenir certs vectors de pagaments no disponibles en un moment de decisió, anomenats "punts de referència", sobre la preferència per un altre conjunt de vectors de pagaments. Això es connecta amb l'atribució de certes intencions a altres subjectes quan trien determinats cursos d'acció en el joc. Mitjançant la utilització d'experiments s'obtenen resultats que confirmen la importància dels punts de referència en les consideracions de reciprocitat que empren els individus. El quart capítol, " Aspectes distribucionals i els punts de referència", analitza alguns aspectes que poden combinar-se amb els punts de referència en la atribució d'intencions. Aquests aspectes són: el pagament que podia rebre un agent en el punt de referència, el seu pagament relatiu a l'altre agent i, finalment, el pagament conjunt que podien obtenir els dos agents en el punt de referència. Els resultats experimentals obtinguts mostren que cap d'aquests efectes pot explicar per ell mateix els resultats. Finalment, el cinquè capítol, " Els joc del dilema dels presoners en forma seqüencial: Reciprocitat i efectes de dimensió del grup" estudia les reaccions dels individus a certes decisions d'altres individus del procés i els canvis d'aquestes reaccions amb la dimensió del grup. Els resultats experimentals obtinguts , mostren que el comportament observat és consistent amb consideracions de reciprocitat i d'aversió a la desigualtat.
This thesis analyzes several aspects of the motivations that drive individuals and their implications in economic processes. In particular, I analyze in detail normative criteria that individuals apply such as those of fairness and reciprocity. In the Introduction I define the use I make of the concepts of reciprocity, fairness, menu dependence and reference points that will be used in the course of the different chapters. The methodology developed in this thesis employs some theoretical models on the behavior of individuals in strategic interactions, using elements of Game Theory and Experimental Economics. In the second chapter, "On Rabin's Concept of Fairness and the Private Provision of Public Goods", I analyze in detail the implications of Rabin's (1993) theory of individual behavior and its implications. This model introduces, apart from the economic payoffs that the individual obtains in a strategic interaction, psychological phenomena, mainly a sense of fairness in the relation with other agents. In this chapter I analyze the implications of an extended version of this theory to a field where there exists a vast amount of experimental evidences contradicting the behavior predicted by standard game theoretical models. I show that Rabin's theory is consistent with one piece of evidence repeatedly found in experiments, the so call "splitting". I also show that the model is inconsistent with another piece of evidence in the field, the "MPCR effect". The third chapter, "Reference Points and Negative Reciprocity in Simple Sequential Games", analyzes the influence that certain payoff vectors, the "reference points", not attainable at that time, may have on the preference by other payoff vectors. This is connected with the attribution of certain intentions to the other players when selecting some courses of action. By using experiments I obtain results that confirm the importance of these reference points in the reciprocity considerations that individuals apply. Chapter four , "Distributional Concerns and Reference Points", analyzes some aspects that may interact with the reference points in the attributions of intentions. These aspects are the payoff to the agent from a given course of action, his/her relative payoff and the joint payoff. The experimental results show that none of these elements is able to explain by itself the results. Finally, the fifth chapter, "The Sequential Prisoner's Dilemma Game: Reciprocity and Group Size Effects" analyzes how aspects of the individual motivations interact with social aspects. In particular it studies how the reactions of individuals change with the dimension of the group in certain processes. The experimental results obtained show that in the prisoner's dilemma game (two-person and three-person games) the behavior of subjects may be consistent with reciprocity considerations and with inequality aversion considerations.

Un component important de molts sistemes de distribució és el càlcul de les rutes dels vehicles per servir els clients. El Vehicle Routing Problem (VRP) proporciona el marc teòric per tractar aquest tipus de problemes logístics relacionats amb la distribució física de béns. Per la seva complexitat i aplicabilitat, aquest tipus de problemes logístics es troba entre les línies de recerca més populars en optimització combinatòria. Aquesta tesi de doctorat té com a objectiu la introducció de tres metodologies diferents per resoldre el VRP. Aquestes metodologies han estat especialment dissenyades per ser flexibles, en el sentit que poden ser utilitzades, amb adaptacions menors, per resoldre diferents variants del VRP presents en casos d’aplicació industrial. En les tres metodologies descrites en aquest treball s’utilitzen diferents tècniques per aconseguir la flexibilitat, l’eficiència i la robustesa desitjades. Constraint Programming (CP) ha estat escollit com a paradigma de modelat per descriure les principals restriccions presents en el VRP. CP proporciona la flexibilitat desitjada per les tres metodologies, atès que afegir restriccions addicionals presents en molts casos d’aplicació real només afecta al modelat del problema, però no a la definició dels algorismes de cerca. En les dues primeres metodologies descrites, el model de CP només s’utilitza per comprovar la factibilitat de les solucions durant la cerca. La tercera metodologia presenta un model més ric del VRP que permet tractar diferents variants del problema. En aquest cas, la cerca es realitza i es controla fent servir els mecanismes que CP proporciona. La Relaxació Lagrangiana (LR) i una versió probabilística de l’heurística Clarke and Wright Savings (RCWS) s’utilitzen amb una finalitat molt específica dins de les metodologies. LR s’utilitza per minimitzar la distància total recorreguda pels vehicles, mentre que la RCWS es fa servir per calcular una solució inicial de bona qualitat. Ambdós mètodes proporcionen una aproximació eficient als problemes respectius. A més, la utilització de LR permet reduir la complexitat computacional dels processos de cerca local i, d’aquesta manera, redueix el temps computacional necessari per resoldre el VRP. Totes les metodologies es basen en la metaheurística coneguda com Variable Neighborhood Search (VNS). El VNS està format per una família d’algorismes que aprofiten sistemàticament la idea de canviar el veïnat explorat al voltant d’una solució, tant en el procés de cerca per trobar un mínim local com en el procés de pertorbació, per escapar de la vall corresponent. Malgrat que és un mètode bastant estès, hi ha pocs exemples d’aplicació en el VRP. En tot cas, fins i tot els mètodes VNS més simples han aconseguit bons resultats quan han estat aplicats en aquest problema. Aquesta tesi té com a objectiu contribuir en la recerca de l’aplicació de la metaheurística VNS en el VRP. Aquesta ha estat escollida com a marc en el que integrar les tècniques mencionades. Així, la metaheurística s’utilitza per guiar la cerca, mentre que l’eficiència desitjada s’aconsegueix mitjançant els mètodes que s’hi integren. D’altra banda, utilitzar CP com a paradigma de modelat proporciona la flexibilitat requerida. Aquesta característica és especialment rellevant en el cas de la darrera metodologia descrita. En aquest cas, la cerca de CP es guia mitjançant una combinació de les metaheurístiques VNS i Large Neighborhood Search (LNS). Aquesta metodologia representa una primera aproximació a la resolució eficient de problemes VRP més complexos, similars a casos d’aplicació real.
An important component of many distribution systems is routing vehicles to serve customers. The Vehicle Routing Problem (VRP) provides a theoretical framework for approaching this class of logistics problems dealing with physical distribution. Because of its complexity and applicability, this class of logistics problems is among the most popular research areas in combinatorial optimization. This PhD. Thesis is aimed to introduce three different yet related hybrid methodologies to solve the VRP. These methodologies have been especially designed for being flexible in the sense that they can be used, with minor adaptations, for solving different variants of the VRP present in industrial application cases. In the three methodologies described in this work, different technologies are used to achieve the desired flexibility, efficiency, and robustness. Constraint Programming (CP) has been chosen as the modeling paradigm to describe the main constraints involved in the VRP. CP provides the pursued flexibility for the three methodologies, since adding side constraints present in most real application cases becomes a modeling issue and does not affect the search algorithm definition. In the first two hybrid methodologies, the CP model is used to check solution's feasibility during search. The third methodology presents a richer model for the VRP capable of tackling different problem variants. In this case, the search is performed and controlled from a CP perspective. Lagrangian Relaxation (LR) and a probabilistic version of the Clarke and Wright Savings (CWS) heuristic are used for specific purposes within the proposed methodologies. The former is used for minimizing the total traveled distance and the latter to provide a good initial solution. Both methods provide an efficient approach to the respectively faced problems. Moreover, the use of LR permits reducing the computational complexity of the performed local search processes and therefore reduces the required computational time to solve the VRP. All methodologies are based on the so-called Variable Neighborhood Search (VNS) metaheuristic. The VNS is formed by a family of algorithms that exploits systematically the idea of neighborhood changes both in the search phase to find a local minimum, and in perturbation phase, to escape from the corresponding valley. Although it is an extended method, there are few examples of its application to the VRP. However, interesting results have been obtained even applying the simplest VNS algorithms to this problem. The present thesis is aimed to contribute to the current research on the application of the VNS metaheuristic to the VRP. It has been chosen as the framework where the mentioned techniques are embedded. Hence, the metaheuristic is used to guide the search, while the desired efficiency is provided by the composing methods. On the other hand, using CP as the modeling paradigm provides the required flexibility. This characteristic is enhanced in the last described methodology. In this case, the CP search is guided by a combination of the VNS and the Large Neighborhood Search (LNS) metaheuristics. This methodology represents an initial approach for tackling efficiently more complex and richer VRP, similar to real application cases.

En los clusters de altas prestaciones, los requerimientos actuales de las comunicaciones de las aplicaciones, como el patrón de tráfico, el volúmen de comunicaciones entre otras, pueden cambiar a lo largo del tiempo y son difíciles de predecir. Estas necesidades generalmente exceden o no se corresponden con los recursos disponibles realmente, lo cual conlleva a una situación de desbalanceo de los recursos, congestión en la red, reducción del throughput y un incremento considerable en los valores de latencia de los mensajes. Todo esto conlleva una degradación general del rendimiento de todo el sistema computacional. Los estudios de las aplicaciones paralelas demuestran que estas tienen un comportamiento repetitivo. Además, esta repetitividad puede detectarse y caracterizarse a través de unas fases representativas. Este trabajo propone un Algoritmo de Encaminamiento Predictivo y Distribuido (PR-DRB). Este nuevo método propone controlar la congestión de la red de manera gradual basándose en la expansión controlada de caminos, la distribución del tráfico, la repetitividad en las aplicaciones paralelas y el encaminamiento adaptativo especulativo; de manera a mantener los valores de latencia controlados. PR-DRB monitorea la latencia de los mensajes en los encaminadores y guarda las mejores soluciones adaptativas encontradas a una situación de congestión. Esto se realiza de manera a re aplicar estas mejores soluciones de manera rápida ante situaciones similares futuras. Fueron desarrollados varios experimentos que generen congestión de tráfico a fin de evaluar el rendimiento de la propuesta, y se han logrado mejoras importantes en el rendimiento global del sistema.
In high performance clusters, current parallel application communication needs, such as traffic pattern, communication volume, etc., change along time and are difficult to know in advance. Such needs often exceed or do not match available resources causing resource use imbalance, network congestion, throughput reduction and message latency increase, thus degrading the overall system performance. Studies on parallel applications show repetitive behavior that can be characterized by a set of representative phases. This work presents a Predictive and Distributed Routing Balancing (PR-DRB) technique, a new method developed to gradually control network congestion, based on paths expansion, traffic distribution, applications pattern repetitiveness and speculative adaptive routing, in order to maintain low latency values. PR-DRB monitors messages latencies on routers and saves the found solutions to congestion, to quickly respond in future similar situations. Traffic congestion experiments were conducted in order to evaluate the performance of the method, and improvements were observed.

La tesi consta de dues parts. En la primera s'estenen els resultats i tècniques de Fabbri et al. 2005 per estudiar la dinàmica combinatòria, el <> i l'entropia topològica de certes aplicacions triangulars al cilindre forçades quasiperiòdicament. Aquesta teoria dóna com a corol.lari una demostració més estructurada del Teorema de Sharkovski per aquest cas, demostrat inicialment a Fabbri et al., 2005. Quant a l'entropia es defineix la noció de ferradura en aquest context i es prova, com en el cas de l'interval, que si una d'aquestes funcions té una s-ferradura llavors la seva entropía topològica és més gran o igual a log s. D'això se'n dedueixen fites inferior de l'entropia en funció dels períodes de les orbites periòdiques. Això representa una extensió dels resultats anàlegs a l'interval a aquest context. En el context anterior sorgeix de manera natural la següent pregunta: El Teorema de Sharkovsky es compleix restringit a corbes en lloc de bandes generals? L'objectiu de la segona part de la memòria és el de respondre a aquesta pregunta de forma negativa mitjançant un contraexample: Es construeix una funció que té una òrbita periòdica de període 2 de corbes (que són, de fet, els cercles superiors i inferiors del cilindre) i sense cap corba invariant (solament té una pseudocorba invariant). En particular, això demostra que hi ha aplicacions triangulars al cilindre forçades quasiperiòdicament sense corbes invariants. Aquest és el primer resultat analític d'aquesta naturalesa que apareix a la literatura malgrat l'existencia d'evidències numèriques prèvies en aquest sentit. Els resultats obtinguts són solament una primera fase en la comprensió analítica/topològica de la dinàmica d'aquestes aplicacions, el que obra una via de treball futura.
The thesis consists of two parts. In the first we aim at extending the results and techniques from Fabbri et al. 2005 to study the Combinatorial Dynamics, the <> and the topological Entropy of certain quasiperiodically forced skew-product on the cylinder. This theory gives a structured demonstration from the Sharkovski Theorem as a corollary, proved initially in Fabbri et al., 2005. About entropy defines the notion of horseshoe in this context and shwow, as in the interval case, if one of these functions has a s-horseshoe then its topological entropy is greater than or equal to log s. It follows lower entropy based on periodic orbits periods. This represents an similar extension to the results a l'interval in this context. In the above context arises naturally the following question: Sharkovsky theorem holds restricted curves instead of bands general? The aim of the second part of the report is to answer this question negatively by a contraexample: It constructs a function that has two curves as periodic orbit of period 2 (which are, in fact, the upper and lower circles cylinder) with no invariant curve (only has an invariant pseudo-curve). In particular, this shows that there are quasiperiodically forced skew-product on the cylinder without invariant curves. This is the first analytical result of this kind appearing in the literature despite the existence of previous numerical evidence in this regard. The results are only the first stage in understanding analytic/topological dynamics of these applications, which work via a future job.

En aquest treball ens plantegem dos tipus de problemes. El primer fa referència a la qüestió de l’estacionalitat en el context de les sèries temporals discretes, mentre que en la segona part es tracten models autoregressius de primer ordre amb innovacions no gaussianes. Les sèries temporals a valors enters apareixen en molts i molt variats contextos. L’anàlisi clàssica de sèries temporals contínues pot resultar poc adequada a l’hora de modelitzar fenòmens basats en recomptes, ja que assumeix normalitat en les variacions aleatòries de la sèrie, premissa que difícilment es compleix en el cas de les sèries de nombres enters. Aquest fet motiva l’estudi de models basats en distribucions discretes (Poisson, binomial negativa, …). Tanmateix, en el context dels models habituals de sèries temporals discretes (INAR, INMA,…) no s’han desenvolupat tècniques suficients per tractar amb possibles comportaments estacionals en les dades, i per tant, calen eines adients per modelitzar fenòmens amb aquesta característica, com per exemple, la incidència de malalties com grip, al·lèrgies, pneumònies… En aquest treball proposem una variació del model INAR(2) per tal d’incloure-hi una component estacional i estudiem com es pot aplicar per analitzar dades relatives a ingressos hospitalaris per grip. Seguint amb el mateix exemple, es plantegen diversos mètodes per realitzar prediccions sobre l’ocupació futura de llits hospitalaris basats en aquest tipus de models de sèries temporals de recomptes, a curt i llarg termini. La segona qüestió que s’aborda en aquest treball apareix com un problema de caracterització de distribucions, en un context de models autoregressius de primer ordre, motivada per un resultat sorprenent de McKenzie que afirma que donat un procés Y t amb estructura AR(1), i considerant la sèrie exponenciada Xt = eY t, la funció d’autocorrelació de Xt és la mateixa que la de la sèrie original Y t si i només si la distribució estacionària de Xt és una gamma. Amb aquest punt de partida, el nostre objectiu principal ha estat generalitzar aquest resultat de McKenzie, en el sentit de caracteritzar la distribució de les innovacions en aquest context, i desenvolupar un contrast de bondat de l’ajust basat en la funció distribució empírica per tal de decidir si és raonable pensar, amb un cert nivell de confiança, que la distribució de les innovacions és una distribució concreta. En particular, aquest contrast es pot utilitzar, en la situació clàssica, per tal de comprovar si les innovacions en un model autoregressiu de primer ordre són gaussianes. Aquest contrast s’ha aplicat en primer lloc sobre les captures de peix a l’oceà Atlàntic i golf del riu St. Lawrence, entre 1990 i 1996 per tal d’estudiar si l’assumpció de normalitat de les innovacions és raonable o no. En segon lloc s’ha realitzat el contrast sobre les dades del deflactor del producte interior brut espanyol des de 1962 fins a 2011. Finalment, es presenta un estudi de la potència del contrast, en diferents situacions, considerant diversos valors per al primer coeficient d’autocorrelació, diferents mides mostrals i diverses distribucions marginals.
In this work we consider two kinds of problems. The first concerns the issue of seasonality in the context of discrete time series, while the second part will deal with first-order autoregressive models with non-Gaussian innovations. Integer valued time series appear in many different contexts. The classical analysis of continuous time series can be inadequate when modeling phenomena based on counts, as the assumption of normal random variations is hardly achieved in the case of integer series. This motivates the study of models based in discrete distributions (Poisson, negative binomial, …). However, in the context of standard models of discrete time series (INAR, INMA, …) there is a lack of techniques focused on dealing with possible seasonal behavior in the data, and therefore there is a need of suitable tools to model phenomena presenting this feature, as, for example, the incidence of diseases such as flu, allergies, pneumonia,… In this work we propose a variation of the INAR(2) model to include a seasonal component, and we study how can it be applied to analyze data concerning hospital admissions caused by influenza. Following the same example, we consider several methods to make predictions about future occupation of hospital beds based on this type of time-series models of counts in the short and long term. The second issue addressed in this work appears as a problem of characterization of distributions in the context of first-order autoregressive models, prompted by a surprising result by McKenzie, establishing that a process Y t with AR(1) structure, and considering the exponentiated series Xt = eYt, the autocorrelation function of Xt is the same as the original series Y t if and only if the stationary distribution of Xt is gamma. Using this result as a starting point, our main goal has been to generalize this result by McKenzie in the sense of characterizing the distribution of the innovations in this context, and develop a goodness of fit test based on the empirical distribution function in order to decide whether it is reasonable to assume, at some level of confidence, that the the innovations follows a specific distribution. In particular, this contrast can be used in the classical situation, in order to check if the innovations of a first-order autoregressive model are Gaussian. This contrast has been applied on a data set concerning fish catches in the Atlantic Ocean and Gulf of St. Lawrence River between 1990 and 1996 to study whether the assumption of normality of the innovations is reasonable or not. As a second example, the contrast has been made on data concerning the deflator of the Spanish gross domestic product from 1962 to 2011. Finally, a study of the power of the test, in different situations is presented, considering different values for the first autocorrelation coeffcient, different sample sizes and different marginal distributions.

Las herramientas computacionales que se describen en esta tesis representan posibles alternativas de solución en la construcción de modelos de calibración multivariable a partir de datos obtenidos con arreglos de sensores electroquímicos. Tanto el trabajo experimental como las aplicaciones computacionales están dirigidos a la construcción de lenguas electrónicas de los tipos potenciométrico y voltamperométrico. Las propuestas de solución que aquí se presentan están basadas en técnicas computacionales diseñadas para explorar grandes bases de datos en la búsqueda de patrones consistentes y/o relaciones sistemáticas entre variables, que permitan posteriormente aplicar estos modelos a nuevos datos con el fin de generar predicciones o estimaciones de resultados esperados. Algunas de las herramientas se implementaron con redes neuronales tipo perceptrón multicapas y diferentes funciones de transferencia en las neuronas de la capa oculta. Las funciones de activación sigmoidales comúnmente usadas en las redes neuronales se sustituyeron por funciones más complejas y de poco (o nulo) uso en el área química. Para hacer compatible la estructura de la mayoría de los datos usados en esta tesis, con las entradas de las redes neuronales, se hizo un tratamiento previo de la información electroquímica usando técnicas de procesamiento mono- o multi-modales para reducir el número de variables y dimensiones. Además de las propuestas basadas en estructuras de redes neuronales, también se ha planteado la construcción de modelos a partir de funciones base de los tipos spline truncada y B-spline. La primera se conoce como Splines Adaptativas de Regresión Multivariable (MARS) y la segunda como B-splines Adaptativas de Regresión Multivariable (B-MARS). Adicionalmente a las herramientas anteriormente descritas e implementadas como propuestas de solución, también se construyeron exitosamente modelos de calibración usando la regresión multimodo por mínimos cuadrados parciales (N-PLS).
The computational tools described in this thesis are meant to be alternative solutions to build multivariate calibration models from multi-way data obtained with arrays of electrochemical sensors. Both experimental and computational applications described herein are aimed to build electronic tongues of potentiometric and voltammetric types. The solution proposals are based on computational techniques designed to explore large databases in search of consistent patterns and/or systematic relationships between variables, allowing then to apply these models to new data to predict or estimate expected results. Some of the tools were implemented using multilayer perceptron neural networks with complex transfer functions (of little or no use in the chemical area) in the hidden layer neurons. To make compatible the type of structure of most of the data used in this thesis with the input of the neural networks, the electrochemical information was pretreated using mono- or multi-dimensional processing techniques in order to reduce the number of variables and dimensions. In addition to the structres based on neural networks, we also propose to build models using base functions of the truncated spline and B-spline types. The first is known as Adaptive Regression Splines Multivariable (MARS) and the second as B-splines Multivariate Adaptive Regression (B-MARS). In addition to the tools described above and implemented as proposed solutions, we also built successfully calibration models using multi-way partial least squares regression (N-PLS).

En aquesta memòria es tracten tres problemes diferents. En el Capítol 1 es construeixen dues famílies de processos que convergeixen, en el sentit de les distribucions en dimensió finita, cap a dos processos Gaussians independents. El Capítol 2 està dedicat a l’estudi d’un model de tractament amb bacteriòfags per infeccions bacterianes. Finalment, en el Capítol 3, estudiem alguns aspectes del L2 mòdul de continuïtat del temps local del Brownià. En el primer capítol considerem dos processos Gaussians independents que es poden representar en termes d’una integral estocàstica d’un nucli determinista respecte el procés de Wiener, i construïm, a partir d’un únic procés de Poisson, dues famílies de processos que convergeixen, en el sentit de les distribucions en dimensió finita, cap a aquests processos Gaussians. Utilitzarem aquest resultat per a provar resultats de convergència en llei cap a altres processos, com ara el moviment Brownià sub-fraccionari. En el Capítol 2 construïm i estudiem diferents model que pretenen estudiar el comportament d’un tractament amb bacteriòfags en certs animals de granja. Aquest problema ha estat motivat pel Grup de Biologia Molecular del Departament de Genètica i Microbiologia de la Universitat Autònoma de Barcelona. Començant per un model bàsic, n’estudiarem diferent variacions, primer des d’un punt de vista determinista, trobant diversos resultat sobre els equilibris i l’estabilitat, i després en un context amb soroll, produint resultats de concentració. Finalment, en el Capítol 3 estudiarem la descomposició en caos de Wiener del L2 mòdul de continuïtat del temps local del Brownià. Més concretament, trobarem un Teorema Central del Límit per a cada element del caos de Wiener del L2 mòdul de continuïtat del temps local del Brownià. Aquest resultat ens proporciona un exemple d’una família de variables que convergeix en llei cap a una distribució Normal, però que els elements del seu caos d’ordre parell no convergeixen.
In this dissertation three different problems are treated. In Chapter 1 we construct two families of processes that converge, in the sense of the finite dimensional distributions, towards two independent Gaussian processes. Chapter 2 is devoted to the study of a model of bacteriophage treatments for bacterial infections. Finally, in Chapter 3 we study some aspects of the L2 modulus of continuity of Brownian local time. In the first chapter we consider two independent Gaussian processes that can be represented in terms of a stochastic integral of a deterministic kernel with respect to the Wiener process and we construct, from a single Poisson process, two families of processes that converge, in the sense of the finite dimensional distributions, towards these Gaussian processes. We will use this result to prove convergence in law results towards some other processes, like sub-fractional Brownian motion. In Chapter 2 we construct and study several models that pretend to study how will behave a treatment of bateriophages in some farm animals. This problem has been brought to our attention by the Molecular Biology Group of the Department of Genetics and Microbiology at the Universitat Autònoma de Barcelona. Starting from a basic model, we will study several variations, first from a deterministic point of view, finding several results on equilibria and stability, and later in a noisy context, producing concentration type results. Finally, in Chapter 3 we shall study the decomposition on Wiener chaos of the L2 modulus of continuity of the Brownian local time. More precisely, we shall find a Central Limit Theorem for each Wiener chaos element of the L2 modulus of continuity of the Brownian local time. This result provides us with an example of a family of random variables that is convergent in law to a Normal distribution, but its chaos elements of even order do not converge.

Durant els últims anys, hi ha hagut un interès creixent en les tècniques de reconeixement d'objectes basades en imatges, on cadascuna de les quals es correspon a una aparença particular de l'objecte. Aquestes tècniques que únicament utilitzen informació de les imatges són anomenades tècniques basades en l'aparença i l'interès sorgit per aquestes tècniques és degut al seu éxit a l'hora de reconèixer objectes. Els primers mètodes basats en l'aparença es recolzaven únicament en models globals. Tot i que els mètodes globals han estat utilitzats satisfactòriament en un conjunt molt ampli d'aplicacions basades en la visió per computador (per exemple, reconeixement de cares, posicionament de robots, etc), encara hi ha alguns problemes que no es poden tractar fàcilment. Les oclusions parcials, canvis excessius en la il·luminació, fons complexes, canvis en l'escala i diferents punts de vista i orientacions dels objectes encara són un gran problema si s'han de tractar des d'un punt de vista global. En aquest punt és quan els mètodes basats en l'aparença local van sorgir amb l'objectiu primordial de reduir l'efecte d'alguns d'aquests problemes i proporcionar una representació molt més rica per ser utilitzada en entorns encara més complexes.
Usualment, els mètodes basats en l'aparença local utilitzen descriptors d'alta dimensionalitat a l'hora de descriure regions locals dels objectes. Llavors, el problema de la maledicció de la dimensionalitat (curse of dimensionality) pot sorgir i la classificació dels objectes pot empitjorar. En aquest sentit, un exemple típic per alleujar la maledicció de la dimensionalitat és la utilització de tècniques basades en la reducció de la dimensionalitat. D'entre les possibles tècniques per reduir la dimensionalitat, es poden utilitzar les transformacions lineals de dades. Bàsicament, ens podem beneficiar de les transformacions lineals de dades si la projecció millora o manté la mateixa informació de l'espai d'alta dimensió original i produeix classificadors fiables. Llavors, el principal objectiu és la modelització de patrons d'estructures presents als espais d'altes dimensions en espais de baixes dimensions.
La primera part d'aquesta tesi utilitza primordialment histogrames color, un descriptor local que ens proveeix d'una bona font d'informació relacionada amb les variacions fotomètriques de les regions locals dels objectes. Llavors, aquests descriptors d'alta dimensionalitat es projecten en espais de baixes dimensions tot utilitzant diverses tècniques. L'anàlisi de components principals (PCA), la factorització de matrius amb valors no-negatius (NMF) i la versió ponderada del NMF són 3 transformacions lineals que s'han introduit en aquesta tesi per reduir la dimensionalitat de les dades i proporcionar espais de baixa dimensionalitat que siguin fiables i mantinguin les estructures de l'espai original. Una vegada s'han explicat, les 3 tècniques lineals són àmpliament comparades segons els nivells de classificació tot utilitzant una gran diversitat de bases de dades. També es presenta un primer intent per unir aquestes tècniques en un únic marc de treball i els resultats són molt interessants i prometedors. Un altre objectiu d'aquesta tesi és determinar quan i quina transformació lineal s'ha d'utilitzar tot tenint en compte les dades amb que estem treballant. Finalment, s'introdueix l'anàlisi de components independents (ICA) per modelitzar funcions de densitat de probabilitats tant a espais originals d'alta dimensionalitat com la seva extensió en subespais creats amb el PCA. L'anàlisi de components independents és una tècnica lineal d'extracció de característiques que busca minimitzar les dependències d'alt ordre. Quan les seves assumpcions es compleixen, es poden obtenir característiques estadísticament independents a partir de les mesures originals. En aquest sentit, el ICA s'adapta al problema de reconeixement estadístic de patrons de dades d'alta dimensionalitat. Això s'aconsegueix utilitzant representacions condicionals a la classe i un esquema de decisió de Bayes adaptat específicament. Degut a l'assumpció d'independència aquest esquema resulta en una modificació del classificador ingenu de Bayes.
El principal inconvenient de les transformacions lineals de dades esmentades anteriorment és que no consideren cap tipus de relació espacial entre les característiques locals. Conseqüentment, es presenta un mètode per reconèixer objectes tridimensionals a partir d'imatges d'escenes complexes, tot utilitzant un únic model après d'una imatge de l'objecte. Aquest mètode es basa directament en les característiques visuals locals extretes de punts rellevants dels objectes i té en compte les relacions espacials entre elles. Aquest nou esquema redueix l'ambigüitat de les representacions anteriors. De fet, es presenta una nova metodologia general per obtenir estimacions fiables de distribucions conjuntes de vectors de característiques locals de múltiples punts rellevants dels objectes. Per fer-ho, definim el concepte de k-tuples per poder representar l'aparença local de l'objecte a k punts diferents i al mateix moment les dependències estadístiques entre ells. En aquest sentit, el nostre mètode s'adapta a entorns complexes i reals demostrant una gran habilitat per detectar objectes en aquests escenaris amb resultats molt prometedors.
During the last few years, there has been a growing interest in object recognition techniques directly based on images, each corresponding to a particular appearance of the object. These techniques which use only information of images are called appearance based models and the interest in such techniques is due to its success in recognizing objects. Earlier appearance-based approaches were focused on the use of holistic approaches. In spite of the fact that global representations have been successfully used in a broad set of computer vision applications (i.e. face recognition, robot positioning, etc), there are still some problems that can not be easily solved. Partial object occlusions, severe lighting changes, complex backgrounds, object scale changes and different viewpoints or orientations of objects are still a problem if they should be faced under a holistic perspective. Then, local appearance approaches emerged as they reduce the effect of some of these problems and provide a richer representation to be used in more complex environments.
Usually, local appearance methods use high dimensional descriptors to describe local regions of objects. Then, the curse of dimensionality problem appears and object classification degrades. A typical example to alleviate the curse of dimensionality problem is to use techniques based on dimensionality reduction. Among possible reduction techniques, one could use linear data transformations. We can benefit from linear data transformations if the projection improves or mantains the same information of the high dimensional space and produces reliable classifiers. Then, the main goal is to model low dimensional pattern structures present in high dimensional data.
The first part of this thesis is mainly focused on the use of color histograms, a local descriptor which provides a good source of information directly related to the photometric variations of local image regions. Then, these high dimensional descriptors are projected to low dimensional spaces using several techniques. Principal Component Analysis (PCA), Non-negative Matrix Factorization (NMF) and a weighted version of NMF, the Weighted Non-negative Matrix Factorization (WNMF) are 3 linear transformations of data which have been introduced in this thesis to reduce dimensionality and provide reliable low dimensional spaces. Once introduced, these three linear techniques are widely compared in terms of performances using several databases. Also, a first attempt to merge these techniques in an unified framework is shown and results seem to be very promising. Another goal of this thesis is to determine when and which linear transformation might be used depending on the data we are dealing with. To this end, we introduce Independent Component Analysis (ICA) to model probability density functions in the original high dimensional spaces as well as its extension to model subspaces obtained using PCA. ICA is a linear feature extraction technique that aims to minimize higher-order dependencies in the extracted features. When its assumptions are met, statistically independent features can be obtained from the original measurements. We adapt ICA to the particular problem of statistical pattern recognition of high dimensional data. This is done by means of class-conditional representations and a specifically adapted Bayesian decision scheme. Due to the independence assumption this scheme results in a modification of the naive Bayes classifier.
The main disadvantage of the previous linear data transformations is that they do not take into account the relationship among local features. Consequently, we present a method of recognizing three-dimensional objects in intensity images of cluttered scenes, using a model learned from one single image of the object. This method is directly based on local visual features extracted from relevant keypoints of objects and takes into account the relationship between them. Then, this new scheme reduces the ambiguity of previous representations. In fact, we describe a general methodology for obtaining a reliable estimation of the joint distribution of local feature vectors at multiple salient points (keypoints). We define the concept of k-tuple in order to represent the local appearance of the object at k different points as well as the statistical dependencies among them. Our method is adapted to real, complex and cluttered environments and we present some results of object detection in these scenarios with promising results.

Parallel and distributed programming constitutes a highly promising approach to improving the performance of many applications. However, in comparison to sequential programming, many new problems arise in all phases of the development cycle of this kind of applications.
For example, in the analysis phase of parallel/distributed programs, the programmer has to decompose the problem (data and/or code) to find the concurrency of the algorithm. In the design phase, the programmer has to be aware of the communication and synchronization conditions between tasks. In the implementation phase, the programmer has to learn how to use specific communication libraries and runtime environments but also to find a way of debugging programs. Finally, to obtain the best performance, the programmer has to tune the application by using monitoring tools, which collect information about the application's behavior. Tuning can be a very difficult task because it can be difficult to relate the information gathered by the monitor to the application's source code. Moreover, tuning can be even more difficult for those applications that change their behavior dynamically because, in this case, a problem might happen or not depending on the execution conditions.
It can be seen that these issues require a high degree of expertise, which prevents the more widespread use of this kind of solution. One of the best ways to solve these problems would be to develop, as has been done in sequential programming, tools to support the analysis, design, coding, and tuning of parallel/distributed applications.
In the particular case of performance analysis and/or tuning, it is important to note that the best way of analyzing and tuning parallel/distributed applications depends on some of their behavioral characteristics. If the application to be tuned behaves in a regular way then a static analysis (predictive or trace based) would be enough to find the application's performance bottlenecks and to indicate what should be done to overcome them. However, if the application changes its behavior from execution to execution or even dynamically changes its behavior in a single execution then the static analysis cannot offer efficient solutions for avoiding performance bottlenecks.
In this case, dynamic monitoring and tuning techniques should be used instead. However, in dynamic monitoring and tuning, decisions must be taken efficiently, which means that the application's performance analysis outcome must be accurate and punctual in order to effectively tackle problems; at the same time, intrusion on the application must be minimized because the instrumentation inserted in the application in order to monitor and tune it alters its behavior and could introduce performance problems that were not there before the instrumentation.
This is more difficult to achieve if there is no information about the structure and behavior of the application; therefore, blind automatic dynamic tuning approaches have limited success, whereas cooperative dynamic tuning approaches can cope with more complex problems at the cost of asking for user collaboration. We have proposed a third approach. If a programming tool, based on the use of skeletons or frameworks, has been used in the development of the application then much information about the structure and behavior of the application is available and a performance model associated to the structure of the application can be defined for use by the dynamic tuning tool. The resulting tuning tool should produce the outcome of a collaborative one while behaving like an automatic one from the point of view of the application developer.

Des dels principis de la informàtica, s'ha intentat dotar als ordinadors de la capacitat per realitzar moltes de les tasques quotidianes de les persones. Un dels problemes més estudiats i encara menys entesos actualment és la capacitat d'aprendre a partir de les nostres experiències i generalitzar els coneixements adquirits.
Una de les tasques inconscients per a les persones i que més interès està despertant en àmbit científics des del principi, és el que es coneix com a reconeixement de patrons. La creació de models del món que ens envolta, ens serveix per a reconèixer objectes del nostre entorn, predir situacions, identificar conductes, etc. Tota aquesta informació ens permet adaptar-nos i interactuar amb el nostre entorn. S'ha arribat a relacionar la capacitat d'adaptació d'un ésser al seu entorn amb la quantitat de patrons que és capaç d'identificar.
Quan parlem de reconeixement de patrons en el camp de la Visió per Computador, ens referim a la capacitat d'identificar objectes a partir de la informació continguda en una o més imatges. En aquest camp s'ha avançat molt en els últims anys, i ara ja som capaços d'obtenir resultats "útils" en entorns reals, tot i que encara estem molt lluny de tenir un sistema amb la mateixa capacitat d'abstracció i tan robust com el sistema visual humà.
En aquesta tesi, s'estudia el detector de cares de Viola i Jones, un dels mètode més estesos per resoldre la detecció d'objectes. Primerament, s'analitza la manera de descriure els objectes a partir d'informació de contrastos d'il·luminació en zones adjacents de les imatges, i posteriorment com aquesta informació és organitzada per crear estructures més complexes. Com a resultat d'aquest estudi, i comparant amb altres metodologies, s'identifiquen dos punts dèbils en el mètode de detecció de Viola i Jones. El primer fa referència a la descripció dels objectes, i la segona és una limitació de l'algorisme d'aprenentatge, que dificulta la utilització de millors descriptors.
La descripció dels objectes utilitzant les característiques de Haar, limita la informació extreta a zones connexes de l'objecte. En el cas de voler comparar zones distants, s'ha d'optar per grans mides de les característiques, que fan que els valors obtinguts depenguin més del promig de valors d'il·luminació de l'objecte, que de les zones que es volen comparar. Amb l'objectiu de poder utilitzar aquest tipus d'informacions no locals, s'intenta introduir els dipols dissociats en l'esquema de detecció d'objectes.
El problema amb el que ens trobem en voler utilitzar aquest tipus de descriptors, és que la gran cardinalitat del conjunt de característiques, fa inviable la utilització de l'Adaboost, l'algorisme utilitzat per a l'aprenentatge. El motiu és que durant el procés d'aprenentatge, es fa un anàlisi exhaustiu de tot l'espai d'hipòtesis, i al ser tant gran, el temps necessari per a l'aprenentatge esdevé prohibitiu. Per eliminar aquesta limitació, s'introdueixen mètodes evolutius dins de l'esquema de l'Adaboost i s'estudia els efectes d'aquest canvi en la capacitat d'aprenentatge. Les conclusions extretes són que no només continua essent capaç d'aprendre, sinó que la velocitat de convergència no és afectada significativament.
Aquest nou Adaboost amb estratègies evolutives obre la porta a la utilització de conjunts de característiques amb cardinalitats arbitràries, el que ens permet indagar en noves formes de descriure els nostres objectes, com per exemple utilitzant els dipols dissociats. El primer que fem és comparar la capacitat d'aprenentatge del mètode utilitzant les característiques de Haar i els dipols dissociats. Com a resultat d'aquesta comparació, el que veiem és que els dos tipus de descriptors tenen un poder de representació molt similar, i depenent del problema en que s'apliquen, uns s'adapten una mica millor que els altres. Amb l'objectiu d'aconseguir un sistema de descripció capaç d'aprofitar els punts forts tant de Haar com dels dipols, es proposa la utilització d'un nou tipus de característiques, els dipols dissociats amb pesos, els quals combinen els detectors d'estructures que fan robustes les característiques de Haar amb la capacitat d'utilitzar informació no local dels dipols dissociats. A les proves realitzades, aquest nou conjunt de característiques obté millors resultats en tots els problemes en que s'ha comparat amb les característiques de Haar i amb els dipols dissociats.
Per tal de validar la fiabilitat dels diferents mètodes, i poder fer comparatives entre ells, s'ha utilitzat un conjunt de bases de dades públiques per a diferents problemes, tals com la detecció de cares, la detecció de texts, la detecció de vianants i la detecció de cotxes. A més a més, els mètodes també s'han provat sobre una base de dades més extensa, amb la finalitat de detectar senyals de trànsit en entorns de carretera i urbans.
Ever since computers were invented, we have wondered whether they might perform some of the human quotidian tasks. One of the most studied and still nowadays less understood problem is the capacity to learn from our experiences and how we generalize the knowledge that we acquire.
One of that unaware tasks for the persons and that more interest is awakening in different scientific areas since the beginning, is the one that is known as pattern recognition. The creation of models that represent the world that surrounds us, help us for recognizing objects in our environment, to predict situations, to identify behaviors... All this information allows us to adapt ourselves and to interact with our environment. The capacity of adaptation of individuals to their environment has been related to the amount of patterns that are capable of identifying.
When we speak about pattern recognition in the field of Computer Vision, we refer to the ability to identify objects using the information contained in one or more images. Although the progress in the last years, and the fact that nowadays we are already able to obtain "useful" results in real environments, we are still very far from having a system with the same capacity of abstraction and robustness as the human visual system.
In this thesis, the face detector of Viola & Jones is studied as the paradigmatic and most extended approach to the object detection problem. Firstly, we analyze the way to describe the objects using comparisons of the illumination values in adjacent zones of the images, and how this information is organized later to create more complex structures. As a result of this study, two weak points are identified in this family of methods: The first makes reference to the description of the objects, and the second is a limitation of the learning algorithm, which hampers the utilization of best descriptors.
Describing objects using Haar-like features limits the extracted information to connected regions of the object. In the case we want to compare distant zones, large contiguous regions must be used, which provokes that the obtained values depend more on the average of lighting values of the object than in the regions we are wanted to compare. With the goal to be able to use this type of non local information, we introduce the Dissociated Dipoles into the outline of objects detection.
The problem using this type of descriptors is that the great cardinality of this feature set makes unfeasible the use of Adaboost as learning algorithm. The reason is that during the learning process, an exhaustive search is made over the space of hypotheses, and since it is enormous, the necessary time for learning becomes prohibitive. Although we studied this phenomenon on the Viola & Jones approach, it is a general problem for most of the approaches, where learning methods introduce a limitation on the descriptors that can be used, and therefore, on the quality of the object description. In order to remove this limitation, we introduce evolutionary methods into the Adaboost algorithm, studying the effects of this modification on the learning ability. Our experiments conclude that not only it continues being able to learn, but its convergence speed is not significantly altered.
This new Adaboost with evolutionary strategies opens the door to the use of feature sets with an arbitrary cardinality, which allows us to investigate new ways to describe our objects, such as the use of Dissociated Dipoles. We first compare the learning ability of this evolutionary Adaboost using Haar-like features and Dissociated Dipoles, and from the results of this comparison, we conclude that both types of descriptors have similar representation power, but depends on the problem they are applied, one adapts a little better than the other. With the aim of obtaining a descriptor capable of share the strong points from both Haar-like and Dissociated Dipoles, we propose a new type of feature, the Weighted Dissociated Dipoles, which combines the robustness of the structure detectors present in the Haar-like features, with the Dissociated Dipoles ability to use non local information. In the experiments we carried out, this new feature set obtains better results in all problems we test, compared with the use of Haar-like features and Dissociated Dipoles.
In order to test the performance of each method, and compare the different methods, we use a set of public databases, which covers face detection, text detection, pedestrian detection, and cars detection. In addition, our methods are tested to face a traffic sign detection problem, over large databases containing both, road and urban scenes.

L'analogia juga un papel fonamental en la resolucio de problemes i es troba darrere de molts dels processos centrals de la capacitat cognitiva humana, fins al punt que s'ha considerat "el nucli del coneixement". El raonament analogic funciona a traves del proces de la transferencia, l'us del coneixement apres en una situacio en l'altra per a la qual no va ser destinat. El paradigma de raonament basat en casos (case-based reasoning, CBR) presenta un model molt relacionat, pero lleugerament diferent de raonament utilitzat principalment en la intel.ligencia artificial; diferent en part perque el raonament analogic se centra habitualment en la similitud estructural entre-dominis mentre que CBR te a veure amb la transferencia de solucions entre els casos semanticament similars dins d'un domini especific. En aquesta tesi, ens unim a aquests enfocaments interrelacionats de la ciència cognitiva, la psicologia i la intel.ligencia artificial, en un sistema CBR, on la recuperacio i l'adaptacio es duen a terme per l'Motor d'Associacio Estructural (SME) i son recolzats per el raonament de sentit comu integrant la informacio des de diverses bases de coneixement. Per permetre aixo, utilitzem una estructura de representacio de casos que es basa en les xarxes semantiques. Aixo ens dona un model CBR capac de recuperar i adaptar solucions de dominis que son aparentment diferents pero estructuralment molt similars, formant una de les nostres contribucions en aquest estudi. Una de les principals limitacions de la investigacio sobre els sistemes CBR sempre ha estat l'adaptacio, on la majoria de les aplicacions es van conformar amb una simple "reutilitzacio" de la solucio del cas recuperat, principalment mitjancant una adaptacio null} o adaptacio sustitucional. La dificultat de l'adaptacio es encara mes evident per al nostre cas d'inter-domini CBR utilitzant xarxes semantiques. Resoldre aquesta dificultat aplana el cami per a una contribucio igualment important d'aquesta tesi, on s'introdueix una tecnica nova d'adaptacio generativa basada en la computacio evolutiva que permet la creacio o modificacio espontania de les xarxes semantiques d'acord a les necessitats d'adaptacio CBR. Per a l'avaluacio d'aquest treball, apliquem el nostre sistema CBR al problema de la mediacio, un metode important en la resolucio de conflictes. El problema de la mediacio no es trivial i representa un molt bon exemple del mon real, en el qual podem detectar problemes estructuralment similars de dominis aparentment tan lluny com les relacions internacionals, conflictes familiars i els drets intel.lectuals.
Analogy plays a fundamental role in problem solving and it lies behind many processes central to human cognitive capacity, to the point that it has been considered "the core of cognition". Analogical reasoning functions through the process of transfer, the use of knowledge learned in one situation in another for which it was not targeted. The case-based reasoning (CBR) paradigm presents a highly related, but slightly different model of reasoning mainly used in artificial intelligence, different in part because analogical reasoning commonly focuses on cross-domain structural similarity whereas CBR is concerned with transfer of solutions between semantically similar cases within one specific domain. In this dissertation, we join these interrelated approaches from cognitive science, psychology, and artificial intelligence, in a CBR system where case retrieval and adaptation are accomplished by the Structure Mapping Engine (SME) and are supported by commonsense reasoning integrating information from several knowledge bases. For enabling this, we use a case representation structure that is based on semantic networks. This gives us a CBR model capable of recalling and adapting solutions from seemingly different, but structurally very similar domains, forming one of our contributions in this study. A traditional weakness of research on CBR systems has always been about adaptation, where most applications settle for a very simple "reuse" of the solution from the retrieved case, mostly through null adaptation or substitutional adaptation. The difficulty of adaptation is even more obvious for our case of cross-domain CBR using semantic networks. Solving this difficulty paves the way to another contribution of this dissertation, where we introduce a novel generative adaptation technique based on evolutionary computation that enables the spontaneous creation or modification of semantic networks according to the needs of CBR adaptation. For the evaluation of this work, we apply our CBR system to the problem of mediation, an important method in conflict resolution. The mediation problem is non-trivial and presents a very good real world example where we can spot structurally similar problems from domains seemingly as far as international relations, family disputes, and intellectual rights.

Donat un conjunt d'objectes, el concepte genèric de mediana està definit com l'objecte amb la suma de distàncies a tot el conjunt, més petita. Sovint, aquest concepte és usat per a obtenir el representant del conjunt.
En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana és conegut com median graph. Potencialment, té les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs.
Tot i la seva simple definició i les potencials aplicacions, s'ha demostrat que el seu càlcul és una tasca extremadament complexa. Tots els algorismes existents només han estat capaços de treballar amb conjunts petits de grafs, i per tant, la seva aplicació ha estat limitada en molts casos a usar dades sintètiques sense significat real. Així, tot i el seu potencial, ha restat com un concepte eminentment teòric.
L'objectiu principal d'aquesta tesi doctoral és el d'investigar a fons la teoria i l'algorísmica relacionada amb el concepte de medinan graph, amb l'objectiu final d'extendre la seva aplicabilitat i lliurar tot el seu potencial al món de les aplicacions reals. Per això, presentem nous resultats teòrics i també nous algorismes per al seu càlcul. Des d'un punt de vista teòric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teòriques del median graph poden ser millorades sota determinades condicions. Més enllà de les aportacioncs teòriques, proposem cinc noves alternatives per al seu càlcul. La primera d'elles és una conseqüència directa del concepte d'spectral median graph. Després, basats en les millores de les propietats teòriques, presentem dues alternatives més per a la seva obtenció. Finalment, s'introdueix una nova tècnica per al càlcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes més.
L'avaluació experimental dels mètodes proposats utilitzant una base de dades semi-artificial (símbols gràfics) i dues amb dades reals (mollècules i pàgines web), mostra que aquests mètodes són molt més eficients que els existents. A més, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classificació i clustering que validen aquesta hipòtesi i permeten preveure una pròspera aplicació del median graph a un bon nombre d'algorismes d'aprenentatge.
Given a set of objects, the generic concept of median is defined as the object with the smallest sum of distances to all the objects in the set. It has been often used as a good alternative to obtain a representative of the set.
In structural pattern recognition, graphs are normally used to represent structured objects. In the graph domain, the concept analogous to the median is known as the median graph. By extension, it has the same potential applications as the generic median in order to be used as the representative of a set of graphs.
Despite its simple definition and potential applications, its computation has been shown as an extremely complex task. All the existing algorithms can only deal with small sets of graphs, and its application has been constrained in most cases to the use of synthetic data with no real meaning. Thus, it has mainly remained in the box of the theoretical concepts.
The main objective of this work is to further investigate both the theory and the algorithmic underlying the concept of the median graph with the final objective to extend its applicability and bring all its potential to the world of real applications. To this end, new theory and new algorithms for its computation are reported. From a theoretical point of view, this thesis makes two main contributions. On one hand, the new concept of spectral median graph. On the other hand, we show that some of the existing theoretical properties of the median graph can be improved under some specific conditions. In addition to these theoretical contributions, we propose five new ways to compute the median graph. One of them is a direct consequence of the spectral median graph concept. In addition, we provide two new algorithms based on the new theoretical properties. Finally, we present a novel technique for the median graph computation based on graph embedding into vector spaces. With this technique two more new algorithms are presented.
The experimental evaluation of the proposed methods on one semi-artificial and two real-world datasets, representing graphical symbols, molecules and webpages, shows that these methods are much more ecient than the existing ones. In addition, we have been able to proof for the first time that the median graph can be a good representative of a class in large datasets. We have performed some classification and clustering experiments that validate this hypothesis and permit to foresee a successful application of the median graph to a variety of machine learning algorithms.

En Estadística el término "invariancia" puede ser entendido como sinónimo de simetría. Si disponemos de una familia invariante frente a la acción de un grupo, la solución a nuestro problema debería reflejar la propiedad de invariancia de la familia. Sin embargo, no todas las familias son invariantes frente a la acción de algún grupo; habitualmente dispondremos de familias que no serán invariantes pero para las que es posible que su transformación por éste no quede "demasiado alejada" de un desplazamiento de la familia original. En esta situación de "casi invariancia" ¿deberemos desestimar toda la información que nos proporciona la teoría clásica? ¿Tenemos que escoger entre el "blanco" y el "negro"?

Justamente, el objetivo de este trabajo pretende ser una contribución a la estimación puntual donde se analice el problema de un estimador para esos "grises", situaciones que van desde la existencia de una invariancia clásica hasta su total ausencia. Los diferentes "tonos de gris" serán las órdenes de invariancia que vamos a definir, en el contexto de la Geometría Diferencial Informativa.

Esta tesis estudia la aplicación de modelos de racionamiento humano en la área de la economía. El objetivo del análisis es observar el efecto que tienen distintos modelos de adaptación y aprendizaje sobre el resultado final de varios juegos.
En los tres trabajos que forman la tesis se analizan distintos juegos.
En el primero el juego es el Dilema del Prisionero y el objetivo es estudiar la influencia del aprendizaje social e individual o imitación sobre el resultado del juego. Los resultados demuestran que la elección de uno de estos modelos determina el resultado final.
El segundo trabajo se dedica a crear en modelo dinámico de formación de coaliciones en el que los individuos no saben el valor que tiene cada coalición para ellos. El modelo crea un proceso de Markov no estacionario. Nuestros resultados demuestran que los puntos fijos del sistema se pueden aproximar por una secuencia de dinámicas perturbadas en los que los jugadores saben el valor de las coaliciones.
En el ultimo trabajo analizamos la dinámica de un mercado usando un modelo computacional. El enfoque del trabajo es la influencia de los hábitos de los consumidores sobre la estructura del mercado. Los resultados demuestran que algunas de las características del comportamiento de los consumidores pueden sostener la diversidad en calidades y tamaño de las empresas en el mercado.
This thesis focuses on studying the way in which individuals' adaptation mechanizms influence their behavior and the outcomes in different games. In all the models presented here the emphasis is put on the adaptation process and its elements, rather than on the equilibrium behavior of the players.
The thesis consists of three papers.
The first one focuses on the importance of the way the information is exchanged in the context of Repeated Prisoner's Dilemma game. In Chapter 2 we build a simulation model imitating the structure of human reasoning in order to study how people face a Repeated Prisoner's Dilemma game. The results are ranged starting from individual learning in which case the worst result -defection- is obtained, passing through a partial imitation, where individuals could end up in cooperation or defection, and reaching the other extreme of social learning, where mutual cooperation can be obtained. The influence of some particular strategies on the attainment of cooperation is also considered. Those differences in the results of the three scenarios we have constructed suggest that one should be very careful when deciding which one to choose.
Chapter 3 studies the process of coalition formation when players are unsure about the true benefit of belonging to a given coalition. Under such strong incomplete information scenario, we use a Case-Based Decision Theory approach to study the underlying dynamic process. We show that such process can be modeled as a non-stationary Markov process. Our main result shows that any rest point of such dynamics can be approached by a sequence of similar "perturbed" dynamics in which players learn all the information about the value of each possible coalition
In Chapter 4 we study the dynamics of an experience good market using a two-sided adaptation Agent Based Computational Economics (ACE) model. The main focus of the analysis is the influence of consumers' habits on market structure. Our results show that given characteristics of consumers' behavior might sustain the diversity in the market both in terms of quality and firms' size. We observe that the more adaptive one side of the market is, the more the market reflects its interests.

A graph consists of a finite non-empty set of vertices and a set of unordered pairs of vertices, called edges. A dominating set of a graph is a set of vertices D such that every vertex not in D is adjacent to some vertex in D. A hypergraph on a finite set X is a collection of subsets of X, none of which is a proper subset of another. The domination hypergraph of a graph is the collection of all the minimal vertex dominating sets of the graph. A hypergraph is a domination hypergraph if it is the domination hypergraph of a graph. In general, a hypergraph is not a domination hypergraph. The objective of this work is to approximate a hypergraph by domination hypergraphs and that the optimal approximations determine uniquely the hypergraph. In Chapter 1 we introduce two structures of distributive lattices on the set of hypergraphs on a finite set and also define some operations: the complementary hypergraph and two transversal operations. We study the behavior of these operations with respect to the partial orders and the lattice structures. In Chapter 2 we first introduce several hypergraphs associated with a graph, the most important one being the domination hypergraph, and we establish several relationships among them. Then we compute the domination hypergraph of all graphs, modulo isomorphism, up to order 5. We also investigate when a given hypergraph is a domination hypergraph and find all domination hypergraphs in some cases. In Chapter 3 we present the problem of approximating a hypergraph by domination hypergraphs. We introduce four families of approximations of a hypergraph, which we call completions, depending on which partial order we use and on which side we approximate. We set some sufficient conditions for the existence of completions, introduce the sets of minimal or maximal completions of a hypergraph and study the concept of decomposition, which leads to the decomposition index of a hypergraph. Avoidance properties turn out to be an essential ingredient for the existence of domination completions. In Chapter 4 we give some computational techniques and calculate the upper minimal domination completions and the decomposition indices of some hypergraphs. In the appendices we give the SAGE code developed to perform the calculations of the thesis and we list all the domination hypergraphs of all graphs of order 5 and all the graphs of order 5 with the same domination hypergraph.
Un grafo consiste en un conjunto no vacío de vértices y un conjunto de pares no ordenados de vértices denominados aristas. Un conjunto de vértices D es dominante si todo vértice que no esté en D es adyacente a algún vértice de D. Un hipergrafo sobre un conjunto finito X es una colección de subconjuntos de X, ninguno de los cuales es un subconjunto de ningún otro. El hipergrafo de dominación de un grafo es la colección de los conjuntos dominantes minimales del grafo. Un hipergrafo es de dominación si es el hipergrafo de dominación de un grafo. En el capítulo 1 introducimos dos estructuras de retículo distributivo en el conjunto de hipergrafos sobre un conjunto finito y también definimos algunas operaciones: el complementario de un hipergrafo y las dos operaciones de transversal correspondientes a cada una de las estructuras de retículo. Estudiamos el comportamiento de estas operaciones con respecto a los órdenes parciales y las estructuras de retículo. En el capítulo 2 introducimos varios hipergrafos asociados a un grafo, siendo los más importantes el hipergrafo de dominación y el hipergrafo de independencia-dominación del grafo, cuyos elementos son los conjuntos independientes maximales del grafo, y establecemos varias relaciones entre ellos. Después calculamos el hipergrafo de dominación de todos los grafos de orden 5, salvo isomorfismo. También investigamos cuándo un hipergrafo es un hipergrafo de dominación y encontramos todos los hipergrafos de dominación en algunos casos. En el capítulo 3 presentamos el problema de la aproximación de un hipergrafo por hipergrafos de una familia dada. Dado un hipergrafo, definimos cuatro familias de aproximaciones, que llamamos compleciones, dependiendo del orden parcial usado y de por dónde aproximemos el hipergrafo. Establecemos condiciones suficientes para la existencia de compleciones, introducimos los conjuntos de compleciones minimales o maximales de un hipergrafo y estudiamos el concepto de descomposición, que conduce al índice de descomposición de un hipergrafo. Las propiedades de evitación resultan ser cruciales en el estudio de la existencia de descomposiciones. En el capítulo 4 presentamos técnicas de cálculo y calculamos las compleciones de dominación minimales superiores y los índices de descomposición de algunos hipergrafos. En los apéndices damos el código SAGE, desarrollado para realizar los cálculos de esta tesis, y damos la lista de los hipergrafos de dominación de todos los grafos de orden 5 así como todos los grafos de orden 5 que poseen el mismo hipergrafo de dominación.

In this thesis the Flexible Periodic Vehicle Routing Problem is introduced and studied. In this problem a carrier must establish a distribution plan to serve a given set of customers over a planning horizon using a fleet of homogeneous capacitated vehicles. The total demand of each customer is known for the time horizon and it can be satisfied by visiting the customer in several time periods. There is, however, a limit on the maximum quantity that can be delivered at each visit. The aim is to minimize the total routing cost. This problem can be seen as a generalization of the Periodic Vehicle Routing Problem which, instead, has fixed service schedules and fixed delivered quantities per visit. On the other hand, the Flexible Periodic Routing Problem shares some characteristics with the Inventory Routing Problem in which inventory levels are considered at each time period, the delivery of product is a decision of the problem and, typically, an inventory cost is involved in the objective function. The relation among these periodic routing problems is discussed and a worst-case analysis, which shows the advantages of the studied problem with respect to the problems with periodicity mentioned above, is presented. Furthermore, alternative mixed-integer programming formulations are described and computationally tested. Given the difficulty to optimally solve the studied problem for small size instances, a matheuristic is developed, which is able to solve large size instances efficiently. Extensive computational experiments illustrate the characteristics of the solutions of the problem and show that, also in practice, allowing flexible policies may produce substantial savings in the routing costs in comparison with both the Periodic Vehicle Routing Problem and the Inventory Routing Problem.
: En esta tesis se presenta y estudia el Problema de Ruteo de Vehículos Periódico Flexible. En este problema, un transportista debe establecer un plan de distribución para atender a un conjunto determinado de clientes durante un horizonte de planificación utilizando una flota de vehículos con capacidad homogénea. La demanda total de cada cliente es conocida por el horizonte temporal y se puede satisfacer visitando al cliente en varios períodos de tiempo. Sin embargo, hay un límite en la cantidad máxima que se puede entregar en cada visita. El objetivo es minimizar el costo total de ruteo. Este problema puede verse como una generalización del Problema clásico de Ruteo de Vehículos Periódico que, en cambio, tiene programas de servicio fijos y cantidades de entrega fijas por visita. Por otro lado, el Problema de Ruteo de Vehículos Periódico Flexible comparte algunas características con el Problema de Ruteo de Inventarios en el cual los niveles de inventario se consideran en cada período de tiempo, la entrega del producto es una variable de decisión y, típicamente, un costo de inventario está involucrado en la función objetivo. Se discute la relación entre estos problemas periódicos de rutas y se presenta un análisis del peor de los casos, que muestra las ventajas del problema estudiado con respecto a los problemas periódicos mencionados anteriormente. Además, las formulaciones alternativas de programación entera mixta se describen y se prueban computacionalmente. Dada la dificultad de resolver a optimalidad el problema estudiado para instancias de tamaño pequeño , se desarrolla una matheurística que puede resolver instancias de gran tamaño de manera eficiente. Una extensa experiencia computacional ilustra las características de las soluciones del problema y muestra que, también en la práctica, permitir políticas flexibles puede producir ahorros sustanciales en los costos de ruteo en comparación con el Problema de Ruteo de Vehículos Periódico y el Problema de Rutas de Inventario.

We consider some models of random graphs and directed graphs and investigate their behavior near thresholds for the appearance of certain types of connected components. Firstly, we look at the critical window for the appearance of a giant strongly connected component in binomial random digraphs. We provide bounds on the probability that the largest strongly connected component is very large or very small. Next, we study the configuration model for graphs and show new upper bounds on the size of the largest connected component in the subcritical and barely subcritical regimes. We also show that these bounds are tight in some instances. Finally we look at the configuration model for random digraphs. We investigate the barely sub-critical region and show that this model behaves similarly to the binomial random digraph whose barely sub- and super-critical behaviour was studied by Luczak and Seierstad. Moreover, we show the existence of a threshold for the existence of a giant weak component, as predicted by Kryven.
En aquesta tesi considerem diversos models de grafs i graf dirigits aleatoris, i investiguem el seu comportament a prop dels llindars per l'aparició de certs tipus de components connexes. En primer lloc, estudiem la finestra crítica per a l'aparició d'una component fortament connexa en dígrafs aleatoris binomials (o d'Erdos-Rényi). En particular, provem diversos resultats sobre la probabilitat límit que la component fortament connexa sigui sigui molt gran o molt petita. A continuació, estudiem el model de configuració per a grafs no dirigits i mostrem noves cotes superiors per la mida de la component connexa més gran en els règims sub-crítics i quasi-subcrítics. També demostrem que, en general, aquestes cotes no poden ser millorades. Finalment, estudiem el model de configuració per a dígrafs aleatoris. Ens centrem en la regió quasi-subcrítica i demostrem que aquest model es comporta de manera similar al model binomial, el comportament del qual va ser estudiat per Luczak i Seierstad en les regions quasi-subcrítica i quasi-supercrítica. A més a més, demostrem l'existència d'una funció llindar per a l'existència d'una component feble gegant, tal com va predir Kryven.
Matemàtica aplicada

Esta investigación surge de la necesidad de elaborar un discurso teórico que nos permita superar el problema de conocimiento fundamentado en el ensayo y el error, práctica que a menudo utilizamos en nuestras aulas, y aportar directrices más sólidas que nos permitan obtener criterios generales para poder “leer” y “escribir” este tipo de mensajes. Nuestro objetivo es definir y enumerar los elementos mínimos sin significado de las representaciones visuales funcionales, bidimensionales y fijas , que nos permitan profundizar en cómo se articula su significado y hacer una propuesta concreta sobre su análisis, a partir de las aportaciones de los diferentes autores consultados. La situación con la que nos encontramos es la de que los estudios de representación visual no proceden de una disciplina propia, sino de varias (arte, psicología, comunicación, semiótica, etc.), y que no dispone de un cuerpo teórico estable, sino que cambia en función de cada disciplina. Esto nos obliga a realizar un enfoque interdisciplinar y a comprender cada propuesta teórica, para tratar de formalizar una especie de «mínimo común múltiplo» de los elementos constitutivos, a partir de las aportaciones de los autores consultados. El estudio detallado de las fuentes de referencia nos permiten agrupar los textos en cuatro grandes bloques: • los que toman como referencia las aportaciones de Da Vinci y Kandinsky (Villafañe, Wong, Arnheim, etc.); • los que siguen, de alguna manera, el camino iniciado por Barthes (Joly y el Grupo μ, entre otros); • los que reflexionan sobre las articulaciones de las representaciones visuales, y sobre la noción de código, a partir de las aportaciones de Prieto y de Eco, fundamentalmente; • y aquellos que han realizado sus aportaciones desde un enfoque más visual que lingüístico, teniendo en cuenta algunas de sus características como, por ejemplo, la espacialidad (Saint Martin, Cossette). Además, en nuestra búsqueda de los elementos básicos de las representaciones visuales funcionales, al margen de épocas o estilos, tendremos en cuenta el cuerpo teórico que nos proporciona la lingüística porque, aunque en muchos sentidos las estructuras verbales y visuales no son comparables, es un referente sine qua non para un análisis de estas características, bien para utilizar sus aportaciones, bien para diferenciarse de ellas. En nuestro caso, en tanto que tratamos de profundizar en la construcción del signo, nos enmarcamos dentro de los estudios de la semiótica visual porque, aunque no hay un acuerdo total al respecto, consideramos que la semiótica es la disciplina que debería elaborar una teoría de la significación y, en el caso de la semiótica de la imagen, la responsable de encontrar los equivalentes visuales de los conceptos lingüísticos de fonema, palabra, oración, etc.
Aquesta investigació parteix de la necessitat d'elaborar un discurs teòric que ens permeti superar el problema de coneixement fonamentat en l'assaig i l'error, pràctica que sovint fem servir a les nostres aules, i aportar directrius més sòlides que ens permetin obtenir criteris generals per poder " llegir "i" escriure "aquest tipus de missatges. El nostre objectiu és definir i enumerar els elements mínims sense significat de les representacions visuals funcionals, bidimensionals i fixes , que ens permetin aprofundir en com s'articula el seu significat i fer una proposta concreta sobre la seva anàlisi, a partir de les aportacions dels diferents autors consultats. La situació amb què ens trobem és la de que els estudis de representació visual no procedeixen d'una disciplina única i pròpia, sinó de diverses (art, psicologia, comunicació, semiòtica, etc.), i que no disposa d'un cos teòric estable, sinó que canvia en funció de cada disciplina. Això ens obliga a fer un enfocament interdisciplinari i comprendre cada proposta teòrica, per intentar formalitzar una mena de «mínim comú múltiple» dels elements constitutius, a partir de les aportacions dels autors consultats. L'estudi detallat de les fonts de referència ens permeten agrupar els textos en quatre grans blocs: • els que prenen com a referència les aportacions de Da Vinci i Kandinsky (Villafañe, Wong, Arnheim, etc.); • els que segueixen, d'alguna manera, el camí iniciat per Barthes (Joly i el Grup μ, entre d'altres); • els que reflexionen sobre les articulacions de les representacions visuals, i sobre la noció de codi, a partir de les aportacions de Prieto i d'Eco, fonamentalment; • i aquells que han realitzat les seves aportacions des d'un enfocament més visual que lingüístic, tenint en compte algunes de les seves característiques com, per exemple, l'espacialitat (Saint Martin, Cossette). A més, en la nostra recerca dels elements bàsics de les representacions visuals funcionals, al marge d'èpoques o estils, tindrem en compte el cos teòric que ens proporciona la lingüística perquè, encara que en molts sentits les estructures verbals i visuals no són comparables, és un referent sine qua non per a una anàlisi d'aquestes característiques, bé per fer servir les seves aportacions, bé per allunyar-se de elles. En el nostre cas, en tant que tractem d'aprofundir en la construcció del signe, ens emmarquem dins dels estudis de la semiòtica visual perquè, encara que no hi ha un acord total sobre això, considerem que la semiòtica és la disciplina que hauria d'elaborar una teoria de la significació i, en el cas de la semiòtica de la imatge, la responsable de trobar els equivalents visuals dels conceptes lingüístics de fonema, paraula, oració, etc.
Our research stems from the need to develop a theoretical discourse capable of overcoming the problem of knowledge based on trial and error—common in our classrooms—and of providing more solid guidelines and general criteria to ‘read’ and ‘write’ this type of messages. Our aims are: to identify and define those minimum elements without meaning in two-dimensional, functional, fixed visual representations that illustrate how its actual meaning is conveyed; and to propose how those elements might be analyzed, based on contributions of the different authors we consulted. The current situation is that studies in visual representation do not have their own specialty and are dispersed among different disciplines (art, psychology, communications, semiotics, etc.) and do not have a stable body of theory (thus changing according to each discipline). We must therefore adopt an interdisciplinary approach and broach each theoretical proposal separately in order to formalize something like a ‘minimum common denominator’ of the constituent elements based, again, on the contributions of the different authors we consulted. A detailed analysis of sources and references allow the literature to be broken down into four large blocks: • Those that look to Da Vinci and Kandinsky (Villafañe, Wong, Arnheim, etc.); • Those that follow to some degree the path marked by Barthes (Joly and Groupe μ, among others); • Those that reflect on the production of visual representations and the idea of code, fundamentally through the prisms of Prieto and Eco; • Those that use a visual (rather than linguistic) focus and consider characteristics such as ‘spaceness’ (Saint Martin, Cossette). In our review of the basic elements of functional visual representations and independently of period and styles, we use the theoretical corpus that linguistics offers—even though verbal and visual structures are not always comparable—because it is an inevitable point of reference for an analysis of this nature, either to co-opt its concepts or differ from them. We immediately situate ourselves in the field of visual semiotics as soon as we try to dig deeper into the construction of the signifier because (although there is no general agreement in this regard) semiotics should be the discipline that elaborates a theory of meaning and—as in the case of semiotics of images—finds visual equivalents to the linguistic concepts of phoneme, word, speech, and so on.

Nuestra línea de investigación se ha desarrollado en el ámbito de la estadística aplicada a las finanzas. Nuestro objetivo es encontrar y analizar nuevos modelos estadísticos para ajustar los datos financieros y nuevas técnicas para estudiar el comportamiento de las colas. Una aplicación destacada de este trabajo es el estudio del riesgo operacional. En los últimos años, la industria bancaria ha cambiado profundamente por los procesos de liberalización, innovación financiera y tecnológica. Esto, ha generado en las entidades financieras una evolución en el ámbito de la modelización de procesos para la medición y gestión del riesgo. El riesgo financiero se define como el impacto adverso en el rendimiento debido a diferentes fuentes de incertidubre. En la actualidad, y desde una perspectiva avanzada de riesgos, se identificarían y se cuantificarían tres tipos de riesgo: riesgo de mercado, riesgo de crédito y riesgo operacional. A diferencia de los anteriores, el riesgo operacional es un riesgo que no es producto de la toma de una posición de riesgo, tiene su origen en sucesos que no pueden ser adscritos a riesgo de mercado o a riesgo de crédito, se define como la pérdida potencial por deficiencias en los controles, por los errores en el procesamiento y almacenamiento de las operaciones o en la transmisión de información, así como por resoluciones administrativas y judiciales adversas, fraudes, robos o por factores externos. El método más reciente para la cobertura de riesgo operacional es el método de medición avanzado (AMA) que consiste en la modelización de la distribución agregada de pérdidas (Loss Distribution Approach o LDA) que se ha utilizado con éxito en el ámbito de seguros. Bajo el supuesto de que las severidades son independientes entre si e independientes de la frecuencia de los sucesos, la metodología LDA requiere la modelización por separado de la frecuencia y de la severidad. El capital regulatorio se calcula como el percentil de la distribución agregada de pérdidas para un nivel de probabilidad del 99;9%. Las fluctuaciones pronunciadas de precios conducen a serias inestabilidades en los mercados financieros. Estas perturbaciones llevan a problemas en la gestión del riesgo. En este contexto, es necesaria la modelización del comportamiento de estos precios que alcanzan valores extremos. La distribución normal no determina con suficiente precisión dicho comportamiento, lo cual obliga a recurrir a otro tipo de distribuciones de colas pesadas o semi pesadas. En el Capítulo uno, haremos una descripción de las distribuciones de colas pesadas que son distribuciones que tienen colas más pesadas que la distribución exponencial. Históricamente se han utilizado en el mundo de seguros, especificamente las distribuciones subexponenciales. En la última década, esta metodología se ha trasladado al mundo de las finanzas. De forma más amplia los mercados financieros están bajo una permanente tensión por la interacción entre la oferta y la demanda, lo cual implica fluctuaciones pronunciadas en los precios. El modelo clásico para estudiar la evolución de los precios es el modelo de Black Scholes que supone normalidad en la distribución de los precios. Los estudios empíricos, que presentan una curtosis elevada y valores extremos que no se pueden ajustar por la distribución normal, muestran que este modelo está lejos de ser adecuado. Suponiendo normalidad de la distribución de la oferta y de la demanda, y si hay tantas ofertas como demandas (mercado ideal), las transacciones siguen una mixtura de normales. En caso contrario, cuando no se aceptan de la misma manera las ofertas y las demandas las transacciones pueden seguir una mixtura de normales truncadas. En el Capítulo dos, proponemos la mixtura de normales truncadas para ajustar los datos de tipo de cambio. Es un modelo muy apropiado dado que en la práctica nos permite estudiar la no-normalidad de los datos teniendo en cuenta la asimetría de los mismos. Para ello, primero desarrollamos las propiedades de la distribución propuesta y a continuación demostramos que la función de verosimilitud tiene un máximo único y que este máximo depende del coeficiente de variación. El enfoque basado en la modelización de la distribución de severidad mediante distribuciones de colas semi pesadas tales que la distribución lognormal, la inversa gaussiana y la mixtura de normales proporcionan estimaciones robustas estables del capital regulatorio, es decir, las cifras de capital entre dos periodos sólo pueden variar por su exposición al riesgo. El enfoque basado en la teoría de valor extremo que se caracteriza por el ajuste de los valores que superan un determinado umbral con la distribución de Pareto generalizada es de mucha importancia dado que las entidades se basan únicamente sobre las pérdidas elevadas, aunque la elección de manera eficiente del umbral a partir del cual se realiza el ajuste a una distribución de Pareto es crucial para obtener valores estables de las medidas de riesgo. Varios autores estudiaron la estimación de la distribución de Pareto generalizada mediante el método de máxima verosimilitud. No obstante, los métodos numéricos no siempre tienen soluciones sobretodo cuando las muestras son pequeñas, por ello se han propuesto otros métodos tales como el método de los momentos ponderados que sólo se puede utilizar cuando el momento de orden dos es finito, y el método que consiste en estimar los parámetros a través de los estadísticos de orden. En el Capítulo tres, explicaremos los problemas destacados de la no convergencia en algunos casos de la función profile verosimilitud de la distribución de Pareto generalizada. Luego, demostraremos que la función profile verosimilitud se caracteriza por el coeficiente de variación empírico. Por último, probaremos que en el caso de la distribución de Pareto, la función de verosimilitud tiene un máximo global cuando el coeficiente de variación empírico es mayor que uno. Por otro lado, ilustramos con un ejemplo que la función de verosimilitud de la distribución de Pareto generalizada puede no tener soluciones. En el Capítulo cuatro, utilizamos la caracterización de la distribución de Pareto generalizada a través del coeficiente de variación condicionado para desarrollar una metodología previa y complementaria a los estudios paramétricos y contrastar el modelo desde un punto de vista empírico. Es un método alternativo a los métodos clásicos ME-Plot y el Hill-Plot para estudiar las colas. Además nos permite encontrar de manera eficiente el umbral a partir del cual podemos ajustar los datos por una distribución de Pareto y estimar el parámetro del peso de la cola. Por otro lado, proponemos un test de exponencialidad contra las alternativas de cola Pareto. Una de las dificultades de la distribución de Pareto generalizada es que al incluir distribuciones de soporte acotado, existen problemas de convergencia de los estimadores. Además las ecuaciones de verosimilitud para muestras pequeñas pueden no tener soluciones. Por ello, proponemos la distribucón TNP que es la unión de la normal truncada, la distribución exponencial y la distribución de Pareto como alternativa a la distribución GPD.
Our line of investigation has developed in the field of the statistical applied to the finances. Our aim is to find and analyse new statistical models to adjust the financial data and new techniques to study the behavior of the tails. An application of this work is the study of operational risk. The banking business has changed deeply by the processes of liberalization, financial and technological innovation. This, has generated an evolution in the field of modeling the processes for the measurement and the quantification of the risk. The risk of loss has his origin in events that can not be attribute to market risk or to credit risk, it is resulting from inadequate or failed internal processes, people and systems or from external events. This definition includes legal risk but excludes strategic and reputacional risk. The most recent method for hedging the operational risk is the method of advanced measurement (AMA) that consists in modeling the aggregate distribution of losses (Loss Distribution Approach or LDA) that has been used successfully in the field of insurances. assuming that the severities are independent, and, that are independent of the frequency of the events, the methodology LDA requires modeling separately the frequency and the severity. The VaR is then calculated as the percentile of the aggregate distribution of losses for a level of probability 99;9%. In the Chapter one, we give an overview on heavy-tailed distributions. Historically, it have been used in the world of insurances, specifically the distributions subexponentials. In the last decade, this methodology has moved to the world of the finances. In the Chapter two, it is shown that the prices formation mechanism may explain some amount of non-normality. Assuming normality for bid and ask prices, the observed transaction prices may be a mixture of normal distributions or a mixture of left- right truncated normal distributions, the latter case being more likely. The statistical properties of the mixture of left-right truncated normal distri- butions are developed. It is proved that there is only one maximum for the likelihood function and the maximum is closely related to the coeficient of variation. Our results show that continuity at zero of this distribution can be avoided in statistical analysis. Empirical work suggests that in financial data non-normality is also produced for a large number of values close to the mean, here referred to as ïnliers". This could explain that the Laplace approximation is often a better approach than normal distribution for daily returns. The approach based in the modeling the distribution of severity by semi weighed distributions such as the lognormal distribution, the inverse gaussian and the mixture of normal provide robust estimates estables of the VaR. The approach based in the theory of extreme value that adjust the values over an determined threshold by the generalized Pareto distribution is of importance To obtain values estables of the measures of the risk. In the Chapter three, we provide precise arguments to explain the anomalous behavior of the likelihood surface when sampling from the generalized Pareto distribution for small or moderate samples. The behavior of the profile-likelihood function is characterized in terms of the empirical coefficient of variation. A suficient condition is given for global maximum of the likelihood function of the Pareto distribution to be at a finite point. In the Chapter four, we develop a previous and complementary methodology to the parametric studies to contrast the model from a point of empirical view. New methods to decide between polynomial or exponential tails are introduced. Is an alternative method to the classical methods ME-Plot and the Hill-Plot. The key idea is based on a characterization of the exponential distribution and uses the residual coefficient of variation as a random process. A graphical method, called a CV plot, is introduced to distinguish between exponential and polynomial tails. Moreover, new statistics introduced from a multivariate point of view allow for testing exponentiality using simultaneously several thresholds. The usefulness of our approach is clearly shown with the daily returns of exchange rates between the US dollar and the Japan yen. One of the difficulties of the distribution of generalized Pareto is that include bounded distributions, there lead a problems of convergence of the estimators. Besides the likelihood functions for small samples can not having solutions. Thus, we propose the TNP distribution that is the union of the normal truncated, the exponential distribution and the distribution of Pareto and is an alternative to the distribution GPD to modeling financial data.

El objetivo original de esta tesis, titulada ‘Métodos Estadísticos Avanzados para Radiación Citogenética Radioactiva’ era ’desarrollar nuevas soluciones para el análisis estadístico de datos citogenéticos’ y la cuestión tratada en este proyecto era ‘cuál es la mejor manera de cuantificar correctamente el daño citogenético inducido por la radiación en complejos escenarios de exposición a la radiación, donde se reconoce que las técnicas actuales son insuficientes’. El proyecto fue creado con el objetivo de proveer estimaciones citogenéticas de dosis con mayor precisión estadística llevadas a cabo para el servicio de dosimetría biológica de la Public Health England y para el propósito de la investigación científica, los cuales informarán después correspondientemente la evaluación de riesgo de la salud para protección radiológica. Los objetivos específicos eran: 1. Identificación de las limitaciones en las metodologías citogenéticas existentes (además de las previamente identificadas); 2. Identificación de escenarios que plantean dificultades para la biodosimetría citogenética práctica, para los cuales los avances de los métodos estadísticos deben ofrecer soluciones; 3. Identificación y comparación de soluciones que han sido previamente desarrolladas/propuestas en la literatura y su futuro desarrollo/aplicación; 4. Desarrollo y pruebas de nuevas soluciones en los marcos Bayesianos y clásicos, y la implementación de éstos para su aplicación en la biodosimetría citogenética (por ejemplo en Java); 5. Publicación de los resultados. Este proyecto ha llevado a cabo el objetivo principal y los específicos a través seis publicaciones científicas originales de investigación en métodos estadísticos para dosimetría biológica. Los principales resultados de cada una de estas publicaciones son los siguientes: Una revisión de la literatura para identificar escenarios de exposición a la radiación que sugieren trabajo futuro en modelos Bayesianos y presenta un ejemplo práctico; Desarrollo de técnicas para solucionar las limitaciones identificadas, en particular nuevos modelos de regresión inversa e irradiación de cuerpo parcial; Aplicación de estos nuevos métodos en existentes y nuevos datos para diferentes escenarios y Desarrollo de dos paquetes de R-project, uno para dar soporte al uso de la nueva metodología y otro para el manejo de la familia de Distribuciones de Hermite Generalizada.
The original aim of this thesis, entitled ‘Advanced Statistical Methods for Cytogenetic Radiation Biodosimetry’ was to ‘develop novel solutions for statistical analysis of cytogenetic data’ and the question that was to be addressed by this project was ‘how best to correctly quantify cytogenetic damage that is induced by radiation in complex scenarios of radiation exposure, where it is recognised that the current techniques are insufficient.’ The project was created with the aim of providing increased statistical accuracy of cytogenetic dose estimates carried out both for the Public Health England's biological dosimetry service and for research purposes, which will correspondingly further inform health risk assessment for radiation protection. The specific objectives were: 1. Identification of further limitations in the existing cytogenetic methodologies (in addition to those that had been previously identified); 2. Identification of scenarios that pose particular difficulties for practical cytogenetic biodosimetry, for which advancement of statistical methods may offer solutions; 3. Identification and comparison of solutions that have been previously developed/proposed in the literature and their further development/application (as appropriate) for the scenarios found in 2; 4. Development and testing of further novel solutions, in the Bayesian and classical frameworks, and implementation of these for use in practical cytogenetic biodosimetry (e.g. in Java); 5. Publication of the results. This project has addressed the original aim and above objectives through original research into statistical methods for biological dosimetry resulting in six peer-reviewed publications. The main results from each of these publications are as follows: A review of the literature to identify radiation exposure scenarios requiring further work which outlines the rationale behind a Bayesian approach and gives a practical example; Development of techniques to address the identified gaps, in particular new models for inverse regression and partial body irradiation; Demonstration of application of these novel methodologies to existing and new cytogenetic data in a number of different scenarios and Development of two R-project packages, one to support biological dose estimation using the novel methodology and another to manage the family of Generalized Hermite Distributions.

La teoria de valors extrems (EVT) és l’única disciplina estadística que desenvolupa tècniques i models per descriure el comportament inusual en comptes de l’habitual, l’objectiu principal de la qual és l’estimació de quantils corresponents a successos molt extrems. En moltes àrees d’aplicació un requisit típic és estimar el valor en risc a un cert nivell (VaR), prou alt per a que la possibilitat de superació d’aquest sigui menor a una quantitat donada. La teoria probabilista associada a l’EVT es troba ben establerta, gràcies als resultats de Fisher i Tippet (1923), Balkema i de Haan (1974) i Pickands (1975). Dos enfocs principals van ser desenvolupats: el mètode per blocs de màxims i el mètode d’excessos sobre un llindar, l’aplicació dels quals presenta dificultats a l’hora d’aplicar eines estadístiques, Diebold et al. (1998). La determinació del llindar a partir del qual la distribució límit pot utilitzar-se i del comportament d’aquesta són els problemes principals a tractar. Per distingir les dades generals de les que són objecte d’estudi, es farà servir el concepte de cua, el qual fa referència a aquells valors que es troben per sobre d’un valor suficientment alt. Per als excessos sobre un llindar, la distribució asimptòtica que caracteritza el comportament de la cua és la Pareto Generalitzada (GPD); el seu paràmetre de forma, anomenat índex del valor extrem, permet classificar les cues en pesades, exponencials i lleugeres. L’aplicació del model GPD es pot trobar extensament detallada a McNeil et al. (2005) o Embrechts et al. (1997), però es troben limitacions, per exemple, quan no hi ha moments suficients o la subjectivitat que sorgeix quan s’utilitzen mètodes gràfics. L’objectiu d’aquesta tesi és presentar noves eines per a l’EVT, que serveixen per a la selecció de llindar i l’estimació de l’índex del valor extrem i solucionen alguns dels problemes existents. En el Capítol 1 es fa un repàs de la teoria estadística per a valors extrems. Es recorden els mètodes gràfics més utilitzats, el mean excess plot i el Hill-plot, i els mètodes d’estimació disponibles per a la GPD, finalment es presenten un nou mètode gràfic anomenat CV-plot, Castillo et al. (2014), i un enfoc aparegut recentment per a cues pesades i exponencials, Castillo et al. (2013). En el Capítol 2 s’utilitza el fet que el coeficient de variació residual caracteritza distribucions, Gupta i Kirmani (2000), per trobar el CV-plot teòric per a algunes distribucions i aplicar la teoria asimptòtica al cas de la GPD, sempre que hi hagi existència de moments d’ordre quatre. Gràcies a una transformació, presentada en el Capítol 3, el CV-plot es podrà aplicar en qualsevol situació. En el Capítol 4 es presenten uns estadístics que permeten estimar l’índex del valor extrem, contrastar la hipòtesi de GPD i s’utilitzen en un algoritme automàtic de selecció de llindars. Aquest tercer punt suposa un gran avenç per a l’aplicació del mètode Peak over Threshold, el qual requereix de l’estimació del llindar, a partir d’un mètode gràfic, i l’estimació de l’índex del valor extrem, mitjançant màxima versemblança, Coles (2001), ja que desapareix la subjectivitat de l’investigador quan s’estima el llindar. El Capítol 5 es troba dedicat a l’estudi de 16 conjunts de dades en sistemes informàtics encastats. El CV-plot i els estadístics Tm han estat utilitzats, obtenint bons resultats per a la majoria dels casos. En el Capítol 6 es tornen a aplicar les noves eines a les dades daneses sobre assegurances de focs, McNeil (1997), i les dades financeres analitzades a Gomes i Pestana (2007). Per finalitzar, en el Capítol 7 es presenten les conclusions d’aquest treball i s’exposen les noves línies de recerca que es poden seguir.
Extreme value theory (EVT) is the only statistical discipline that develops techniques and models to describe the unusual behavior instead of the usual one, the main objective of which is the quantile estimation corresponding to very extreme events. In many areas of application, a typical requirement is to estimate the value at risk (VaR), high enough to overcome the possibility that this is less than a given amount. The probability theory associated to the EVT is well-established thanks to the results of Fisher and Tippet (1923), Balkema and de Haan (1974), and Pickands (1975). Two main approaches were developed; the block maxima method and the method of the excesses over a threshold, the application of which presents difficulties in applying statistical tools, Diebold et al. (1998). The determination of the threshold from which the limit distribution can be used and its behavior are the main problems to deal with. To distinguish the general data from those which are under study, we will use the concept of tail, which refers to values that are above a sufficiently high value. For excesses over a threshold the distribution that characterizes the asymptotic behavior of the tail is the Generalized Pareto (GPD), its shape parameter, called extreme value index, classifies tails in heavy, exponential, and light. The application of the GPD model is extensively detailed in McNeil et al. (2005) and Embrechts et al. (1997), but there are limitations, for example, when there are no finite moments or the subjectivity that arises when graphical methods are used. The aim of this thesis is to present new tools for EVT, which can be used for the threshold selection and the extreme value index estimation and they solve some existing problems. Chapter 1 is a review of statistical theory for extreme values. The most used graphical methods are remembered, the mean excess plot and the Hill-plot, and the estimation methods available for GPD too. Finally, a new graphical method called CV plot, Castillo et al. (2014), and a recently appeared approach to heavy and exponential tails, Castillo et al. (2013), are presented. In Chapter 2 the fact that the coefficient of variation characterizes residual distributions, Gupta and Kirman (2000), is used to find the theoretical CV plot for some distributions and to apply the asymptotic theory to the case of GPD, provided by the existence of four finite moments. Thanks to a transformation, presented in Chapter 3, the CV-plot can be applied in any situation. Chapter 4 presents statistics that allow us to estimate the extreme value index, to contrast the hypothesis of GPD and they are used in an automated selection thresholds algorithm. This third point is a major breakthrough for the application of the method Peak over Threshold, which requires estimating the threshold from a graphical method and estimating the extreme value index through the maximum likelihood, Coles (2001), since researcher's subjectivity disappears when the threshold is estimated. Chapter 5 is dedicated to the study of 16 data sets in embedded systems. The CV plot and statistical Tm have been used, obtaining good results in most cases. In Chapter 6, we will again apply new tools to data on Danish fire insurance, McNeil (1997), and financial data analyzed in Gomes and Pestana (2007). Finally, Chapter 7 presents the conclusions of this work and the new lines of research.

La agro-indústria xilena ha experimentat un augment constant d'exportacions de fruita processada en la darrera dècada, arribant a un augment del 107% en volum total i 185% en valor. Aquest creixement significa que la cadena de subministrament de fruita fresca, ja sigui per a conserva, deshidratats, congelat i fresc de fruites o sucs, requereix suport per fer gestió cada vegada més eficient. Fins ara, alguns problemes relacionades directament amb la necessitat de millorar la competitivitat del sector no han estat encara tractats. En els últims anys els costos de producció han augmentat degut principalment a l'escassetat de mà d'obra i la mala qualitat de la fruita fresca. Això fa que millorar l'eficiència de cadena de subministrament i per tant la competitivitat agroindústria, requereixi de noves eines que serveixin de suport a la presa de decisions a la cadena de subministrament de fruita fresca. En aquest context, l'objectiu general d'aquesta recerca era desenvolupar un conjunt d'eines per donar suport a les decisions tàctiques de la cadena de subministrament de la fruita i millorar la gestió de compres, de les cambres frigorífiques i el transport. Tres importants contribucions es fan en aquest treball de recerca. La primera d'elles té a veure amb l'estat de l'art de les cadenes de subministrament, revisant els models d'optimització aplicats a les cadenes de subministrament de fruita fresca. La segona consisteix a proporcionar quatre eines per recolzar les decisions tàctiques de les cadenes de subministrament de fruita fresca, en concret, tres models matemàtics per a l'optimització de les decisions que donen suport a la selecció de productors i la compra de fruita fresca, el seu posterior emmagatzematge i transport i la proposta d'un model per a la gestió de cambres frigorífiques. Una tercera aportació és la proposta d'un sistema de suport a la presa de decisió (DSS), permeti la transparència del coneixement dels models anteriors al sector per al seu us pràctic. Destacar el valor addicional del treball a l'haver aplicat els models a casos reals. Així, tots el models proposats van ser validats amb l'ajut de l'agroindústria de la regió centre-sud de Xile que tenien problemes amb la seva cadena de subministrament.
The Chilean agro-industry has experienced a steady increase of industrialized fruit exports over the last decade, reaching a total volume increase of 107% and 185% in value. This growth means that the fresh fruit supply chain, either for preserved, frozen, dehydrated, fresh fruit or juices, requires support in order to make management increasingly more efficient. So far, some problems directly related to the need to improve the sector´s competitiveness have not yet been addressed. In the last few years production costs have risen mainly due to labor shortage and poor quality of raw material (fresh fruit). That is why, improving the supply chain efficiency and thus the agro-industry competitiveness, particularly in the center-south region of the country, requires new tools that could support decisions making regarding the fresh fruit supply chain. Within this context, the general objective of this research was to develop a set of tools aiming to support tactical decisions that could enhance management of fresh fruit purchasing, cold storage, transport, and opening of cold chambers. Three important contributions are made in this research study. The first one has to do with the state-ofthe- art of supply chains management, by reviewing optimization models applied to fresh fruit supply chains. The second one consists in providing four tools to support tactical decisions regarding fresh fruit supply chains, specifically, three mathematical models for the optimization of decisions that support the selection of growers and the purchasing of fresh fruit, their subsequent storage and transportation, and the proposal of a mathematical model for cold storage management. The third contribution is the proposal of a Decision Support System (DSS), which aids in decisions about growers selection and purchasing of fresh fruit, as well as its subsequent storage and transportation. Finally, there is an important additional contribution that involves the application of the models to real cases. All models proposed were created and validated with the support of agro-industries from the centersouth region of the country having problems with their supply chain, which were addressed in this research study.

La Ciència de la Complexitat és un camp d'estudi interdisciplinari que aplica conceptes i mètodes de la física estadística i la teoria dels fenòmens crítics a altres camps, des de la Biologia a l'Economia, la Geologia o la Ciència de l'Esport. Ciència de la Complexitat posa en dubte el reduccionisme científic, afirmant que "el tots és més que la suma de les parts", i que, per tant, el reduccionisme fracassarà tard o d'hora: Si un problema o sistema s'analitza estudiant-ne les unitats que el constitueixen, i aquestes unitats s'estudien, al seu torn, en termes d'altres elements més simples, i així successivament, aleshores s'acaba formant una jerarquia de paradigmes o nivells d'estudi. I si bé el sistema pot entendres, fins a cert grau, en termes de conceptes i mecanismes específics de cada un dels nivells d'estudi, no hi ha cap garantia d'una reconstrucció comprensible i satisfactòria del sistema. En altres paraules, el reduccionisme només ens ofereix un bitllet d'anada dins de la jerarquia de teories, en direcció a aquelles suposadament més bàsiques i elementals; la Ciència de la Complexitat tracta de trobar el camí de tornada, des dels elements microscòpic elementals fins a l'objecte inicial d'estudi. La invariància d'escala es la propietat d'ésser invariant sota una transformació d'escala. Per tant, els objectes invariants d'escala no tenen escales característiques, ja que un re-escalament de les variables no produeix cap efecte detectable. Això es considera molt important en el paradigma de la complexitat, ja que permet connectar el món microscòpic amb el món macroscòpic. Aquesta Tesi consisteix en un estudi de les propietats invariants d'escala de la representació en freqüències de la llei de Zipf en llenguatge, de la corba de creixement "type-token" en sistemes zipfians generals, i de la distribució de durada d'esdeveniments en un "thresholded birth-death process". S'evidencia que algunes propietats d'aquests sistemes poden expressar-se com a lleis d'escala, i per tant són invariants d'escala. Es determinen els exponents d'escala i les funciones d'escala corresponents.
Complexity Science is an interdisciplinary field of study that applies ideas and methods mostly from statistical physics and critical phenomena to a variety of systems in almost any other field, from Biology to Economics, to Geology or even Sports Science. In essence, it attempts to challenge the reductionist approach to scientific inquiry by claiming that "the total is more that the sum of its parts" and that, therefore, reductionism shall ultimately fail: When a problem or system is analyzed by studying its constituent units, and these units are subsequently analyzed in terms of even simpler units, and so on, then a descending hierarchy of realms of study is formed. And while the system might be somewhat understood in terms of different concepts at each different level, from the coarser description down to its most elementary units, there is no guarantee of a successful bottom-up, comprehensive "reconstruction" of the system. Reductionism only provides a way down the hierarchy of theories, i.e., towards those supposedly more basic and elementary; Complexity aims at finding a way back home, that is, from the basic elementary units up to the original object of study. Scale invariance is the property of being invariant under a scale transformation. Thus, scale-invariant systems lack characteristic scales, as rescaling its variables leaves them unchanged. This is considered of importance in Complexity Science, because it provides a bridge between different realms of physics, linking the microscopic world with the macroscopic world. This Thesis studies the scale invariant properties of the frequency-count representation of Zipf's law in natural languages, the type-token growth curve of general Zipf's systems and the distribution of event durations in a thresholded birth-death process. It is shown that some properties of this systems can be expressed as scaling laws, and are therefore scale-invariant. The associated scaling exponents and scaling functions are determined.

¿Es adecuado un sistema rápido pero poco robusto?¿Es adecuado un sistema disponible pero lento? Estas dos cuestiones representan la importancia de prestaciones y disponibilidad en clusters de computadores.
Esta tesis se enmarca en el estudio de la relación entre prestaciones y disponibilidad cuando un cluster de computadores basado en el modelo de paso de mensajes, usa un protocolo de tolerancia a fallos basado en rollback-recovery con log de mensajes pesimista. Esta relación también es conocida como performability.
Los principales factores que influyen en la performability cuando se usa la arquitectura de tolerancia a fallos RADIC son identificados y estudiados. Los factores fundamentales son la latencia de envío de mensajes que se incrementa cuando se usa el log pesimista, que implica una perdida de prestaciones, como también la replicación de los datos redundantes (checkpoint y log) necesaria para el incremento de la disponibilidad en RADIC y el cambio de la distribución de procesos por nodo causada por los fallos, que pueden causar degradación de las prestaciones así como las paradas por mantenimiento preventivo.
Para tratar estos problemas se proponen alternativas de diseño basadas en análisis de la performability. La pérdida de prestaciones causada por el log y la replicación ha sido mitigada usando la técnica de pipeline. El cambio en la distribución de procesos por nodo puede ser evitado o restaurada usando un mecanismo flexible y transparente de redundancia dinámica que ha sido propuesto, que permite inserción dinámica de nodos spare o de repuesto.
Los resultados obtenidos demuestran que las contribuciones presentadas son capaces de mejorar la performability de un cluster de computadores cuando se usa una solución de tolerancia a fallos como RADIC.
Is a fast but fragile system good? Is an available but slow system good? These two questions demonstrate the importance of performance and availability in computer clusters.
This thesis addresses issues correlated to performance and availability when a rollback- recovery pessimistic message log based fault tolerance protocol is applied into a computer cluster based on the message-passing model. Such a correlation is also known as performability.
The root factors influencing the performability when using the RADIC (Redundant Array of Distributed Independent Fault Tolerance Controllers) fault tolerance architecture are raised and studied. Factors include the message delivery latency, which increases when using pessimistic logging causing performance overhead, as also in the redundant data (logs and checkpoints) replication needed to increase availability in RADIC and the process per node distribution changed by faults, which may cause performance degradation and preventive maintenance stops.
In order to face these problems some alternatives are presented based on a performability analysis. Using a pipeline approach the performance overhead of message logging and the redundant data replication were mitigated. Changes in the process per node distribution can be avoided or restored using the flexible and transparent mechanism for dynamic redundancy proposed, or using a dynamic insertion of spare or replacement nodes.
The obtained results show that the presented contributions could improve the performability of a computer cluster when using a fault tolerance solution such as RADIC.

En el artículo "NP-completeness in Hedonic Games", identificamos algunas limitaciones significativas de los modelos estándar de juegos cooperativos: A menudo, es imposible alcanzar una organización estable de una sociedad en una cantidad de tiempo razonable. Las implicaciones básicas de estos resultados son las siguientes, Primero, desde un punto de vista positivo, las sociedades están "condenadas" a evolucionar constantemente, más que a alcanzar un estadio de equilibrio en el corto plazo. Segundo, desde una perspectiva normativa, un hipotético organizador de la sociedad debería tomar en consideración las limitaciones prácticas de tiempo a la hora de implementar un orden social estable.
Para obtener nuestros resultados, utilizamos el concepto de NP-completitud, que es un modelo bien establecido de complejidad temporal en Ciencias de la Computación. En concreto, nos concentramos en estabilidad grupal y estabilidad individual en juegos hedónicos. Los juegos hedónicos son una clase simple de juegos cooperativos en los que la utilidad de cada individuo viene totalmente determinada por el grupo laboral al que pertenece. Nuestros resultados referentes a la complejidad, expresados en términos de NP-completitud, cubren un amplio espectro de dominios de las preferencias individuales, incluyendo preferencias estrictas, indiferencias en las preferencias o preferencias libres sobre el tamaño de los grupos. Dichos resultados también se cumplen si nos restringimos al caso en el que el tamaño máximo de los grupos es pequeño (dos o tres jugadores)
En el artículo "Who is Who in Networks. Wanted: The Key Player" (junto con Antoni Calvó Armengol e Yves Zenou), analizamos un modelo de efectos de grupo en el que los agentes interactúan en un juego de influencias bilaterales. Los juegos no cooperativos con población finita y utilidades linales-cuadráticas, en los cuales cada jugador decide cuánto esfuerzo ejercer, pueden ser interpretados como juegos en red con complementariedades en los pagos, junto con un componente de susitucion global y uniforme, y un efecto de concavidad propia.
Para dichos juegos, la acción de cada jugador en un equilibrio de Nash es proporcional a su centralidad de Bonacich en la red de complementariedades, estableciendo así un puente con la literatura de redes sociales. Dicho vínculo entre Bonacich y Nash implica que el equilibrio agregado aumenta con el tamaño y la densidad de la red.
También analizamos una política que consiste en seleccionar al jugador clave, ésto es, el jugador que, una vez eliminado del juego, induce un cambio óptimo en la actividad agregada. Proveemos una caracterización geométrica del jugador clave, identificada con una medida de inter-centralidad, la cual toma en cuenta tanto la centralidad de cada jugador como su contribución a la centralidad de los otros.
En el artículo "Optimal Targets in Peer Networks" (junto con Antoni Calvó Armengol e Yves Zenou), nos centramos en las consecuencias y limitaciones prácticas que se derivan del modelo de decisiones sobre delincuencia. Las principales metas que aborda el trabajo son las siguientes. Primero, la elección se extiende el concepto de delincuente clave en una red al de grupo clave. En dicha situación se trata de seleccionar de modo óptimo al conjunto de delincuentes a eliminar/neutralizar, dadas las restricciones presupuestarias para aplicar medidas. Dicho problema presenta una inherente complejidad computacional que solo puede salvarse mediante el uso de procedimientos aproximados, "voraces" o probabilísticos. Por otro lado, tratamos el problema del delincuente clave en el contexto de redes dinámicas, en las que, inicialmente, los individuos deciden acerca de su futuro como delincuentes o como ciudadanos que obtienen un salario fijo en el mercado. En dicha situación, la elección del delincuente clave es más compleja, ya que el objetivo de disminuir la delincuencia debe tener en cuenta los efectos en cadena que pueda traer consigo la desaparición de uno o varios delincuentes. Por último, estudiamos la complejidad computacional del problema de elección óptima y explotamos la propiedad de submodularidad de la intercentralidad de grupo, lo cual nos permite acotar el error relativo de la aproximación basada en un algoritmo voraz.
The aim of this thesis work is to contribute to the analysis of the interaction of agents in social networks and groups.
In the chapter "NP-completeness in Hedonic Games", we identify some significant limitations in standard models of cooperation in games: It is often impossible to achieve a stable organization of a society in a reasonable amount of time. The main implications of these results are the following. First, from a positive point of view, societies are bound to evolve permanently, rather than reach a steady state configuration rapidly. Second, from a normative perspective, a planner should take into account practical time limitations in order to implement a stable social order.
In order to obtain our results, we use the notion of NP-completeness, a well-established model of time complexity in Computer Science. In particular, we concentrate on group stability and individual stability in hedonic games. Hedonic games are a simple class of cooperative games in which each individual's utility is entirely determined by her group. Our complexity results, phrased in terms of NP-completeness, cover a wide spectrum of preference domains, including strict preferences, indifference in preferences or undemanding preferences over sizes of groups. They also hold if we restrict the maximum size of groups to be very small (two or three players).
The last two chapters deal with the interaction of agents in the social setting. It focuses on games played by agents who interact among them. The actions of each player generate consequences that spread to all other players throughout a complex pattern of bilateral influences.
In "Who is Who in Networks. Wanted: The Key Player" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze a model peer effects where agents interact in a game of bilateral influences. Finite population non-cooperative games with linear-quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own-concavity effect.
For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich-Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists in targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an inter-centrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.
Finally, in the last chapter, "Optimal Targets in Peer Networks" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze the previous model in depth and study the properties and the applicability of network design policies.
In particular, the key group is the optimal choice for a planner who wishes to maximally reduce aggregate activity. We show that this problem is computationally hard and that a simple greedy algorithm used for maximizing submodular set functions can be used to find an approximation. We also endogeneize the participation in the game and describe some of the properties of the key group. The use of greedy heuristics can be extended to other related problems, like the removal or addition of new links in the network.

This thesis presents the a stabilized projection-based Reduced Order Model (ROM) formulation in low speed fluid flows using a Variational Multi-Scale (VMS) approach. To develop this formulation we use a Finite Element (FE) method for the Full Order Model (FOM) and a Proper Orthogonal Decomposition (POD) to construct the basis. Additional to the ROM formulation, we introduce two techniques that became possible using this approach: a mesh-based hyper-reduction that uses an Adaptive Mesh Refinement (AMR) approach, and a domain decomposition scheme for ROMs. To illustrate and test the proposed formulation we use five different models: a convection–diffusion–reaction, the incompressible Navier–Stokes, a Boussinesq approximation, a low Mach number model, and a three-field incompressible Navier–Stokes.
Esta tesis presenta un modelo de orden reducido estabilizado paran fluidos a baja velocidad utilizando un enfoque de multiescala variacional. Para desarrollar esta formulación utilizamos el método de elementos finitos para el modelo no reducido y una descomposición en autovalores del mismo para construir la base. Adicional a la formulación del modelo reducido, presentamos dos técnicas que podemos formular al utilizar este enfoque: una reducción adicional del dominio, basada en la reducción de la malla, donde usamos una técnica de refinamiento adaptativa y un esquema de descomposición de dominio para el modelo reducido. Para ilustrar y probar la formulación propuesta, utilizamos cuatro diferentes modelos fisicos: una ecuación de convección-difusión-reacción, la ecuación de Navier-Stokes para fluidos incompresibles, una aproximación de Boussinesq para la ecuación de Navier-Stokes, y una aproximación para números de Mach bajos de la ecuación de Navier-Stokes.

Esta tesis doctoral aborda la aplicación de seis enfoques estadísticos que se utilizan para estimar tamaños de muestra en poblaciones multinomiales los que corresponden a: Angers (1974), Tortora (1978), Thompson (1987), Cochran (1977), Bromaghin (1993) y Fitzpatrick & Scott (1987), dichos enfoques están ampliamente discutidos en la literatura del muestreo estadístico pero generan controversia al momento de aplicarlos en estudios de salud dado a que no siempre permiten conjugar costos, representatividad y tamaños de muestra adecuados para un esquema de muestreo aleatorio simple y muestreo complejo de poblaciones en donde la variable de diseño o estudio corresponde a una distribución de tipo multinomial. Se discute inicialmente como la utilización de la máxima varianza cuando la variable de diseño con k=2 categorías entrega estimaciones de prevalencias considerando un valor P=0,50 para estimar dicho tamaño muestral, sin conocer valores previos de dicho estimador lo que entrega estimaciones sesgadas. Posteriormente se simularon poblaciones teóricas para variables de k=3, 4, 5, 6 y 7 categorías, generando 25 poblaciones distintas de tamaño N=1.000.000 que variaban según distintos valores de proporciones para las distintas categorías. Para dichas poblaciones se extrajeron mediante muestro aleatorio simple, muestras de distintos tamaños que fueron estimadas mediante los seis enfoques mencionados anteriormente que consideraron distintos valores de errores muestrales, posteriormente se evaluó el desempeño de estos mediante: 1) Tamaño de muestra, 2) Nivel de confianza real, 3) Estimador promedio, 4) Sesgo y 5) Mediana del Error cuadrático medio. Luego la discusión se enfoca en la determinación de que método analizado entrega mejores tamaños de muestra y estimaciones considerando distintos escenarios en donde las categorías consideradas van desde k=3 a k=7, finalmente se propone y discute la utilización de las medidas de incertidumbre o entropía de Shannon para estudiar la incertidumbre asociada a los vectores estimados mediante los distintos métodos.
This dissertation addresses the application of six statistical approaches used to estimate sample sizes in multinomial populations which correspond to: Angers (1974), Tortora (1978), Thompson (1987), Cochran (1977), Bromaghin (1993) and Fitzpatrick & Scott (1987), such approaches are widely discussed in the literature of statistical sampling but generated controversy when applying in health studies because they do not always allow combining costs, representation and adequate sample sizes for sampling scheme simple random sampling and complex populations where the design variable or study corresponds to a multinomial distribution type. Initially discusses how the use of a maximun variance when the design variable with k = 2 gives estimates of prevalence categories considering a P = 0.50 for this sample size estimate without knowing previous values of this estimator which delivers biased estimates. Later theoretical populations were simulated for variables k = 3, 4, 5, 6 and 7 categories, generating 25 different populations of size N = 1,000,000 varying proportions according to different values for different categories. For these populations were extracted by simple random sampling, samples of different sizes were estimated using the six approaches mentioned above that considered different values of sampling errors, then the performance of these was assessed by: 1) sample size, 2) Level of real confidence, 3) average Estimator, 4) bias and 5) mean Square Error. The discussion then focuses on determining which delivery method best used sample sizes and estimates considering scenarios where the categories considered ranging from k = 3 to k = 7, finally proposes and discusses the use of measures of uncertainty or entropy Shannon to study the uncertainty associated with the estimated vectors using different methods.

The topic of this thesis is the development of SAT-based techniques and tools for solving industrial combinatorial problems. First, it describes the architecture of state-of-the-art SAT and SMT Solvers based on the classical DPLL procedure. These systems can be used as black boxes for solving combinatorial problems. However, sometimes we can increase their efficiency with slight modifications of the basic algorithm. Therefore, the study and development of techniques for adjusting SAT Solvers to specific combinatorial problems is the first goal of this thesis. Namely, SAT Solvers can only deal with propositional logic. For solving general combinatorial problems, two different approaches are possible: - Reducing the complex constraints into propositional clauses. - Enriching the SAT Solver language. The first approach corresponds to encoding the constraint into SAT. The second one corresponds to using propagators, the basis for SMT Solvers. Regarding the first approach, in this document we improve the encoding of two of the most important combinatorial constraints: cardinality constraints and pseudo-Boolean constraints. After that, we present a new mixed approach, called lazy decomposition, which combines the advantages of encodings and propagators. The other part of the thesis uses these theoretical improvements in industrial combinatorial problems. We give a method for efficiently scheduling some professional sport leagues with SAT. The results are promising and show that a SAT approach is valid for these problems. However, the chaotical behavior of CDCL-based SAT Solvers due to VSIDS heuristics makes it difficult to obtain a similar solution for two similar problems. This may be inconvenient in real-world problems, since a user expects similar solutions when it makes slight modifications to the problem specification. In order to overcome this limitation, we have studied and solved the close solution problem, i.e., the problem of quickly finding a close solution when a similar problem is considered.

The frequency of occurrence of an accident is a key aspect in the risk assessment field. Variables such as the human factor, which is a major cause of undesired events in process industries, are usually not considered explicitly, mainly due to the uncertainty related to the lack of knowledge and the complexity associated to it. In this thesis, a frequency modifier has been developed in order to introduce the human factor in the failure frequency estimation. This modifier takes into account variables such as: the organizational factor, the job characteristic factor and the personal characteristic factor. The inclusion of the human factor was done through the application of two methodologies: the fuzzy logic and the Monte Carlo simulation. The first one is based on the operation of the human reason, because of that, the contribution of international experts on the subject area was taken into account through a questionnaire. In the second one, Monte Carlo, the variables are represented by probability functions through a probabilitic treatment. The modifiers were applied to four case studies of real chemical plants: two related to the storage of flammable products and another two dedicated to the toxic and flammable products storage. The new frequency values are considered more realistic and accurate since the human factor is now reflected. In addition, the models were validated with the comparison of the obtained results with a widely international recognized method: the Quantitative Risk Analysis (QRA). Consequently, the final evaluation of the risk is more conservative but in the same line as the results obtained through a QRA.
La frecuencia de los accidentes es un aspecto muy importante en el campo del análisis del riesgo. Variables cómo el factor humano en general no se consideran explícitamente en su evaluación. Esto se debe a la incertidumbre que se genera debido a la falta de información y la complejidad para calcular este factor. No obstante, el factor humano es una de las mayores causas de eventos no deseados en las industrias de proceso. En esta tesis, se desarrolló un modificador de la frecuencia de accidentes con el objetivo de introducir el factor humano en la estimación de riesgo. Este modificador tiene en cuenta variables como: el factor organizacional, el factor de las características del trabajo y el factor de las características personales. La inclusión del factor humano se hizo mediante la aplicación de dos metodologías: La lógica difusa y la simulación de Monte Carlo. La primera de ellas se basa en el funcionamiento del razón humana, por ello fue necesaria la contribución de expertos internacionales en el área de estudio a través de su contribución en un cuestionario. En la segunda, Montecarlo, las variables son representades por funciones de probabilidad a través de un tratamiento probabilístico. Los modificadores fueron aplicados a cuatro casos de estudio de industrias químicas reales: dos relacionados con empresas que almacenan productos inflamables y dos que almancenan productos tóxicos e inflamables. Los nuevos valores de frecuencia, después de aplicar el modificador obtenido, son considerados más realistas debido a que ya incluyen el factor humano. Además, los modelos fueron validados con la comparación de los resultados obtenidos con el método internacionalmente aceptado para la evaluación de riesgo: el Análisis Cuantitativo de Riesgo (ACR). Consecuentemente, la evaluación final de riesgo es más conservadora aunque en la línia de los resultados obtenidos a partir de un ACR.

Els incendis forestals són un tipus de desastre natural que representa un gran repte per a la societat a causa dels seus elevats costos econòmics i humans. Amb l’objectiu d’evitar els costos derivats d’aquest desastre natural i millorar l’extinció dels mateixos, els simuladors de propagació d’incendis es poden utilitzar per intentar anticipar el comportament de l’incendi i ajudar a aconseguir una extinció de l’incendi més eficient i segura. Quan es propociona una predicció de la propagació d’un incendi forestal existeixen dos elements claus: la precisió i el temps necessari per computar la predicció. Sota el context de la simulació de desastres naturals, és ben conegut que part de l’error de la predicció estàsubjecta a la incertesa en les dades d’entrada utilitzades pel simulador. Per aquesta raó, la comunitat científica ha creat diferents mètodes de calibratge per reduir la incertesa de les dades d’entrada i així millorar l’error de la predicció. En aquest treball s’utilitza una metodologia de predicció basada en dues etapes que ha estat provada en treballs previs amb bons resultats. Aquest mètode de calibratge implica una necessitat considerable de recursos computacionals i eleva el temps de còmput a causa de l’ús d’un Algorisme Genètic com a mètode de cerca de les millors dades d’entrada del simulador. S’ha de tenir en compte les restriccions de temps sota les quals treballa un sistema de predicció d’incendis. Es necessari mantenir un equilibri adequat entre precisió i temps de còmput utilitzat per poder proporcionar una bona predicció a temps. Per poder utilitzar la tècnica de calibratge esmentat, s’ha de solucionar el problema que representa que algunes solucions siguin inviables ja que impliquen temps d’execució molt llargs, fet que pot impedir que es pugui donar resposta a temps en un suposat context operacional. La present Tesi Doctoral utilitza les arquitectures multi-core amb l’objectiu d’accelerar el mètode de predicció basat en dues etapes per poder proporcionar una predicció sota temps de lliurament que es donarien en un context real. Per aquesta raó, es defineix una política d’assignació de nuclis basada en el temps disponible d’execució. Aquesta política d’assignació assignaràun nombre determinat de recursos a una determinada simulació prèviament a ser executada. La política d’assignació es basa en arbres de decisió creats amb els paràmetres de simulació utilitzats. No obstant això, es pro¬posen dos mètodes per a aquells casos on l’Algorisme Genètic tendeix a crear individus el temps d’execució dels quals provoquen que sigui impossible acabar el calibratge a temps: ReTAC i SoftTAC. La proposta ReTAC utilitza la resolució de les simulacions per solucionar el problema. En concret, ReTAC tracta de trobar la mínima reducció de la resolució que permeti que aquelles simulacions que són massa llargues puguin ser executades mantenint la precisió sota control. D’altra banda, SoftTAC utilitza poblacions de grandària dinàmica. Es a dir, els individus no es maten en arribar al límit de temps d’execució assignat a una generació de l’AG, sino que es permet l’execució simultanea d’individus de diferents generacions de l’algorisme genètic. Totes les estratègies de predicció proposades han estat provades amb casos reals obtenint resultats satisfactoris en termes de precisió i de temps de còmput utilitzat.
Los incendios forestales son un tipo de catástrofe natural que representa un gran reto para sociedad debido a sus elevados costes económicos y humanos. Con el objetivo de evitar los costes derivados de dicho desastre natural y mejorar la extinción de éstos, los simuladores de propagación de incendios se pueden utilizar para intentar anticipar el comportamiento del incendio y ayudar a conseguir una extinción del incendio más eficiente y segura. Cuando se propociona una predicción de la propagación de un incendio forestal existen dos elementos clave: la precisión y el tiempo necesario para computar la predicción. Bajo el contexto de la simulación de desastres naturales, es bien conocido que parte del error de la predicción está sujeta a la incertidumbre en los datos de entrada utilizados por el simulador. Por esta razón, la comunidad científica ha creado distintos métodos de calibración para reducir la incertidumbre de los datos de entrada y así mejorar el error de la predicción. En este trabajo se utiliza una metodología de calibración basada en dos etapas que ha sido probada en trabajos previos con buenos resultados. Este método de calibración implica una necesidad considerable de recursos computacionales y eleva el tiempo de cómputo debido al uso de un Algoritmo Genético como método de búsqueda de los mejores datos de entrada del simulador. Se debe tener en cuenta las restricciones de tiempo bajo las que trabaja un sistema de predicción de incendios. Es necesario mantener un equilibrio adecuado entre precisión y tiempo de cómputo utilizado para poder proporcionar una buena predicción a tiempo. Para poder utilizar la técnica de calibración mencionada, se debe solucionar el problema que representa que algunas soluciones sean inviables debido a que implican tiempos de ejecución muy largos, lo que puede impedir que se pueda dar respuesta a su debido tiempo en un supuesto contexto operacional. La presente Tesis Doctoral utiliza las arquitecturas multi-core con el objetivo de acelerar el método de calibración basado en dos etapas y poder proporcionar una predicción bajo tiempos de entrega que se darían en un contexto real. Por esta razón, se define una política de asignación de núcleos basada en el tiempo disponible de ejecución . Esta política de asignación asignará un número determinado de recursos a una determinada simulación previamente a ser ejecutada. La política de asignación se basa en árboles de decisión creados con los parametros de simulación n utilizados. Sin embargo, se proponen dos métodos para aquellos casos donde el algoritmo genético tienda a crear individuos cuyo tiempo de ejecución provocan que sea imposible acabar la calibración a tiempo: Re-TAC y Soft-TAC. La propuesta ReTAC utiliza la resolución de las simulaciones para solucionar el problema. En concreto, Re-TAC trata de encontrar la mínima reducción de la resolución que permita que aquellas simulaciones que son demasiado largas puedan ser ejecutadas manteniendo la precisión bajo control. Por otro lado, Soft-TAC utiliza poblaciones de tama˜no dinámico. Es decir, los individuos no se matan al alcanzar el límite de timepo de ejecución asignado a una generación del Algoritmo Genético, sino que se permite la ejecución simultanea de individuos de distintas generaciones haciendo que el tamaño de la población sea dinámico. Todas la estrategias de predicción propuestas han sido probadas con casos reales obteniendo resultados satisfactorios en términos de precisión y de tiempo de cómputo utilizado.
Large forest fires are a kind of natural hazard that represents a big threat for the society because it implies a significant number of economic and human costs. To avoid major damages and to improve forest fire management, one can use forest fire spread simulators to predict fire behaviour. When providing forest fire predictions, there are two main considerations: accuracy and computation time. In the context of natural hazards simulation, it is well known that part of the final forecast error comes from uncertainty in the input data. For this reason several input data calibration methods have been developed by the scientific community. In this work, we use the Two-Stage calibration methodology, which has been shown to provide good results. This calibration strategy is computationally intensive and timeconsuming because it uses a Genetic Algorithm as an optimization strategy. Taking into account the aspect of urgency in forest fire spread prediction, we need to maintain a balance between accuracy and the time needed to calibrate the input parameters. In order to take advantage of this technique, we must deal with the problem that some of the obtained solutions are impractical, since they involve simulation times that are too long, preventing the prediction system from being deployed at an operational level. This PhD Thesis exploits the benefits of current multi-core architectures with the aim of accelerating the Two-Stage forest fire prediction scheme being able to deliver predictions under strict real time constraints. For that reason, a Time-Aware Core allocation (TAC) policy has been defined to determine in advance the more appropriate number of cores assigned to a given forest fire spread simulation. Each execution configuration is obtained considering the particular values of the input data needed for each simulation by applying a dynamic decision tree. However, in those cases where the optimization process will drive the system to solutions whose simulation time will prevent the system to finish on time, two different enhanced schemes have been defined: Re-TAC and Soft-TAC. Re-TAC approach deals with the resolution of the simulation. In particular, Re-TAC finds the minimum resolution reduction for such long simulations, keeping accuracy loss to a known interval. On the other hand, Soft-TAC considers the GA's population size as dynamic in the sense that none individual will be killed for over passing the internal generations deadline, but it will be keep executing and the population size for the subsequent GA's generation is modified according to that. All proposed prediction strategies have been tested with past real cases obtaining satisfactory results both in terms of prediction accuracy and in the time required to deliver the prediction.