41 |
Proposta de um agente para o jogo de dominó de 4 pontas utilizando o algoritmo expectiminimaxSilva, Endrews Sznyder Souza da 04 September 2015 (has links)
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:37:59Z
No. of bitstreams: 1
Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:38:31Z (GMT) No. of bitstreams: 1
Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:39:45Z (GMT) No. of bitstreams: 1
Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Made available in DSpace on 2016-06-06T19:39:45Z (GMT). No. of bitstreams: 1
Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5)
Previous issue date: 2015-09-04 / Não informada / Dominoes game is played by millions of people around Brazil and entire world. People usually play this game during family meetings, with friends and in universities. Dominoes game does not have universal version and rules, the way it is played can vary according its region. Although dominoes' version diversity, this game is simple. Dominoes game to is an incomplete information and non-deterministic type. Uncertainty and stochastic characteristic of this game make it difficult to solve by applying artificial intelligence techniques. Thus, this thesis proposes an agent for four-sided dominoes. This dominoes' version is played in Amazonas state. The proposed agent is based on partial expectiminimax algorithm. Partially searching the game tree generates horizon effect, and to reduce it, phase related search will be used in each round phase. Moreover, due to chance events it will be necessary probability modeling to obtain opponent's moves probability values. This thesis proposes eight strategies, which differ from each other in depth search through a round. Each strategy is evaluated against a pair, which uses the basic one and pair with strategy based on genetic algorithm. The best strategy is this work obtained 72,04% of victories in 5000 matches against the basic one, and 58,34% of victories against the strategy based on genetic algorithm. / O jogo de dominó é praticado por milhões de pessoas pelo Brasil e no mundo. As pessoas costumam praticar este jogo em reuniões familiares, círculos de amigos e nas universidades. O jogo de dominó não possui uma versão e regras universais, podendo variar de acordo com a região em que é praticado. Apesar de suas diversas variações, este jogo é simples de jogar. O dominó é um jogo de informação incompleta e não determinístico. As incertezas e a característica estocástica o fazem um jogo complexo de solucionar com as metodologias existentes na área de inteligência artificial. Nesse sentido, esta dissertação propõe uma agente para o jogo de dominó de 4 pontas. Esta versão do jogo de dominó é praticada no Amazonas. O agente proposto é baseado no algoritmo de busca expectiminimax com busca parcial. A busca parcial tem como consequência o efeito de horizonte, e para atenuar este efeito será realizada uma busca por fases dentro de uma rodada. Além disso, devido à presença dos eventos de chance nesse jogo será necessária a modelagem probabilística para os mesmos. Neste trabalho foram definidas oito estratégias com profundidades diferentes em cada fase das rodadas. Cada estratégia será testada contra a estratégia básica de jogo e contra o melhor resultado obtido pela estratégia que utiliza algoritmos genéticos. A melhor estratégia deste trabalho obteve 72,04% de vitórias em 5000 partidas, contra a estratégia básica de jogo. Contra a melhor estratégia que utiliza algoritmos genéticos o percentual de vitorias foi de 58,34 %.
|
42 |
Método do ponto proximal inexato e uma técnica de busca linear não monótona para otimização irrestritaLima, Suellen Paulino 15 December 2015 (has links)
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:39:28Z
No. of bitstreams: 1
Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:39:51Z (GMT) No. of bitstreams: 1
Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-08T19:40:06Z (GMT) No. of bitstreams: 1
Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5) / Made available in DSpace on 2016-06-08T19:40:06Z (GMT). No. of bitstreams: 1
Dissertação - Suellen Paulino Lima.pdf: 623720 bytes, checksum: 10d03fee1aa131fb068db1c244116b29 (MD5)
Previous issue date: 2015-12-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper shows algorithms for problem solving
Unrestricted. Initially it will address the Proximal Point Algorithm Inaccurate
using classical algorithms for solving the problem of
regularization of convex function, continuously differentiable and decisive
the Hessian near zero. Then the Search Algorithm
Nonlinear monotone that aims to improve the likelihood of
find a global optimum, using traditional methods to decrease
obtaining the step size, moreover, they can improve the speed of
convergence in specific cases of monotonous scheme. At the end we will
implementation of quadratic functions and analysis of results / Apresentaremos neste trabalho algoritmos para resolução de problemas
irrestritos. Inicialmente será abordado o Algoritmo do Ponto Proximal Inexato
com a utilização de algorítimos clássicos para resolução do problema de
regularização da função convexa, continuamente diferenciável e com determinante
da hessiana próximo de zero. Em seguida, o Algoritmo de Busca
Linear não monótona que tem o objetivo de melhorar a probabilidade de
encontrar um ótimo global, utilizando métodos de descida tradicionais para
obter o tamanho do passo, além disso, eles podem melhorar a velocidade de
convergência em casos específicos do esquema monótono. Ao final faremos a
implementação de funções quadráticas e a análise dos resultados obtidos
|
43 |
Métodos de Poda Estática para Índices de Máquina de BuscaSilva, Francisca Sancha Azevedo da 27 July 2009 (has links)
Made available in DSpace on 2015-04-11T14:03:13Z (GMT). No. of bitstreams: 1
DISSERTACAO.pdf: 487136 bytes, checksum: a15e0d0fd4eafc6664cf921aa9c18433 (MD5)
Previous issue date: 2009-07-27 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Métodos de poda de índices têm sido propostos a fim de melhorar a eficiência de máquinas de busca. Nos métodos de poda estática, as entradas do índice que têm pouca contribuição para ordenação das respostas são descartadas, reduzindo o tempo de acesso ao índice. Neste trabalho é realizado um estudo sobre métodos de poda estática e são propostos dois métodos.O primeiro método proposto leva em consideração a raridade dos termos do vocabulário para realizar a poda. Este método é apropriado para coleções que possuam grande incidência de termos raros nas consultas e um vocabulário com os tamanhos dos termos não concentrado em faixas de tamanho específicas. O segundo método proposto é apropriado para coleções onde os termos das consultas têm baixos valores de idf (inverse document frequency) e baseia-se no tamanho dos termos de logs de consultas para realizar a poda. Os resultados apresentados foram satisfatórios e podem ser aplicados a coleções com as características das estudadas neste trabalho.
|
44 |
Perspectivas para eliminação da malária residual em área rural da Amazônia brasileira: estratégia de busca ativa reativa na identificação de reservatórios de Plasmodium vivax. / Prospects for residual malaria elimination in rural Brazilian Amazon: strategy of reactive case detection for surveillance Plasmodium vivax in reservoir hosts.Pablo Secato Fontoura 09 December 2016 (has links)
Casos de malária no Brasil atingiu seu nível mais baixo em 35 anos e o Plasmodium vivax é responsável por 85% dos casos em todo o país. A vigilância epidemilógica da transmissão residual da malária persistente na Amazônia é o próximo grande desafio para os esforços vigentes de eliminação. Esta situação nos levou a avaliar uma estratégia para detecção de portadores do parasito (sintomáticos ou não) em áreas que se aproximam a eliminação da malária. Nossa hipótese é que o monitoramento sistemático de moradores de domicílios com um ou mais casos de malária vivax clínica confirmados pela vigilância passiva de rotina (referido como casos índices) e seus vizinhos tem um melhor custo-benecífio na identificação de novas infecções em relação aos inquéritos em massa da população em geral. Para testar essa hipótese, foram recrutados 41 casos índices (24 indivíduos classificados como autóctones, 11 como possíveis recaídas e, seis como casos importados), 163 moradores dos domicílios índices (indivíduos morando na mesma residência do caso índice), 878 moradores vizinhos (moradores de domicílios a um raio de < 3 km) e 841 controles (moradores da mesma localidade, porém a > 5 km de distância do domicílio índice) entre os meses de fevereiro a julho de 2013. Participantes residiam em comunidades rurais pertencentes a Acrelândia, onde o P. vivax é a única espécie implicada na transmissão da malária humana. Todos os participantes foram convidados a fornecerem amostra de sangue capilar para realização do diagnóstico para malária no momento de identificação do caso índice (dia 0), 30, 60 e 180 dias após a primeira visita. Em geral, 6028 análises por microscopia revelaram um aumento na prevalência de malária nos domicílios índices (6,1%; odds ratio [OR] = 36,3, P < 0,001) e vizinhos (2,6%; OR = 13,6, P < 0,001) comparados aos controles (0,1%). Não houve casos positivos para P. falciparum. Moradores dos domicílios índices e vizinhos foram associados com uma maior probabilidade de infecção pelo P. vivax em comparação com os indivíduos controles, após análise ajustada por potenciais confundidores (modelos de regressão logística para efeitos mistos), além desses participantes albergarem > 90% da biomassa parasitária circulante. Nos quatro seguimentos da RCD a microscopia identificou somente 49,5% das infecções diagnosticadas por qPCR, porém 76,8% do total da carga parasitária circulante nas proximidades do domicílio índice. Embora, moradores dos domicílios controles foram responsáveis por 27,6% das amostras positivas por qPCR, 92,6% desses indivíduos eram portadores assintomáticos da infecção, que provavelmente não seriam alvos da RCD. Tipagem molecular dos parasitos utilizando três marcadores polimórficos - msp1F3, MS16 e pv3.27 revelaram alta diversidade de P. vivax, consistente com a complexidade das vias de transmissão e múltiplas fontes de infecção dentro dos aglomerados, potenciais complicações para os programas de eliminação de malária. / Malaria burden in Brazil has reached its lowest levels in 35 years and Plasmodium vivax now accounts for 85% of cases countrywide. The epidemiological surveillance residual malaria transmission entrenched in the Amazon is the next major challenge for ongoing elimination efforts. This situation prompted us to evaluate a strategy for targeted detection of parasite carriers (either symptomatic or asymptomatic) in areas approaching malaria elimination. We hypothesize that repeated screening of households (HHs) with one or more slide-confirmed clinical vivax malaria cases diagnosed by routine passive surveillance (referred to as index cases) and their neighbors is more cost-effective for finding new malaria infections than population-wide mass blood surveys. To test this hypothesis, we recruited 41 index cases (24 subjects classified with indigenous, 11 possible relapsing and 6 cases imported) 163 index household members (subjects sharing the household with index cases), 878 neighbors (subjects living within a radius of up to 3 km from index cases) and 841 controls (subjects living in the same locality, but > 5 km from the index case) between January and July 2013. Study participants lived in rural communities surrounding Acrelândia town, where P. vivax is the only malaria parasite diagnosed in humans. They were invited to contribute finger-prick blood samples, for laboratory diagnosis of malaria, at the time of index case diagnosis (day 0) and 30, 60, and 180 days later. Overall, 6,028 microscopical analysis revealed an increased prevalence of infection in index households (6.1%; odds ratio [OR] = 36.3, P < 0.001) and neighbors (2.6%; OR = 13.6, P < 0.001) compared to controls (0.1%). There were no positive cases for P. falciparum. Subjects in index and neighbor households were significantly more likely to be parasitemic than control households members, after adjusting for potential confounders (mixed-effects logistic regression models), and together harbored > 90% of the P. vivax biomass in study subjects. Four rounds of microscopy-based RCD would identify only 49.5% of the infections diagnosed by qPCR, but 76.8% of the total parasite biomass circulating in the proximity of index HHs. However, control HHs accounted for 27.6% of qPCR-positive samples, 92.6% of them from asymptomatic carriers who were beyond the reach of RCD. Molecular genotyping analysis of parasites with three polymorphic molecular markers (msp1F3, MS16, and Pv3.27) revealed high P. vivax diversity, consistent with complex transmission networks and multiple sources of infection within clusters, potentially complicating malaria elimination efforts.
|
45 |
Comportamento de busca da informação ambiental por pesquisadores da área de meio ambienteSantos, Fernando Bittencourt dos [UNESP] 06 November 2008 (has links) (PDF)
Made available in DSpace on 2014-06-11T19:26:44Z (GMT). No. of bitstreams: 0
Previous issue date: 2008-11-06Bitstream added on 2014-06-13T20:34:32Z : No. of bitstreams: 1
santos_fb_me_mar.pdf: 809380 bytes, checksum: 7658ccae5a3373b47c194e7a99f23b85 (MD5) / Universidade Estadual Paulista (UNESP) / A questão ambiental ocupa um importante espaço na sociedade e vem crescendo cada vez mais em abrangência. Uma das características da área de meio ambiente é que esta apresenta facetas de difícil controle, por ser multi e interdisciplinar. A informação produzida e utilizada nesta área encontra-se dispersa em diversas fontes. Dessa forma, o comportamento de busca da informação ambiental por pesquisadores da área faz-se pertinente. A pesquisa teve como objetivo principal a análise do comportamento de busca e uso da informação ambiental por parte dos pesquisadores de duas instituições vinculados a programas de pós-graduação da área de Ecologia. Objetivou-se ainda caracterizar a informação ambiental, incluindo aspectos históricos e atuais, enfocando o contexto brasileiro, delinear o perfil dos pesquisadores-usuários da informação ambiental, identificar os hábitos de busca e as fontes de informação consideradas fundamentais. Utilizou-se uma metodologia quantitativa e descritiva e os dados foram obtidos através de questionário contendo perguntas abertas, semi-abertas e fechadas. Constatou-se que os pesquisadores da área de meio ambiente, tanto de mestrado, quanto de doutorado, apresentam um comportamento de busca e uso da informação independente, não necessitando necessariamente de intermediários para a realização da busca por informação e estes apresentam aspectos similares e diferentes no que concerne a esse comportamento. Espera-se que este estudo possa trazer significativas contribuições ao campo da Ciência da Informação, em especial a linha de Organização da Informação e que suscite outras discussões sobre este tema. / The environmental issue occupies an important place in society and is growing increasingly in scope. One of the characteristics of environment area is that it presents facets difficult to control, to be multi and interdisciplinary. The information produced and used in this area is scattered in various sources. Thus, the study of the conduct of search of environmental information by researchers in the field it is relevant. The research was aimed primarily at examining the conduct of search of environmental information by researchers from both institutions linked to postgraduate programmes in the ecology area. The objective was to further characterize the environmental information, including current and historical aspects, focusing on the Brazilian context, outlining the profile of researchers-users of environmental information, identify patterns of search and sources of information considered essential. We used a descriptive and quantitative methodology and data were obtained through a questionnaire containing questions open, semi-open and closed. It was found that researchers in the field of environment, both master's or a doctorate, presenting a performance of search and use of independent information, not necessarily requiring an intermediary to conduct the search for information and they have similar and different aspects in relation to this behavior.It is hoped that this study could bring significant contributions to the field of Information Science, in particular the line of Organization of information and that raises further discussions on this subject.
|
46 |
[pt] BUSCA DO CONSUMIDOR NO VAREJO DE GASOLINA BRASILEIRO / [en] CONSUMER SEARCH IN BRAZILIAN GASOLINE RETAILBARBARA FERNANDES INTROPIDI 03 May 2022 (has links)
[pt] Este trabalho procura entender padrões de busca do consumidor e se fricções informacionais desempenham um papel na dispersão de preços no varejo
brasileiro de gasolina. Na nossa abordagem, os consumidores devem se engajar
em busca custosa para obter informação sobre os preços cobrados pelos postos de gasolina. Empiricamente, dividimos nossa análise em duas partes. Na
primeira, utilizamos um modelo estrutural que nos permite estimar pontos da
distribuição dos custos de busca. Estimamos o modelo usando dados de preços
no nível do posto para vários mercados no Brasil. Na segunda parte, em duas
análises independentes, investigamos os determinantes da proporção de consumidores com baixa quantidade de busca por OLS e construímos uma estimativa
para o custo médio de busca por mercado encaixando nossas estimativas pontuais em uma distribuição paramétrica por NLS. Nossas descobertas revelam
uma variação significativa na busca do consumidor entre os mercados. Além
disso, nossos resultados revelam que a maioria dos consumidores não compara
muitos preços antes de comprar gasolina. Ademais, nossas estimativas indicam
que o número de postos de gasolina em um mercado, a distância média entre os
postos, a renda e a população são fatores importantes para explicar a proporção de consumidores que procuram em apenas um posto antes de comprar. Por
fim, o custo médio estimado de busca representa 3 por cento dos preços da gasolina,
proporção esta não desprezível. Portanto, os resultados indicam que os atritos
de informação são importantes para explicar a dispersão de preços no varejo
brasileiro de gasolina. / [en] This paper seeks to understand consumer search patterns and whether
information frictions play a role in price dispersion in Brazilian gasoline retail.
In our setting, consumers must engage in costly search to gain information
about the prices charged by gas stations. Empirically, we divide our analysis
into two parts. In the first part, we use a structural model that permits us to
estimate points of the distribution of search costs. We estimate the model using
price data at the station level for multiple markets in Brazil. In the second part,
in two independent analyzes, we investigate the determinants of the proportion
of consumers with a low amount of search by OLS and construct an estimate
for the average search cost per market by fitting our point estimates into a
parametric distribution by NLS. Our findings reveal significant variation in
consumer search across markets. Furthermore, our results reveal that most
consumers do not compare many prices before buying gasoline. Moreover, our
estimates indicate that the number of gas stations in a market, the average
distance between gas stations, income, and population are important drivers of
the proportion of consumers that search in only one gas station before buying.
Finally, the estimated average search cost represents 3 percent of gasoline prices,
a non-negligible proportion. Therefore, the results indicate that information
frictions are important to explain price dispersion in Brazilian gasoline retail.
|
47 |
Métodos de busca em coordenada / Coordinate descent methodsSantos, Luiz Gustavo de Moura dos 22 November 2017 (has links)
Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais. / Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.
|
48 |
Findability: elementos essenciais para as formas de encontro da informação em bibliotecas digitaisLandshoff, Renate 19 November 2011 (has links)
Made available in DSpace on 2016-04-29T14:23:04Z (GMT). No. of bitstreams: 1
Renate Landshoff.pdf: 3875996 bytes, checksum: a0da1263d095248a5d6973fb7cd4e325 (MD5)
Previous issue date: 2011-11-19 / This study aims to recommend key elements which impact the ways to find information in digital library environments, including features found in Web 2.0. The theory is based on the concept of Findability, coined by Morville, on the significant contribution of Manovich, on Santaella‟s study about cognitive profiles of readers and Internet users, and on Weinberg and Cunha‟s view on the mission of digital libraries. The development of this work is based on the method of qualitative case studies, highlighting positive and negative aspects of search interfaces from elements considered relevant to digital library projects and identified with the contribution of concepts brought from Library and Information Science. The study emphasizes the contribution of digital libraries for Web search, without however fail to point to their weaknesses and need for evolution. The processing of information at the time of data entry, the development of more intelligent search interfaces, the different cognitive profiles of users, the participation of multidisciplinary teams and constant monitoring of the digital environment elements must be considered and pursued over the existence of a design of this profile. The study points out finally the changes that must occur in searching from the Semantic Web and the development of artificial intelligence, impacting the way we are used to seek information, continually increasing its "findability." / Este estudo tem por objetivo recomendar elementos essenciais que impactam as formas de encontro da informação em ambientes de bibliotecas digitais, incluindo as funcionalidades encontradas na Web 2.0. A fundamentação teórica está baseada no conceito de Findability, cunhado por Morville, na contribuição expressiva de Manovich, no estudo de Santaella sobre os perfis cognitivos de leitores e internautas e na visão de Weinberg e Cunha sobre a missão de bibliotecas digitais. O desenvolvimento deste trabalho está baseado no método de estudos de casos qualitativos, ressaltando aspectos positivos e negativos de interfaces de busca a partir de elementos considerados relevantes para projetos de bibliotecas digitais e identificados com a contribuição de conceitos trazidos da área de Biblioteconomia e Ciência da Informação. O estudo destaca a contribuição das bibliotecas digitais para a pesquisa na Web, sem no entanto deixar de apontar para as suas fragilidades e necessidade de evolução. O tratamento da informação no momento da entrada de dados, o desenvolvimento de interfaces de busca mais inteligentes, os diversos perfis cognitivos de usuários, a participação de equipes multidisciplinares e o monitoramento constante do ambiente digital devem ser elementos considerados e perseguidos ao longo da existência de um projeto deste perfil. O estudo destaca por fim, as mudanças que devem ocorrer com a busca a partir da Web Semântica e o desenvolvimento da inteligência artificial, impactando na forma como estamos acostumados a buscar a informação, aumentando cada vez mais a sua encontrabilidade
|
49 |
[en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM / [pt] MATEURÍSTICAS PARA VARIANTES DO PROBLEMA DO CONJUNTO DOMINANTEMAYRA CARVALHO ALBUQUERQUE 14 June 2018 (has links)
[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas
afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.
|
50 |
Characterizing and modeling visual persistence, search strategies and fixation timesAmor, Tatiana María Alonso January 2017 (has links)
AMOR, T. M. A. Characterizing and modeling visual persistence, search strategies and fixation times. 2017. 114 f. Tese (Doutorado em Física) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Pós-Graduação em Física (posgrad@fisica.ufc.br) on 2017-04-05T18:55:10Z
No. of bitstreams: 1
11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5) / Rejected by Giordana Silva (giordana.nascimento@gmail.com), reason: Boa tarde Ana cleide,
Fiz algumas alterações. Só não consegui deletar o arquivo anexado a fim de renomeá-lo. Isto porque o arquivo,conforme as orientações daquele guia, deverá ter a seguimte nomenclatura: 2017_tese_tmaamor
O co-orientador é aquele que está no registro? Pergunto isso porque procurei o nome no trabalho e não localizei.
Estou concluindo o manual e já lhe envio.
on 2017-04-05T19:39:41Z (GMT) / Submitted by Pós-Graduação em Física (posgrad@fisica.ufc.br) on 2017-04-07T16:49:43Z
No. of bitstreams: 1
11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5) / Approved for entry into archive by Giordana Silva (giordana.nascimento@gmail.com) on 2017-04-07T18:13:24Z (GMT) No. of bitstreams: 1
11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5) / Made available in DSpace on 2017-04-07T18:13:24Z (GMT). No. of bitstreams: 1
11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5)
Previous issue date: 2017 / To gather information from the world around us, we move our eyes constantly. In different
occasions we find ourselves performing visual searches, such as trying to find someone in a
crowd or a book in a shelf. While searching, our eyes “jump” from one location to another
giving rise to a wide repertoire of patterns, exhibiting distinctive persistent behaviors.
Initially, by focusing on saccadic directions and intersaccadic angles, we disclose that the
probability distributions of these measures show a clear preference of participants towards a
reading-like mechanism (geometrical persistence), whose features and potential advantages
for searching/foraging are discussed.We then perform a Multifractal Detrended Fluctuation
Analysis (MF-DFA) over the time series of jump magnitudes in the eye trajectory and find
that it exhibits a typical multifractal behavior arising from the sequential combination
of saccades and fixations. By inspecting the time series composed of only fixational
movements, our results reveal instead a monofractal behavior with a Hurst exponent
H ∼ 0.7, which indicates the presence of long-range power-law positive correlations
(statistical persistence). Motivated by the experimental findings from the study of the
distribution of the intersaccadic angles, we developed a simple visual search model that
quantifies the wide variety of possible search strategies. From our experiments we know
that when searching a target within an image our brain can adopt different strategies. The
question then is which one does it choose? We present a simple two-parameter visual search
model (VSM) based on a persistent random walk and the experimental inter-saccadic
angle distribution. The model captures the basic observed visual search strategies that
range from systematic or reading-like to completely random. We compare the results
of the model to the experimental data by measuring the space-filling efficiency of the
searches. Within the parameter space of the model, we are able to quantify the strategies
used by different individuals for three searching tasks and show how the average search
strategy changes along these three groups. Even though participants tend to explore a vast
range of parameters, when all the items are placed on a regular lattice, participants are
more likely to perform a systematic search, whereas in a more complex field, the search
trajectories resemble a random walk. In this way we can discern with high sensitivity
the relation between the visual landscape and the average strategy, disclosing how small
variations in the image induce strategy changes. Finally, we move beyond visual search
and study the fixation time distributions across different visual tasks. Fixation times are
commonly associated to some cognitive process, as it is in this instances where most of the
visual information is gathered. However, the distribution for the fixation durations exhibits
certain similarities across a wide range of visual tasks and foveated species. We studied
how similar these distributions are, and found that, even though they share some common
properties, such as similar mean values, most of them are statistically different. Because
fixations durations can be controlled by two different mechanisms: cognitive or ocular, we
focus our research into finding a model for the fixation times distribution flexible enough
to capture the observed behaviors in experiments that tested these concepts. At the same
time, the candidate function to model the distribution needs to be the response of some
very robust inner mechanism found in all the aforementioned scenarios. Hence, we discuss
the idea of a model based on the microsacaddic inter event time statistics, resulting in the
sum of Gamma distributions, each of these related to the presence of a distinctive number
of microsaccades in a fixation. / To gather information from the world around us, we move our eyes constantly. In different
occasions we find ourselves performing visual searches, such as trying to find someone in a
crowd or a book in a shelf. While searching, our eyes “jump” from one location to another
giving rise to a wide repertoire of patterns, exhibiting distinctive persistent behaviors.
Initially, by focusing on saccadic directions and intersaccadic angles, we disclose that the
probability distributions of these measures show a clear preference of participants towards a
reading-like mechanism (geometrical persistence), whose features and potential advantages
for searching/foraging are discussed.We then perform a Multifractal Detrended Fluctuation
Analysis (MF-DFA) over the time series of jump magnitudes in the eye trajectory and find
that it exhibits a typical multifractal behavior arising from the sequential combination
of saccades and fixations. By inspecting the time series composed of only fixational
movements, our results reveal instead a monofractal behavior with a Hurst exponent
H ∼ 0.7, which indicates the presence of long-range power-law positive correlations
(statistical persistence). Motivated by the experimental findings from the study of the
distribution of the intersaccadic angles, we developed a simple visual search model that
quantifies the wide variety of possible search strategies. From our experiments we know
that when searching a target within an image our brain can adopt different strategies. The
question then is which one does it choose? We present a simple two-parameter visual search
model (VSM) based on a persistent random walk and the experimental inter-saccadic
angle distribution. The model captures the basic observed visual search strategies that
range from systematic or reading-like to completely random. We compare the results
of the model to the experimental data by measuring the space-filling efficiency of the
searches. Within the parameter space of the model, we are able to quantify the strategies
used by different individuals for three searching tasks and show how the average search
strategy changes along these three groups. Even though participants tend to explore a vast
range of parameters, when all the items are placed on a regular lattice, participants are
more likely to perform a systematic search, whereas in a more complex field, the search
trajectories resemble a random walk. In this way we can discern with high sensitivity
the relation between the visual landscape and the average strategy, disclosing how small
variations in the image induce strategy changes. Finally, we move beyond visual search
and study the fixation time distributions across different visual tasks. Fixation times are
commonly associated to some cognitive process, as it is in this instances where most of the
visual information is gathered. However, the distribution for the fixation durations exhibits
certain similarities across a wide range of visual tasks and foveated species. We studied
how similar these distributions are, and found that, even though they share some common
properties, such as similar mean values, most of them are statistically different. Because
fixations durations can be controlled by two different mechanisms: cognitive or ocular, we
focus our research into finding a model for the fixation times distribution flexible enough
to capture the observed behaviors in experiments that tested these concepts. At the same
time, the candidate function to model the distribution needs to be the response of some
very robust inner mechanism found in all the aforementioned scenarios. Hence, we discuss
the idea of a model based on the microsacaddic inter event time statistics, resulting in the
sum of Gamma distributions, each of these related to the presence of a distinctive number
of microsaccades in a fixation.
|
Page generated in 0.0386 seconds