Molts problemes de la vida quotidiana estan plens de decisions multi-classe. En l'àmbit del Reconeixement de Patrons, s'han proposat moltes tècniques d'aprenentatge que treballen sobre problemes de dos classes. No obstant, la extensió de classificadors binaris al cas multi-classe és una tasca complexa. En aquest sentit, Error-Correcting Output Codes (ECOC) han demostrat ser una eina potent per combinar qualsevol nombre de classificadors binaris i així modelar problemes multi-classe. No obstant, encara hi ha molts punts oberts sobre les capacitats del framework d'ECOC. En aquesta tesis, els dos estats principals d'un disseny ECOC són analitzats: la codificació i la decodificació. Es presenten diferents alternatives de dissenys dependents del domini del problema. Aquests dissenys fan ús del coneixement del domini del problema per minimitzar el nombre de classificadors que permeten obtenir un alt rendiment de classificació. Per altra banda, l'anàlisi de la codificació de dissenys d'ECOC es emprada per definir noves regles de decodificació que prenen total avantatja de la informació provinent del pas de la codificació. A més a més, com que classificacions exitoses requereixen rics conjunts de característiques, noves tècniques de detecció/extracció de característiques es presenten i s'avaluen en els nous dissenys d'ECOC. L'avaluació de la nova metodologia es fa sobre diferents bases de dades reals i sintètiques: UCI Machine Learning Repositori, símbols manuscrits, senyals de trànsit provinents de sistemes Mobile Mapping, imatges coronàries d'ultrasò, imatges de la Caltech Repositori i bases de dades de malats de Chagas. Els resultats que es mostren en aquesta tesis mostren que s'obtenen millores de rendiment rellevants tant a la codificació com a la decodificació dels dissenys d'ECOC quan les noves regles són aplicades. / Many real problems require multi-class decisions. In the Pattern Recognition field, many techniques have been proposed to deal with the binary problem. However, the extension of many 2-class classifiers to the multi-class case is a hard task. In this sense, Error-Correcting Output Codes (ECOC) demonstrated to be a powerful tool to combine any number of binary classifiers to model multi-class problems. But there are still many open issues about the capabilities of the ECOC framework. In this thesis, the two main stages of an ECOC design are analyzed: the coding and the decoding steps. We present different problem-dependent designs. These designs take advantage of the knowledge of the problem domain to minimize the number of classifiers, obtaining a high classification performance. On the other hand, we analyze the ECOC codification in order to define new decoding rules that take full benefit from the information provided at the coding step. Moreover, as a successful classification requires a rich feature set, new feature detection/extraction techniques are presented and evaluated on the new ECOC designs. The evaluation of the new methodology is performed on different real and synthetic data sets: UCI Machine Learning Repository, handwriting symbols, traffic signs from a Mobile Mapping System, Intravascular Ultrasound images, Caltech Repository data set or Chaga's disease data set. The results of this thesis show that significant performance improvements are obtained on both traditional coding and decoding ECOC designs when the new coding and decoding rules are taken into account.

La utilització d'agents mòbils en sistemes distribuïts comporta diverses avantatges. Les avantatges més freqüentment citades inclouen: reducció de la càrrega de la xarxa, decrement de la latència de les comunicacions, adaptació dinàmica, i millor suport per dispositius mòbils amb connexions intermitents, entre d'altres. No obstant, els beneficis oferts pels agents mòbils no han estat suficients per estimular el seu ús generalitzat. La raó principal per la qual els agents mòbils no han estat àmpliament adoptats encara, a pesar dels seus avantatges tecnològics, és que aquesta tecnologia comporta certs riscos de seguretat. S'han dut a terme molts avenços en la seguretat, la fiabilitat i la eficiència dels agents mòbils, però hi ha problemes de seguretat que encara romanen sense solució.El treball principal d'aquesta tesi gira en torn a la protecció dels agents mòbils contra els hostes maliciosos. Per tal de proporcionar una solució a alguns dels problemes de seguretat actuals, en primer lloc, s'ha presentat un protocol de protecció d'itineraris que suporta agents que viatgen lliurament. Els protocols de protecció d'itineraris proposats fins ara limiten la capacitat de l'agent de migrar a voluntat. Per tant, aquesta tesi presenta un protocol que permet als agents descobrir noves plataformes en temps d'execució, de tal manera que les aplicacions poden aprofitar tots els avantatges proporcionats per la tecnologia dels agents mòbils.En segon lloc, s'ha presentat un protocol que protegeix els agents mòbils d'atacs de re-execució externs. Els atacs de re-execució externs estan basats en tornar a enviar l'agent a la seva plataforma destí, per tal de forçar-lo a re-executar part del seu itinerari. El protocol proposat evita aquest tipus d'atacs sense limitar la capacitat de l'agent de visitar certes plataformes repetidament.Les solucions de seguretat presentades en aquesta tesi es basen en el fet que en molts, si no en la majoria, dels escenaris basats en agents mòbils podem trobar plataformes de confiança. Mitjançant la incorporació de plataformes de confiança en l'itinerari de l'agent, les solucions proposades proporcionen un compromís equilibrat entre seguretat i flexibilitat.Per tal de promoure el desenvolupament d'aplicacions basades en agents mòbils segurs, aquesta tesi també presenta un entorn de desenvolupament que facilita la implementació dels protocols de protecció d'agents proposats, així com altres solucions de seguretat. / Several advantages have been identified in using mobile agents in distributed systems. The most frequently cited advantages include: reduction of network load, decrease in communication latency, dynamic adaptation, and better support for mobile devices with intermittent connections, among others. However, the benefits offered by mobile agents have not been sufficient to stimulate their widespread deployment. The main reason why mobile agents have not been widely adopted yet, despite their technological benefits, is their inherent security risks. Many breakthroughs have been achieved in the security, reliability and efficiency of mobile agents, but there are security issues still remaining unsolved.The core work of this thesis revolves around the protection of mobile agents against malicious hosts. In order to provide a solution to some of the current security issues, first of all, an itinerary protection protocol is presented that supports free-roaming agents. Itinerary protection protocols proposed to date limit the agent's ability to migrate at will. Therefore, this thesis presents a protocol that allows agents to discover new platforms at runtime, so that applications can take full advantage of the benefits provided by mobile agent itineraries.Second, a protocol is presented that protects mobile agents against external replay attacks. External replay attacks are based on resending the agent to another platform, so as to force the reexecution of part of its itinerary. The proposed protocol counters this kind of attacks without limiting the agent's ability to visit certain platforms repeatedly.The security solutions presented in this thesis are based on the fact that trusted platforms can be found in many, if not most, mobile agent-based scenarios. By incorporating trusted platforms in the agent's itinerary, the proposed solutions provide a balanced trade-off between security and flexibility.In order to promote the development of secure mobile agent-based applications, this thesis also presents a development environment that facilitates the implementation of the proposed agent protection protocols as well as other security solutions.

Contribution to the study of alliances in graphs.ResumenEn este trabajo se estudian propiedades matemáticas de las alianzas (defensivas, ofensivas y duales) en grafos. Entre los temas tratados se destacan los siguientes:· Se estudian las alianzas en grafos producto. Específicamente, se obtienen relaciones entre las alianzas en grafos producto Cartesiano y las alianzas en los factores. · Se estudia las particiones de un grafo en alianzas. En particular, se hacen estimaciones del número máximo de conjuntos pertenecientes a una partición del grafo en k-alianzas. Además, se estudian las relaciones existentes entre dicho número y otros invariantes del grafo, tales como el orden, la medida, el número cromático, el número isoperimétrico y la medida de bipartición. · Se estudian las propiedades matemáticas de los conjuntos libres de alianzas y los cubrimientos de alianzas. En particular, se obtienen cotas tensas para la cardinalidad máxima de un conjunto libre de alianzas y la cardinalidad mínima de un cubrimiento de alianzas. Además, se caracterizan grafos que son libres de k-alianzas defensivas.· Se introduce el concepto de alianza frontera y se estudian algunas de sus propiedades. Entre los resultados obtenidos se destaca una condición necesaria para la existencia de una partición de un grafo regular en dos alianzas fronteras. · Se estudian las alianzas ofensivas globales y sus relaciones con algunos conjuntos característicos en grafos, tales como conjuntos dominantes, t-dominantes y r-dependientes.· Se estudian las alianzas de cardinal mínimo. En particular, se hacen estimaciones de dicho cardinal en función de diversos invariantes del grafo.

A pesar del ideal de “oficina sin papeles” nacida en la década de los setenta, la mayoría de empresas siguen todavía luchando contra una ingente cantidad de documentación en papel. Aunque muchas empresas están haciendo un esfuerzo en la transformación de parte de su documentación interna a un formato digital sin necesidad de pasar por el papel, la comunicación con otras empresas y clientes en un formato puramente digital es un problema mucho más complejo debido a la escasa adopción de estándares. Las empresas reciben una gran cantidad de documentación en papel que necesita ser analizada y procesada, en su mayoría de forma manual. Una solución para esta tarea consiste en, en primer lugar, el escaneo automático de los documentos entrantes. A continuación, las imágenes de los documentos puede ser analizadas y la información puede ser extraida a partir de los datos. Los documentos también pueden ser automáticamente enviados a los flujos de trabajo adecuados, usados para buscar documentos similares en bases de datos para transferir información, etc. Debido a la naturaleza de esta “sala de correo” digital, es necesario que los métodos de representación de documentos sean generales, es decir, adecuados para representar correctamente tipos muy diferentes de documentos. Es necesario que los métodos sean robustos, es decir, capaces de representar nuevos tipos de documentos, imágenes con ruido, etc. Y, por último, es necesario que los métodos sean escalables, es decir, capaces de funcionar cuando miles o millones de documentos necesitan ser tratados, almacenados y consultados. Desafortunadamente, las técnicas actuales de representación, clasificación y búsqueda de documentos no son aptos para esta sala de correo digital, ya que no cumplen con algunos o ninguno de estos requisitos. En esta tesis nos centramos en el problema de la representación de documentos enfocada a la clasificación y búsqueda en el marco de la sala de correo digital. En particular, en la primera parte de esta tesis primero presentamos un descriptor de documentos basado en un histograma de “runlengths” a múltiples escalas. Este descriptor supera en resultados a otros métodos del estado-del-arte en bases de datos públicas y propias de diferente naturaleza y condición en tareas de clasificación y búsqueda de documentos. Más tarde modificamos esta representación para hacer frente a documentos más complejos, tales como documentos de varias páginas o documentos que contienen más fuentes de información como texto extraído por OCR. En la segunda parte de esta tesis nos centramos en el requisito de escalabilidad, sobre todo para las tareas de búsqueda, en el que todos los documentos deben estar disponibles en la memoria RAM para que la búsqueda pueda ser eficiente. Proponemos un nuevo método de binarización que llamamos PCAE, así como dos distancias asimétricas generales para descriptores binarios que pueden mejorar significativamente los resultados de la búsqueda con un mínimo coste computacional adicional. Por último, señalamos la importancia del aprendizaje supervisado cuando se realizan búsquedas en grandes bases de datos y estudiamos varios enfoques que pueden aumentar significativamente la precisión de los resultados sin coste adicional en tiempo de consulta. / Despite the “paperless office” ideal that started in the decade of the seventies, businesses still strive against an increasing amount of paper documentation. Although many businesses are making an effort in transforming some of the internal documentation into a digital form with no intrinsic need for paper, the communication with other businesses and clients in a pure digital form is a much more complex problem due to the lack of adopted standards. Companies receive huge amounts of paper documentation that need to be analyzed and processed, mostly in a manual way. A solution for this task consists in, first, automatically scanning the incoming documents. Then, document images can be analyzed and information can be extracted from the data. Documents can also be automatically dispatched to the appropriate workflows, used to retrieve similar documents in the dataset to transfer information, etc. Due to the nature of this “digital mailroom”, we need document representation methods to be general, i.e., able to cope with very different types of documents. We need the methods to be sound, i.e., able to cope with unexpected types of documents, noise, etc. And, we need to methods to be scalable, i.e., able to cope with thousands or millions of documents that need to be processed, stored, and consulted. Unfortunately, current techniques of document representation, classification and retrieval are not apt for this digital mailroom framework, since they do not fulfill some or all of these requirements. Through this thesis we focus on the problem of document representation aimed at classification and retrieval tasks under this digital mailroom framework. Specifically, on the first part of this thesis, we first present a novel document representation based on runlength histograms that achieves state-of-the-art results on public and in-house datasets of different nature and quality on classification and retrieval tasks. This representation is later modified to cope with more complex documents such as multiple-page documents, or documents that contain more sources of information such as extracted OCR text. Then, on the second part of this thesis, we focus on the scalability requirements, particularly for retrieval tasks, where all the documents need to be available in RAM memory for the retrieval to be efficient. We propose a novel binarization method which we dubbed PCAE, as well as two general asymmetric distances between binary embeddings that can significantly improve the retrieval results at a minimal extra computational cost. Finally, we note the importance of supervised learning when performing large-scale retrieval, and study several approaches that can significantly boost the results at no extra cost at query time.

Esta tesis investiga dos aspectos diferentes sobre cómo un observador percibe una imagen natural: (i) dónde miramos o, concretamente, qué nos atrae la atención, y (ii) qué nos gusta, e.g., si una imagen es estéticamente agradable, o no. Estas dos experiencias son objeto de crecientes esfuerzos de la investigación en visión por computador. Tanto la atención visual como la estética visual pueden ser modeladas como consecuencia de múltiples mecanismos en interacción, algunos bottom-up o involuntarios, y otros top-down o guiados por tareas. En este trabajo nos concentramos en una perspectiva bottom-up, usando mecanismos visuales y características de bajo nivel, ya que es aquí donde los vínculos entre estética y atención son más evidentes, o fácilmente analizables. En la Parte 1 de la tesis presentamos la hipótesis de que las regiones en una imagen que atraen o no la atención pueden ser estimadas usando representaciones estándar de bajo nivel de imágenes en color. Demostramos esta hipótesis usando un modelo de percepción de color de bajo nivel y adaptándolo a un modelo de estimación de la atención. Nuestro modelo de atención hereda una selección de parámetros y un mecanismo de spatial pooling de los modelos de percepción en los que está basado. Éste mecanismo de pooling ha sido ajustado usando datos psicofísicos adquiridos a través de experimentos sobre color y luminancia. El modelo propuesto mejora el estado-del-arte en la tarea de predecir los puntos de atención en dos bases de datos. Tras demostrar la efectividad de nuestro modelo básico de atención, introducimos una representación de la imagen mejorada, basada en conjuntos geométricos. Con esta mejorada representación de imágenes, el rendimiento de nuestro modelo de atención mejora en las dos bases de datos. En la Parte 2 de la tesis, investigamos el problema del análisis estético visual. Debido a que la estética de imágenes es algo complejo y subjetivo, las bases de datos existentes, que proveen unas pocas imágenes y anotaciones, tienen importantes limitaciones. Para tratar estas limitaciones, hemos presentado una base de datos a gran escala para llevar a cabo actividades de análisis estético visual, que llamamos AVA. AVA contiene más de 250,000 imágenes, junto con una rica variedad de anotaciones. Hemos demostrado que aprovechando los datos en AVA, y usando características genéricas de bajo nivel, como SIFT e histogramas de color, podemos superar el estado-del-arte en tareas de predicción de la calidad estética. Finalmente, consideramos la hipótesis de que la información visual de bajo nivel en nuestro modelo de atención puede también ser usada para predecir la estética visual. Para ello, capturamos las características locales de la imagen como contraste, agrupaciones y aislamiento de características, que se suponen relacionadas con reglas universales de la estética. Usamos las respuestas del centre-surround que forman la base de nuestro modelo de atención, para crear un vector de características que describe la estética. También introducimos un nuevo espacio de color, para representaciones de grano fino. Para terminar, demostramos que las características resultantes alcanzan la precisión del estado-del-arte en el problema de clasificación de la calidad estética. Una contribución prometedora de esta tesis es demostrar que diversas experiencias de la visión - percepción de color a bajo nivel, atención visual, y estimación de la estética visual - pueden ser satisfactoriamente modeladas usando un marco de trabajo unificado. Esto sugiere una arquitectura similar en el área V1 del cerebro para la percepción del color y la atención, y añade evidencias a la hipótesis que la apreciación estética está influenciada, en parte, por información de bajo nivel. / This thesis investigates two different aspects of how an observer experiences a natural image: (i) where we look, namely, where attention is guided, and (ii) what we like, i.e., whether or not the image is aesthetically pleasing. These two experiences are the subjects of increasing research efforts in computer vision. Both visual attention and visual aesthetics can be modeled as a consequence of multiple interacting mechanisms, some bottom-up or involuntary, and others top-down or task-driven. In this work we focus on a bottom-up perspective, using low-level visual mechanisms and features, as it is here that the links between aesthetics and attention may be more obvious and/or easily studied. In Part 1 of the thesis, we hypothesize that salient and non-salient image regions can be estimated to be the regions which are enhanced or assimilated in standard low-level color image representations. We prove this hypothesis by adapting a low-level model of color perception into a saliency estimation model. This model shares the three main steps found in many successful models for predicting attention in a scene: convolution with a set of filters, a center-surround mechanism and spatial pooling to construct a saliency map. For such models, integrating spatial information and justifying the choice of various parameter values remain open problems. Our saliency model inherits a principled selection of parameters as well as an innate spatial pooling mechanism from the perception model on which it is based. This pooling mechanism has been fitted using psychophysical data acquired in color-luminance setting experiments. The proposed model outperforms the state-of-the-art at the task of predicting eye-fixations from two datasets. After demonstrating the effectiveness of our basic saliency model, we introduce an improved image representation. With this improved image representation, the performance of our saliency model in predicting eye-fixations increases for both datasets. In Part 2 of the thesis, we investigate the problem of aesthetic visual analysis. Because image aesthetics is complex and subjective, existing datasets, which have few images and few annotations, have significant limitations. To address these limitations, we introduced a new large-scale database for conducting Aesthetic Visual Analysis, which we call AVA. AVA contains more than 250,000 images, along with a rich variety of annotations. We investigate how the wealth of data in AVA can be used to tackle the challenge of understanding and assessing visual aesthetics by looking into several problems relevant for aesthetic analysis. We demonstrate that by leveraging the data in AVA, and using generic low-level features such as SIFT and color histograms, we can exceed state-of-the-art performance in aesthetic quality prediction tasks. Finally, we entertain the hypothesis that low-level visual information in our saliency model can also be used to predict visual aesthetics by capturing local image characteristics such as feature contrast, grouping and isolation, characteristics thought to be related to universal aesthetic laws. We use the weighted center-surround responses that form the basis of our saliency model to create a feature vector that describes aesthetics. We also introduce a novel color space for fine-grained color representation. We then demonstrate that the resultant features achieve state-of-the-art performance on aesthetic quality classification. As such, a promising contribution of this thesis is to show that several vision experiences - low-level color perception, visual saliency and visual aesthetics estimation - may be successfully modeled using a unified framework. This suggests a similar architecture in area V1 for both color perception and saliency and adds evidence to the hypothesis that visual aesthetics appreciation is driven in part by low-level cues.

En matemáticas, la integrabilidad de los campos de vectores polinomiales ha sido objeto de estudio desde hace más de cien años. En 1878, Darboux dio unas condiciones que permiten establecer la existencia de una integral prime- ra para estos campos. La existencia de integrales primeras simplifica mucho el estudio de la dinámica de un sistema diferencial, pero dado un sistema diferencial no es fácil, en general, saber si posee o no integrales primeras. A pesar de los notables progresos que en los últimos años se han obtenido sobre este tema dentro de la teoría de integrabilidad de Darboux, todavía no se ha encontrado una respuesta plenamente satisfactoria. En esta memoria estudiamos aspectos relacionados con la teoría de integrabilidad de Darboux y generalizamos algunos resultados. En particular nos interesan los campos de vectores polinomiales en Rn+1 definidos sobre hipersuperficies regulares algebraicas. En 1979 Jouanolou mostró que si el número de hipersuperficies algebraicas invariantes de un campo vectorial en Rn+1 de grado m es por lo menos (n+m n+1 ) +n+1, entonces el campo vectorial tiene una integral primera racional que se puede calcular utilizando hipersuperficies algebraicas inva- riantes. En el capítulo 2 extendemos este resultado mostrando que el número de hipersuperficies algebraicas invariantes necesarias para garantizar la exis- tencia de una integral primera racional de un campo de vectorial polinomial definido sobre una hipersuperficie de grado d es (n+m n+1 ) ��� (n+m ���d n+1 ) + n. Otro aspecto relacionado con la teoría de integrabilidad de Darboux es el estudio del número máximo de clases de hipersuperficies invariantes que un campo vectorial polinomial puede tener. Para encontrar hipersuperficies algebraicas invariantes utilizamos el concepto de hipersuperficie algebraica extáctica. En el capítulo 3 obtenemos cotas superiores para el número máxi- mo de esferas n-dimensionales invariantes de campos vectoriales polinomiales de Rn+1 en función del grado del campo y teniendo en cuenta la multiplicidad de las esferas invariantes. En el capítulo 4 estudiamos los campos vectoriales polinomiales de R3 definidos sobre una cuádrica y obtenemos las cotas supe- riores para el número máximo de cónicas invariantes que uno de estos campos puede tener en función de su grado y que vivan sobre planos invariantes. Pa- ra esto extendemos la noción de multiplicidad de una superficie algebraica invariante. Además, probamos si estas cotas pueden ser alcanzadas o no. En los capítulos 5 y 6 estudiamos sistemas cuadráticos. El estudio de esta clase de sistemas diferenciales no es trivial y se han publicado más de mil artículos sobre ellos. En el capítulo 5 estudiamos sistemas cuadráticos con una silla integrable. Recientemente este tipo de sillas han sido estudiadas por varios autores. Artés, Llibre y Vulpe caracterizaron los retratos de fase de todos los sistemas cuadráticos con una silla integrable pero no encontra- ron sus integrales primeras. Nosotros obtenemos las expresiones explícitas para las integrales primeras Liouvillianas de estos sistemas cuadráticos. En el capítulo 6 estudiamos los sistemas cuadráticos Lotka-Volterra que poseen un invariante Darboux. Cuando no podemos calcular una integral primera de un sistema diferencial es útil determinar si el sistema tiene un invariante Darboux. Nosotros caracterizamos los retratos de fase globales en el disco de Poincaré de todos los sistemas cuadráticos Lotka-Volterra que poseen un invariante Darboux. / In mathematics, the integrability of polynomial vector fields has been studied for more than one hundred years. In 1878, Darboux provided conditions to establish the existence of first integrals for these fields. The existence of first integrals simplifies the study of the dynamics of a differential system, but given a differential system it is not easy, in general, to know whether or not it has first integrals. Despite the remarkable progress that in recent years have been obtained in the Darboux theory of integrability, this question has not yet a satisfactory answer. We study aspects related to the Darboux theory of integrability and we generalize some results. In particular we are interested in polynomial vector fields in Rn+1 defined on regular algebraic hypersurfaces. In 1979 Jouanolou showed that if the number of invariant algebraic hypersurfaces of a vector field in Rn+1 of degree m is at least (n+m n+1 ) + n + 1, then the vector field has a rational first integral that can be calculated using invariant algebraic hypersurfaces. In chapter 2 we extend this result by showing that the number of invariant algebraic hypersurfaces to ensure the existence of a rational first integral of a polynomial vector field defined on a regular algebraic hypersurface of degree d is (n+m n+1 ) �� (n+m ��d n+1 ) + n. Other aspect related to the Darboux integrability theory is the study of the maximum number of classes of invariant hypersurfaces that a polynomial vector field can have. In order to find invariant algebraic hypersurfaces we use the concept of extactic algebraic hypersurface. In chapter 3 we obtain upper bounds for the maximum number of invariant n-dimensional spheres of polynomial vector fields in Rn+1 in function of the degree of the field and taking into account the multiplicity of the invariant spheres. In chapter 4 we study the polynomial vector fields of R3 defined on a quadric and we obtain upper bounds for the maximum number of invariant conics that one of these fields can have in terms of their degree and living on invariant planes. To do this we extend the notion of multiplicity of an invariant algebraic surface. Moreover, we show whether these bounds can be reached or not. In chapters 5 and 6 we study quadratic differential systems. The study of this class of differential systems is not trivial and have been published more than one thousand papers about them. In chapter 5 we study quadratic systems with an integrable saddle. Recently these saddles have been studied by several authors. Artes, Llibre and Vulpe characterized the phase portraits of all quadratic systems having an integrable saddle, but they did not provide their first integrals. We obtain explicit expressions for the Liouvillian first integrals of these systems. In chapter 6 we study the Lotka-Volterra quadratic systems having a Darboux invariant. When we cannot calculate a first integral of a differential system is useful to determine if the system has a Darboux invariant. We characterize the global phase portraits in the Poincaré disc of all quadratic Lotka-Volterra systems possessing a Darboux invariant.

Objetivos • Demostrar la siguiente conjetura: la sucesión x_{-2}=x_{-1}=x_0=1, x_{k+1}=1/(x_{k}+x_{k-2}) es asintóticamente dos periódica prima. • Estudiar el concepto de irreducibilidad de una ecuación en diferencias racional, y aplicarlo a la resolución de un problema sobre el carácter no finalmente positivo de las soluciones de ciertas ecuaciones en diferencias racionales. • Generalizar las definiciones de caos en el sentido de Li-Yorke y Marotto, enunciados en el caso diferenciable, al caso no continuo de las ecuaciones en diferencias racionales. Extender la condición suficiente de Marotto para la existencia de caos (presencia de un repulsor de retorno finito) a ecuaciones en diferencias racionales. • Realizar análisis numéricos que justifiquen la siguiente conjetura: los teoremas sobre la presencia de repulsores de retorno finito y órbitas homoclínicas en ecuaciones en diferencias perturbadas son también válidos en el contexto racional. • Estudiar los conjuntos prohibidos de ecuaciones en diferencias racionales. Metodología El contenido de la Memoria se ha desarrollado en las siguientes etapas: 1. Un extenso trabajo de documentación en el que se ha consultado la literatura sobre los objetivos antes expuestos, de la cual destacamos los siguientes textos: a) E. Camouzis y G. Ladas. Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures. Advances in Discrete Mathematics and Applications, v.5. Taylor & Francis, 2007. b) F.R. Marotto. Snapback repellers imply chaos in Rn . Journal of Mathematical Analysis and Applications, 63:199–223, 1978. c) F.R. Marotto. Perturbation of stable and chaotic difference equations. J. Math. Anal. Appl, (72):716–729, 1979. d) F. J. Palladino. On invariants and forbidden sets. Xiv:1203.2170v2, 2012. e) R. Azizi. Global behaviour of the rational Riccati difference equation of order two: the general case. Journal of Difference Equations and Applications, 18:947–961, 2012. 2. Simulación numérica utilizando los sistemas algebraicos computacionales wxMaxima 11.08.0 y Mathematica 5.0 3. Un trabajo creativo en el que se han ido obteniendo los teoremas y conjeturas de la Memoria. 4. La presentación de partes de dicho trabajo en diversas publicaciones y comunicaciones en congresos, 5. La revisión del trabajo por el director mediante medios telemáticos y entrevistas frecuentes, durante un periodo de siete años. Conclusiones En la Memoria se han conseguido los siguientes resultados: • La demostración de la conjetura sobre la sucesión citada en el objetivo 1. • La extensión de la conjetura a condiciones iniciales más generales y la determinación de la cuenca de atracción del equilibrium positivo de la ecuación x_{k+1}=1/(x_k+x_{k-2}) • La irreducibilidad de ciertas ecuaciones en diferencias racionales. También se ha encontrado un ejemplo de ecuación no irreducible que puede ser estudiada mediante una ecuación irreducible asociada a ella. • Un teorema general sobre ecuaciones en diferencias racionales no uniformemente finalmente positivas. • La extensión, al contexto de las ecuaciones en diferencias racionales, del teorema de Marotto sobre caos y repulsores de retorno finito. • Se han propuesto diversas conjeturas sobre ecuaciones en diferencias racionales obtenidas mediante perturbaciones de modelos unidimensionales caóticos. Éstas se podrían aplicar a la generalización del modelo de competición de especies de Hassell y Comins. • Dichas conjeturas se han apoyado en simulaciones numérico-gráficas sobre los modelos anteriores. • Se ha recopilado la literatura reciente más relevante sobre los conjuntos prohibidos de ecuaciones en diferencias racionales. • Se han investigado, tanto analítica como numéricamente, los conjuntos prohibidos de las ecuaciones en diferencias estudiadas en el resto de la Memoria. Además durante el desarrollo del trabajo han ido surgiendo diversas conjeturas y problemas abiertos recopilados en el último capítulo de la Memoria. Archena, a 27 de enero de 2014 / Objectives The main objectives of the dissertation are: • To prove the following conjecture: the sequence x_{-2}=x_{-1}=x_0=1, x_{k+1}=1/(x_{k}+x_{k-2}) is asymptotically a period-two sequence (with prime period). • To study the concept of irreducible rational difference equation, applying it to the resolution of a problem about the non eventually positive character of the solutions of some rational difference equations. • To generalize the definitions of Li-Yorke chaos and Marotto chaos to the non continuous framework of rational difference equations, and to extend Marotto's snap-back repeller criterion to rational difference equations. • To make numerical analysis in the aim of justify some conjectures about the presence of snap-back repellers or homoclinic orbits in rational difference equations constructed by a perturbation of a one-dimensional model having such trajectories. • To study the forbidden sets of rational difference equations. Metodology The steps of our work were the following: 1. A wide work of documentation. We have read several books and papers related to the former objectives. For example: a) E. Camouzis y G. Ladas. Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures. Advances in Discrete Mathematics and Applications, v.5. Taylor & Francis, 2007. b) F.R. Marotto. Snapback repellers imply chaos in Rn . Journal of Mathematical Analysis and Applications, 63:199–223, 1978. c) F.R. Marotto. Perturbation of stable and chaotic difference equations. J. Math. Anal. Appl, (72):716–729, 1979. d) F. J. Palladino. On invariants and forbidden sets. Xiv:1203.2170v2, 2012. e) R. Azizi. Global behaviour of the rational Riccati difference equation of order two: the general case. Journal of Difference Equations and Applications, 18:947–961, 2012. 2. A numerical analysis using the computer algebra systems wxMaxima 11.08.0 and Mathematica 5.0 3. A creative work to obtain the theorems and conjectures of the dissertation. 4. The presentation of the former work in several articles and congress communications. For example: a) The difference equation x n1=1 / x n x n−2  . NoLineal 2010 – Cartagena (Spain), june 2010. b) On the difference equation x n1=1 / x n x n−2  . CSS Workshop on Discrete Dynamical Systems – La Manga (Spain), september 2010 c) On solutions of rational difference equations with non positive initial conditions. VCDS, Banská Bystrica (Slovakia), july 2011 d) Snap-back repellers in rational difference equations. ICDEA – Barcelona (Spain), 22th - 27th july 2012. 5. A seven years review work of the dissertation director, using telematic resources and periodic interviews. Conclusions In the dissertation we have achieved the following results: • The proof of the conjecture cited in objective 1. • The extension of the conjecture to more general initial conditions and the determination of the basin of attraction of the positive equilibrium in equation x_{k+1}=1/(x_k+x_{k-2}) • Several examples of irredutible rational difference equations and a non-irreducible rational difference equation with and associated reducible one. • A general theorem about non uniformly eventually positive rational difference equations. • The extension to rational difference equations of the Li-Yorke and Marotto chaos definitions. The extension of Marotto's snap-back repeller rule to detect chaos in a rational difference equation. • We have conjectured several results about the existence of snap-back repellers or homoclinic orbits in rational difference equations obtained by perturbing one-dimensional models. The results could be applied to the Hassell-Comins species competition model. • The former conjectures have been made subsequent to several numerical analysis of those rational difference equations. • We have compiled the recent literature about forbidden sets in rational difference equations, providing a summary of the different techniques for the study of such sets. • We have studied analytically and numerically the forbidden sets of the equations in the former chapters of the dissertation. Finally we have compiled in the last chapter the open problems and conjectures produced along the dissertation. Archena, january 27, 2014

Aquesta tesi tracta d'algoritmes i fenòmens complexos en xarxes.En la primera part s'estudia un model de neurones estocàstiques inter-comunicades mitjançant potencials d'acció. Proposem una tècnica de modelització a escala mesoscòpica i estudiem una transició de fase en un acoblament crític entre les neurones. Derivem una regla de plasticitat sinàptica local que fa que la xarxa s'auto-organitzi en el punt crític.Seguidament tractem el problema d'inferència aproximada en xarxes probabilístiques mitjançant un algorisme que corregeix la solució obtinguda via belief propagation en grafs cíclics basada en una expansió en sèries. Afegint termes de correcció que corresponen a cicles generals en la xarxa, s'obté el resultat exacte. Introduïm i analitzem numèricament una manera de truncar aquesta sèrie.Finalment analizem la interacció social en una comunitat d'Internet caracteritzant l'estructura de la xarxa d'usuaris, els fluxes de discussió en forma de comentaris i els patrons de temps de reacció davant una nova notícia. / This thesis is about algorithms and complex phenomena in networks.In the first part we study a network model of stochastic spiking neurons. We propose a modelling technique based on a mesoscopic description level and show the presence of a phase transition around a critical coupling strength. We derive a local plasticity which drives the network towards the critical point.We then deal with approximate inference in probabilistic networks. We develop an algorithm which corrects the belief propagation solution for loopy graphs based on a loop series expansion. By adding correction terms, one for each "generalized loop" in the network, the exact result is recovered. We introduce and analyze numerically a particular way of truncating the series.Finally, we analyze the social interaction of an Internet community by characterizing the structure of the network of users, their discussion threads and the temporal patterns of reaction times to a new post.

No description available.

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