Banca de QUALIFICAÇÃO: CAMILA NASCIMENTO DE OLIVEIRA

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: CAMILA NASCIMENTO DE OLIVEIRA
DATA: 26/10/2012
HORA: 08:00
LOCAL: Sala de reuniões do DIMAp
TÍTULO:

Uma Investigação de Algoritmos Exatos e Metaheurísticos Aplicados ao Nonograma


PALAVRAS-CHAVES:

Nonograma, Busca em Profundidade, Las Vegas, Problema de Satisfação de Restrições, Busca Tabu, Algoritmo Memético.


PÁGINAS: 72
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Sistemas de Computação
ESPECIALIDADE: Arquitetura de Sistemas de Computação
RESUMO:

O Nonograma é um jogo lógico cujo problema de decisão associado é NP-completo. Ele possui aplicação em problemas de identificação de padrões e de compactação de dados, dentre outros. O jogo consiste em determinar uma alocação de cores em pixels distribuídos em uma matriz nXm atendendo restrições em linhas e colunas. Um Nonograma é codificado através de vetores cujos elementos especificam o número de pixels existentes em cada coluna e linha de uma figura, sem especificar suas coordenadas. Este trabalho apresenta abordagens exatas e heurísticas para resolver o Nonograma. A Busca em Profundidade foi uma das abordagens escolhidas por ser um exemplo típico de algoritmo força bruta de fácil implementação. Outra abordagem exata implementada foi um algoritmo de Las Vegas, através do qual se pretende investigar se a aleatoriedade introduzida na Busca em Profundidade traria algum benefício para a solução do problema. O Nonograma também é modelado como um Problema de Satisfação de Restrições e resolvido com um solver. Três abordagens heurísticas são propostas: uma Busca Tabu e dois Algoritmos Meméticos. As abordagens são testadas em diversos casos testes, com o tamanho variando de 8 x 8 a 100 x 100, o que inclui Nonogramas lógicos e aleatórios.


MEMBROS DA BANCA:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA
Interno - 1149561 - MARCO CESAR GOLDBARG
Externo à Instituição - ANTONIO CARLOS GAY THOMÉ - UFRJ
Notícia cadastrada em: 01/11/2012 09:56
SIGAA | Superintendência de Informática - (84) 3215-3148 | Copyright © 2006-2019 - UFRN - sigaa03-producao.info.ufrn.br.sigaa03-producao