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

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

No description available.

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

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

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

En Estadística el término "invariancia" puede ser entendido como sinónimo de simetría. Si disponemos de una familia invariante frente a la acción de un grupo, la solución a nuestro problema debería reflejar la propiedad de invariancia de la familia. Sin embargo, no todas las familias son invariantes frente a la acción de algún grupo; habitualmente dispondremos de familias que no serán invariantes pero para las que es posible que su transformación por éste no quede "demasiado alejada" de un desplazamiento de la familia original. En esta situación de "casi invariancia" ¿deberemos desestimar toda la información que nos proporciona la teoría clásica? ¿Tenemos que escoger entre el "blanco" y el "negro"?Justamente, el objetivo de este trabajo pretende ser una contribución a la estimación puntual donde se analice el problema de un estimador para esos "grises", situaciones que van desde la existencia de una invariancia clásica hasta su total ausencia. Los diferentes "tonos de gris" serán las órdenes de invariancia que vamos a definir, en el contexto de la Geometría Diferencial Informativa.

LOS ESTUDIOS DESARROLLADOS SE ENMARCAN, DENTRO DE LA TEORIA DE GRAFOS, EN EL ANALISIS DE CONDICIONES SUFICIENTES PARA OBTENER ALGUNAS MEDIDAS DE CONECTIVIDAD OPTIMA.SE HAN ESTUDIADO CONDICIONES DE TIPO MIXTO PARA EL CASO DE DIGRAFOS BIPARTITOS QUE MEJORAN LOS CONOCIDOS HASTA EL MOMENTO.SE HAN ESTUDIADO LA T-DISTANCIA CONECTIVIDAD, CONSTRUYENDO DIGRAFOS QUE MUESTRAN LA INDEPENDENCIA DE LOS PARAMETROS QUE LE DEFINEN Y OBTENIENDO COTAS SUPERIORES SOBRE EL DIAMETRO QUE GARANTIZAN VALORES OPTIMOS PARA LAS MISMAS.SE HA INTRODUCIDO EL CONCEPTO DE DIAMETRO CONDICIONAL QUE HA PERMITIDO LA AMPLIACION DE LAS COTAS CONOCIDAS SOBRE EL DIAMETRO, ASI COMO LA MEJORA DE ALGUNAS DE ELLAS.POR ULTIMO SE HAN OBTENIDO NUEVAS CONDICIONES DE TIPO CHARTRAND PARA LA CONECTIVIDAD Y LA SUPERCONECTIVIDAD DE DIGRAFOS S-GEODETICOS.

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

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