Search

La combinació d'observacions experimentals i estudis de la Density Functional Theory (DFT) és un dels pilars de la investigació química moderna. Atès que permeten recopilar informació física addicional d'un sistema químic, difícilment accessible a través de l'entorn experimental, aquests estudis es fan servir àmpliament per modelar i predir el comportament d'una gran varietat de compostos químics en entorns únics. A la catàlisi heterogènia, els models DFT s'utilitzen habitualment per avaluar la interacció entre els compostos moleculars i els catalitzadors, vinculant aquestes interpretacions amb els resultats experimentals. Tanmateix, l'alta complexitat trobada tant als escenaris catalítics com a la reactivitat, implica la necessitat de metodologies sofisticades que requereixen automatització, emmagatzematge i anàlisi per estudiar correctament aquests sistemes. Aquest treball presenta el desenvolupament i la combinació de múltiples metodologies per avaluar correctament la complexitat d'aquests sistemes químics. A més, aquest treball mostra com s'han utilitzat les tècniques proporcionades per estudiar noves configuracions catalítiques d'interès acadèmic i industrial. La combinación de observaciones experimentales y estudios de la Density Functional Theory (DFT) es uno de los pilares de la investigación química moderna. Dado que permiten recopilar información física adicional de un sistema químico, difícilmente accesible a través del entorno experimental, estos estudios se emplean ampliamente para modelar y predecir el comportamiento de una gran variedad de compuestos químicos en entornos únicos. En la catálisis heterogénea, los modelos DFT se emplean habitualmente para evaluar la interacción entre los compuestos moleculares y los catalizadores, vinculando estas interpretaciones con los resultados experimentales. Sin embargo, la alta complejidad encontrada tanto en los escenarios catalíticos como en la reactividad, implica la necesidad de metodologías sofisticadas que requieren de automatización, almacenamiento y análisis para estudiar correctamente estos sistemas. Este trabajo presenta el desarrollo y la combinación de múltiples metodologías con el objetivo de evaluar correctamente la complejidad de estos sistemas químicos. Además, este trabajo muestra cómo las técnicas proporcionadas se han utilizado para estudiar nuevas configuraciones catalíticas de interés académico e industrial. The combination of Experimental observations and Density Functional Theory studies is one of the pillars of modern chemical research. As they enable the collection of additional physical information of a chemical system, hardly accessible via the experimental setting, Density Functional Theory studies are widely employed to model and predict the behavior of a diverse variety of chemical compounds under unique environments. Particularly, in heterogeneous catalysis, Density Functional Theory models are commonly employed to evaluate the interaction between molecular compounds and catalysts, lately linking these interpretations with experimental results. However, high complexity found in both, catalytic settings and reactivity, implies the need of sophisticated methodologies involving automation, storage and analysis to correctly study these systems. Here, I present the development and combination of multiple methodologies, aiming at correctly asses complexity. Also, this work shows how the provided techniques have been actively used to study novel catalytic settings of academic and industrial interest.

La sincronització en xarxes és la música dels sistemes complexes. Els ritmes col·lectius que emergeixen de molts oscil·ladors acoblats expliquen el batec constant del cor, els patrons recurrents d'activitat neuronal i la sincronia descentralitzada a les xarxes elèctriques. Els models matemàtics són sòlids i han avançat significativament, especialment en el problema del camp mitjà, on tots els oscil·ladors estan connectats mútuament. Tanmateix, les xarxes reals tenen interaccions complexes que dificulten el tractament analític. Falta un marc general i les soluciones existents en caixes negres numèriques i espectrals dificulten la interpretació. A més, la informació obtinguda en mesures empíriques sol ser incompleta. Motivats per aquestes limitacions, en aquesta tesi proposem un estudi teòric dels oscil·ladors acoblats en xarxes sota incertesa. Apliquem propagació d'errors per predir com una estructura complexa amplifica el soroll des dels pesos microscòpics fins al punt crític de sincronització, estudiem l'efecte d'equilibrar les interaccions de parelles i d'ordre superior en l'optimització de la sincronia i derivem esquemes d'ajust de pesos per mapejar el comportament de sincronització en xarxes diferents. A més, un desplegament geomètric rigorós de l'estat sincronitzat ens permet abordar escenaris descentralitzats i descobrir regles locals òptimes que indueixen transicions globals abruptes. Finalment, suggerim dreceres espectrals per predir punts crítics amb àlgebra lineal i representacions aproximades de xarxa. En general, proporcionem eines analítiques per tractar les xarxes d'oscil·ladors en condicions sorolloses i demostrem que darrere els supòsits predominants d'informació completa s'amaguen explicacions mecanicistes clares. Troballes rellevants inclouen xarxes particulars que maximitzen el ventall de comportaments i el desplegament exitós del binomi estructura-dinàmica des d'una perspectiva local. Aquesta tesi avança la recerca d'una teoria general de la sincronització en xarxes a partir de principis mecanicistes i geomètrics, una peça clau que manca en l'anàlisi, disseny i control de xarxes neuronals biològiques i artificials i sistemes d'enginyeria complexos. La sincronización en redes es la música de los sistemas complejos. Los ritmos colectivos que emergen de muchos osciladores acoplados explican el latido constante del corazón, los patrones recurrentes de actividad neuronal y la sincronía descentralizada de las redes eléctricas. Los modelos matemáticos son sólidos y han avanzado significativamente, especialmente en el problema del campo medio, donde todos los osciladores están conectados entre sí. Sin embargo, las redes reales tienen interacciones complejas que dificultan el tratamiento analítico. Falta un marco general y las soluciones en cajas negras numéricas y espectrales dificultan la interpretación. Además, las mediciones empíricas suelen ser incompletas. Motivados por estas limitaciones, en esta tesis proponemos un estudio teórico de osciladores acoplados en redes bajo incertidumbre. Aplicamos propagación de errores para predecir cómo una estructura compleja amplifica el ruido desde las conexiones microscópicas hasta puntos críticos macroscópicos, estudiamos el efecto de equilibrar interacciones por pares y de orden superior en la optimización de la sincronía y derivamos esquemas de ajuste de pesos para mapear el comportamiento en estructuras distintas. Una expansión geométrica del estado sincronizado nos permite abordar escenarios descentralizados y descubrir reglas locales que inducen transiciones abruptas globales. Por último, sugerimos atajos espectrales para predecir puntos críticos usando álgebra lineal y representaciones aproximadas de red. En general, proporcionamos herramientas analíticas para manejar redes de osciladores en condiciones ruidosas y demostramos que detrás de las suposiciones predominantes de información completa se ocultaban claras explicaciones mecanicistas. Hallazgos relevantes incluyen redes particulares que maximizan el rango de comportamientos y la explicación del binomio estructura-dinámica desde una perspectiva local. Esta tesis avanza en la búsqueda de una teoría general de sincronización en redes desde principios mecánicos y geométricos, una pieza clave que falta en el análisis, diseño y control de redes neuronales biológicas y artificiales y sistemas de ingeniería complejos. Synchronization in networks is the music of complex systems. Collective rhythms emerging from many interacting oscillators appear across all scales of nature, from the steady heartbeat and the recurrent patterns in neuronal activity to the decentralized synchrony in power-grids. The mathematics behind these processes are solid and have significantly advanced lately, especially in the mean-field problem, where oscillators are all mutually connected. However, real networks have complex interactions that difficult the analytical treatment. A general framework is missing and most existing results rely on numerical and spectral black-boxes that hinder interpretation. Also, the information obtained from measurements is usually incomplete. Motivated by these limitations, in this thesis we propose a theoretical study of network-coupled oscillators under uncertainty. We apply error propagation to predict how a complex structure amplifies noise from the link weights to the synchronization onset, study the effect of balancing pair-wise and higher-order interactions in synchrony optimization, and derive weight-tuning schemes to map the synchronization behavior of different structures. Also, we develop a rigorous geometric unfolding of the synchronized state to tackle decentralized scenarios and to discover optimal local rules that induce global abrupt transitions. Last, we suggest spectral shortcuts to predict critical points using linear algebra and network representations with limited information. Overall, we provide analytical tools to deal with oscillator networks under noisy conditions and prove that mechanistic explanations were hidden behind the prevalent assumptions of complete information. Relevant finding include particular networks that maximize the range of behaviors and the successful unfolding of the structure-dynamics interplay from a local perspective. This thesis advances the quest of a general theory of network synchronization built from mechanistic and geometric principles, a key missing piece in the analysis, design and control of biological and artificial neural networks and complex engineering systems.

Актуальність теми. Випадкові числа використовуються давно і досить широко. Нагадаємо деякі області їх застосування: - Соціологічні та наукові дослідження. Підготовка випадкових вибірок при зборі даних, опитуванні думок або в дослідженні фізичних явищ з випадковим вибором результатів експериментів. - Моделювання. У комп'ютерному моделюванні фізичних явищ. Крім того, математичне моделювання використовує випадкові числа як один з інструментів чисельного аналізу. - Криптографія та інформаційна безпека. Випадкові числа можуть використовуватися в тестуванні коректності або ефективності алгоритмів і програм. Багато алгоритмів використовують генерацію псевдовипадкових чисел для вирішення прикладних завдань (наприклад, криптографічні алгоритми шифрування, генерація унікальних ідентифікаторів та ін.). Теорія побудови генераторів псевдовипадкових чисел (ГПВЧ) глибоко і добре вивчена. Однак у тій же інженерній практиці виникає необхідність у генерації якихось спеціальних послідовностей певної підмножини векторів довжини n. Прикладом може бути область тестування цифрової апаратури Об’єктом дослідження є процес побудови гамільтонових циклів в графах, побудованих на основі сформованих векторів. Предметом дослідження є спосіб формування гамільтонових циклів для генераторів псевдовипадкових чисел з різною вагою. Мета роботи: Проаналізувати можливість побудови гамільтонового циклу для генератора псевдовипадкових двійкових векторів з вагами p1…pk (послідовно розташованих на числовій осі) на основі стандартної схеми: n-розрядний регістр зсуву зі зворотним зв'язком. Наукова новизна полягає в наступному: Розроблено спосіб пошуку усіх гамільтонових циклів для заданого набору векторів з вагами p1…pk. Практична цінність У роботі розглядаються теоретичні аспекти проблеми побудови генератора псевдовипадкових двійкових векторів з кількома вагами, що йдуть на основі класичної схеми: зсувний регістр зі зворотним зв'язком у вигляді схеми, що реалізує певну булеву функцію. Показується, що це можливо, доводиться існування гамільтонова циклу у графі переходів генератора у випадку нелінійної функції оберненого зв’язку. Розглядається можливість пошуку різних гамільтонових циклів графа, втілення яких призводить до різних генераторів, які можуть серйозно відрізнятися в плані складності реалізації булевої функції зворотного зв'язку та за якістю імовірнісних характеристик послідовності, що генерується двійкових векторів. Це розширює можливості розробника під час побудови генератора. Апробація роботи. Основні положення і результати роботи були представлені та обговорювались на XV конференцію молодих вчених ПМК-2022 року (Київ, 16-18 листопада 2022 р.); Тези до доповіді на IX Міжнародній науково-технічній Internet-конференції 2022 року. Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів та висновків. У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи, наведено відомості про апробацію результатів і їхнє впровадження. У першому розділі розглянуто загальні відомості про ГПВЧ, а також проведений аналіз, який дає змогу визначити основні переваги та недоліки цих способів. У другому розділі аналізуються існуючі генератори псевдовипадкових та реальних чисел. У третьому розділі наведено види та критерії тестів для статичних властивостей генераторів псевдовипадкових чисел. У четвертому розділі представлений спосіб формування векторів з різною вагою згідно заданих параметрів, та пошуку для них гамільтонових циклів. У висновках представлені результати проведеної роботи. Робота представлена на 80 аркушах, містить посилання на список використаних літературних джерел. Actuality of theme. Random numbers have been used for a long time and quite widely. We will recall some areas of their application: - Sociological and scientific research. Preparation of random samples in data collection, opinion polls or in the study of physical phenomena with a random selection of experimental results. - Modeling. In computer modeling of physical phenomena. In addition, mathematical modeling uses random numbers as one of the numerical analysis tools. - Cryptography and information security. Random numbers can be used in testing the correctness or efficiency of algorithms and programs. Many algorithms use the generation of pseudo-random numbers to solve applied problems (for example, cryptographic encryption algorithms, generation of unique identifiers, etc.). The theory of building pseudo-random number generators (PNGs) is deeply and well studied. However, in the same engineering practice, sometimes there is a need to generate some special sequences of a certain subset of vectors of length n. An example can be the area of testing digital equipment The object of research is a process of constructing Hamiltonian cycles based on the generated vectors. The subject of the research are ways of forming Hamiltonian cycles for pseudorandom number generators with different weights. Purpose: Analyze the possibility of building a generator of all pseudorandom binary vectors with weights p1 ... pk (sequentially located on the numerical axis) based on a standard scheme: an n-bit shift register with feedback. Prove that it is possible to build a generator for any values of n and a set of p, that is, the feedback function always exists. The scientific novelty is as follows: A method of finding all Hamiltonian cycles for a given set of vectors with weights p1 ... pk has been developed. The practical value: The paper considers the theoretical aspects of the problem of constructing a generator of pseudo-random binary vectors with several weights based on a classical scheme: a shift register with feedback in the form of a scheme that implements a certain Boolean function. It is shown that this is possible, why the existence of a Hamiltonian cycle in the transition graph of the generator is proved. The feedback function in the case is non-linear. The possibility of finding different Hamiltonian cycles of the graph, the implementation of which leads to different generators, which can seriously differ in terms of the complexity of the implementation of the Boolean feedback function and the quality of the probabilistic characteristics of the generated sequence of binary vectors, is considered. This expands the capabilities of the developer when building the generator. Approbation of work. The main provisions and results of the work were presented and discussed at the XV conference of young scientists of the PMK-2022 (Kyiv, November 16-18, 2022). Publications. The main provisions and results of the work were presented and discussed at the XV conference of young scientists of the PMK-2022 (Kyiv, November 16-18, 2022)."; Theses at the 9th International Scientific and Technical Internet Conference. Structure and scope of work. The master's thesis consists of an introduction, four chapters and conclusions. The introduction provides a general description of the work, assesses the current state of the problem, substantiates the relevance of the research direction, formulates the purpose and tasks of the research, shows the scientific novelty of the obtained results and the practical value of the work, provides information on the approbation of the results and their implementation. In the first section, general information about HDV is considered, as well as the analysis carried out, which makes it possible to determine the main advantages and disadvantages of these methods. The second section analyzes existing generators of pseudo-random and real numbers. In the third section, types and criteria of tests for static properties of pseudorandom number generators are given. The fourth chapter presents the method of forming vectors with different weights according to given parameters and finding Hamiltonian cycles for them. The results of the work are presented in the conclusions.The work is presented on 80 sheets, contains links to the list of used literary sources.

En aquesta investigació, s'han examinat tècniques d'optimització per resoldre problemes de restriccions i s'ha fet un estudi de l'era quàntica i de les empreses líders del mercat, com ara IBM, D-Wave, Google, Xanadu, AWS-Braket i Microsoft. S'ha après sobre la comunitat, les plataformes, l'estat de les investigacions i s'han estudiat els postulats de la mecànica quàntica que serveixen per crear els sistemes i algorismes quàntics més eficients. Per tal de saber si és possible resoldre problemes de Problema de cerca de restriccions (CSP) de manera més eficient amb la computació quàntica, es va definir un escenari perquè tant la computació clàssica com la quàntica tinguessin un bon punt de referència. En primer lloc, la prova de concepte es centra en el problema de programació dels treballadors socials i més tard en el tema de la preparació per lots i la selecció de comandes com a generalització del Problema dels treballadors socials (SWP). El problema de programació dels treballadors socials és una mena de problema d'optimització combinatòria que, en el millor dels casos, es pot resoldre en temps exponencial; veient que el SWP és NP-Hard, proposa fer servir un altre enfoc més enllà de la computació clàssica per a la seva resolució. Avui dia, el focus a la computació quàntica ja no és només per la seva enorme capacitat informàtica sinó també, per l'ús de la seva imperfecció en aquesta era Noisy Intermediate-Scale Quantum (NISQ) per crear un poderós dispositiu d'aprenentatge automàtic que utilitza el principi variacional per resoldre problemes d'optimització en reduir la classe de complexitat. A la tesi es proposa una formulació (quadràtica) per resoldre el problema de l'horari dels treballadors socials de manera eficient utilitzant Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), Minimal Eigen Optimizer i ADMM optimizer. La viabilitat quàntica de l'algorisme s'ha modelat en forma QUBO, amb Docplex simulat Cirq, Or-Tools i provat a ordinadors IBMQ. Després d'analitzar els resultats de l'enfocament anterior, es va dissenyar un escenari per resoldre el SWP com a raonament basat en casos (qCBR), tant quànticament com clàssicament. I així poder contribuir amb un algorisme quàntic centrat en la intel·ligència artificial i l'aprenentatge automàtic. El qCBR és una tècnica d’aprenentatge automàtic basada en la resolució de nous problemes que utilitza l’experiència, com ho fan els humans. L'experiència es representa com una memòria de casos que conté qüestions prèviament resoltes i utilitza una tècnica de síntesi per adaptar millor l'experiència al problema nou. A la definició de SWP, si en lloc de pacients es tenen lots de comandes i en lloc de treballadors socials robots mòbils, es generalitza la funció objectiu i les restriccions. Per això, s'ha proposat una prova de concepte i una nova formulació per resoldre els problemes de picking i batching anomenat qRobot. Es va fer una prova de concepte en aquesta part del projecte mitjançant una Raspberry Pi 4 i es va provar la capacitat d'integració de la computació quàntica dins de la robòtica mòbil, amb un dels problemes més demandats en aquest sector industrial: problemes de picking i batching. Es va provar en diferents tecnologies i els resultats van ser prometedors. A més, en cas de necessitat computacional, el robot paral·lelitza part de les operacions en computació híbrida (quàntica + clàssica), accedint a CPU i QPU distribuïts en un núvol públic o privat. A més, s’ha desenvolupat un entorn estable (ARM64) dins del robot (Raspberry) per executar operacions de gradient i altres algorismes quàntics a IBMQ, Amazon Braket (D-Wave) i Pennylane de forma local o remota. Per millorar el temps d’execució dels algorismes variacionals en aquesta era NISQ i la següent, s’ha proposat EVA: un algorisme d’aproximació de Valor Exponencial quàntic. Fins ara, el VQE és el vaixell insígnia de la computació quàntica. Avui dia, a les plataformes líders del mercat de computació quàntica al núvol, el cost de l'experimentació dels circuits quàntics és proporcional al nombre de circuits que s'executen en aquestes plataformes. És a dir, amb més circuits més cost. Una de les coses que aconsegueix el VQE, el vaixell insígnia d'aquesta era de pocs qubits, és la poca profunditat en dividir el Hamiltonià en una llista de molts petits circuits (matrius de Pauli). Però aquest mateix fet, fa que simular amb el VQE sigui molt car al núvol. Per aquesta mateixa raó, es va dissenyar EVA per poder calcular el valor esperat amb un únic circuit. Tot i haver respost a la hipòtesi d'aquesta tesis amb tots els estudis realitzats, encara es pot continuar investigant per proposar nous algorismes quàntics per millorar problemes d'optimització. En esta investigación, se han examinado técnicas de optimización para resolver problemas de restricciones y se ha realizado un estudio de la era cuántica y de las empresas lideres del mercado, como IBM, D-Wave, Google, Xanadu, AWS-Braket y Microsoft. Se ha aprendido sobre su comunidad, sus plataformas, el estado de sus investigaciones y se han estudiado los postulados de la mecánica cuántica que sirven para crear los sistemas y algoritmos cuánticos más eficientes. Por tal de saber si es posible resolver problemas de Problema de búsqueda de restricciones (CSP) de manera más eficiente con la computación cuántica, se definió un escenario para que tanto la computación clásica como la cuántica tuvieran un buen punto de referencia. En primer lugar, la prueba de concepto se centra en el problema de programación de los trabajadores sociales y más tarde en el tema de la preparación por lotes y la selección de pedidos como una generalización del Problema de los trabajadores sociales (SWP). El problema de programación de los trabajadores sociales es una clase de problema de optimización combinatoria que, en el mejor de los casos, puede resolverse en tiempo exponencial; viendo que el SWP es NP-Hard, propone usar otro enfoque mas allá de la computación clásica para su resolución. Hoy en día, el foco en la computación cuántica ya no es sólo por su enorme capacidad informática sino también, por el uso de su imperfección en esta era Noisy Intermediate-Scale Quantum (NISQ) para crear un poderoso dispositivo de aprendizaje automático que usa el principio variacional para resolver problemas de optimización al reducir su clase de complejidad. En la tesis se propone una formulación (cuadrática) para resolver el problema del horario de los trabajadores sociales de manera eficiente usando Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), Minimal Eigen Optimizer y ADMM optimizer. La viabilidad cuántica del algoritmo se ha modelado en forma QUBO, con Docplex simulado Cirq, Or-Tools y probado en computadoras IBMQ. Después de analizar los resultados del enfoque anterior, se diseñó un escenario para resolver el SWP como razonamiento basado en casos (qCBR), tanto cuántica como clásicamente. Y así, poder contribuir con un algoritmo cuántico centrado en la inteligencia artificial y el aprendizaje automático. El qCBR es una técnica de aprendizaje automático basada en la resolución de nuevos problemas que utiliza la experiencia, como lo hacen los humanos. La experiencia se representa como una memoria de casos que contiene cuestiones previamente resueltas y usa una técnica de síntesis para adaptar mejor la experiencia al nuevo problema. En la definición de SWP, si en lugar de pacientes se tienen lotes de pedidos y en lugar de trabajadores sociales robots móviles, se generaliza la función objetivo y las restricciones. Para ello, se ha propuesto una prueba de concepto y una nueva formulación para resolver los problemas de picking y batching llamado qRobot. Se hizo una prueba de concepto en esta parte del proyecto a través de una Raspberry Pi 4 y se probó la capacidad de integración de la computación cuántica dentro de la robótica móvil, con uno de los problemas más demandados en este sector industrial: problemas de picking y batching. Se probó en distintas tecnologías y los resultados fueron prometedores. Además, en caso de necesidad computacional, el robot paraleliza parte de las operaciones en computación híbrida (cuántica + clásica), accediendo a CPU y QPU distribuidos en una nube pública o privada. Además, desarrollamos un entorno estable (ARM64) dentro del robot (Raspberry) para ejecutar operaciones de gradiente y otros algoritmos cuánticos en IBMQ, Amazon Braket (D-Wave) y Pennylane de forma local o remota. Para mejorar el tiempo de ejecución de los algoritmos variacionales en esta era NISQ y la siguiente, se ha propuesto EVA: un algoritmo de Aproximación de Valor Exponencial cuántico. Hasta la fecha, el VQE es el buque insignia de la computación cuántica. Hoy en día, en las plataformas de computación cuántica en la nube líderes de mercado, el coste de la experimentación de los circuitos cuánticos es proporcional al número de circuitos que se ejecutan en dichas plataformas. Es decir, con más circuitos mayor coste. Una de las cosas que consigue el VQE, el buque insignia de esta era de pocos qubits, es la poca profundidad al dividir el Hamiltoniano en una lista de muchos pequeños circuitos (matrices de Pauli). Pero este mismo hecho, hace que simular con el VQE sea muy caro en la nube. Por esta misma razón, se diseñó EVA para poder calcular el valor esperado con un único circuito. Aún habiendo respuesto a la hipótesis de este trabajo con todos los estudios realizados, todavía se puede seguir investigando para proponer nuevos algoritmos cuánticos para mejorar problemas de optimización combinatoria. In this research, Combinatorial optimization techniques to solve constraint problems have been examined. A study of the quantum era and market leaders such as IBM, D-Wave, Google, Xanadu, AWS-Braket and Microsoft has been carried out. We have learned about their community, their platforms, the status of their research, and the postulates of quantum mechanics that create the most efficient quantum systems and algorithms. To know if it is possible to solve Constraint Search Problem (CSP) problems more efficiently with quantum computing, a scenario was defined so that both classical and quantum computing would have a good point of reference. First, the proof of concept focuses on the social worker scheduling problem and later on the issue of batch picking and order picking as a generalization of the Social Workers Problem (SWP). The social workers programming problem is a combinatorial optimization problem that can be solved exponentially at best; seeing that the SWP is NP-Hard, it claims using another approach beyond classical computation for its resolution. Today, the focus on quantum computing is no longer only on its enormous computing power but also on the use of its imperfection in this era Noisy Intermediate-Scale Quantum (NISQ) to create a powerful machine learning device that uses the variational principle to solve optimization problems by reducing their complexity class. In the thesis, a (quadratic) formulation is proposed to solve the problem of social workers' schedules efficiently using Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), Minimal Eigen Optimizer and ADMM optimizer. The quantum feasibility of the algorithm has been modelled in QUBO form, with Cirq simulated, Or-Tools and tested on IBMQ computers. After analyzing the results of the above approach, a scenario was designed to solve the SWP as quantum case-based reasoning (qCBR), both quantum and classically. And thus, to be able to contribute with a quantum algorithm focused on artificial intelligence and machine learning. The qCBR is a machine learning technique based on solving new problems that use experience, as humans do. The experience is represented as a memory of cases containing previously resolved questions and uses a synthesis technique to adapt the background to the new problem better. In the definition of SWP, if instead of patients there are batches of orders and instead of social workers mobile robots, the objective function and the restrictions are generalized. To do this, a proof of concept and a new formulation has been proposed to solve the problems of picking and batching called qRobot. A proof of concept was carried out in this part of the project through a Raspberry Pi 4 and the integration capacity of quantum computing within mobile robotics was tested, with one of the most demanded problems in this industrial sector: picking and batching problems. It was tested on different technologies, and the results were promising. Furthermore, in case of computational need, the robot parallelizes part of the operations in hybrid computing (quantum + classical), accessing CPU and QPU distributed in a public or private cloud. Furthermore, we developed a stable environment (ARM64) inside the robot (Raspberry) to run gradient operations and other quantum algorithms on IBMQ, Amazon Braket (D-Wave) and Pennylane locally or remotely. To improve the execution time of variational algorithms in this NISQ era and the next, EVA has been proposed: A quantum Exponential Value Approximation algorithm. To date, the VQE is the flagship of quantum computing. Today, in the market-leading quantum cloud computing platforms, the cost of experimenting with quantum circuits is proportional to the number of circuits running on those platforms. That is, with more circuits, higher cost. One of the things that the VQE, the flagship of this low-qubit era, achieves is shallow depth by dividing the Hamiltonian into a list of many small circuits (Pauli matrices). But this very fact makes simulating with VQE very expensive in the cloud. For this same reason, EVA was designed to calculate the expected value with a single circuit. Even having answered the hypothesis of this work with all the studies carried out, it is still possible to continue research to propose new quantum algorithms to improve combinatorial optimization.

Випадкові числа використовуються давно і досить широко. Нагадаємо деякі області їх застосування: - Соціологічні та наукові дослідження. Підготовка випадкових вибірок при зборі даних, опитуванні думок або в дослідженні фізичних явищ з випадковим вибором результатів експериментів. - Моделювання. У комп'ютерному моделюванні фізичних явищ. Крім того, математичне моделювання використовує випадкові числа як один з інструментів чисельного аналізу. - Криптографія та інформаційна безпека. Випадкові числа можуть використовуватися в тестуванні коректності або ефективності алгоритмів і програм. Багато алгоритмів використовують генерацію псевдовипадкових чисел для вирішення прикладних завдань (наприклад, криптографічні алгоритми шифрування, генерація унікальних ідентифікаторів та ін.). Теорія побудови генераторів псевдовипадкових чисел (ГПСЧ) глибоко і добре вивчена. Однак у тій же інженерній практиці іноді виникає необхідність у генерації якихось спеціальних послідовностей певної підмножини векторів довжини n. Прикладом може бути область тестування цифрової апаратури. The paper analyzes the algorithm for finding Hamiltonian cycles for the generator of all pseudo-random binary vectors with weights p1…pk based on the standard scheme. The article considers the method of forming vectors, their distribution into groups and the subsequent formation of Hamiltonian cycles, taking vectors as the vertices of graphs as a basis

In this paper, we investigate pollutant reduction policies under uncertainty. We consider two kinds of policies as distinguished by their associated costs. The first policy incurs a proportional reduction cost, while the second policy incurs fixed and proportional reduction costs. We formulate the policymaker's decision as a singular stochastic control problem in the first case and as a stochastic impulse control problem in the second case. Using this analysis, we provide the optimal pollutant reduction policies in both cases and their characteristics using numerical analysis., 特集 経済制度と社会秩序の形成に関する理論実証分析, Special issue: theoretical and empirical studies on the evolution of economic institutions and social order, 論説(Article)

Doctoral thesis Nowadays, knowledge extraction from data is an essential task for decisionmaking in many areas. However, the data sets commonly present some negative problems (complexities) that decrease the performance in the knowledge extraction process. The imbalanced distribution of data between classes and the presence of noise and/or class overlap are data intrinsic characteristics that frequently decrease the performance of the knowledge extraction because data are assumed to keep a uniform distribution and free from any other problem. All these issues have been studied in Pattern Recognition and Data Mining, because of their impact on the performance of the learning models. Thus this Ph.D. thesis addresses class imbalance, class overlap and/or noise through techniques that reduce and clean the most represented class. Among the solutions to handle with the class imbalance problem, new algorithms based on graphs are proposed. This idea arises from the fact that many real-world problems (network analysis, chemical models, remote sensing, among others) have been tackled by using graph-based strategies, in which the problem is transformed in terms of vertices and edges. Keeping this in mind, the proposals presented in this Ph.D. thesis consider the most represented class as as a complete graph in such a way that a representative subset of majority class instances is obtained through reduction criteria. Regarding the data sets with class imbalance and class overlap and/or noise, the proposals include the use of clustering algorithms as a cleaning strategy. It is well known that these algorithms are used to group instances according to similar characteristics; however, the proposal here presented makes use of their ability to detect noisy instances. By this, the application of a clustering algorithm is carried out before facing the class imbalance. As a further extension to the proposals presented in this Ph.D. thesis and due to the growing interest in Big Data problems, the last part of this report introduces a graph-based algorithm to handle class imbalance in large-scale data sets. Becas nacionales del CONACYT

Predictive policing is a global strategic orientation of the police that emphasizes the anticipation of crimes to prevent them. Its development comes from various fields of knowledge, in which criminology has created a theoretical body on criminal patterns in space and time, mathematics and statistics have modelled these patterns and ICTs have made possible their implementation in police forces. The research remains open, accompanied by uncertainties about its modelling and application. This thesis reviews the scientific, theoretical and practical knowledge related to predictive policing and the possibilities of applying it in Catalonia to predict residential burglaries with forced entry, which had a significant increase between 2009 and 2015 and, since then, they have remained at high crime rates. The spatiotemporal pattern of repeated and near-repeated victimization has been analysed. It has been verified that the residential burglaries in Catalonia are temporarily distributed in non-random waves when analysing the series in large cells, of 5km on each side. On a small scale, in cells less than 1km2, this pattern is less detected. This has suggested that the pattern of near repeated victimization in Catalonia is manifested differently than is usual in other countries, where it has basically been detected on a micro scale and in urban environments. This difference is related to the heterogeneity of Catalan geography, especially with respect to urban and residential, so it has been proposed to expand the concept of repetition in geographical proximity, to repetition in different areas, also far away, but which have similarities from the point of view of criminal opportunity. Criminal groups would choose these areas in advance and victimize them for periods of several weeks, generating waves of burglaries through a proposed new spatiotemporal pattern: the "all-in-one." The viability of this new pattern to explain, predict and prevent burglaries at home in Catalonia has been verified. It generates networks of relatively similar scattered areas that tend to activate at the same time and have been called "burglaries constellations." It is suggested that in geographical environments similar to Catalonia, such as much of southern Europe, the spatiotemporal distribution of residential burglaries could also follow these same proposed patterns El predictive policing és una orientació estratègica global de la policia que posa èmfasi en l’anticipació dels delictes per prevenir-los. El seu desenvolupament prové de varis camps del coneixement, en què la criminologia ha creat un cos teòric sobre els patrons delictius en l’espai i el temps, la matemàtica i l’estadística han modelat aquests patrons i les TIC n’han fet possible la implementació als cossos policials. La recerca segueix oberta, acompanyada d’incerteses sobre la seva modelització i aplicació. Aquesta tesi fa una revisió del coneixement científic, teòric i pràctic, relacionat amb el predictive policing i les possibilitats d’aplicar-lo a Catalunya per predir els robatoris amb força a domicili, que van tenir un increment important entre els anys 2009 a 2015 i, des de llavors, s’han mantingut amb uns índexs delictius elevats. S’ha analitzat el patró espai temps de la victimització repetida i quasi repetida. S’ha comprovat que els robatoris a Catalunya es distribueixen temporalment en onades no aleatòries quan s’analitzen les sèries en cel·les grans, de 5km de costat. A petita escala, en cel·les de menys d’1km2, aquest patró és menys detectat. Això ha suggerit que el patró de victimització quasi repetida a Catalunya es manifesta de forma diferent del que és habitual en altres països, on bàsicament s’ha detectat en una escala micro i en entorns urbans. Aquest diferència es relaciona amb l’heterogeneïtat de la geografia catalana, especialment la urbana i residencial, de manera que s’ha proposat ampliar el concepte de repetició en la proximitat geogràfica, al de repetició en zones diferents, també allunyades, però que tenen semblances des del punt de vista de l’oportunitat delictiva. Els grups criminals escollirien aquestes zones d’antuvi i les victimitzarien durant períodes de vàries setmanes, generant les onades de robatoris mitjançant un nou patró espai-temps que es proposa: l’ “all-in-one”. S’ha comprovat la viabilitat d’aquest nou patró per explicar, predir i prevenir els robatoris amb força a domicili a Catalunya. Aquest patró genera xarxes de zones disperses, relativament semblants, que tenen tendència a activar-se a la vegada i que s’han anomenat “constel·lacions de robatoris”. Es suggereix que en entorns geogràfics semblants al de Catalunya, com pot ser gran part del sud d’Europa, la distribució espaciotemporal dels robatoris també podria seguir aquests mateixos patrons proposats Programa de Doctorat Interuniversitari en Dret, Economia i Empresa

Suposem que una o diverses entitats estan situades en alguns dels vèrtexs d'un graf simple, i que una entitat situada en un vèrtex es pot ocupar d'un problema en qualsevol vèrtex del seu entorn tancat. En general, una entitat pot consistir en un robot, un observador, una legió, un guàrdia, etc. Informalment, diem que un graf està protegit sota una determinada ubicació d'entitats si hi ha almenys una entitat disponible per tractar un problema en qualsevol vèrtex. S'han considerat diverses estratègies (o regles d'ubicació d'entitats), sota cadascuna de les quals el graf es considera protegit. Aquestes estratègies de protecció de grafs s'emmarquen en la teoria de la dominació en grafs, o en la teoria de la dominació segura en grafs. En aquesta tesi, introduïm l'estudi de la w-dominació (segura) en grafs, el qual és un enfocament unificat a la idea de protecció de grafs, i que engloba variants conegudes de dominació (segura) en grafs i introdueix de noves. La tesi està estructurada com un compendi de deu articles, els quals han estat publicats en revistes indexades en el JCR. El primer està dedicat a l'estudi de la w-dominació, el cinquè a l'estudi de la w-dominació segura, mentre que els altres treballs estan dedicats a casos particulars d'estratègies de protecció total. Com és d'esperar, el nombre mínim d'entitats necessàries per a la protecció sota cada estratègia és d'interès. En general, s'obtenen fórmules tancades o fites ajustades sobre els paràmetres estudiats. Supongamos que una o varias entidades están situadas en algunos de los vértices de un grafo simple y que una entidad situada en un vértice puede ocuparse de un problema en cualquier vértice de su vecindad cerrada. En general, una entidad puede consistir en un robot, un observador, una legión, un guardia, etc. Informalmente, decimos que un grafo está protegido bajo una determinada ubicación de entidades si existe al menos una entidad disponible para tratar un problema en cualquier vértice. Se han considerado varias estrategias (o reglas de ubicación de entidades), bajo cada una de las cuales el grafo se considera protegido. Estas estrategias de protección de grafos se enmarcan en la teoría de la dominación en grafos, o en la teoría de la dominación segura en grafos. En esta tesis, introducimos el estudio de la w-dominación (segura) en grafos, el cual es un enfoque unificado a la idea de protección de grafos, y que engloba variantes conocidas de dominación (segura) en grafos e introduce otras nuevas. La tesis está estructurada como un compendio de diez artículos, los cuales han sido publicados en revistas indexadas en el JCR. El primero está dedicado al estudio de la w-dominación, el quinto al estudio de la w-dominación segura, mientras que los demás trabajos están dedicados a casos particulares de estrategias de protección total. Como es de esperar, el número mínimo de entidades necesarias para la protección bajo cada estrategia es de interés. En general, se obtienen fórmulas cerradas o cotas ajustadas sobre los parámetros estudiados Suppose that one or more entities are stationed at some of the vertices of a simple graph and that an entity at a vertex can deal with a problem at any vertex in its closed neighbourhood. In general, an entity could consist of a robot, an observer, a legion, a guard, and so on. Informally, we say that a graph is protected under a given placement of entities if there exists at least one entity available to handle a problem at any vertex. Various strategies (or rules for entities placements) have been considered, under each of which the graph is deemed protected. These strategies for the protection of graphs are framed within the theory of domination in graphs, or in the theory of secure domination in graphs. In this thesis, we introduce the study of (secure) w-domination in graphs, which is a unified approach to the idea of protection of graphs, that encompasses known variants of (secure) domination in graphs and introduces new ones. The thesis is structured as a compendium of ten papers which have been published in JCR-indexed journals. The first one is devoted to the study of w-domination, the fifth one is devoted to the study of secure w-domination, while the other papers are devoted to particular cases of total protection strategies. As we can expect, the minimum number of entities required for protection under each strategy is of interest. In general, we obtain closed formulas or tight bounds on the studied parameters.

Les molècules es configuren de manera natural com a xarxes, de manera que són ideals per estudiar utilitzant les seves representacions gràfiques, on els nodes representen àtoms i les vores representen els enllaços químics. Una alternativa per a aquesta representació directa és el gràfic reduït ampliat, que resumeix les estructures químiques mitjançant descripcions de nodes de tipus farmacòfor per codificar les propietats moleculars rellevants. Un cop tenim una manera adequada de representar les molècules com a gràfics, hem de triar l’eina adequada per comparar-les i analitzar-les. La distància d'edició de gràfics s'utilitza per resoldre la concordança de gràfics tolerant als errors; aquesta metodologia calcula la distància entre dos gràfics determinant el nombre mínim de modificacions necessàries per transformar un gràfic en l’altre. Aquestes modificacions (conegudes com a operacions d’edició) tenen associat un cost d’edició (també conegut com a cost de transformació), que s’ha de determinar en funció del problema. Aquest estudi investiga l’eficàcia d’una comparació molecular basada només en gràfics que utilitza gràfics reduïts ampliats i distància d’edició de gràfics com a eina per a aplicacions de cribratge virtual basades en lligands. Aquestes aplicacions estimen la bioactivitat d'una substància química que utilitza la bioactivitat de compostos similars. Una part essencial d’aquest estudi es centra en l’ús d’aprenentatge automàtic i tècniques de processament del llenguatge natural per optimitzar els costos de transformació utilitzats en les comparacions moleculars amb la distància d’edició de gràfics. Las moléculas tienen la forma natural de redes, lo que las hace ideales para estudiar mediante el empleo de sus representaciones gráficas, donde los nodos representan los átomos y los bordes representan los enlaces químicos. Una alternativa para esta representación sencilla es el gráfico reducido extendido, que resume las estructuras químicas utilizando descripciones de nodos de tipo farmacóforo para codificar las propiedades moleculares relevantes. Una vez que tenemos una forma adecuada de representar moléculas como gráficos, debemos elegir la herramienta adecuada para compararlas y analizarlas. La distancia de edición de gráficos se utiliza para resolver la coincidencia de gráficos tolerante a errores; esta metodología estima una distancia entre dos gráficos determinando el número mínimo de modificaciones necesarias para transformar un gráfico en el otro. Estas modificaciones (conocidas como operaciones de edición) tienen un costo de edición (también conocido como costo de transformación) asociado, que debe determinarse en función del problema. Este estudio investiga la efectividad de una comparación molecular basada solo en gráficos que emplea gráficos reducidos extendidos y distancia de edición de gráficos como una herramienta para aplicaciones de detección virtual basadas en ligandos. Estas aplicaciones estiman la bioactividad de una sustancia química empleando la bioactividad de compuestos similares. Una parte esencial de este estudio se centra en el uso de técnicas de procesamiento de lenguaje natural y aprendizaje automático para optimizar los costos de transformación utilizados en las comparaciones moleculares con la distancia de edición de gráficos. Molecules are naturally shaped as networks, making them ideal for studying by employing their graph representations, where nodes represent atoms and edges represent the chemical bonds. An alternative for this straightforward representation is the extended reduced graph, which summarizes the chemical structures using pharmacophore-type node descriptions to encode the relevant molecular properties. Once we have a suitable way to represent molecules as graphs, we need to choose the right tool to compare and analyze them. Graph edit distance is used to solve the error-tolerant graph matching; this methodology estimates a distance between two graphs by determining the minimum number of modifications required to transform one graph into the other. These modifications (known as edit operations) have an edit cost (also known as transformation cost) associated, which must be determined depending on the problem. This study investigates the effectiveness of a graph-only driven molecular comparison employing extended reduced graphs and graph edit distance as a tool for ligand-based virtual screening applications. Those applications estimate the bioactivity of a chemical employing the bioactivity of similar compounds. An essential part of this study focuses on using machine learning and natural language processing techniques to optimize the transformation costs used in the molecular comparisons with the graph edit distance. Overall, this work shows a framework that combines graph reduction and comparison with optimization tools and natural language processing to identify bioactivity similarities in a structurally diverse group of molecules. We confirm the efficiency of this framework with several chemoinformatic tests applied to regression and classification problems over different publicly available datasets.

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

ngesta de fibra dietètica s'ha relacionat amb la salut digestiva i cardiovascular en adults, però hi ha poques evidències d'aquesta relació durant la infància. A més, les recomanacions d'ingesta de fibra en pediatria es basen en una extrapolació de les indicades per als adults, desconeixent-se si són adequades per a la salut en la infància. L’objectiu d’aquesta tesi doctoral va ser analitzar l’associació entre la ingesta de fibra dietètica i la seva adequació a les recomanacions durant la infància amb els marcadors de salut cardiometabòlics. Es va realitzar una anàlisi longitudinal observacional secundària a l'Assaig EU Childhood Obesity Project. Es va descriure la ingesta de fibra i les fonts (recollida a intervals regulars mitjançant diaris de 3 dies) des del naixement fins als 8 anys en participants d'Alemanya, Bèlgica, Polònia, Itàlia i Espanya. Els nens es van classificar segons el compliment de les recomanacions d'ingesta de fibra. Es va calcular el percentatge d'adequació a les recomanacions a totes les edats. Als 8 anys es va avaluar la seva antropometria, pressió arterial sistòlica (PAS) i les anàlisis bioquímiques en sang (lipoproteïnes, triglicèrids i homeòstasi per a resistència a la insulina (HOMA-IR)). La puntuació z interna d’aquests paràmetres es va sumar com a indicador de risc cardiometabòlic. Baixos consums de fibra de forma mantinguda al llarg de la infància es van relacionar amb menor tolerància a la glucosa, xifres superiors de PAS i una puntuació de risc cardiometabòlic més alta als 8 anys. Diferents fonts de fibra (fruites i verdures o llegums) es van associar amb diferents paràmetres del risc cardiometabòlic. Un percentatge elevat de la població infantil tenia ingestes de fibra inferiors a les recomanades de l'EFSA, encara que el fet de no complir-les no es va associar amb la salut cardiometabòlica en aquestes edats. No es va trobar un punt de tall específic d'ingesta de fibra associat a efectes beneficiosos sobre la salut als 8 anys que es pogués marcar com a nova recomanació. Tot i això, el fet que una ingesta mantinguda al voltant de 6.7 gr/1000 kcal al dia s'associés amb pitjors marcadors cardiometabòlics, podria suggerir que una ingesta superior a aquesta seria suficient per prevenir aquest tipus d'alteracions cardiometabòliques en edats primerenques. La ingesta de fibra dietética se ha relacionado con la salud digestiva y cardiovascular en adultos, pero existen escasas evidencias de esta relación durante la infancia. Además, las recomendaciones de ingesta de fibra en pediatría se basan en una extrapolación de las indicadas para los adultos, desconociéndose si son adecuadas para la salud en la infancia. El objetivo de esta tesis doctoral fue analizar la asociación entre la ingesta de fibra dietética y su adecuación a las recomendaciones durante la infancia con los marcadores de salud cardiometabólicos. Se realizó un análisis longitudinal observacional secundario al Ensayo EU Childhood Obesity Project. Se describió la ingesta de fibra y sus fuentes (recogida a intervalos regulares mediante diarios de 3 días) desde el nacimiento hasta los 8 años en participantes de Alemania, Bélgica, Polonia, Italia y España. Los niños se clasificaron en función del cumplimiento de las recomendaciones de ingesta de fibra. Se calculó el porcentaje de adecuación a las recomendaciones en todas las edades. A los 8 años se evaluó su antropometría, presión arterial sistólica (PAS) y los análisis bioquímicos en sangre (lipoproteínas, triglicéridos y homeostasis para resistencia a la insulina (HOMA-IR)). La puntación z interna de estos parámetros se sumó como indicador de riesgo cardiometabólico. Bajos consumos de fibra de forma mantenida a lo largo de la infancia se relacionaron con menor tolerancia a la glucosa, cifras superiores de PAS y un puntaje de riesgo cardiometabólico más alto a los 8 años. Diferentes fuentes de fibra (frutas y verduras o legumbres) se asociaron con diferentes parámetros del riesgo cardiometabólico. Un porcentaje elevado de la población infantil realizaba ingestas de fibra inferiores a las recomendadas de la EFSA, aunque el hecho de no cumplirlas no se asoció con la salud cardiometabólica en estas edades. No se halló un punto de corte específico de ingesta de fibra asociado a efectos beneficiosos sobre la salud a los 8 años que pudiera marcarse como nueva recomendación. Sin embargo, el hecho de que una ingesta mantenida alrededor de 6.7 gr/1000 kcal al día se asociase con peores marcadores cardiometabólicos, podría sugerir que una ingesta superior a ésta sería suficiente para prevenir este tipo de alteraciones cardiometabólicas en edades tempranas. Dietary fiber intake has been associated with digestive and cardiovascular health in adults, but there is little evidence about this relationship during childhood. Furthermore, the fiber intake recommendations in pediatrics are based on an extrapolation of those indicated for adults, and it is unknown whether they are appropriate or not for children’s health. The aim of this doctoral thesis was to analyze dietary fiber intake and its adherence to recommendations in relation to cardiometabolic health markers during childhood. We performed an observational longitudinal analysis secondary to the EU Childhood Obesity Project Trial. Fiber intake and its dietary sources (collected at regular intervals using 3-day diaries) were described in participants from Germany, Belgium, Poland, Italy, and Spain from birth to 8 years. The children were classified depending on the compliance with the fiber intake recommendations. The percentage of adequacy with the recommendations was calculated at all ages. At 8 years of age, anthropometry, systolic blood pressure (SBP) and biochemical blood parameters (lipoproteins, triglycerides and homeostasis for insulin resistance (HOMA-IR)) were assessed. The internal z-score of these parameters was added as an indicator of cardiometabolic risk. Sustained low fiber intakes throughout childhood were associated with worse glucose tolerance, SBP levels, and overall cardiometabolic risk score at age 8 years. Different dietary sources of fiber (fruits and vegetables or legumes) were associated with different parameters of cardiometabolic risk. A high percentage of the child population had fiber intakes lower than those recommended by the EFSA, although not following them was not associated with cardiometabolic health at these ages. We did not find a specific cut-off point for fiber intake associated with beneficial health effects at 8 years which could be set as a new recommendation. However, the fact that an intake maintained around 6.7 g / 1000 kcal per day is associated with worse cardiometabolic markers, could suggest that an intake higher than this would be sufficient to prevent this type of cardiometabolic disturbances at an early age.

La predicció de ‘links’ o enllaços en xarxes complexes és un problema de molta importància, degut a la utilitat pràctica que implica. La capacitat de predir enllaços correctament en una xarxa és, però, també una conseqüència directa de la comprensió del funcionament i de les dinàmiques del sistema que s’estudia. En aquesta tesi doctoral, s’explora el problema de la predicció interpretable d’enllaços en xarxes complexes. En particular, l’anàlisi es centra en xarxes bipartides amb diferents tipus d’enllaços, degut a la seva presència en multitud de sistemes socials i naturals, així com a la seva capacitat d’analitzar diferents tipus d’interaccions. En aquest sentit, es presenta una família de models amb els quals és possible fer prediccions interpretables d’enllaços en aquest tipus de xarxes. Posteriorment, aquests models s’apliquen a dos problemes de diferents disciplines. En primer lloc, considerem un experiment social en el que un grup nombrós de persones pren decisions estratègiques en el context de la teoria de jocs. Observem que és possible agrupar les persones segons el seu comportament coŀlectiu a l’hora de prendre decisions. En funció d’aquests grups, podem predir correctament aproximadament el 75% de les decisions. En segon lloc, s’estudia un problema de microbiota intestinal humana en el que tenim mostres microbials d’un nombre elevat de pacients. De manera anàloga al problema anterior, intentem trobar grups de pacients basant-nos en les similituds del seus perfils microbials. D’acord amb aquests grups, aconseguim predir al voltant d’un 80% de les abundàncies. En conclusió, es demostra que és possible aplicar aquesta família de mètodes a problemes molt diferents, de tal manera que podem construir models predictius i interpretables, basats en la capacitat d’identificar grups o comunitats de nodes, així com de monitoritzar les interaccions entre aquestes comunitats. La predicción de ‘links’ o enlaces en redes complejas es un problema de suma importancia debido a la utilidad práctica que comporta. Sin embargo, la capacidad de predecir links correctamente en una red, es también la consecuencia de la comprensión del funcionamiento y las dinámicas del sistema que se estudia. En esta tesis, exploramos el problema de la predicción interpretable de links en redes complejas. En particular, nos centramos en redes bipartidas con varios tipos de links, debido a su ubicuidad en multitud de sistemas sociales y naturales, así como a la riqueza formal que aportan a nivel de las interacciones. A tal efecto, presentamos una familia de modelos con los que es posible hacer predicciones de links interpretables en dichas redes y la aplicamos a dos problemas de diferentes campos. En primer lugar, consideramos un experimento social en el que un grupo numeroso de personas toma decisiones estratégicas en el contexto de la teoría de juegos. Observamos que podemos agrupar a las personas por su comportamiento colectivo a la hora de tomar decisiones y que, en base a esos grupos, podemos predecir correctamente el 75% de las decisiones aproximadamente. En segundo lugar, estudiamos un problema de microbiota intestinal humana en el que tenemos muestras microbiales de un número elevado de pacientes. De manera análoga al problema anterior, intentamos encontrar grupos de pacientes por las similitudes en sus perfiles microbiales y, sobre esa base, predecir las abundancias de las diferentes especies de microbios. Conseguimos predecir aproximadamente un 80% de las abundancias. En definitiva, demostramos que es posible aplicar nuestros métodos a problemas muy diferentes, de tal manera que podemos construir modelos predictivos e interpretables, basados en la capacidad de identificar grupos o comunidades de nodos, así como de monitorizar las interacciones entre dichas comunidades. Link prediction in complex networks is a very important problem due to its practical importance. However, the ability of predicting links successfully arises naturally from a good understanding of the functioning and the dynamics of the system under study. In this thesis, we explore the problem of interpretable link prediction in complex networks. In particular, we focus on multilink bipartite networks; first, because bipartite networks are ubiquitous in many natural and social systems and second, because the existence of multiple links allows us to analyze different types of interactions. To that end, we present a family of models that can make interpretable link prediction in this kind of networks and we apply them to two different problems. In the first problem, we consider a social experiment in which a large group of people make strategic decisions in a game theoretical context. We observe that it is possible to find groups of people according to their collective strategic behaviors (i.e., how do they make decisions) and that it is possible to make link prediction upon those groups. In our case we can successfully predict around 75% of the decisions. The second problem is a human microbiology one. We have data on gut microbiome samples from a large number of patients. In a similar fashion, we look for groups of patients according to similarities in their microbial profiles. We then make predictions of microbial abundances using that group structure with an approximately 80% accuracy rate. In conclusion, we show that it is possible to implement our methods to problems that are very different in their nature, so that we can build predictive and interpretable models that work on the ability to identify groups or communities of nodes and track the interactions among those communities.

The present thesis is a compendium of three research articles produced between 2015 and 2019. The three articles are different contributions based on compositional statistical methodology and statistical inference of genetic 2/2 relatedness. In the first work of this thesis, we review the classical graphical methods used to detect relatedness and introduce the analysis of Compositional Data for relatedness research. In the second article, we propose the analysis of identity by state genotype sharing data instead of the classical identity by state allele sharing data. The third article finishes the thesis with the development of the likelihood ratio approach to infer three-quarter siblings in genetic databases. To illustrate all the results of this doctoral thesis we use genetic markers from worldwide human population projects such as the Human Genome Diversity Project and the 1000 Genomes Project, as well as from a local prospective human cohort of the Genomes of Catalonia (GCAT) Aquesta tesi doctoral és un compendi de tres articles de recerca produïts entre el 2015-2019. Els tres articles són aportacions diferents basades en la metodologia de les dades composicionals i en la inferència estadística de relacions familiars. En el primer treball d'aquesta tesi, revisem els mètodes gràfics clàssics utilitzats per detectar relacions familiars i introduïm l'anàlisi de les dades composicionals per a la investigació de relacions familiars. En el segon, es proposa l'anàlisi de dades de genotips compartits idèntics per estat en lloc de les clàssiques dades d'al·lels compartits. El tercer article finalitza la tesi amb l'elaboració de la raó de versemblances per inferir tres quarts germans en bases de dades genètiques. Per il·lustrar els resultats, s'utilitzen marcadors genètics de projectes de població humana com el Projecte de la Diversitat del Genoma Humà, el Projecte 1000 Genomes i una cohort humana prospectiva local dels genomes de Catalunya (GCAT) Programa de Doctorat en Tecnologia

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.

Навчальний посібник створений за матеріалами лекцій з курсу «Дискретна математика». Він містить основні положення теорії множин, комбінаторики та теорії графів. Зокрема розглянуті основи теорії множин, відповідностей та відношень на множинах. Представлені відношення еквівалентності та порядку, детально описані їх властивості. Основні положення комбінаторики представлені законами комбінаторики, комбінаторними вибірками та типовими комбінаторними алгоритмами. Значна увага приділена теорії графів. Розглянуті базові визначення теорії графів, способи створення та властивості графів, відношення та відображення на графах, магічні числа графів. Окремо розглянуто дерева, їх властивості та ліс. Описані основні алгоритми на графах, призначені для обходу графів, визначення найкоротших шляхів у них та побудови мінімальних остовних дерев. Наведені базові поняття та теореми, пов’язані з правильним мінімальним розфарбуванням графів. Дано код або псевдокод основних алгоритмів розфарбування. Посібник може бути корисним для інженерів та студентів технічних спеціальностей. The textbook is based on the materials of the lecture course "Discrete Mathematics". It contains the basics of set theory, combinatorics and graph theory. In particular, the basics of set theory, correspondences, and relations on sets are considered. The relations of equivalence and order are presented, their properties are described in detail. The main provisions of combinatorics are represented by the rules of combinatorics, combinatorial sampling and combinatorial algorithms. Considerable attention is paid to graph theory. The basic definitions of graph theory, methods of creating and properties of graphs, relations and mappings on graphs, magic numbers of graphs are considered. Trees, their properties and forest are considered separately. The basic algorithms on graphs intended for traversal of graphs, definition of the shortest ways in them and construction of the minimum core trees are described. The basic concepts and theorems related to the correct minimal coloring of graphs are given. The codes or pseudocodes of the main coloring algorithms are given. The manual can be useful for engineers and technical students. Учебное пособие создано по материалам курса лекций «Дискретная математика». Оно содержит основные положения теории множеств, комбинаторики и теории графов. В частности, рассмотрены основы теории множеств, соответствий и отношений на множествах. Представлены отношения эквивалентности и порядка, подробно описаны их свойства. Основные положения комбинаторики представлены законами комбинаторики, комбинаторными выборками и комбинаторными алгоритмами. Значительное внимание уделено теории графов. Рассмотрены базовые определения теории графов, способы создания и свойства графов, отношения и отображения на графах, магические числа графов. Отдельно рассмотрены деревья, их свойства и лес. Описаны основные алгоритмы на графах, предназначенные для обхода графов, определения кратчайших путей в них и построения минимальных остовных деревьев. Приведены базовые понятия и теоремы, связанные с правильной минимальной раскраской графов. Даны коды или псевдокоды основных алгоритмов раскраски. Пособие может быть полезным для инженеров и студентов технических специальностей.

目次1．はじめに2．ビンズン省の概要と都市開発 2．1 ビンズン省の概要 2．2 ビンズン省と都市開発 2．3 ビンズン新都市と周辺地域の開発3．ビンズン省とスマートコミュニティ 3．1 スマートコミュニティとは 3．2 ビンズン省と電力エネルギー 3．3 ビンズン新都市におけるスマート化 3．4 ビンズン新都市のスマート化目標4．おわりに

スマートコミュニティ (Smart Community) は，地域におけるエリア全体のエネルギー利用の効率化による省エネルギーの促進や再生可能エネルギーの導入など，都市の環境問題や交通システム，住民のライフスタイル変革まで，複合的・総合的に組み合わせた社会システムにおける概念のことである。 スマートコミュニティでは，家庭や企業などによる省エネルギーの促進とともに，太陽光や太陽熱，水力，風力，バイオマス，地熱など発電といった再生可能エネルギーの導入によるエネルギー源の多様化，および地球温暖化の進行を防ぐための省CO_2 (二酸化炭素)化や電気自動車 (Electric Vehicles) の導入などの活用において，IT (Information Technology) を積極的に活用したエネルギー・マネジメント・システム (Energy Management System) が見受けられる。 近年，新興国のベトナムにおいても，国内の各地でスマートコミュニティの概念に基づく，積極的な地域開発や都市開発などの取り組みが見られるようになっている。そこで，本論文では，ベトナムの中部地方都市であるダナン市の事例において，地域開発や都市開発における高品質電力，ITインフラ整備，スマート交通を中核としたスマートコミュニティ戦略の現状と課題についての考察を行う。

L’aparició de nous virus causants de malalties està estretament lligada a l’especialització de subpoblacions virals cap a nous tipus d’amfitrions. La modelització matemàtica proporciona un marc quantitatiu que pot ajudar amb la predicció de processos a llarg termini com pot ser l’especialització. A causa de la naturalesa complexa que presenten les interaccions intra i interespecífiques en els processos evolutius, cal aplicar eines matemàtiques complexes, com ara l’anàlisi de bifurcacions, al estudiar dinàmiques de població. Aquesta tesi desenvolupa una jerarquia de models de població per poder comprendre l’aparició i les dinàmiques d’especialització, i la seva dependència dels paràmetres del sistema. Utilitzant un model per a un virus de tipus salvatge i un virus mutat que competeixen pel mateix amfitrió, es determinen les condicions per a la supervivència únicament de la subpoblació mutant, juntament amb la seva coexistència amb el cep de tipus salvatge. Els diagrames d’estabilitat que representen regions de dinàmiques diferenciades es construeixen en termes de taxa d’infecció, virulència i taxa de mutació; els diagrames s’expliquen en base a les característiques biològiques de les subpoblacions. Per a paràmetres variables, s’observa i es descriu el fenomen d’intersecció i intercanvi d’estabilitat entre diferents solucions sistemàtiques i periòdiques en l’àmbit dels ceps de tipus salvatge i els ceps mutants en competència directa. En el cas de que diversos tipus d’amfitrions estiguin disponibles per a ser disputats per ceps especialitzats i generalistes existeixen regions de biestabilitat, i les probabilitats d’observar cada estat es calculen com funcions de les taxes d’infecció. S’ha trobat un rar atractor caòtic i s’ha analitzat amb l’ús d’exponents de Lyapunov. Això, combinat amb els diagrames d’estabilitat, mostra que la supervivència del cep generalista en un entorn estable és un fet improbable. A més, s’estudia el cas dels diversos ceps N>>1 que competeixen per diferents tipus de cèl·lules amfitriones. En aquest cas s’ha descobert una dependència no monotònica, contraria al que es preveia, del temps d’especialització sobre la mida inicial i la taxa de mutació, com a conseqüència de la realització d’un anàlisi de regressió sobre dades obtingudes numèricament. En general, aquest treball fa contribucions àmplies a la modelització matemàtica i anàlisi de la dinàmica dels patogens i els processos evolutius. La aparición de nuevos virus causantes de enfermedades está estrechamente ligada a la especialización de las subpoblaciones virales hacia nuevos tipos de anfitriones. La modelizaci ón matemática proporciona un marco cuantitativo que puede ayudar a la predicción de procesos a largo plazo como la especialización. Debido a la naturaleza compleja que presentan las interacciones intra e interespecíficas en los procesos evolutivos, aplicar herramientas matemáticas complejas, tales como el análisis de bifurcación, al estudiar dinámicas de población. Esta tesis desarrolla una jerarquía de modelos de población para poder comprender la aparición y las dinámicas de especialización, y su dependencia de los parámetros del sistema. Utilizando un modelo para un virus de tipo salvaje y un virus mutado que compiten por el mismo anfitrión, se determinan las condiciones para la supervivencia únicamente de la subpoblación mutante, junto con su coexistencia con la cepa de tipo salvaje. Los diagramas de estabilidad que representan regiones de dinámicas diferenciadas se construyen en términos de tasa de infección, virulencia y tasa de mutación; los diagramas se explican en base a las características biológicas de las subpoblaciones. Para parámetros variables, se observa y se describe el fenómeno de intersección e intercambio de estabilidad entre diferentes soluciones sistemáticas y periódicas en el ámbito de las cepas de tipo salvaje y las cepas mutantes en competencia directa. En el caso de que varios tipos de anfitriones estén disponibles para ser disputados por cepas especializadas y generalistas existen regiones de biestabilidad, y las probabilidades de observar cada estado se calculan como funciones de las tasas de infección. Se ha encontrado un raro atractor caótico y se ha analizado con el uso de exponentes de Lyapunov. Esto, combinado con los diagramas de estabilidad, muestra que la supervivencia de la cepa generalista en un entorno estable es un hecho improbable. Además, se estudia el caso de los varias cepas N>> 1 que compiten por diferentes tipos de células anfitrionas. En este caso se ha descubierto una dependencia no monotónica, contraria a lo que se preveía, del tiempo de especialización sobre el tamaño inicial y la tasa de mutación, como consecuencia de la realización de un análisis de regresión sobre datos obtenidos numéricamente. En general, este trabajo hace contribuciones amplias a la modelización matemática y el análisis de la dinámica de los patógenos y los procesos evolutivos. The occurrence of new disease-causing viruses is tightly linked to the specialisation of viral sub-populations towards new host types. Mathematical modelling provides a quantitative framework that can aid with the prediction of long-term processes such as specialisation. Due to the complex nature of intra- and interspecific interactions present in evolutionary processes, elaborate mathematical tools such as bifurcation analysis must be employed while studying population dynamics. In this thesis, a hierarchy of population models is developed to understand the onset and dynamics of specialisation and their dependence on the parameters of the system. Using a model for a wild-type and mutant virus that compete for the same host, conditions for the survival of only the mutant subpopulation, along with its coexistence with the wild-type strain, are determined. Stability diagrams that depict regions of distinct dynamics are constructed in terms of infection rates, virulence and the mutation rate; the diagrams are explained in terms of the biological characteristics of the sub-populations. For varying parameters, the phenomenon of intersection and exchange of stability between different periodic solutions of the system is observed and described in the scope of the competing wild-type and mutant strains. In the case of several types of hosts being available for competing specialist and generalist strains, regions of bistability exist, and the probabilities of observing each state are calculated as functions of the infection rates. A strange chaotic attractor is discovered and analysed with the use of Lyapunov exponents. This, combined with the stability diagrams, shows that the survival of the generalist in a stable environment is an unlikely event. Furthermore, the case of N=1 different strains competing for different types of host cells is studied. For this case, a counterintuitive and non-monotonic dependence of the specialisation time on the burst size and mutation rate is discovered as a result of carrying out a regression analysis on numerically obtained data. Overall, this work makes broad contributions to mathematical modelling and analysis of pathogen dynamics and evolutionary processes.

espanolLa presente Tesis se centra en el desarrollo del Analisis de Arquetipos (AA) y demuestra su viabilidad y rigor. Amplia la tipologia de datos con las que puede trabajar utilizando, ademas de los datos multivariantes continuos, datos binarios y datos funcionales. Hemos trabajado esta amalgama de datos, implementando AA en diferentes bases de datos, dando como fruto tres investigaciones independientes. En la primera aportacion trabajamos resultados de examenes utilizando una variante de AA, el Analisis de Arquetipoides (ADA) con datos binarios y funcionales, en la segunda aportacion presentamos un algoritmo basado en AA para trabajar la segmentacion de texturas y en la ultima presentamos otro algoritmo para la busqueda de datos atipicos (outliers). En todas estas investigaciones, se han utilizado datos reales y se ha hecho un estudio comparativo con otros analisis y algoritmos mas reconocidos. Los resultados obtenidos han demostrado con creces la viabilidad y la competencia de AA. EnglishThis Thesis develops the Archetype Analysis (AA) and demonstrates its viability and rigor. Expands the type of data which can work with, in addition to continuous multivariate data, it will manage binary data and functional data too. This amalgam of data will be used by implementing AA in different databases, resulting in three independent investigations. In the first contribution we work out exam results using a variant of AA, Archetypoids Analysis (ADA) with binary and functional data, in the second contribution we present an AA-based algorithm to work on texture segmentation and in the last one we present another algorithm for the search outliers. In all these investigations, real data have been used and a comparative study has been done with other more recognized analyzes and algorithms. The results obtained have demonstrated the AA feasibility and competence. catalaAquesta Tesi desenvolupa l’Analisi d’Arquetipus (AA) i demostra la seua viabilitat i rigor. Amplia la tipologia de dades amb les quals pot treballar utilitzant, a banda de les dades multivariants continues, dades binaries i dades funcionals. Aquesta amalgama de dades l’hem treballat implementant AA en diferents bases de dades, donant com a fruit tres investigacions independents. En la primera aportacio treballem resultats d’examens utilitzant una variant d’AA, l’Analisi d’Arquetipoids (ADA) amb dades binaries i funcionals, en la segona aportacio presentem un algorisme basat en AA per a treballar la segmentacio de textures i en la darrera presentem un altre algorisme per a la cerca de dades atipiques (outliers). En totes aquestes investigacions, s’han utilitzat dades reals i s’ha fet un estudi comparatiu amb altres analisis i algorismes mes reconeguts. Els resultats obtinguts han demostrat amb escreix la viabilitat i la competencia d’AA.

In real-world logistic operations there are a lot of situations that can be exploited to get better operational strategies. It is important to study these new alternatives, because they can represent significant cost reductions to the companies working with physical distribution. This thesis defines the Multi-Depot Vehicle Routing Problem with Vehicle Interchanges (MDVRPVI). In this problem, both vehicle capacities and duration limits on the routes of the drivers are imposed. To favor a better utilization of the available capacities and working times, it is allowed to combine pairs of routes at predefined interchange locations. The objective of this thesis is to analyze and solve the Multi-Depot Vehicle Routing Problem adding the possibility to interchange vehicles at predefined points. With this strategy, it is possible to reduce the total costs and the number of used routes with respect to the classical approach: The Multi-Depot Vehicle Routing Problem (MDVRP). It should be noted that the MDVRP is more challenging and sophisticated than the single-depot Vehicle Routing Problem (VRP). Besides, most exact algorithms for solving the classical VRP are difficult to adapt in order to solve the MDVRP (Montoya-Torres et al., 2015). From the complexity point of view, the MDVRPVI is NP-Hard, since it is an extension of the classical problem, which is already NP-Hard. We present a tight bound on the costs savings that can be attained allowing interchanges. Three integer programming formulations are proposed based on the classical vehicle-flow formulations of the MDVRP. One of these formulations was solved with a branch-and-bound algorithm, and the other two formulations, with branch-and-cut algorithms. Due to its great symmetry, the first formulation is only able to solve small instances. To increase the dimension of the instances used, we proposed two additional formulations that require one or more families of constraints of exponential size. In order to solve these formulations, we had to design and implement specific branch-and-cut algorithms. For these algorithms we implemented specific separation methods for constraints that had not previously been used in other routing problems. The computational experience performed evidences the routing savings compared with the solutions obtained with the classical approach and allows to compare the efficacy of the three solution methods proposed. En les operacions logístiques del món real es donen situacions que poden ser explotades per obtenir millors estratègies operacionals. És molt important estudiar aquestes noves alternatives, perquè poden representar una reducció significativa de costos per a les companyies que treballen en distribució de mercaderies. En aquesta tesi es defineix el Problema d'Enrutament de Vehicles amb Múltiples Dipòsits i Intercanvi de Vehicles (MDVRPVI). En aquest problema, es consideren tant la capacitat dels vehicles com els límits de duració de les rutes dels conductors. Per tal de millorar la utilització de les capacitats i temps de treball disponibles, es permet combinar parelles de rutes en punts d'intercanvi predefinits. L'objectiu d'aquesta tesi és analitzar i resoldre el problema d'Enrutament de Vehicles amb Múltiples Dipòsits, on es permet l'intercanvi de vehicles. Amb aquesta estratègia, és possible reduir els costos totals i el nombre de les rutes utilitzades respecte l'enfocament clàssic: el problema d'Enrutament de Vehicles amb Múltiples Dipòsits (MDVRP). Cal assenyalar que el MDRVP és més desafiant i sofisticat que el problema d'Enrutament de Vehicles d'un únic dipòsit (VRP). A més, molts algoritmes exactes per resoldre el VRP clàssic son complicats d'adaptar per resoldre el MDVRP (Montoya-Torres et al., 2015). Des del punt de vista de la complexitat, el MDRVPVI és NP-Dur, perquè és una extensió del problema clàssic, que també ho és. Presentem una cota ajustada de l'estalvi en els costos de distribució que es pot obtenir permetent els intercanvis. Es proposen tres formulacions de programació sencera basades en la formulació clàssica “vehicle-flow” del MDVRP. La primera formulació, degut a la seva grandària i la seva simetria, només permet resoldre instàncies molt petites. Per augmentar la dimensió de les instàncies abordables, es proposen dues formulacions addicionals que requereixen una o vàries famílies de restriccions de mida exponencial. Per això, per tal de resoldre el problema amb aquestes formulacions, ha calgut dissenyar i implementar sengles algorismes de tipus branch-and-cut. En aquests algorismes s'han implementat mètodes de separació específics per a les restriccions que no s'havien utilitzat prèviament en altres problemes de rutes. L’experiència computacional realitzada evidencia els estalvis obtinguts comparació amb les solucions corresponents l'enfocament clàssic. També es compara l’eficàcia dels tres mètodes propostes a l'hora de resoldre el problema.

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.

Donat que les dades de recompte es troben en molt fenòmens reals, la necessitat de mètodes i tècniques de qualitat per modelitzar i analitzar aquest tipus de dades és completament indiscutible. En aquest sentit, durant els últims anys, s’han trobat molts articles a la literatura dins dels que s’han desenvolupat tant mètodes bαsics com més generals per l’anàlisi d’aquestes dades. Tot i que a la literatura hi ha un ampli ventall de treballs que tracten alguns dels problemes més rellevants de les dades de recompte, molts altres problemes encara no s’han abordat. Aquesta tesi doctoral té la finalitat d’introduir nous mètodes i tècniques per analitzar alguns dels problemes de les dades de recompte com la sobredispersió, la inflació al zero (i la deflació al zero), i el fenomen que es dona quan hi ha falta de recomptes. Aquesta tesis està formada per un conjunt de publicacions que presenten i discuteixen en detall alguns dels mètodes proposats per tractar els problemes anteriorment mencionats. Particularment, dos d’aquests articles [1, 2] es centren en ajustar el fenomen de falta de recomptes, proposant dos models basats en els processos autoregressius de dades discretes i no negatives. A més a més, s’han estudiat una sèrie d’aplicacions, en diferents contextos, basades en dades reals, amb la finalitat de demostrar la usabilitat d’aquests nous models. D’altra banda, el treball [3] proposa un model més general de series temporals de recomptes. Aquest model considera series temporals amb una sobredispersió moderada, independentment de si la sèrie és o no estacionaria. Aquest nou model s’ha utilitzat per analitzar les dades de mortalitat recollides en granges bovines a petita escala. Aquestes dades de mortalitat tenen la particularitat de ser recomptes baixos, amb molts zeros i una sobredispersió forτa lleugera. Aquesta anàlisi forma part dæun projecte del Ministeri d’Agricultura, Pesca i Alimentació del Govern d’Espanya. L’última publicació que s’ha inclòs en aquesta tesi [4] proposa una proba exacte de bondat d’ajustament per detectar l’ inflació al zero (i la deflació al zero) en distribucions discretes dins del marc de la dosimetria biològica. La proba proposada en aquest treball va ser introduïda per primer cop per [5], derivada dels problemes d’ocupació. En el context de la dosimetria biològica, aquest nou test es considera un complement del test clàssic u quan les dades no són sobredisperses (sotadisperses), però si estan inflades al zero (no inflades al zero). Els mètodes introduïts en aquesta tesi doctoral es poden veure com a petits signes de progrés dins de l’anàlisi de dades de recompte. Aquests mètodes permeten estudiar problemes des de diferents punts de vista, mostrant resultats especialment bons quan s’analitzen problemes reals dins de l’àmbit de la salut publica i la dosimetria biològica. No obstant, encara que aquest treball és un avenτ dins de l’anàlisi de dades de recompte, molts més esforτos s’han de fer per anar millorant les tècniques i les eines d’anàlisis de dades de recompte. [1] Fernández-Fontelo, A., Cabaña, A., Puig, P. and Moriña, D. (2016). Under-reported data analysis with INAR-hidden Markov chains. Statistics in Medicine; 35(26): 4875-4890. [2] Fernández-Fontelo, A., Cabaña, A., Joe, H., Puig, P. and Moriña, D. Count time series models with under-reported data for gender-based violence in Galicia (Spain). Submitted. [3] Fernández-Fontelo, A., Fontdecaba, S., Alba, A. and Puig, P. (2017). Integer-valued AR processes with Hermite innovations and time-varying parameters: An application to bovine fallen stock surveillance at a local scale. Statistical Modelling; 17(3): 172-195. [4] Fernández-Fontelo, A., Puig, P., Ainsbury, E.A. and Higueras, M. (2018). An exact goodness-of-fit test based on the occupancy problems to study zero-inflation and zero-deflation in biological dosimetry data. Radiation Protection Dosimetry: 1-10. [5] Rao, C.R. and Chakravarti, I.M. (1956). Some small sample tests of significance for a Poisson distribution. Biometrics; 12: 264-282. Since count data are present in the nature of many real processes, the need for high-quality methods and techniques to accurately model and analyse these data is irrefutable. In this sense, in the past years, many comprehensive works have been presented in the literature where both, primary and more general methods to deal with count data, have developed based on different approaches. Despite the vast amount of excellent works dealing with the major concerns in count data, some issues related to these data remain to be addressed. This Ph.D. thesis is aimed at introducing novel methods and techniques of count data analysis to deal with some issues such that the overdispersion, the zero-inflation (and zero-deflation), and the phenomenon of under-reporting. In this sense, this thesis comprises different publications where innovative methods have been presented and discussed in detail. In particular, two of these articles [1, 2] are focused on the assessment of the under-reporting issue in count time series. These works propose two realistic models based on integer-valued autoregressive models. Besides, real-data applications within different frameworks are studied to demonstrate the practicality of these proposed models. On the other hand, the paper by [3] proposes a general model of count time series, which considers slightly overdispersed data, even if a series is non-stationary. This model has been used to analyse data of fallen cattle collected at a local scale when series have low counts, many zeros, and moderate overdispersion as part of a project commanded by the Ministry of Agriculture, Food and Environment of Spain. The last paper included in this thesis [4] proposes an exact goodness-of-fit test for detecting zero-inflation (and zero-deflation) in count distributions within the biological dosimetry framework. The test suggested in [4] was firstly introduced by [5] derived from the problems of occupancy. In the biological dosimetry context, this test is viewed as a complement to the always used u-test, when data are not overdispersed (not underdispersed), but they are zero-inflated (zero-deflated). The methods introduced in this Ph.D. thesis can be viewed as small but relevant signs of progress in count data analysis. They allow studying several issues of count data from different points of view, showing especially good results when dealing with some real-world concerns in public health and biological dosimetry frameworks. Although this work constitutes an advance in count data analysis, more efforts have to keep doing to improve the existing techniques and tools. [1] Fernández-Fontelo, A., Cabaña, A., Puig, P. and Moriña, D. (2016). Under-reported data analysis with INAR-hidden Markov chains. Statistics in Medicine; 35(26): 4875-4890. [2] Fernández-Fontelo, A., Cabaña, A., Joe, H., Puig, P. and Moriña, D. Count time series models with under-reported data for gender-based violence in Galicia (Spain). Submitted. [3] Fernández-Fontelo, A., Fontdecaba, S., Alba, A. and Puig, P. (2017). Integer-valued AR processes with Hermite innovations and time-varying parameters: An application to bovine fallen stock surveillance at a local scale. Statistical Modelling; 17(3): 172-195. [4] Fernández-Fontelo, A., Puig, P., Ainsbury, E.A. and Higueras, M. (2018). An exact goodness-of-fit test based on the occupancy problems to study zero-inflation and zero-deflation in biological dosimetry data. Radiation Protection Dosimetry: 1-10. [5] Rao, C.R. and Chakravarti, I.M. (1956). Some small sample tests of significance for a Poisson distribution. Biometrics; 12: 264-282.

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.

Dissertação (Mestrado) - Pontifícia Universidade Católica de Minas Gerais, Programa de Pós-Graduação em Ensino. Bibliografia: f. 89-92 O ensino da Análise Combinatória nas escolas brasileiras, no início do século XXI, baseia-se geralmente apenas na utilização de fórmulas matemáticas, podendo, dessa maneira, prejudicar o apendizado do aluno. Diante desse quadro, o presente trabalho se dispõe a propor uma estratégia didática que possa contribuir para o ensino desse conteúdo. O objetivo da pesquisa foi o desenvolvimento de um aplicativo para smartphone, utilizando a plataforma Android Studio na criação de um jogo para o ensino de Análise Combinatória na Educação Básica. Para isso, foi desenvolvida uma pesquisa-ação em conformidade com a revisão bibliográfica realizada. O uso deste aplicativo tem como suporte uma sequência didática elaborada com desafios que envolvem problemas de contagem, atraindo, assim, a atenção os alunos e favorecendo o processo de construção do seu conhecimento. Esse fato pode ser constatado por meio do questionário que os alunos responderam ao final da pesquisa. O jogo foi aplicado nos alunos do segundo ano do ensino médio da Escola Educação Criativa, localizada no município de Ipatinga, MG. Por meio deste estudo foi possível verificar que novas metodologias de ensino aliadas ao uso de tecnologias, podem contribuir para o ensino de Matemática, especialmente para o de Análise Combinatória. Palavras-chave: Análise Combinatória. Jogos. Tecnologia no ensino. The teaching of Combinatorial Analysis in Brazilian schools, at the beginning of the 21st century, is generally based only on the use of mathematical formulas, which may, in this way, hinder students' apprehension. In view of this framework, the present work sets out to propose a didactic strategy that can contribute to the teaching of this content. The objective of the research was the development of a smartphone application, using the Android Studio platform in the creation of a game for teaching Combinatorial Analysis in Basic Education. For this, an action research was developed in accordance with the literature review. The use of this application is supported by a didactic sequence elaborated with challenges that involve counting problems, thus attracting students attention and favoring the process of building their knowledge. This fact can be verified through the questionnaire that the students answered at the end of the research. The game was applied to the students of the second year of high school at Escola Educação Criativa, located in the municipality of Ipatinga, MG. Through this study it was possible to verify that new teaching methodologies combined with the use of technologies can contribute to the teaching of Mathematics, especially to Combinatorial Analysis. Keywords : Combinatorial Analysis. Games. Technology in teaching.

La dimensió mètrica d'un espai mètric general es va introduir el 1953, però va atreure poca atenció fins que, uns vint anys més tard, es va aplicar a les distàncies entre els vèrtexs d'un graf. Des de llavors s'ha utilitzat amb freqüència en la teoria de grafs, la química, la biologia, la robòtica i moltes altres disciplines. A causa de la multiplicitat de situacions de les que pot sorgir el problema de distingir els vèrtexs d'un graf, diverses variants del concepte original de la dimensió mètrica ha anat apareixent en la literatura especialitzada. En aquesta tesi s'estudia una d'aquestes variants, és a dir, la dimensió mètrica local. En concret, aquesta tesi ens centrem en el problema de calcular la dimensió mètrica local de grafs. En primer lloc, presentem l'estat de l'art de la dimensió mètrica local i obtenim alguns resultats originals en els que caracteritzem tots els grafs que atenyen algunes fites conegudes. En segon lloc, obtenim fórmules tancades i fites tenses per a la dimensió mètrica local de diverses famílies de grafs, incloent grafs producte fort, grafs corona i grafs producte lexicogràfic. Finalment, introduïm l'estudi de la dimensió mètrica local simultània i donem alguns resultats generals en aquesta nova línia d'investigació., La dimensión métrica de un espacio métrico general fue introducida en 1953, pero atrajo poca atención hasta que, aproximadamente veinte años más tarde, se aplicó a las distancias entre vértices de un gráfico. Desde entonces se ha utilizado con frecuencia en la teoría de los gráficos, la química, la biología, la robótica y muchas otras disciplinas. Debido a la multiplicidad de situaciones desde las que puede surgir el problema de distinguir los vértices de un gráfico, en la literatura especializada han aparecido varias variantes del concepto original de dimensión métrica. En esta tesis estudiamos una de estas variantes, a saber, la dimensión métrica local. En particular, nos centramos en el problema de calcular la dimensión métrica local de grafos. Primero presentamos el estado del arte de la dimensión métrica local y presentamos algunos resultados originales en los que caracterizamos todos los grafos que alcanzan algunas de las cotas conocidas. En segundo lugar, obtenemos fórmulas cerradas y cotas tensas para la dimensión métrica local de varias familias de grafos, entre los que destacamos los grafos producto fuerte, grafos corona y grafos producto lexicográfico. Finalmente, introducimos el estudio de la dimensión métrica local simultánea y damos algunos resultados generales en esta nueva línea de investigación., The metric dimension of a general metric space was introduced in 1953 but attracted little attention until, about twenty years later, it was applied to the distances between vertices of a graph. Since then it has been frequently used in graph theory, chemistry, biology, robotics and many other disciplines. Due to the variety of situations from which the problem of distinguishing the vertices of a graph can arise, several variants of the original concept of metric dimension have been appearing in specialized literature. In this thesis we study one of these variants, namely, the local metric dimension. Specifically, we focus on the problem of computing the local metric dimension of graphs. We first report on the state of the art on the local metric dimension and present some original results in which we characterize all graphs that reach some known bounds. Secondly, we obtain closed formulas and tight bounds on the local metric dimension of several families of graphs, including strong product graphs, corona product graphs, rooted product graphs and lexicographic product graphs. Finally, we introduce the study of simultaneous local metric dimension and we give some general results on this new research line.

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.

東京海洋大学修士学位論文 平成29年度(2017) 海運ロジスティクス 修士 第2671号, 指導教員: 渡邉豊, 全文公表年月日: 2017-10-25

La coordinació és un factor important que afecta directament el resultat de les operacions de resposta en les xarxes de gestió d’emergències. Marcs de treball i protocols de gestió de catàstrofes estableixen una base per a la col·laboració de l’organització i coordinació en el cas d’una crisi (provocada per l’home o per causes naturals). Existeixen marcs de treball de gestió d’emergències que es basen en conceptes agafats de les pràctiques militars (i.e. comandament i control) i de les operacions organitzatives convencionals. Degut a la naturalesa complexa d’un desastre o d’una emergència, l’enfocament actual està fallant per a enfrontar-se a aquests alts nivells d’incertesa i a la intensa aparició de canvis en el transcurs d’un desastre. En comptes de romandre bloquejats amb plans de resposta rígids, les organitzacions i els individus es gestionen per a enfrontar-se a la complexitat dels desastres mitjançant la formació d’estructures en xarxa. Aquestes xarxes es formen en resposta a les necessitats que es desenvolupen per a enfrontar-se a un incident de desastre. La comprensió de les característiques d’aquestes noves xarxes en les operacions de resposta a desastres és fonamental per a tot el procés de l’elaboració de marcs de treball de resposta a desastres, els quals podrien ajudar en la prevenció de pèrdues de vides humanes i béns. En aquesta investigació, s’examinen exemples d’operacions de resposta a desastres per a estudiar els patrons de la xarxa de coordinació entre les organitzacions que participen en aquestes operacions de resposta. Per a assolir els objectius de la investigació, es desenvolupa una nova metodologia per a examinar la coordinació dinàmica en xarxes de resposta a desastres. El resultat de l’anàlisi ofereix una perspectiva dinàmica que descriu l’evolució de la coordinació dels clústers en les estructures organitzades en xarxes. La comprensió de las característiques dels clústers de coordinació ajuda a identificar les tasques crítiques i les unitats més enllà dels recursos requerits durant les operacions de resposta a desastres. El treball de recerca contribueix als continus canvis en els conceptes de la gestió de desastres i crisis i canviar vers una xarxa i vers sistemes de resposta basats en funcions., La coordinación es un factor importante que afecta directamente el resultado de las operaciones de respuesta en las redes de gestión de catástrofes. Marcos de trabajo y protocolos de emergencias establecen una base para la colaboración de la organización y coordinación en caso de una crisis (provocada por el hombre o por causas naturales). Existen marcos de trabajo de gestión de emergencias que se basan en conceptos tomados de las prácticas militares (i.e. comando y control) y de las operaciones organizativas convencionales. Debido a la naturaleza compleja de un desastre o emergencia, el enfoque actual está fallando para hacer frente a estos altos niveles de incertidumbre y a la intensa aparición de cambios en el transcurso de un desastre. En lugar de estar bloqueados con planes de respuesta rígidos, las organizaciones y los individuos se gestionan para hacer frente a la complejidad de los desastres mediante la formación de estructuras organizadas en redes. Estas redes se forman en respuesta a las necesidades que se desarrollan para hacer frente a un incidente de desastre. La comprensión de las características de estas nuevas redes en las operaciones de respuesta a desastres es fundamental para todo el proceso de la elaboración de marcos de trabajo de respuesta a desastres, los cuáles podrían ayudar en la prevención de pérdidas de vidas humanas y bienes. En esta investigación, se examinan ejemplos de las operaciones de respuesta a desastres para estudiar los patrones de la red de coordinación entre las organizaciones que participan en estas operaciones de respuesta. Para lograr los objetivos de la investigación, se desarrolla una nueva metodología para examinar la coordinación dinámica en redes de respuesta a desastres. El resultado del análisis ofrece una perspectiva dinámica que describe la evolución de la coordinación de los clústeres en las estructuras de las redes. La comprensión de las características de los clústeres de coordinación ayuda a identificar las tareas críticas y las unidades más allá de los recursos requeridos durante las operaciones de respuesta a desastres. El trabajo de investigación contribuye a los continuos cambios en los conceptos de la gestión de desastres y crisis y cambiar hacia una red y hacia sistemas de respuesta basados en funciones., Coordination is an important factor that affects directly the outcome of response operations in disaster management networks. Disaster management frameworks and protocols establish a foundation for organizational collaboration and coordination in the event of a crisis (natural or man-made). Existing disaster management frameworks are based on concepts borrowed from military practices (i.e. command and control) and conventional organizational operations. Due to the complex nature of a disaster or emergency, the existing approach is failing to cope with such high levels of uncertainty and intense occurrence of changes during the course of a disaster. Instead of being locked-in rigid response plans, organizations and individuals managed to cope with disasters’ complexities by forming network-governed structures. Those networks are formed in response to the unfolding needs of coping with a disaster incident. Understanding the characteristics of those emerging networks in disaster response operations is critical to the whole process of developing proper disaster response frameworks that would help in preventing losses in human lives and assets. In this research, we examine examples of disaster response operations to study the patterns of networked-coordination between the organizations engaged in those response operations. To achieve the research goals, we develop a new methodology for examining the coordination dynamic in disaster response networks. The analysis outcome provides a dynamic perspective that describes the evolution of coordination-clusters in network-governed structures. Understanding characteristics of coordination-clusters helps to identify critical tasks and units beyond the resources required during disaster response operations. The research work contributes to the continuous changes in concepts of disaster and crisis management and the shift towards a network and function-based response systems.

En aquesta tesi s'estudia la dimensió (k,t)-mètrica dels grafs. Particularment s'emfatitza en la dimensió k-mètrica i la dimensió de k-adjacència. Al primer capítol es dedica als conceptes bàsics i les notacions emprades a la tesi. Al segon capítol es determina el més gran enter k, de manera que hi ha una base (k,t) -mètrica d'un graf. Es mostra, a més, que la complexitat temporal de calcular aquest valor de k és cúbica, pel que fa a l'ordre del graf. Al tercer capítol, s'obtenen fórmules tancades i cotes per a la dimensió (k,t) -mètrica d'alguns grafs. Així mateix, es delimita el valor de la dimensió k-mètrica en funció de paràmetres relacionats amb la distància, i es descriuen les classes de grafs en què s’aconsegueixen aquestes cotes com, per exemple, en els arbres. En particular, per a aquests últims, s'estableix una fórmula per calcular la dimensió k-mètrica de qualsevol arbre. També s'estudia la dimensió de k-adjacència de diversos grafs perquè s'ha trobat una forta relació entre la dimensió k-mètrica de productes de grafs i la dimensió de k-adjacència d'un dels seus factors. Aquesta relació permet obtenir nombrosos resultats per al producte lexicogràfic i per al producte corona. A l'últim capítol, es demostra que trobar el més gran enter k, de manera que hi hagi una base (k,t) –mètrica d’un graf, es pot resoldre en temps cúbic pel que fa a l'ordre del graf. Es prova, a més, que el problema de calcular la dimensió és NP-complex a través d'una transformació polinòmica al 3-SAT. Malgrat tot, per la fórmula obtinguda per a la dimensió k-mètrica d’arbres (que es demostra al capítol 3), es proposa un algoritme que es pot resoldre en temps lineal per determinar la dimensió k-mètrica i una base k-mètrica de qualsevol arbre., En esta tesis se estudia la dimensión (k, t)-métrica de los grafos. Particularmente se enfatiza en la dimensión k-métrica y la dimensión de k-adyacencia. El primer capítulo se dedica a los conceptos básicos y las notaciones empleadas en la tesis. En el segundo capítulo se determina el mayor entero k, de modo que existe una base (k, t)-métrica de un grafo. Se muestra, además, que la complejidad temporal de calcular este valor de k es cúbica, con respecto al orden del grafo. En el tercer capítulo, se obtiene fórmulas cerradas y cotas para la dimensión (k, t)-métrica de algunos grafos. Asimismo, se acota el valor de la dimensión k-métrica en función de parámetros relacionados con la distancia, y se describe las clases de grafos donde estas cotas son alcanzadas, como por ejemplo en los árboles. En particular, para estos últimos, se establece una fórmula para calcular la dimensión k-métrica de cualquier árbol. También se estudia la dimensión de k-adyacencia de varios grafos debido a que se ha encontrado una fuerte relación entre la dimensión k-métrica de productos de grafos y la dimensión de k-adyacencia de uno de sus factores. Esta relación permite obtener numerosos resultados para el producto lexicográfico y el producto corona. En el último capítulo, se demuestra que encontrar el mayor entero k, de modo que exista una base (k, t)-métrica de un grafo, puede resolverse en tiempo cúbico con respecto al orden del grafo. Se prueba además que el problema de calcular la dimensión es NP-complejo a través de una transformación polinómica al 3-SAT. No obstante, por la fórmula obtenida para la dimensión k-métrica de árboles (demostrada en el capítulo 3), se propone un algoritmo que puede ser resuelto en tiempo lineal para determinar la dimensión k-métrica y una base k-métrica de cualquier árbol., In this thesis we study the (k, t)-metric dimension of graphs. The central results of the thesis are focused on the k-metric dimension and the k-adjacency dimension. The first chapter is devoted to the basic concepts and the notations used in the thesis. In the second chapter we find the largest integer k such that there exists a (k,t)-metric basis of a graph. We also show that the time complexity of computing this value k is cubic with respect to the order of the graph. In the third chapter, we obtain closed formulae and bounds for the (k,t)-metric dimension of some graphs. We also bound the value for the k-metric dimension of graphs in terms of parameters related to the distance and we describe some classes of graphs where these bounds are achieved, such as trees. In particular, we give a formula for computing the k-metric dimension of any tree. We also study the k-adjacency dimension of several graphs due to we have found a strong relationship between the k-metric dimension of product graphs and the k-adjacency dimension of one of its factors. This relationship allows us to obtain several results for the lexicographic product and corona product. In the last chapter, we prove that finding the value k such that there exists a $(k,t)$-metric basis of a graph can be solved in cubic time with respect to the order of the graph. We also show that the problem of computing the k-metric dimension of a graph is NP-Hard through a polynomial transformation from the 3-SAT problem. However, by using a obtained formula for the k-metric dimension of trees (proven in Chapter 3), we propose algorithms, which can be solved in linear time, for determining the k-metric dimension and a k-metric basis of any tree.

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.

Aquesta tesi consta principalment de dues parts. A la primera part, es generalitza a variable contínua un famós teorema en l'àmbit tèoric de l'optimització: El No-Free-Lunch Theorem, el qual diu que tots els algorismes són igual de bons quan es fa la mitjana de la seva eficiència sobre totes les possibles funcions a optimitzar. Aquesta generalització utilitza de manera molt natural la teoria de processos estocàstics, i arriba a la conclusió que no hi ha teoremes de No-Free-Lunch en el continu, excepte en determinats casos extrems de poca importància pràctica. A la segona part, s'ha considerat el Pont Brownià com un model probabilístic per a problemes d'optimització tipus “caixa negra”, en què no es té cap forma analítica de la funció, sinó que aquesta només pot ser avaluada en un nombre determinat de punts, i a més a més, considerant que cadascuna d'aquestes avaluacions és molt costosa de fer, i per tant només se'n faran unes quantes. El model probabilístic considera que la funció a optimitzar és una trajectòria d'un procés amb una determinada llei. Des del punt de vista de la complexitat computacional, això correspon a estudiar el “average performance” d'algorismes, en front de l'habitual “worst-case performance”. Però això es fa sempre des del punt de vista asimptòtic, quan el nombre d'avaluacions tendeix a infinit, i un dels objectius d'aquesta tesi se centra en la millora de l'estimació del valor òptim quan només es pot avaluar la funció en pocs punts. En aquest sentit, i en un estudi que mancava a la literatura, es comparen i analitzen diverses heurístiques adaptatives i no-adaptatives, arribant a la conclusió de quina és més eficient. D'altra banda, el treball amb el Pont Brownià, ha donat lloc a dues fórmules no explicitades anteriorment, la densitat de l'argument del mínim del Pont Brownià i la densitat conjunta del Pont Brownià i del seu mínim. A més, en aquesta tesi es realitzen molts experiments de simulació per calcular quantitats que són molt difícils, costoses o impossibles d'obtenir analíticament. Seguint una filosofia de practicitat, s'han programat rutines, com per exemple l'histograma de l'argument del mínim d'un Pont Brownià condicionat a n punts, que obtenen una estimació probabilística raonable de l'error comès., This Ph.D. thesis consists mainly of two parts. In the first part, a famous theorem in the field of theoretical optimisation is generalised to continuous variable: The No-Free-Lunch Theorem, which states that all algorithms are equally good when one averages its efficiency over all possible functions to optimise. This generalisation uses in a very natural way the theory of stochastic processes, and concludes that there are no No-Free-Lunch theorems in the continuum, except for certain extreme cases of little practical significance. In the second part, the Brownian Bridge has been considered as a probabilistic model for optimisation problems of the "black box" type, in which we do not have an analytical form of the function, but that the latter can only be evaluated in a certain number of points. Moreover, we consider that each of these evaluations are very expensive, so that only a few of them will be made. The probabilistic model considers that the function to optimise is a path of a stochastic process with a given probability law. From the point of view of computational complexity, this study corresponds to the "average performance" of algorithms, versus the usual "worst-case performance". But this has always been done before from the asymptotic standpoint, when the number of evaluations tends to infinity, and one of the goals of this thesis focuses on improving the estimation of the optimal value when the function can only be evaluated in a few points. In this regard, in a study that was missing in the literature, we compare and analyze several heuristics, adaptive and non-adaptive, concluding which one is most efficient. Moreover, in working with Brownian bridge, we found two formulae not given explicitly before, namely the density of the argument of the Brownian bridge (in the general setting) and the joint density of a bridge and its minimum. In addition, in this thesis many simulation experiments have been performed to calculate quantiites that are difficult, expensive or impossible to obtain analytically. Following a philosophy of practicality, some routines have been programmed, such as the histogram of the argument of the minimum of the Brownian Bridge conditioned to n points, that get a reasonable probabilistic estimate of the error incurred.

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.

For a given cost matrix and a given communication requirement matrix, the OCSTP is defined as finding a spanning tree that minimizes the operational cost of the network. OCST can be used to design of more efficient communication and transportation networks, but appear also, as a subproblem, in hub location and sequence alignment problems. This thesis studies several mixed integer linear optimization formulations of the OCSTP and proposes a new one. Then, an efficient Branch & Cut algorithm derived from the Benders decomposition of one of such formulations is used to successfully solve medium-sized instances of the OCSTP. Additionally, two new combinatorial lower bounds, two new heuristic algorithms and a new family of spanning tree neighborhoods based on the Dandelion Code are presented and tested.

En aquesta tesi vam introduir la noció de resolubilitat simultània per a famílies de grafs definides sobre un conjunt de vèrtexs en comú. Els principals resultats de la tesi s'han abordat als generadors i bases mètrics simultanis, així com la dimensió mètrica simultània d'aquestes famílies. Addicionalment, hem tractat dues formes de resolubilitat simultània relacionades. Primerament, vam abordar la dimensió d'adjacència simultània, la qual va demostrar la seva utilitat per caracteritzar la dimensió mètrica simultània de famílies compostes per grafs-producte lexicogràfics i corona. En segon lloc, vam estudiar les propietats principals de la dimensió mètrica forta simultània. En tots els casos, el focus va estar a determinar les cotes generals per a aquests paràmetres, les seves relacions amb els paràmetres de resolubilitat estàndard dels grafs individuals i, quan va ser possible, donar valors exactes o cotes ajustades per certes famílies específiques. Des del punt de vista computacional, el problema encara no es pot considerar resolt per al cas general, ja que vam aconseguir verificar que el requisit de simultaneïtat augmenta la complexitat computacional dels càlculs relacionats amb aquests paràmetres, els quals ja s'havia demostrat que eren NP -difícils. En particular, vam caracteritzar famílies compostes per grafs pels quals alguns paràmetres estàndards de resolubilitat es poden calcular eficientment, mentre que calcular els paràmetres simultanis associats és NP-difícil. Per pal•liar aquest problema, vam proposar diversos mètodes per estimar aproximadament aquests paràmetres i vam realitzar una avaluació experimental per estudiar el seu comportament en col•leccions de famílies de grafs generades aleatòriament., En esta tesis hemos introducido la noción de resolubilidad simultánea para familias de grafos definidas sobre un conjunto de vértices en común. Los principales resultados de la tesis han abordado los generadores y bases métricos simultáneos, así como la dimensión métrica simultánea de dichas familias. Adicionalmente, hemos tratado dos formas de resolubilidad simultánea relacionadas. Primeramente, abordamos la dimensión de adyacencia simultánea, la cual demostró su utilidad para caracterizar la dimensión métrica simultánea de familias compuestas por grafos-producto lexicográficos y corona. En segundo lugar, estudiamos las propiedades principales de la dimensión métrica fuerte simultánea. En todos los casos, el foco estuvo en determinar las cotas generales para estos parámetros, sus relaciones con los parámetros de resolubilidad estándar de los grafos individuales y, cuando fue posible, dar valores exactos o cotas ajustadas para ciertas familias específicas. Desde el punto de vista computacional, los problemas aún no se pueden considerar resueltos para el caso general, ya que logramos verificar que el requisito de simultaneidad aumenta la complejidad computacional de los cálculos relacionados con estos parámetros, los cuales ya se había demostrado que eran NP-difíciles. En particular, caracterizamos familias compuestas por grafos para los cuales algunos parámetros estándares de resolubilidad se pueden calcular eficientemente, mientras que calcular los parámetros simultáneos asociados es NP-difícil. Para paliar este problema, propusimos varios métodos para estimar aproximadamente estos parámetros y realizamos una evaluación experimental para estudiar su comportamiento en colecciones de familias de grafos generadas aleatoriamente., In this thesis we have introduced the notion of simultaneous resolvability for graph families defined on a common vertex set. The main results of the thesis have dealt with simultaneous metric generators and bases, as well as the simultaneous metric dimension of such families. Additionally, we have covered two related forms of simultaneous resolvability. Firstly, we treated the simultaneous adjacency dimension, which proved useful for characterizing the simultaneous metric dimension of families composed by lexicographic and corona product graphs. Secondly, we studied the main properties of the simultaneous strong metric dimension. In all cases, our focus was on determining the general bounds for these parameters, their relations to the standard resolvability parameters of the individual graphs and, when possible, giving exact values or sharp bounds for a number of specific families. Computationally, these problems are far from solved for the general case, as we were able to verify that the requirement of simultaneity adds on the complexity of the calculations involving these resolvability parameters, which had already been proven to be NP-hard for their standard counterparts. In particular, we characterized families composed by graphs for which some standard resolvability parameters can be efficiently computed, while computing the associated simultaneous parameters is NP-hard. To alleviate this problem, we proposed several methods for approximately estimating these parameters and conducted an experimental evaluation to study their behaviour on randomly generated collections of graph families.

En las últimas décadas, la globalización ha impulsado la adaptación del sector del Transporte y la Logística a las nuevas demandas sociales. Al mismo tiempo, el transporte ha sido la columna vertebral de la globalización. Esta necesidad social crea consumidores ambiciosos que necesitan sus productos de forma rápida y a un precio asequible muchas veces sin ser conscientes de su origen, el transporte o los aspectos medioambientales, entre otros factores. Sin embargo, para satisfacer las demandas del cliente, es necesario encontrar el modo de transporte más barato, que significa la mejora de la logística del transporte de estos productos. Por lo tanto, estas demandas requieren un servicio cada vez más flexible para satisfacer las necesidades del cliente, y, además, las empresas quieren un transporte eficiente y productivo. Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) proporcionan el marco teórico para tratar este tipo de problemas logísticos relacionados con la distribución física de mercancías desde un almacén central hasta los clientes. Son dos de los problemas más desafiantes e investigados debido a su complejidad y aplicabilidad. El objetivo principal de esta tesis doctoral es la introducción de metodologías híbridas que integran varias técnicas para resolver de manera eficiente rich VRPs con restricciones realistas. Esta tesis comienza con problemas teóricos y evoluciona hacia escenarios más realistas abordando un total de seis problemas combinatorios relacionados con el transporte por carretera. Una metaheurística llamada Tailored Lagrangian Metaheuristic (TLM) se ha desarrollado para abordar el TSP. Está basa en la relajación de Lagrange que se utiliza para explotar la estructura del problema que reduce considerablemente su complejidad moviendo restricciones difíciles de satisfacer a la función objetivo, asociando una penalización en caso de que no se cumplen. La metaheurística desarrollada para el TSP se ha integrado en dos metodologías híbridas combinadas con Constraint Programming para hacer frente a problemas más complejos. En primer lugar, el Capacitated Vehicle Routing Problem (CVRP), cuyos los vehículos tienen limitaciones de capacidad de carga de las mercancías que deben ser entregadas, es abordado. En segundo lugar, se ha abordado un problema real, Home Health Care (HHC), del servicio de Salud en el municipio de Ferrara, Italia. Este consiste en la asignación de los tratamientos de los pacientes a las enfermeras que viajan a las casas de los pacientes. Investigaciones teóricas suelen asumir la simetría de los costes basados en la distancia de viajar de un lugar a otro y la existencia de una flota homogénea de vehículos con una misma capacidad. Esta tesis estudia diferentes variantes centradas en el impacto que causa la asimetría de los costes y la heterogeneidad de la flota. Para estos estudios, se abordan la versión con costes asimétricos del TSP y del CVRP -el Asymmetric Traveling Salesman Problem (ATSP) y el Asymmetric Capacitated Vehicle Routing Problem (ACVRP)- y la versión con flota heterogénea del ACVRP –el Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP)., Over the last decades, globalization has driven the adaptation of the Transport and Logistics sector to new social demands. At the same time, transport has been the backbone of globalization. This social need creates ambitious consumers who need their products quickly and an affordable price often unaware of their origin, transport mode or environmental aspects, among other factors. Nevertheless, to satisfy customer demands, it is needed to find the cheapest transport mode, which in turn means the improvement of transport logistics of the products. Therefore, these demands require an increasingly flexible service to meet customer requirements, and in addition companies want an efficient and productive transport. The so called Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) provide the theoretical framework for approaching this class of logistic problems associated with the physical distribution of goods from a central depot to customers. They are two of the most challenging and researched problems because of their complexity and applicability. The main goal of this PhD thesis is to introduce hybrid methodologies that integrate several techniques to efficiently solve rich VRPs with realistic constraints. It starts with theoretical problems and evolves into more realistic scenarios tackling six combinatorial problems related to road transport. A metaheuristic named Tailored Lagrangian Metaheuristic (TLM) has been developed to tackle the TSP. It is based on the Lagrangian Relaxation which is used to exploit the structure of the problem reducing considerably its complexity by moving hard-to-satisfy constraints into the objective function, associating a penalty in case the constraints are not satisfied. The developed metaheuristic for the TSP has been integrated into two hybrid methodologies combined with Constraint Programming to tackle more complex problems. First of all, it is addressed the Capacitated Vehicle Routing Problem (CVRP), whose vehicles have limited loading capacity of the goods that must be delivered. Secondly, it has been addressed a real problem of the Home Health Care (HHC) service in the municipality of Ferrara, Italy. It consists on assigning patients' services to nurses which travel to each patient’s home. Theoretical researches typically assume the symmetry of the distance-based costs associated with traveling from one place to another as well as the existence of a homogeneous fleet of vehicles with limited capacity. This thesis studies different variants focusing on the impact that causes the asymmetry of the costs and the heterogeneity of the fleet. For these purpose, the Asymmetric Traveling Salesman Problem (ATSP), the Asymmetric Capacitated Vehicle Routing Problem (ACVRP) and the Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP) are addressed.

El fet que cada vegada disposem de més dades socials de sistemes socio-tecnològics---sistemes que registren la nostra activitat diària, tals com a registres de targeta de crèdit, registres de trucades telefòniques, correu electrònic, etc.---i les xarxes socials on-line---com facebook, twitter, instagram, etc.---, ha fet possible estudiar el comportament humà des de diferents perspectives. Descobrir els patrons darrere d'aquestes dades no només aportarà un millor coneixement de la societat, sinó que també beneficiaria a la societat en diferents aspectes, com l'adaptació de tecnologia a les necessitats socials o el disseny de millors polítiques per evitar la propagació d'epidèmies. L'objectiu d'aquesta tesi és precisament descobrir patrons estructurals i temporals en els sistemes socials i desenvolupar models predictius sobre la seva base. En particular, analitzem l'evolució a llarg termini en una xarxa de correu electrònic amb més d'1.000 persones al llarg de quatre anys consecutius. Veiem que, encara que l'evolució de la comunicació entre usuaris és altament impredictible, l'evolució macro de les xarxes de comunicació social segueix lleis estadístiques ben definides, caracteritzades pel decaïment exponencial de les variacions logarítmicas del pes de les comunicacions entre usuaris i del pes dels individus a la xarxa. Al mateix temps, trobem que els individus tenen una forma característica de comunicar-se, i aquesta no canvia en anys. Quant a la predictabilidad, desenvolupem dos models basats en xarxes: un model de recomanació (que prediu votacions d'usuaris sobre objectes) i un model d'inferència temporal (que prediu successos en el temps). El nostre model de recomanació és escalable i considerablement més precís en les seves prediccions que els algorismes actuals per bases de dades de milions de votacions. L'enfocament es basa en la suposició que hi ha grups de persones i d'articles (per exemple, pel·lícules, llibres, etc.) i que les preferències d'un individu sobre un element donat depenen del grups als que pertanyin. Però a més, permet que cada individu i cada article pertanyin simultàniament a diferents grups. Les comunitats superposades resultants i les prediccions sobre les votacions poden inferir-se amb un algorisme escalable de maximització d'expectatives basat en una aproximació variacional. En el mo, El hecho que cada vez dispongamos de más datos sociales de sistemas socio-tecnológicos---sistemas que registran nuestra actividad diaria, tales como registros de tarjeta de crédito, registros de llamadas telefónicas, correo electrónico, etc.---y las redes sociales on-line---como facebook, twitter, instagram, etc.---, ha hecho posible estudiar el comportamiento humano desde diferentes perspectivas. Descubrir los patrones detrás de estos datos no sólo aportará un mejor conocimiento de la sociedad, sino que también beneficiaría a la sociedad en diferentes aspectos, como la adaptación de la tecnología a las necesidades sociales o el diseño de mejores políticas para evitar la propagación de epidemias. El objetivo de esta tesis es precisamente descubrir patrones estructurales y temporales en los sistemas sociales y desarrollar modelos predictivos en base a ellos. En particular, analizamos la evolución a largo plazo en una red de correo electrónico con más de 1.000 personas a lo largo de cuatro años consecutivos. Vemos que, aunque la evolución de la comunicación entre usuarios es altamente impredecible, la evolución macro de las redes de comunicación social sigue leyes estadísticas bien definidas, caracterizadas por el decaimiento exponencial de las variaciones logarítmicas del peso de las comunicaciones entre usuarios y del peso de los individuos en la red. Así mismo, encontramos que los individuos presentan una forma caracteristica de comunicarse, y esta no cambia en años. En cuanto a la predictibilidad, desarrollamos dos modelos basados en redes: un modelo de recomendación (que predice votaciones de usuarios sobre objetos) y un modelo de inferencia temporal (que predice sucesos en el tiempo). Nuestro modelo de recomendación es escalable y considerablemente más preciso en sus predicciones que los algoritmos actuales para bases de datos de millones de votaciones. El enfoque se basa en la suposición de que hay grupos de personas y de artículos (por ejemplo, películas, libros, etc.) y que las preferencias de un individuo sobre un artículo dado dependen de los grupos a los que pertenezcan. Pero además, permitimos que cada individuo y cada artículo pertenecan simultáneamente a diferentes grupos. Las comunidades superpuestas resultantes y las predicciones sobre las votaciones pueden inferirse con un algoritmo de maximiz, The increasing availability of social data sources from socio-technological systems ---systems that record our daily activity such as credit card records, call-phone records, email, etc.--- and on-line social networks ---such as facebook, twitter, instagram, etc.---, has made it possible to study human behavior from different perspectives. Uncovering the patterns behind this data would not only give us a better knowledge about our society but could also benefit our society in a number of ways such as adapting technology to social needs or design better policies to avoid spread of epidemics. The aim of this thesis is precisely to uncover both structural and temporal patterns in social systems and to develop predictive models based on them. In particular, we analyze the long-term evolution in an email network with over 1,000 individuals throughout four consecutive years. We find that, although the evolution of individual ties is highly unpredictable, the macro-evolution of social communication networks follows well-defined statistical laws, characterized by exponentially decaying log-variations of the weight of social ties and of individuals' social strength. At the same time, we find that individuals have social signatures that are remarkably stable over the scale of several years. Regarding predictability, we develop two network-based models: a recommender model, and a temporal inference model. Our recommender model makes scalable predictions and is considerably more accurate than current algorithms for large datasets. The approach is based on the assumption that there are groups of individuals and of items (e.g. movies, books, etc.), and that the preferences of an individual for an given item depend on their group memberships. Importantly, we allow each individual and each item to belong simultaneously to different groups. The resulting overlapping communities and the predicted preferences can be inferred with a scalable expectation-maximization algorithm based on a variational approximation. In the temporal inference model users can belong simultaneously to different groups, but also the time intervals belong to overlapping communities. The results suggest that the algorithm is able to distinguish real events of non-events almost perfectly.

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.

L'estudi de xarxes ha contribuït a la comprensió de sistemes complexos en una àmplia gamma de camps com la biologia molecular i cel·lular, l'anatomia, la neurociència, l'ecologia, l'economia i la sociologia. No obstant, el coneixement disponible sobre molts sistemes reals encara és limitat, per aquesta raó el poder predictiu de la ciència en xarxes s'ha de millorar per disminuir la bretxa entre coneixement i informació. Per abordar aquest tema fem servir la família de 'Stochastic Block Models' (SBM), una família de models generatius que està guanyant gran interès recentment a causa de la seva adaptabilitat a qualsevol tipus de xarxa. L'objectiu d'aquesta tesi és el desenvolupament de noves metodologies d'inferència basades en SBM que perfeccionaran la nostra comprensió de les xarxes complexes. En primer lloc, investiguem en quina mesura fer un mostreg sobre models pot millorar significativament la capacitat de predicció que considerar un únic conjunt òptim de paràmetres. Un cop sabem quin model és capaç de descriure millor una xarxa determinada, apliquem aquest mètode en un cas particular d'una xarxa real: una xarxa basada en les interaccions/sutures entre els ossos del crani en nounats. Concretament, descobrim que les sutures tancades a causa d'una malaltia patològica en el nounat humà son menys probables, des d'un punt de vista morfològic, que les sutures tancades sota un desenvolupament normal. Recents investigacions en xarxes multicapa conclou que el comportament de les xarxes d'una sola capa són diferents de les de múltiples capes; d'altra banda, les xarxes del món real se'ns presenten com xarxes d'una sola capa., El estudio de las redes del mundo real han empujado hacia la comprensión de sistemas complejos en una amplia gama de campos como la biología molecular y celular, la anatomía, la neurociencia, la ecología, la economía y la sociología . Sin embargo, el conocimiento disponible de muchos sistemas reales aún es limitado, por esta razón el poder predictivo de la ciencia en redes se debe mejorar para disminuir la brecha entre conocimiento y información. Para abordar este tema usamos la familia de 'Stochastic Block Modelos' (SBM), una familia de modelos generativos que está ganando gran interés recientemente debido a su adaptabilidad a cualquier tipo de red. El objetivo de esta tesis es el desarrollo de nuevas metodologías de inferencia basadas en SBM que perfeccionarán nuestra comprensión de las redes complejas. En primer lugar, investigamos en qué medida hacer un muestreo sobre modelos puede mejorar significativamente la capacidad de predicción a considerar un único conjunto óptimo de parámetros. Seguidamente, aplicamos el método mas predictivo en una red real particular: una red basada en las interacciones/suturas entre los huesos del cráneo humano en recién nacidos. Concretamente, descubrimos que las suturas cerradas a causa de una enfermedad patológica en recién nacidos son menos probables, desde un punto de vista morfológico, que las suturas cerradas bajo un desarrollo normal. Concretamente, descubrimos que las suturas cerradas a causa de una enfermedad patológica en recién nacidos son menos probables, desde un punto de vista morfológico, que las suturas cerradas bajo un desarrollo normal. Recientes investigaciones en las redes multicapa concluye que el comportamiento de las redes en una sola capa son diferentes a las de múltiples capas; por otra parte, las redes del mundo real se nos presentan como redes con una sola capa. La parte final de la tesis está dedicada a diseñar un nuevo enfoque en el que dos SBM separados describen simultáneamente una red dada que consta de una sola capa, observamos que esta metodología predice mejor que la metodología de un SBM solo., The study of real-world networks have pushed towards to the understanding of complex systems in a wide range of fields as molecular and cell biology, anatomy, neuroscience, ecology, economics and sociology. However, the available knowledge from most systems is still limited, hence network science predictive power should be enhanced to diminish the gap between knowledge and information. To address this topic we handle with the family of Stochastic Block Models (SBMs), a family of generative models that are gaining high interest recently due to its adaptability to any kind of network structure. The goal of this thesis is to develop novel SBM based inference approaches that will improve our understanding of complex networks. First, we investigate to what extent sampling over models significatively improves the predictive power than considering an optimal set of parameters alone. Once we know which model is capable to describe better a given network, we apply such method in a particular real world network case: a network based on the interactions/sutures between bones in newborn skulls. Notably, we discovered that sutures fused due to a pathological disease in human newborn were less likely, from a morphological point of view, that those sutures that fused under a normal development. Recent research on multilayer networks has concluded that the behavior of single-layered networks are different from those of multilayer ones; notwhithstanding, real world networks are presented to us as single-layered networks. The last part of the thesis is devoted to design a novel approach where two separate SBMs simultaneously describe a given single-layered network. We importantly find that it predicts better missing/spurious links that the single SBM approach.

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

The main goal of this thesis is to develop lossless compression schemes for analog and binary sources. All the considered compression schemes have as common feature that the encoder can be represented by a graph, so they can be studied employing tools from modern coding theory. In particular, this thesis is focused on two compression problems: the group testing and the noiseless compressed sensing problems. Although both problems may seem unrelated, in the thesis they are shown to be very close. Furthermore, group testing has the same mathematical formulation as non-linear binary source compression schemes that use the OR operator. In this thesis, the similarities between these problems are exploited. The group testing problem is aimed at identifying the defective subjects of a population with as few tests as possible. Group testing schemes can be divided into two groups: adaptive and non-adaptive group testing schemes. The former schemes generate tests sequentially and exploit the partial decoding results to attempt to reduce the overall number of tests required to label all members of the population, whereas non-adaptive schemes perform all the test in parallel and attempt to label as many subjects as possible. Our contributions to the group testing problem are both theoretical and practical. We propose a novel adaptive scheme aimed to efficiently perform the testing process. Furthermore, we develop tools to predict the performance of both adaptive and non-adaptive schemes when the number of subjects to be tested is large. These tools allow to characterize the performance of adaptive and non-adaptive group testing schemes without simulating them. The goal of the noiseless compressed sensing problem is to retrieve a signal from its lineal projection version in a lower-dimensional space. This can be done only whenever the amount of null components of the original signal is large enough. Compressed sensing deals with the design of sampling schemes and reconstruction algorithms that manage to reconstruct the original signal vector with as few samples as possible. In this thesis we pose the compressed sensing problem within a probabilistic framework, as opposed to the classical compression sensing formulation. Recent results in the state of the art show that this approach is more efficient than the classical one. Our contributions to noiseless compressed sensing are both theoretical and practical. We deduce a necessary and sufficient matrix design condition to guarantee that the reconstruction is lossless. Regarding the design of practical schemes, we propose two novel reconstruction algorithms based on message passing over the sparse representation of the matrix, one of them with very low computational complexity., El objetivo principal de la tesis es el desarrollo de esquemas de compresión sin pérdidas para fuentes analógicas y binarias. Los esquemas analizados tienen en común la representación del compresor mediante un grafo; esto ha permitido emplear en su estudio las herramientas de codificación modernas. Más concretamente la tesis estudia dos problemas de compresión en particular: el diseño de experimentos de testeo comprimido de poblaciones (de sangre, de presencia de elementos contaminantes, secuenciado de ADN, etcétera) y el muestreo comprimido de señales reales en ausencia de ruido. A pesar de que a primera vista parezcan problemas totalmente diferentes, en la tesis mostramos que están muy relacionados. Adicionalmente, el problema de testeo comprimido de poblaciones tiene una formulación matemática idéntica a los códigos de compresión binarios no lineales basados en puertas OR. En la tesis se explotan las similitudes entre todos estos problemas. Existen dos aproximaciones al testeo de poblaciones: el testeo adaptativo y el no adaptativo. El primero realiza los test de forma secuencial y explota los resultados parciales de estos para intentar reducir el número total de test necesarios, mientras que el segundo hace todos los test en bloque e intenta extraer el máximo de datos posibles de los test. Nuestras contribuciones al problema de testeo comprimido han sido tanto teóricas como prácticas. Hemos propuesto un nuevo esquema adaptativo para realizar eficientemente el proceso de testeo. Además hemos desarrollado herramientas que permiten predecir el comportamiento tanto de los esquemas adaptativos como de los esquemas no adaptativos cuando el número de sujetos a testear es elevado. Estas herramientas permiten anticipar las prestaciones de los esquemas de testeo sin necesidad de simularlos. El objetivo del muestreo comprimido es recuperar una señal a partir de su proyección lineal en un espacio de menor dimensión. Esto sólo es posible si se asume que la señal original tiene muchas componentes que son cero. El problema versa sobre el diseño de matrices y algoritmos de reconstrucción que permitan implementar esquemas de muestreo y reconstrucción con un número mínimo de muestras. A diferencia de la formulación clásica de muestreo comprimido, en esta tesis se ha empleado un modelado probabilístico de la señal. Referencias recientes en la literatura demuestran que este enfoque permite conseguir esquemas de compresión y descompresión más eficientes. Nuestras contribuciones en el campo de muestreo comprimido de fuentes analógicas dispersas han sido también teóricas y prácticas. Por un lado, la deducción de la condición necesaria y suficiente que debe garantizar la matriz de muestreo para garantizar que se puede reconstruir unívocamente la secuencia de fuente. Por otro lado, hemos propuesto dos algoritmos, uno de ellos de baja complejidad computacional, que permiten reconstruir la señal original basados en paso de mensajes entre los nodos de la representación gráfica de la matriz de proyección.

環境政策のガバナンスは、グローバル・ナショナル・ローカルの各ガバナンス関係の中で変化しつつある。琵琶湖レジャー利用適正化条例の2011年改正はそうしたガバナンス変化を端的に示したものといえる。この条例は琵琶湖環境の総合保全を目指してプレジャーボート使用の制限や外来魚リリース禁止を定め、従来にはない環境政策手法として様々な論争を呼んだ。この事例の分析に基づき、利害関係を持つアクターの変化、ネットワーク変化、そして政策の変更について検討する。, An environmental governance is changing in relation to the multi level governance among global, national and local governances. The amendment 2011 of Shiga Prefecture's Ordinance for the Regulation of Leisure Activity in Lake Biwa shows us the transformation of environmental governance clearly. The ordinace introduced a brand new measure of environmental protection and raised a number of discussions which were composed of various standpoints of view. In this article, we analyze the changes of stake holders, policy network and policy itself of the case., 論説(Article)

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

Vegeu dris1de1resum.pdf, Vegeu dris1de1abstract.pdf

Framing helps us to organize complex phenomena into coherent and comprehensive stories. In the policy process, framing often accounts for social conflicts because they differ among actors who are concerned with the same issue. In general, their frames are closely related to their own interests. This article, firstly, describes the relationship between interests and actions of each actor, and discusses the impacts of framing on the policy process. Secondly, it explores, through a case study of Minamata disease, how each actor makes her/his frame of the issue, why the frame is different among actors, and why the frame has an impact on the action in the policy process., 学術論文