Este trabalho utiliza o problema subset-sum (SSP) como estudo de caso, com o objetivo de analisar a complexidade de paralelização em Unidades de Processamento Gráficas (GPU). O SSP foi escolhido por pertencer à classe dos problemas NP-Completo, possuir grande necessidade de memória e não ter cálculo de ponto flutuante, além de ser amplamente estudado na área acadêmica devido a sua importância prática e teórica. Estas características representam um desafio para paralelização em GPUs, pelo fato de serem especialistas em cálculos de ponto flutuante e por possuir pouca quantidade de memória em relação ao grande número de núcleos. Basicamente, são apresentados 3 novos algoritmos, implementados em linguagem CUDA C, com baixo consumo de memória: somente , onde , é a capacidade da mochila e é a quantidade de itens, ao invés de do paradigma de Bellman, referentes aos algoritmos do estado da arte implementados na mesma arquitetura. Esta característica permite um ganho significativo na quantidade de instâncias solucionáveis, além do melhor tempo computacional. Para uma variedade de benchmarks, obteve-se bons valores de speed-up em relação aos melhores resultados práticos conhecidos até agora. Isto foi possível graças a um novo método para a solução do SSP, permitindo sua computação em tempo e mesmo espaço, caso processadores sejam utilizados.

The Subset-sum Problem (SSP) consists of finding a subset of a set of integers whose sum is as close as possible to a target amount, without exceeding it. The problem is NP-complete, but there are dynamic programming-based algorithms which can solve many instances in reasonable time. Most of these algorithms attempt to minimize the time taken to find the solution for "hard" problem instances, but have sub-optimal performance when dealing with "easy" instances, either containing few items or with multiple equivalent solutions of which just one needs to be found. In this work, we analyze the characteristics of several well-known approaches, including standard dynamic-programming Bellman recursion, Horowitz-Sahni decomposition and core algorithms, and suggest variations which improve their average-case performance for easy instances, without harming their worst-case performance significantly. One variation improves the performance of the YS87 single state - multiple stages algorithm for sparse instances. Another minimizes the amount of work required by decomposition-based approaches before a solution is found, allowing the computation to be aborted earlier for dense instances with many exact solutions; this is achieved by using the programming concept of generators in order to compute partial solutions only when they are needed. We also examine the characteristics of several SSP test instance types which are commonly used to compare algorithm performances, analyzing how the distribution of partial solutions varies according to the type and size of the instances. The times taken by several algorithm implementations to solve each of the SSP instance types are measured and compared, and the variations in their behavior when dealing with each one are explained based on the instances'; characteristics.

Seja (X; t) um espaço topológico e seja F a família de todos os subconjuntos de X que satisfazem uma propriedade topológica dada P (invariante por homeomorfismos). Se acrescentarmos abertos novos à topologia e se F\' é a família de todos os subconjuntos do novo espaço que satisfazem a propriedade P, podemos ter que F ≠ F\'. Se isto sempre acontece, dizemos que o espaço (X; t) é maximal com respeito à família F. Neste trabalho estudaremos os espaços topológicos maximais com respeito a algumas famílias de subconjuntos: discretos, compactos, densos, conexos e das sequências convergentes. / Let (X; t) be a topological space and let F be the family of all subsets of X that satisfy a given topological property P (invariant under homeomorphisms). If we add new open sets to the topology and if F\' is the family of all subsets of the new space which satisfy the property P, we can have F ≠ F\'. If this is always the case, we say that (X; t) is maximal with respect to the family F. We show here some characterizations of maximal spaces with respect to the family of some of its subsets: compacts, dense, discrete and convergent sequences.

Seja (X; t) um espaço topológico e seja F a família de todos os subconjuntos de X que satisfazem uma propriedade topológica dada P (invariante por homeomorfismos). Se acrescentarmos abertos novos à topologia e se F\' é a família de todos os subconjuntos do novo espaço que satisfazem a propriedade P, podemos ter que F ≠ F\'. Se isto sempre acontece, dizemos que o espaço (X; t) é maximal com respeito à família F. Neste trabalho estudaremos os espaços topológicos maximais com respeito a algumas famílias de subconjuntos: discretos, compactos, densos, conexos e das sequências convergentes. / Let (X; t) be a topological space and let F be the family of all subsets of X that satisfy a given topological property P (invariant under homeomorphisms). If we add new open sets to the topology and if F\' is the family of all subsets of the new space which satisfy the property P, we can have F ≠ F\'. If this is always the case, we say that (X; t) is maximal with respect to the family F. We show here some characterizations of maximal spaces with respect to the family of some of its subsets: compacts, dense, discrete and convergent sequences.

According to numerous scientific studies one of the most important points in the area of sustainability in business is related to dialogue with stakeholders. Based on Stakeholder Theory we try to analyze corporate sustainability and the process of preparing a report that a company in the tourism sector in accordance with the guidelines of the guide G3 - Global Reporting Initiative. With the completion of an empirical study seeks to understand the expectations of stakeholders regarding the implementation of the contents of the sustainability report. To achieve the proposed aim we use «The Expertons Method» algorithm that allows the aggregation of opinions of various experts on the subject and represents an important extension of fuzzy subsets for aggregation processes. At the end of our study, we present the results of using this algorithm, the contributions and future research. / De acuerdo con numerosos estudios científicos uno de los puntos más importantes en el ámbito de la sostenibilidad en las empresas radica en el diálogo con los grupos de interés. Tomando como base la teoría de los grupos de interés, trata­remos de analizar la sostenibilidad empresarial y el proceso de elaboración de un informe que una empresa del sector de turismo prepara de acuerdo con las directrices de la guía G3, Global Reporting Initiative (GRI). Con la realización de un estudio empírico se pretende conocer las expectativas de los grupos de interés con respecto al cumplimiento del con­tenido de la memoria de sostenibilidad. Para alcanzar el objetivo propuesto utilizaremos el «método de los expertones», algoritmo que permite la agregación de opiniones de varios expertos sobre el tema y que representa una importante extensión de los subconjuntos borrosos para procesos de agregación. Al final de nuestro estudio, presentaremos los resultados de la utilización de este algoritmo, las aportaciones y futuras líneas de investigación.

The classical Nykodym theorem (1933) asserts that a set H of countably additive complex measures defined on a sigma-algebra S which is bounded for each element of S, then H is uniformly bounded on S. It is well known that this theorem fails if we replace the sigma-algebra S simply by an algebra. Let A be the algebra of subsets of a nonempty set, and consider the Banach space ba(A) of all real (or complex) finitely additive measures of bounded variation defined on A. A subset B of A is said to have the N-property (Nikodym property) if every B-pointwise bounded subset M of ba(A) is uniformly bounded on A. Recall the classical Nikodym-Dieudonné-Grothendieck's theorem which says that each sigma-algebra has the N-property. Moreover B is said to have the strong N-property if for each increasing countable covering (B_{m})_{m} of B there exists B_{n} which has the N-property. Valdivia proved in 1979 that each sigma-algebra has the strong N-property. The aforementioned Valdivia's theorem motivated to prove that each sigma-algebra S of subsets of a set has web-N-property, that is, if (B_{m_1})_{m_1} is an increasing countable covering of S and if (B_{m_1},_{m_2},....,_{m_p},_{m_{p+1}})_{m_{p+1}} is an increasing countably covering of B_{m_1},_{m_2},....,_{m_p}, for each natural numbers p, mi, with i = 1, 2,..., p, then there exists a sequence (n_{r})_{r} such thatB_{n_1},_{n_2},....,_{n_r} has the N-property for every r = 1, 2, 3, ...... . In this thesis it is proved that nearly all infinite chains in the increasing web (B_{m_1},_{m_2},....,_{m_p}: m_i=1,2,... , i=1,2,...,p, and p=1,2,.....} are composed of sets that have web-N-property. In the main result in this thesis it is proved that the algebra J(K) of Jordan measurables subsets of a compact k-dimensional interval K contained in R^k has the web-N-property. This result imporves the 2013 Valdivia's theorem stating that J(K) has the strong Nikodym property, which in turns was a grest improvement of Schachermayer's result of N property of J([0; 1]). The analysis of the demonstration of this result has allowed us give a sufficient condition in an algebra of subsets of a set that implies the property **wN. This sufficient condition is verified by each sigma-algebra as well as by the algebra J(K), whence the properties wN of any sigma-algebra and of J(*K) could have been presented like corollaries of this sufficient condition. It has seemed more natural to follow the chronological order, such as it has done in the Thesis. In the chapter 5 the problem proposed by Valdivia in 2013 is considered, i.e., to prove if it is true or not that when an algebra A of subsets have the property N then it has the property sN. In the section 5.2 this problem is considered in the most general context of normed spaces, because a subset B of an algebra A has the property N if each subset M of finitely additive bounded measures pointwise bounded in the sets of B verifies that M is a bounded subset of the Banach space of bounded finitely additive measures in the algebra A endowed with the supreme norm, what carries to the study of the sets DAU that determine the uniform boundedness of a normed space. Several applications of the obtained results to problems of location of vectorial averages and of convergence of sequences as well as several open problems are presented. The limitation of number of characters prevents to comment other results. We finish this summary indicating that we have proved that the properties wN, w(sN) and w(wN) are equivalents. / El clásico teorema de Nykodym (1933) afirma que si un subconjunto H de medias complejas numerablemente aditivas definidas en una sigma-algebra S está acotado en cada elemento de S, entonces H está uniformente acotado en S. Es bien conocido que este teorema no es cierto en general si se sustituye la sigma-álgebra S por un álgebra. Sea A un álgebra de subconjuntos de un conjunto no vacío, y consideremos el espacio de Banach ba(A) de las medias reales (o complejas) finitamente aditivas de variación acotada definidas en A. Un subconjunto B of A se dice que tiene la propiedad N (propiedad de Nikodym) si para cada subconjunto M of ba(A) que sea B-puntualmente acotado se tiene que M es uniformemente acotado en A. Recordemos que el clásico teorema de Nikodym-Dieudonné-Grothendieck's dice que cada sigma-algebra tiene la propiedad N. Además se dice que B tiene la propiedad N-fuerte si cada para cada cubrimiento numerable creciente (B_{m})_{m} de B existe B_{n} que tiene la propiedad N. Valdivia demmostró en 1979 que cada sigma-algebra tiene la propiedad N-property. Este teorema de Valdivia motivó demostrar que cada sigma-algebra S de subconjuntos de un conjunto tiene la propiedad N para mallas crecientes, es decir, si (B_{m_1})_{m_1} es un cubrimiento numerable creciente de S y si (B_{m_1},_{m_2},....,_{m_p},_{m_{p+1}})_{m_{p+1}} es un cubrimiento numerable creciente de B_{m_1},_{m_2},....,_{m_p}, para cada números naturales p, mi, con i=1, 2,..., p, entonces existe una sucesión (n_{r})_{r} tal que B_{n_1},_{n_2},....,_{n_r} tiene la propiedad N para cada r = 1, 2, 3, ...... . En la tesis se prueba que casi todas las cadenas infinitas en una malla creciente (B_{m_1},_{m_2},....,_{m_p}: m_i=1,2,... , i=1,2,...,p, and p=1,2,.....} están compuestas de conjuntos que tienen la propiedad N para mallas crecientes. El resultado principal de la tesis prueba que el algebra J(K) de los subconjuntos Jordan medibles de un intervalo compacto k-dimensional K contenido en R^k tiene la propiedad N para mallas crecientes. Este resultado mejora el resultado de Valdivia de 2013 de que J (K) tiene la propiedad fuerte de Nikodym, que a su vez mejoraba un resultado anterior de Schachermayer, quien probó que J ([0; 1]) tiene la propiedad N. El análisis de la demostración de este resultado nos ha permitido dar una condición suficiente en un álgebra de subconjuntos de un conjunto que implica la propiedad wN. Esta condición suficiente la verifican tanto las sigma-álgebras como el álgebra J (K), por lo que las propiedades wN de cualquier sigma-álgebra y de J(K) se podían haber presentado como corolarios de dicha condición suficiente. Ha parecido más natural seguir el orden cronológico, tal como se ha hecho en la Tesis. En el capítulo 5 se considera el problema planteado por Valdivia en 2013. Consiste en averiguar si el que un álgebra A de conjuntos tenga la propiedad N implica o no el tener la propiedad sN. En la sección 5.2 se considera este problema en el contexto más general de los espacios normados, pues un subconjunto B de un álgebra A tiene la propiedad N si cada subconjunto M de medidas acotadas, finitamente aditivas y puntualmente acotadas en el conjunto de funciones características de los conjuntos de B verifica que M es un subconjunto acotado del espacio de Banach de dichas medias finitamente aditivas y acotadas definidas en A con la norma supremo, lo que lleva al estudio de los conjuntos DAU que determinan la acotación uniforme en un espacio normado. Se presentan varias aplicaciones de los resultados obtenidos a problemas de localización de medias vectoriales y de convergencia de sucesioens de medias y varios problemas abiertos. La limitación de número de caracteres impide comentar otros resultados. Terminamos este resumen indicando que hemos probado que las propiedades wN, w(sN) y w(wN) son equivalentes. / El clàssic teorema de Nykodym (1933) afirma que si un subconjunt H de mesures complexes numerablement aditives defiides en una sigma-àlgebra S és acotat en cada element de S, aleshores H és uniforment acotat en S. És ben conegut que aquest teorema no és cert en general si es sustitueix la sigma-àlgebra S simplement per una àlgebra. Siga A una àlgebra de subconjunts d'un conjunt no buit, i considerem l'espai de Banach ba(A) de les mesures reals (o complexes) finitament aditives de variació acotada definides en A. Un subconjunt B de A es diu que té la propietat N (propietat de Nikodym) si cada subconjunt M de ba(A) que siga B-puntualment acotat es té que M és uniformement acotat en A. Recordem que el clàssic teorema de Nikodym-Dieudonné-Grothendieck's diu que cada sigma-àlgebra té la propietat N. A més a més es diu que B té la propietat forta N si per a cada cubrimient numerable creixent (B_{m})_{m} de B existeix B_{n} que té la propietat N. Valdivia va provar en 1979 que cada sigma-àlgebra té la propietat N. L'esmentat teorema de Valdivia va motivar demostrar que cada sigma-àlgebra S de subconjunts de un conjunt té la propietat N per a malles creixents, és dir, si (B_{m_1})_{m_1} és un cubrimient numerable creixent de S i si (B_{m_1},_{m_2},....,_{m_p},_{m_{p+1}})_{m_{p+1}} és un cubrimient numerable creixent de B_{m_1},_{m_2},....,_{m_p}, per a cada nombres naturals p, mi, amb i = 1, 2,..., p, aleshores existeix una successió (n_{r})_{r} tal que B_{n_1},_{n_2},....,_{n_r} té la propietat N per a cada r = 1, 2, 3, ...... . En la tesi es prova que gairebé totes les cadenes infinites en una malla creixent (B_{m_1},_{m_2},....,_{m_p}: m_i=1,2,... , i=1,2,...,p, and p=1,2,.....} estan composades de conjunts que tenen la propietat N per a malles creixents. El resultat principal de la tesi prova que l'àlgebra J(K) dels subconjunts Jordan mesurables d'un interval compacte k-dimensional K contingut en R^k té la propietat N per a malles creixents. Aquest resultat millora el resultat de Valdivia de 2013 de que J (K) té la propietat forta de Nikodym, que alhora millorava un resultat anterior de Schachermayer, qui va provar que J([0; 1]) té la propietat N. L'anàlisi de la demostració d'aquest resultat ens ha permès donar una condició suficient en un àlgebra de subconjunts d'un conjunt que implica la propietat wN. Aquesta condició suficient la verifiquen tant les sigma-àlgebres com l'àlgebra J(K), per la qual cosa les propietats wN de qualsevol sigma-àlgebra i de J(K) es podien haver presentat com a corol·laris d'aquesta condició suficient. Ha semblat més natural seguir l'ordre cronològic, tal com s'ha fet en la Tesi. En el capítol 5 es considera el problema plantejat per Valdivia en 2013. Consisteix a esbrinar si el que un àlgebra A de conjunts tinga la propietat N implica o no el tenir la propietat sN. En la secció 5.2 es considera aquest problema en el context més general dels espais normados, doncs un subconjunt B d'un àlgebra A té la propietat N si cada subconjunt M de mesures acotades, finitament additives i puntualment acotades en el conjunt de funcions característiques dels conjunts de B verifica que M és un subconjunt acotat de l'espai de Banach d'aquestes mesure finitament additives i acotades definides en A amb la norma suprem, la qual cosa porta a l'estudi dels conjunts DAU que determinen l'acotació uniforme en un espai normat. Es presenten diverses aplicacions dels resultats obtinguts a problemes de localització de mitjanes vectorials i de convergència de **sucesioens de mitjanes i diversos problemes oberts. La limitació de nombre de caràcters impedeix comentar altres resultats. Acabem aquest resum indicant que hem provat que les propietats wN, w(sN) i w(wN) són equivalents. / López Alfonso, S. (2016). Conjuntos que determinan la acotación uniforme [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/75266 / TESIS

[ES] La consistencia de los datos de la HCE, como dimensión de la calidad, se considera un requisito esencial para la mejora de la prestación de la asistencia sanitaria, los procesos de toma de decisiones clínicas y la promoción de la investigación clínica. En este contexto, la cooperación entre la información y los modelos de dominio se considera esencial en la literatura, pero la comunidad científica no la ha abordado adecuadamente hasta la fecha. La contribución principal de esta tesis es el desarrollo de métodos y herramientas para la inclusión de expresiones de enlaces terminológicos en reglas de consistencia. Las contribuciones específicas son: - Definición de un método para ejecutar ECs sobre una base de datos de SNOMED CT orientada a grafos. - Definición de métodos para simplificar ECs antes y después de su ejecución, y su validación semántica conforme al Machine Readable Concept Model de SNOMED CT (MRCM). - Definición de un método para visualizar, explorar dinámicamente, comprender y validar subconjuntos de SNOMED CT. - Desarrollo de SNQuery, una plataforma que ejecuta, simplifica y valida ECs y visualiza los subconjuntos resultantes. - Definición de EHRules, un lenguaje de expresiones basado en el openEHR Expression Language para la especificación de reglas de consistencia en arquetipos, incluido el enlace terminológico de contenido, con el fin de enriquecer los arquetipos con conocimiento del dominio. - Definición de un método para ejecutar las expresiones de EHRules con el fin de validar la consistencia de los datos de la HCE mediante la ejecución de dichas expresiones sobre instancias de datos de pacientes. Nuestro objetivo es que estas contribuciones ayuden a mejorar la calidad de la HCE, ya que proporcionan métodos y herramientas para la validación y mejora de la consistencia de los datos de la HCE. Pretendemos, además, mediante la definición de enlaces de contenido entre modelos de información y terminologías clínicas, elevar el nivel de interoperabilidad semántica, para lo cual la definición de enlaces terminológicos es crucial. / [CA] La consistència de les dades de la HCE, com a dimensió de la qualitat, es considera un requisit essencial per a la millora de la prestació de l'assistència sanitària, els processos de presa de decisions clíniques i la promoció de la investigació clínica. En aquest context, la cooperació entre la informació i els models de domini es considera essencial en la literatura, però la comunitat científica no l'ha abordada adequadament fins hui. La contribució principal d'aquesta tesi és el desenvolupament de mètodes i ferramentes per a la inclusió d'expressions d'enllaços terminològics en regles de consistència. Les contribucions específiques són: - Definició d'un mètode per a executar ECs sobre una base de dades de SNOMED CT orientada a grafs. - Definició de mètodes per a simplificar ECs abans i després de la seua execució, i la seua validació semàntica conforme al Machine Readable Concept Model de SNOMED CT (MRCM). - Definició d'un mètode per a visualitzar, explorar dinàmicament, comprendre i validar subconjunts de SNOMED CT. - Desenvolupament de SNQuery, una plataforma que executa, simplifica i valida ECs i visualitza els subconjunts resultants. - Definició de EHRules, un llenguatge d'expressions basat en l'openEHR Expression Language per a l'especificació de regles de consistència en arquetips, inclòs l'enllaç terminològic de contingut, amb la finalitat d'enriquir els arquetips amb coneixement del domini. - Definició d'un mètode per a executar les expressions de EHRules amb la finalitat de validar la consistència de les dades de la HCE mitjançant l'execució d'aquestes expressions sobre instàncies de dades de pacients. El nostre objectiu és que aquestes contribucions ajuden a millorar la qualitat de la HCE, ja que proporcionen mètodes i ferramentes per a la validació i millora de la consistència de les dades de la HCE. Pretenem, a més, mitjançant la definició d'enllaços de contingut entre models d'informació i terminologies clíniques, elevar el nivell d'interoperabilitat semàntica, per a la qual cosa la definició d'enllaços terminològics és crucial. / [EN] Consistency of EHR data, as a dimension of quality, is considered an essential requirement to the improvement of healthcare delivery, clinical decision-making processes, and the promotion of clinical research. In this context, cooperation between information and domain models has been considered essential in the literature, but it has not been adequately addressed by the scientific community to date. The main contribution of this thesis is the development of methods and tools for the inclusion of terminology binding expressions in consistency rules. Specific contributions are: - Definition of a method to execute ECs over a SNOMED CT graph-oriented database. - Definition of methods to simplify ECs before and after its execution and semantic validation according to the SNOMED CT Machine Readable Concept Model (MRCM). - Definition of a method to visualize, dynamically explore, understand and validate SNOMED CT subsets. - Development of SNQuery, an execution platform that executes, simplifies and validates ECs, and visualizes the resulting subsets. - Definition of EHRules, an expression language based on the openEHR Expression Language for the specification of consistency expressions in archetypes, including value set bindings, in order to enrich archetypes with domain knowledge. - Definition of a method to execute EHRules expressions in order to validate the consistency of EHR data by executing such rules over patient data instances. Our objective is that these contributions help to enhance the quality of EHR, as they provide methods and tools for the validation and enhancement of the EHR data consistency. We also intend, by defining value set bindings between information models and clinical terminologies, to raise the level of semantic interoperability, for which the definition of terminological bindings is crucial. / This thesis was partially funded by Ministerio de Economía y Competitividad, “Doctorados Industriales”, grant DIN2018-009951, and by Universitat Politècnica de València, “Formación de Personal Investigador” (FPI-UPV). / Giménez Solano, VM. (2021). Enrichment of Archetypes with Domain Knowledge to Enhance the Consistency of Electronic Health Records [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/180082 / TESIS