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.

Made available in DSpace on 2014-06-12T17:36:02Z (GMT). No. of bitstreams: 2 arquivo2523_1.pdf: 1662188 bytes, checksum: ca366b30d35fcf4e22eb4ea7ea20d578 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A decodificação de códigos baseados em matrizes de verificação de paridade esparsas (LDPC, do inglês low-density parity-check) é realizada através do algoritmo soma-produto (ASP). Este trabalho apresenta um estudo do funcionamento do ASP e do seu desempenho em um canal com ruído aditivo Gaussiano branco (AWGN, do inglês additive white Gaussian noise) através de simulações computacionais. Em seguida, esta análise é estendida quando um quantizador uniforme com 2q níveis de quantização é incorporado ao sistema de comunicações. O passo de quantização ótimo é identificado para vários parâmetros do código e do canal. Este estudo indica que para q = 1 (quantização abrupta) ocorre uma perda de desempenho de aproximadamente 1,8 dB em relação ao canal AWGN enquanto que para q = 4 essa perda é reduzida para aproximadamente 0,12 dB

Made available in DSpace on 2014-06-12T17:39:33Z (GMT). No. of bitstreams: 2 arquivo6919_1.pdf: 4119217 bytes, checksum: 3f1efa22858eeae0d86c8392becd8174 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Códigos baseados em matrizes esparsas têm desempenhado um importante papel em teoria da codificação. Os códigos low-density parity-check (LDPC) constituem uma famosa família de códigos definidos a partir de matrizes de verificação de paridade esparsas que apresentam desempenhos excelentes no canal com ruído aditivo Gaussiano branco (RAGB). O sucesso desses códigos se deve a sua representação através de grafos, que permite a operação de um algoritmo de decodificação iterativo cuja complexidade cresce linearmente com o comprimento dos blocos. Esta dissertação apresenta um estudo sobre códigos LDPC e sua principal ferramenta de análise, a density evolution. Para isso, a representação gráfica de códigos de bloco lineares e o funcionamento do algoritmo de decodificação Soma-Produto são apresentados. Algumas técnicas de projeto de códigos LDPC são discutidas e seu desempenho no canal RAGB é avaliado por meio de simulações. Baseando-se nestas ferramentas, a density evolution para os canal RAGB é derivada em forma integral e em forma aproximada. Por fim, uma modificação no algoritmo Soma-Produto é proposta para decodificação de códigos LDPC no canal Gilbert-Elliott

Made available in DSpace on 2017-07-10T17:36:49Z (GMT). No. of bitstreams: 1 2013_Lorena_Maia_Noreto.pdf: 1204258 bytes, checksum: 13d5a3e9e5a92c9d8ebf5436c3142a61 (MD5) Previous issue date: 2013-03-12 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The objective of this study was to determine the growing degree-days sum and the relationship between the period length from sowing to physiological maturity and sowing dates of thirteen wheat cultivars, in the Palotina PR and Cascavel - PR. The data on wheat crop were colected by the Cooperativa Central de Pesquisa Agrícola (COODETEC) and correspond to the harvests of 2006 to 2011. The treatments consisted of 13 wheat cultivars, 3 sowing dates for Cascavel and 4 sowing dates for Palotina. The data used for the analysis were: Total elapsed days from sowing to the silking and to physiological maturity, and of the silking to physiological maturity, along with the growing degree-days sum for these periods, beyond grains yield and hectoliter weight. The results indicate that the average length of sowing to silking was 64 days for Palotina and 71 days for Cascavel. For the period from silking to physiological maturity the average length was 56 days for Palotina and 54 days for Cascavel. The increase in length of time from sowing to silking in cultivars sowed in May 25th (JD 145) was due to the decrease in air temperature. The average of growing degree-days sum between the period from sowing to physiological maturity was 1487, for both locations. The cultivars that stood out presenting a shorter period of silking to physiological maturity and high productivity were the cultivars CD 114, CD 120 and CD 124 for Palotina and CD 114, CD 120, CD 121, CD 122, CD 124 and Onix for Cascavel / O trabalho teve como objetivo determinar o acúmulo de graus-dia e a relação entre a duração do período da semeadura a maturação fisiológica e as datas de semeadura de treze cultivares de trigo, nos municípios de Palotina - PR e Cascavel PR. Os dados referentes a cultura do trigo foram cedidos pela Cooperativa Central de Pesquisa Agrícola (COODETEC) correspondente as safras agrícolas de 2006 a 2011. Os tratamentos foram constituídos de 13 cultivares de trigo, 3 datas de semeadura para Cascavel e 4 datas de semeadura para Palotina. Os dados utilizados para a análise foram: totais de dias transcorridos da semeadura ao espigamento e a maturação fisiológica e do espigamento a maturação fisiológica, juntamente com o acúmulo de graus-dia para estes períodos, além do rendimento de grãos e peso hectolitro. Os resultados indicam que a duração média do período da semeadura ao espigamento foi de 64 dias para Palotina e 71 dias para Cascavel. Para o período do espigamento a maturação fisiológica a duração média foi de 56 dias para Palotina e 54 dias para Cascavel. O aumento na duração do período da semeadura ao espigamento para cultivares semeados em 25 de Maio (DJ 145) ocorreu em virtude da diminuição da temperatura do ar. O acúmulo médio de graus-dia entre o período da semeadura a maturação fisiológica foi de 1487 para as duas localidades. Os cultivares que destacaram-se, apresentando um menor período do espigamento a maturação fisiológica e com boa produtividade foram os cultivares CD 114, CD 120 e CD 124 para Palotina e CD 114, CD 120, CD 121, CD 122, CD 124 e Onix para Cascavel

Cette thèse est divisée en trois parties. Les groupes de première partie des contributions à l'étude des équilibres corrélés. Nous nous concentrons sur les propriétés et les applications de la réduction de la double (Myerson, 1997) et la géométrie de Nash équilibres et des équilibres corrélés. La deuxième partie traite de l'évolution dynamique. Nous étudions le lien entre les stratégies appartenant à l'appui de Nash ou équilibres corrélés et les stratégies de survie dans le long terme. Nous constatons que la dynamique de beaucoup, y compris le réplicateur et les plus dynamiques de réponse peut éliminer toutes les stratégies à l'appui des équilibres corrélés. Élimination de toutes les stratégies à l'appui des équilibres de Nash est jugée encore plus universelle, et peuvent se produire à partir de presque toutes les conditions initiales. Le troisième partie se compose d'un seul article co-écrit, qui appartient au domaine de la biologie théorique. Nous aspects de l'étude de la transition de l'unicellulaire à organismes multi-cellulaires, en particulier les facteurs de conduite germe-soma spécialisation chez les algues vertes volvocine. introductions longues sont donnés au début de chaque partie. Le Bibliographie de la partie I et partie II est disjointe de la bibliographie de la partie III, et est offert à la fin de la partie II. Bien que reliées entre elles, les chapitres sont essentiellement autonome. En particulier, les notations et quelques définitions sont rappelés à chaque fois. Cela explique certaines répétitions.

San Francisco's South of Market (SoMa) neighborhood and the Mission District are facing new forms of redevelopment. The deindustrialization of SoMa has posed an opportunity for a 'new model' of gentrification to create a mixed-use, mixed-income neighborhood from an area previously occupied by abandoned warehouses and vacant lots. In the Mission, awareness of the threats of gentrification and increased community participation are fighting to preserve the neighborhood and eliminate displacement. The innovative approaches to urban revitalization in these two neighborhoods demonstrate how redevelopment may occur without gentrification.

The water and coal samples from the Manisa-Soma-DeniS region were studied on the basis of their basic characteristics, inorganic and organic parameters. Coal samples were determined as low-quality lignite. They have high concentrations of arsenic, uranium and lead. The organics in the coal samples are of aliphatic hydrocarbons and their derivatives (alkanes and alcohols), methyls, phthalates, naphtalenes and benzenes. They are inactive and low in concentrations. Water samples have basic characteristics within the range of drinking waters. They also have high arsenic and uranium concentrations indicating a possible leaching. Their organic compounds are similar to those in the coal samples. However, these organic compounds are not as toxic as those found in endemic samples and their concentration is also very low. Therefore, they are considered not to be a potential for Balkan Endemic Nephropathy (BEN)-disease. On the basis of the findings of this study, the area can be concluded as non-endemic region.

AVELA, Adriano Silva. O número médio de representações de um inteiro positivo como soma dos quadrados de dois inteiros. 2017. 46 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-08-16T14:27:56Z No. of bitstreams: 1 2017_dis_asavela.pdf: 787094 bytes, checksum: 1b45101b32e7b3738ea38b152f128087 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde, Conferi a Dissertação de ADRIANO SILVA AVELA e detectei alguns erros que devem ser corrigidos pelo próprio autor. Os mesmos seguem listados abaixo: 1- CAPA (altere o termo MESTRADO PROFISIONAL EM MATEMÁTICA EM REDE NACIONAL para PROGRAMA DE PÓS-GRADUAÇÃO EM MATEMÁTICA EM REDE NACIONAL) 2- FICHA CATALOGRÁFICA (está faltando a ficha catalográfica do trabalho, a mesma poderá ser elaborada sistema CATALOG, no endereço eletrônico: - http://fichacatalografica.ufc.br/ - e deve ser inserida antes da folha de aprovação) 3- FOLHA DE APROVAÇÃO (a folha de aprovação do trabalho está com formatação inadequada a mesma deve ocupar apenas uma página. O modelo encontra-se disponível no GUIA DE NORMALIZAÇÃO DE TRABALHOS ACADÊMICOS DA UFC, disponível no endereço eletrônico: http://www.biblioteca.ufc.br/images/arquivos/documentos_tecnicos/guia_normalizacao_trabalhos_ufc_2013.pdf 4- DEDICATÓRIA (veja o modelo de formatação da dedicatória no GUIA DE NOEMALIZAÇÃO DA UFC) 5- AGRADECIMENTOS (este item do trabalho não deve conter o nome do autor ao final dos agradecimentos, verifique o modelo no GUIA DE NORMALIZAÇÃO) 6- NUMERAÇÃO INADEQUADA DE PÁGINAS (verifique o trabalho e retire as numerações desordenada das primeiras páginas do trabalho. O número das páginas só deve aparecer a partir da INTRODUÇÃO) 7- EPÍGRAFE (a frase que compõe este elemento do trabalho deve conter a identificação do autor ao qual ela pertence. Mas ela é um elemento opcional, assim você poderá retirá-la sem nenhum prejuízo) 8- RESUMO/ABSTRACT (a formatação dos termos RESUMO e ABSTRACT está incorreta, esses dois termos devem estar em CAIXA ALTA, NEGRITO e FONTE n° 12) 9- PALAVRAS-CHAVE/KEYWORD (acrescente um ponto final no lugar das vírgulas que separam as Palavras e as Keywords) 10 – LISTA DE FIGURAS/LISTA DE TABELAS (Veja o modelo adequado para esses dois itens no GUIA DE NORMALIZAÇÃO) 11 - SUMÁRIO (verifique no GUIA DE NORMALIZAÇÃO o modelo adequado para a elaboração do sumário. Ressalto que o item INTRODUÇÃO é um capítulo e deve constar no sumário com a numeração de primeiro capítulo, Já os termos REFERÊNCIAS e APÊNDICE não devem apresentar numeração de capítulo, verifique no GUIA a formatação desses itens) 12 - TITULO DOS CAPÍTULOS (os títulos de capítulos e seções devem seguir a seguinte formatação: 1 TÍTULOS DE CAPÍTULOS (incluindo a Introdução, CAIXA ALTA, FONTE n° 12, NEGRITO, ALINHADO À ESQUERDA) 1.1 Títulos de seções (seção primária, CAIXA BAIXA, NEGRITO, FONTE N° 12, ALINHADO À ESQUERDA) *NO CASO DE DUVIDA CONSULTE O GUIA DE NORMALIZAÇÃO 13 - NUMERAÇÃO DE PÁGINAS (a número das páginas deve começar a aparecer a partir da folha de introdução, no CANTO SUPERIOR DIREITO) 14- CONCLUSÃO (a conclusão é um item obrigatório que deve constar na dissertação, o GUIA DE NORMALIZAÇÃO DA UFC menciona que “A conclusão deve ser decorrência natural do que foi exposto no desenvolvimento. Assim, em qualquer tipo de trabalho, deve resultar de deduções lógicas sempre fundamentadas no que foi apresentado e discutido anteriormente. Visa a recapitular sinteticamente os resultados da pesquisa.” 15 – REFERÊNCIAS/APÊNDICE (verifique no GUIA DE NORMALIZAÃO a formatação adequada para os títulos da REFERÊNCIAS e APÊNCE) on 2017-08-16T16:56:52Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-08-21T13:41:34Z No. of bitstreams: 1 2017_dis_asavela.pdf: 834141 bytes, checksum: 7d55f68b04bdc455d1c717f7a76571de (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde, Ainda há alguns erros na Dissertação de ADRIANO SILVA AVELA que devem ser corrigidos. Eu envie uma cópia desse email para ele, pois contem o anexo com a ficha catalográfica, que não tem como ser enviado aqui pelo repositório. 1- FICHA CATALÓGRAFICA (havia alguns erros na ficha catalográfica, por isso enviamos em anexo a nova ficha para ser inserida no trabalho) 2- RESUMO E ABSTRACT (Retire o recuo do parágrafo na primeira linha do resumo e do abstract. A letra inicial das duas palavras chaves e das Keywords deve ser maiúscula) 3- NUMERAÇÃO DAS PÁGINAS ( o modelo da numeração está coreto, apenas comece com o número 9 na página da INTRODUÇÃO) 4- SUMÁRIO (segue abaixo o modelo do sumário com a formatação adequada, apenas deve ser inserida a numeração das páginas e a linha pontilhada) 1 INTRODUÇÃO 2 ARITMÉTICA DO RESTOS 2.1 A relação de congruência 2.2 Congruências lineares 2.3 Resíduos quadráticos 3 NÚMEROS PRIMOS E SOMAS DE QUADRADOS 4 FUNÇÃO˜ s2 E FUNÇÃO˜ s3 4.1 Função s2 4.2 Função s3 5 SOMA DE DOIS QUADRADOS 6 SOMA DE TRES QUADRADOS 7 CONCLUSÃO REFERÊNCIAS APÊNDICE A - TABELAS DE VALORES APÊNDICE B - RESULTADOS COMPLEMENTARES APÊNDICE C - TEOREMA DOS QUATRO QUADRADOS on 2017-08-21T17:16:15Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-08-22T15:34:15Z No. of bitstreams: 1 2017_dis_asavela.pdf: 833511 bytes, checksum: 0e2b00b8533fc647e6c76928c5de4671 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-08-23T11:09:25Z (GMT) No. of bitstreams: 1 2017_dis_asavela.pdf: 833511 bytes, checksum: 0e2b00b8533fc647e6c76928c5de4671 (MD5) / Made available in DSpace on 2017-08-23T11:09:25Z (GMT). No. of bitstreams: 1 2017_dis_asavela.pdf: 833511 bytes, checksum: 0e2b00b8533fc647e6c76928c5de4671 (MD5) Previous issue date: 2017-07 / This paper aims to address two themes: the representation of positive integers as sum of squares and the average number of representations of a positive integer as the sum of two squares. About the first theme, we will prove several results to understand under what conditions a positive integer has a representation as a sum of two, three or four squares. About the second theme, we will prove that the mean number of representations of a positive integer as the sum of the squares of two integers is . To do so, we will introduce the function s 2 which associates an integer n with the cardinality of the set X n = {( a, b ) ∈ Z 2 ; a 2 + b 2 = n } and we will calculate the limit of its average value. Finally, as an analogy to the result regarding the mean value of s 2 , we will define the function s 3 , that associates a positive integer n with the cardinality of the set Y n = {( a, b, c ) ∈ Z 3 ; a 2 + b 2 + c 2 = n } and we will prove that there is no mean number of representations of a positive integer as the sum of the squares of three integers. / Este trabalho tem como objetivo abordar dois temas: a representação de inteiros positivos como soma de quadrados e o número médio de representações de um inteiro positivo como soma de dois quadrados. Sobre o primeiro tema, provaremos diversos resultados para entender em quais condições um inteiro positivo possui uma representação como soma de dois, três ou quatro quadrados. Sobre o segundo tema, provaremos que um inteiro positivo tem, em média,pi representações como soma dos quadrados de dois inteiros. Para tanto, introduziremos a função s2 (n), que associa um inteiro n com a cardinalidade do conjunto Xn = {(a, b) Z2 ; a2 + b2 = n} e calcularemos o limite do seu valor médio. Por fim, como analogia ao resultado a respeito do valor médio de s2, definiremos uma outra função s3 que associa um inteiro positivo n com a cardinalidade do conjunto Yn = {(a, b, c) Z3 ; a2 + b2 + c2 = n} e provaremos que não existe um número médio de representações de um inteiro positivo como soma dos quadrados de três inteiros.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-11-04T11:39:40Z No. of bitstreams: 2 arquivototal.pdf: 1037710 bytes, checksum: 4e3c7e69a8c60214c05fdcac3db1ec5e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-11-04T11:41:46Z (GMT) No. of bitstreams: 2 arquivototal.pdf: 1037710 bytes, checksum: 4e3c7e69a8c60214c05fdcac3db1ec5e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-04T11:41:46Z (GMT). No. of bitstreams: 2 arquivototal.pdf: 1037710 bytes, checksum: 4e3c7e69a8c60214c05fdcac3db1ec5e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-08-09 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper is a survey on representation of integers as sums of squares for the cases where we have the sum of two, three and four squares. The idea is to study conditions so that we can ensure the representation of numbers that are written as the sum of two and four square. The central focus is the statement of the theorem of Lagrange four squares, although we have gone a little further studying Fermat' s technique of in nite descense and the case n = 3 of Fermat's last theorem. Finally, we work with the development of a didactic sequence that can be used in the nal grades of elementary school and middle school, addressing Chapter 2 of this dissertation. / Este trabalho tem como objetivo fazer uma pesquisa bibliográ fica sobre o tema da representação de inteiros como soma de quadrados, para os casos onde temos soma de dois, três e quatro quadrados. A ideia é estudar condições para que possamos garantir quando um número inteiro positivo poderá ser representado como uma soma de dois e quatro quadrados. O foco central está na demonstração do teorema dos quatro quadrados de Lagrange, apesar de termos ido um pouco adiante estudando a técnica do descenso in nito de Fernat e o caso n=3 do último teorema de Fermat. Por m, trabalhamos com a elaboração de uma sequência didática que pode ser utilizada nas séries nais do ensino fundamental e no ensino médio, cujo conteúdo abordado nesta sequência são os principais teoremas do capítulo 2 que remete a representação de inteiros como soma de quadrados.