[pt] A extração de entidades de páginas web é comumente utilizada para melhorar a qualidade de muitas tarefas realizadas por máquinas de busca como detecção de páginas duplicadas e ranking. Essa tarefa se torna ainda mais relevante devido ao crescente volume de informação da internet com as quais as máquinas de busca precisam lidar. Existem diversos algoritmos para detecção de conteúdo na literatura, alguns orientados a sites e outros que utilizam uma abordagem mais local e são chamados de algoritmos orientados a páginas. Os algoritmos orientados a sites utilizam várias páginas de um mesmo site para criar um modelo que detecta o conteúdo relevante da página. Os algoritmos orientados a páginas detectam conteúdo avaliando as características de cada página, sem comparar com outras páginas. Neste trabalho apresentamos um algoritmo, chamado NCE ( News Content Extractor), orientado a página e que se propõe a realizar extração de entidades em páginas de notícias. Ele utiliza atributos de uma árvore DOM para localizar determinadas entidades de uma página de notícia, mais especificamente, o título e o corpo da notícia. Algumas métricas são apresentadas e utilizadas para aferir a qualidade do NCE. Quando comparado com outro método baseado em página e que utiliza atributos visuais, o NCE se mostrou superior tanto em relação à qualidade de extração quanto no que diz respeito ao tempo de execução. / [en] The entity extraction of web pages is commonly used to enhance the quality of tasks performed by search engines, like duplicate pages and ranking. The relevance of entity extraction is crucial due to the fact that search engines have to deal with fast growning volume of information on the web. There are many algorithms that detect entities in the literature, some using site level strategy and others using page level strategy. The site level strategy uses many pages from the same site to create a model that extracts templates. The page level strategy creates a model to extract templates according to features of the page. Here we present an algorithm, called NCE (News Content Extractor), that uses a page level strategy and its objective is to perform entity extraction on news pages. It uses features from a DOM tree to search for certain entities, namely, the news title and news body. Some measures are presented and used to evaluate how good NCE is. When we compare NCE to a page level algorithm that uses visual features, NCE shows better execution time and extraction quality.

Orientador: Maria Aparecida Diniz Ehrhardt / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação / Made available in DSpace on 2018-08-22T06:10:21Z (GMT). No. of bitstreams: 1 Ferreira_DeiseGoncalves_M.pdf: 2631020 bytes, checksum: 45eb84901394375843735b1fdef599ad (MD5) Previous issue date: 2013 / Resumo: Neste trabalho voltamos nossa atenção para métodos de otimização que não fazem uso de derivadas. Dentre esses, estamos interessadas em um método de busca padrão para minimização de funções com restrições lineares. Abordamos um algoritmo proposto por Lewis e Torczon, cuja ideia geral é que o padrão deve conter direções de busca ao longo das quais iterações factíveis sejam determinadas. O algoritmo possui resultados de convergência global. Realizamos sua implementação computacional, e propomos novas estratégias de busca e atualização do tamanho do passo, além de um novo padrão de direções de busca. Realizamos testes numéricos, de modo a analisar o desempenho das estratégias propostas e comparar o desempenho do padrão de direções que introduzimos com o proposto por Lewis e Torczon / Abstract: In this work, our interest lies on derivative-free optimization methods. Among these, our aim is to study a pattern search method for linearly constrained minimization. We studied an algorithm proposed by Lewis and Torsion, whose general idea is that the pattern must contain search directions in which feasible iterations must be computed. The algorithm has global convergence results. We accomplished its computational implementation and we propose new strategies of search and updating rule for the step-length control parameter. We also propose a new pattern of search directions. We accomplished numerical experiments in order to analyze the performance of our proposals and also to compare the performance of our pattern with the one proposed by Lewis and Torczon / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-01-19T13:24:41Z No. of bitstreams: 1 marianadoamaralantunes.pdf: 3509048 bytes, checksum: a42bdfdd5833d65a14b442db72753a74 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-01-25T17:57:59Z (GMT) No. of bitstreams: 1 marianadoamaralantunes.pdf: 3509048 bytes, checksum: a42bdfdd5833d65a14b442db72753a74 (MD5) / Made available in DSpace on 2016-01-25T17:57:59Z (GMT). No. of bitstreams: 1 marianadoamaralantunes.pdf: 3509048 bytes, checksum: a42bdfdd5833d65a14b442db72753a74 (MD5) Previous issue date: 2014-05-21 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta pesquisa tem como objetivo investigar a influência dos mecanismos de busca e demais tecnologias de indexação das redes telemáticas na produção e seleção de conteúdo dentro do ambiente imersivo digital – mais precisamente nos valores-notícia que fazem com que determinado assunto se torne notícia na internet e, posteriormente, na TV. Para tal, analisa, de forma empírica, palavras e termos-chave (keywords) mais buscados no Google e comentados no Twitter com notícias coletadas no Portal G1 e no Jornal Nacional, buscando refletir sobre as possíveis causas que levariam os assuntos comumente buscados e discutidos nessas plataformas a servir como pauta ou não dos veículos online e tradicionais, de acordo com sua relevância e apelo lúdico/social/político/ideológico. Dessa forma, a abordagem do trabalho explorao impacto das tecnologias digitais baseadas em indexação no jornalismo, frente a um meio que se encontra em constante evolução. / This research wanted to investigate the influence of search engines and other indexing technologies of such networks in the production and selection of digital content within the immersive environment - more specifically the news values that make certain issue becomes news on the internet and later on TV. It analyzes, empirically, words and key terms (keywords) most popular searches on Google and Twittered collected with the G1 news portal and the National Journal of Globo TV, trying to reflect on the possible causes that would lead commonly sought and discussed issues these platforms to serve as non-tariff or online and traditional vehicles, according to their relevance and recreational / social / political / ideological appeal. The approach to work explores the impact of digital technologies based indexing in journalism, facing a medium that is constantly evolution.

Concurrent programming has become an essential paradigm for reductions in the computational time in many application domains. However, the validation and testing activity is more complex than the testing for sequential programs due to the non-determinism, synchronization and inter-process communication. Mutation testing is based on mistakes produced by software developers and presents a high effectiveness to reveal faults. However, high computational costs limit its applicability even for sequential code, becoming higher for concurrent programs in which each test has to be executed with different (ideally all) thread schedules. To date, only selective mutation have been applied to reduce the number of mutants in concurrent programs, however, the problem of state explosion of thread schedules still remains. This Ph.D. thesis presents the SBBMuT approach that applies deterministic execution and genetic algorithm for the generation and execution of a set of synchronization sequences during the mutation testing of Java multithreaded programs. An experimental study was conducted, and the results showed that the set of synchronization sequences generated by SBBMuT achieved a higher mutation score in comparison with the use of the Java PathFinder model checking tool. / A programação concorrente tornou-se um paradigma essencial para a redução no tempo computacional em muitos domínios de aplicação. No entanto, as atividades de verificação, validação e teste são mais complexas do que o teste para programas sequenciais devido ao não determinismo, sincronização e comunicação entre processos ou threads. O teste de mutação é baseado em enganos cometidos por desenvolvedores de software e apresenta uma alta eficácia para revelar defeitos. No entanto, o alto custo computacional limita a sua aplicação mesmo para programas sequenciais, e tornando-se maior para programas concorrentes no qual cada teste deve ser executado com diferentes (idealmente todas) sequências de sincronizações. Na literatura, apenas mutação seletiva foi aplicada para reduzir o número de mutantes em programas concorrentes, no entanto, o problema de explosão no número de sequências de sincronização ainda permanece. Esta tese de doutorado apresenta a abordagem SBBMuT que aplica execução determinística e algoritmo genético para a geração e execução de um conjunto de sequências de sincronização durante o teste de mutação para programas Java multithread. Um estudo experimental foi conduzido e os resultados mostram que o conjunto de sequências de sincronização gerada pela SBBMuT conseguiu alcançar um escore de mutação maior em comparação com a utilização da ferramenta de validação de modelos Java PathFinder.

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.

A busca de palavras em uma grande coleção de documentos é um problema muito recorrente nos dias de hoje, como a própria utilização dos conhecidos \"motores de busca\" revela. Para que as buscas sejam realizadas em tempo que independa do tamanho da coleção, é necessário que a coleção seja indexada uma única vez. O tamanho destes índices é tipicamente linear no tamanho da coleção de documentos. A compressão de dados é outro recurso bastante utilizado para lidar com o tamanho sempre crescente da coleção de documentos. A intenção deste estudo é aliar a indexação utilizada nas buscas à compressão de dados, verificando alternativas às soluções já propostas e visando melhorias no tempo de resposta das buscas e no consumo de memória utilizada nos índices. A análise das estruturas de índice com os algoritmos de compressão mostra que arquivo invertido por blocos em conjuntos com compressão Huffman por palavras é uma ótima opção para sistemas com restrição de consumo de memória, pois proporciona acesso aleatório e busca comprimida. Neste trabalho também são propostas novas codificações livres de prefixo a fim de melhorar a compressão obtida e capaz de gerar códigos auto-sincronizados, ou seja, com acesso aleatório realmente viável. A vantagem destas novas codificações é que elas eliminam a necessidade de gerar a árvore de codificação Huffman através dos mapeamentos propostos, o que se traduz em economia de memória, codificação mais compacta e menor tempo de processamento. Os resultados obtidos mostram redução de 7% e 9% do tamanho dos arquivos comprimidos com tempos de compressão e descompressão melhores e menor consumo de memória. / Pattern matching over a big document collection is a very recurrent problem nowadays, as the growing use of the search engines reveal. In order to accomplish the search in a period of time independent from the collection size, it is necessary to index the collecion only one time. The index size is typically linear in the size of document collection. Data compression is another powerful resource to manage the ever growing size of the document collection. The objective in this assignment is to ally the indexed search to data compression, verifying alternatives to the current solutions, seeking improvement in search time and memory usage. The analysis on the index structures and compression algorithms indicates that joining the block inverted les with Huffman word-based compression is an interesting solution because it provides random access and compressed search. New prefix free codes are proposed in this assignment in order to enhance the compression and facilitate the generation of self-sinchronized codes, furthermore, with a truly viable random access. The advantage in this new codes is that they eliminate the need of generating the Huffman-code tree through the proposed mappings, which stands for economy of memory, compact encoding and shorter processing time. The results demonstrate gains of 7% and 9% in the compressed le size, with better compression and decompression times and lower memory consumption.

Submitted by Ricardo Cedraz Duque Moliterno (ricardo.moliterno@uefs.br) on 2015-10-21T00:15:50Z No. of bitstreams: 1 DISSERTA??O EM 22 07 2013 CORRIGIDA_luizdaconceicao_oliveira.pdf: 1138739 bytes, checksum: 5649e6c3db1dc2627d2fa1ef2e3c9528 (MD5) / Made available in DSpace on 2015-10-21T00:15:50Z (GMT). No. of bitstreams: 1 DISSERTA??O EM 22 07 2013 CORRIGIDA_luizdaconceicao_oliveira.pdf: 1138739 bytes, checksum: 5649e6c3db1dc2627d2fa1ef2e3c9528 (MD5) Previous issue date: 2013-06-03 / This thesis aims at presenting a study about writer Rachel de Queiroz. We use her books O Quinze, D?ra, Doralina e Memorial de Maria Moura as the corpus for our research. This study is divided into three steps: first, we deal with the writer?s education, from early childhood, when she learned her first words and was in contact with the writers of 1930?s. Second, we talk about gender based on the protagonists: Concei??o, D?ra, Doralina e Maria Moura. We show these stages through orphanhood, search, space, agreements and disagreements, as recurrent categories in Queiroz?s works. We discuss how these stages contributed to the characters? independence, accomplishments and freedom. / O objetivo desta disserta??o ? apresentar um estudo sobre a escritora Rachel de Queiroz, tendo como corpus suas obras O Quinze, D?ra, Doralina e Memorial de Maria Moura. O trabalho divide-se em tr?s etapas: Na primeira, tratamos da forma??o intelectual da escritora, desde a inf?ncia, quando aprendeu as primeiras letras, bem como seu contato com os escritores de 1930. Na segunda, falamos do g?nero, tendo como base as protagonistas: Concei??o, D?ra, Doralina e Maria Moura. Na terceira, enfocamos os diferentes est?gios das problem?ticas que envolveram as protagonistas. Mostramos estes est?gios atrav?s da orfandade, da busca, do espa?o, dos encontros e desencontros, como categorias recorrentes nas obras da autora. Discutimos como estes est?gios contribu?ram para a independ?ncia, a conquista e a liberdade das personagens.

Orientador: Daniela Renata Cantane / Resumo: Este trabalho utiliza um modelo epidemiológico para analisar o comportamento de crises bancárias que possuem origem em um determinado país e são propagadas para outros países atingindo proporções mundiais. O modelo matemático epidemiológico Suscetíveis, Infectados e Recuperados (SIR) empregado permite simular a dinâmica da crise separando os países em três estados: suscetíveis, infectados e recuperados, em cada instante de tempo, além de prever a extensão da crise. Os parâmetros do modelo são obtidos da literatura para cada país envolvido e a crise segue uma dinâmica diferente dependendo do país de origem. Uma breve descrição da importância dos bancos em nível macroeconônico e suas funções básicas são apresentadas. Também são apresentadas algumas definições desta crise, denominada crise sistêmica, bem como os canais de transmissão de como um banco com problemas financeiros, denominado infectado, transmite esta condição para outro. Considerada a possibilidade de uma crise sistêmica, o Banco Central deve intervir nos bancos com problemas. Esta tarefa pode ser modelada como um problema de controle ótimo inserindo uma variável de controle no modelo SIR, que representa a intervenção do Banco Central, e uma função objetivo, em que o custo dessa intervenção deve ser minimizado. O objetivo deste trabalho é investigar um modelo de otimização aplicado ao risco bancário e propor o método heurístico \textit{Variable Neighbourhood Search} (VNS) para resolução do problema de controle ótimo... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work uses an epidemiological model to analyze the behavior of bank crises that originate in a given country and are propagated to other countries reaching worldwide proportions. The epidemiological mathematical model Susceptible, Infected and Recovered (SIR) used allows to simulate the dynamics of the crisis separating the countries in three states: susceptible, infected and recovered, in each instant of time, in addition to predicting the extent of the crisis. The model parameters are obtained from the literature for each country involved and the crisis follows a different dynamic depending on the country of origin. A brief description of the importance of banks at the macroeconomic level and their basic functions is presented. Some definitions of this crisis, called systemic crisis, are also presented, as well as the transmission channels of how a bank with financial problems, called infected, transmits this condition to another. Considering the possibility of a systemic crisis, the Central Bank must intervene in troubled banks. This task can be xiv modeled as an optimal control problem by inserting a control variable in the SIR model, which represents Central Bank intervention, and an objective function involving the cost of this intervention and must be minimized. The objective of this work is to investigate an optimization model applied to banking risk and propose the Variable Neighborhood Search (VNS) heuristic method to solve the proposed optimal control problem. ... (Complete abstract click electronic access below) / Mestre

[pt] Uma sequência temporal de vetores (vector stream) pode ser modeladacomo uma sequência de pares ((v1, t1). . .(vn, tn)), onde vk é um vetor e tk écarimbo de tempo tais que todos os vetores são da mesma dimensão e tkmenor que tk+1. O problema de busca por similaridade em sequências temporais devetores é definido como: Dado um vetor (de alta dimensão) v e um intervalode tempo T, encontre uma lista ranqueada de vetores, recuperados de umasequência temporal de vetores, que sejam similares a v e que foram recebidosdentro do intervalo de tempo T. Esta dissertação primeiro introduz umafamília de métodos de busca por similaridade em sequências temporais devetores que não dependem da sequência completa, mas se adaptam à medidaque os vetores são incluídos na sequência. Os métodos geram uma sequênciade índices, que são então usados para implementar uma busca aproximadado vizinho mais próximo na sequência temporal de vetores. Em seguida, adissertação descreve uma implementação de um método da família baseado em Hierarchical Navigable Small World graphs. Utilizando esta implementação,a dissertação apresenta uma ferramenta de busca de anúncios classificadosque oferece recuperação de anúncios à medida que usuários continuamentesubmetem novos anúncios. A ferramenta é estruturada em um módulo principale três módulos auxiliares, sendo que o módulo principal é responsável porcoordenar os módulos auxiliares e prover uma interface para o usuário, e osmódulos auxiliares são responsáveis pela codificação dos textos e imagens emvetores, a indexação dos vetores, e o armazenamento dos textos, imagens evetores. Por fim, para avaliar a ferramenta, a dissertação utiliza um conjuntode aproximadamente 1 milhão de registros com as descrições de anúnciosclassificados e suas imagens. Os resultados mostraram que a ferramenta atingiuuma precisão de 98 por cento e um recall de 97 por cento. / [en] A vector stream can be modeled as a sequence of pairs ((v1, t1). . .(vn, tn)), where vk is a vector and tk is a timestamp such that all vectors are of the same dimension and tk less than tk+1. The vector stream similarity search problem is defined as: Given a (high-dimensional) vector q and a time interval T, find a ranked list of vectors, retrieved from a vector stream, that are similar to q and that were received in the time interval T. This dissertation first introduces a family of vector stream similarity search methods that do not depend on having the full set of vectors available beforehand but adapt to the vector stream as the vectors are added. The methods generate a sequence of indices that are used to implement approximated nearest neighbor search over the vector stream. Then, the dissertation describes an implementation of a method in the family based on Hierarchical Navigable Small World graphs. Based on this implementation, the dissertation presents a Classified Ad Retrieval tool that supports classified ad retrieval as new ads are continuously submitted. The tool is structured into a main module and three auxiliary modules, where the main module is responsible for coordinating the auxiliary modules and for providing a user interface, and the auxiliary modules are responsible for text and image encoding, vector stream indexing, and data storage. To evaluate the tool, the dissertation uses a dataset with approximately 1 million records with descriptions of classified ads and their respective images. The results showed that the tool reached an average precision of 98 percent and an average recall of 97 percent.

[pt] Um ponto importante para o sucesso de sistemas de busca por palavras-chave é um mecanismo de ranqueamento que considera a importância dos documentos recuperados. A noção de importância em grafos é tipicamente computada usando medidas de centralidade, que dependem amplamente do grau dos nós, como o PageRank. Porém, em grafos RDF, a noção de importância não é necessariamente relacionada com o grau do nó. Sendo assim, esta tese aborda dois problemas: (1) como definir uma medida de importância em grafos RDF; (2) como usar essas medidas para ajudar a compilar e ranquear respostas a consultas por palavras-chave sobre grafos RDF. Para resolver estes problemas, esta tese propõe uma nova família de medidas, chamada de InfoRank, e um sistema de busca por palavras-chave, chamado QUIRA, para grafos RDF. Esta tese é concluída com experimentos que mostram que a solução proposta melhora a qualidade dos resultados em benchmarks de busca por palavras-chave. / [en] A key contributor to the success of keyword search systems is a ranking mechanism that considers the importance of the retrieved documents. The notion of importance in graphs is typically computed using centrality measures that highly depend on the degree of the nodes, such as PageRank. However, in RDF graphs, the notion of importance is not necessarily related to the node degree. Therefore, this thesis addresses two problems: (1) how to define importance measures for RDF graphs; (2) how to use these measures to help compile and rank results of keyword queries over RDF graphs. To solve these problems, the thesis proposes a novel family of measures, called InfoRank, and a keyword search system, called QUIRA, for RDF graphs. Finally, this thesis concludes with experiments showing that the proposed solution improves the quality of the results in two keyword search benchmarks.