Dissertação

A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos

Nesta dissertação é proposto um novo jogo baseado em torres, o Jogo da Torre de Manaus (ToM), sendo uma variação do jogo clássico da Torre de Hanoi (ToH), com restrições nas capacidades dos pinos. Assim, dada uma estrutura com 3 pinos e n discos, o primeiro pino suporta todos os n discos, enquanto...

ver descrição completa

Autor principal: Martins, Lia Alessandra da Silva
Outros Autores: http://lattes.cnpq.br/1657347391123253
Grau: Dissertação
Idioma: por
Publicado em: Universidade Federal do Amazonas 2024
Assuntos:
CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO
Algoritmos
Caminhos
Complexidade computacional
Jogos combinatórios
Teoria dos grafos
Torre de Hanoi
Acesso em linha: https://tede.ufam.edu.br/handle/tede/10521
id oai:https:--tede.ufam.edu.br-handle-:tede-10521
recordtype dspace
spelling oai:https:--tede.ufam.edu.br-handle-:tede-105212024-12-06T05:06:26Z A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos Martins, Lia Alessandra da Silva Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/1657347391123253 http://lattes.cnpq.br/8358219976594707 Moura, Edleno Silva de Zatesk, Leandro Miranda Souza, Simone Dantas de CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO Algoritmos Caminhos Complexidade computacional Jogos combinatórios Teoria dos grafos Torre de Hanoi Nesta dissertação é proposto um novo jogo baseado em torres, o Jogo da Torre de Manaus (ToM), sendo uma variação do jogo clássico da Torre de Hanoi (ToH), com restrições nas capacidades dos pinos. Assim, dada uma estrutura com 3 pinos e n discos, o primeiro pino suporta todos os n discos, enquanto o segundo e o terceiro pinos suportam no máximo n-1 e n-2 discos, respectivamente. O objetivo do jogo consiste em, partindo de uma configuração inicial aleatória, mover todos os discos para o primeiro pino respeitando-se tanto as restrições de capacidade quanto as regras do jogo da ToH, de sempre mover um disco por vez e nunca colocar um disco maior em cima de um menor. Dependendo da configuração inicial, o objetivo pode não ser alcançável, o que resulta em um modelo de grafos não conexo. Assim, é dada a caracterização do grafo da ToM, que modela todas as configurações possíveis do jogo como vértices, e as transições válidas entre elas como arestas. São exploradas propriedades desse grafo, como o número de vértices e de componentes conexas. É, também, proposto um algoritmo para solucionar o jogo quando possível, apresentando-se para isto um algoritmo para decidir se o objetivo é alcançável a partir de uma dada configuração ou não. Adicionalmente, é apresentada uma compilação de modelagem em grafos e aspectos algorítmicos das principais variações da ToH encontradas na literatura. Dentre elas, as Torres de Londres e de Oxford, que eram conhecidas apenas como testes neurocognitivos, são formalizadas neste trabalho como jogos combinatórios. Por fim, é proposta uma formalização da construção recursiva do grafo da ToH, usando-se apenas elementos de Teoria dos Grafos, o que ainda não se conhecia na literatura. In this research, the puzzle game Tower of Manaus (ToM) is proposed, which is a variation of the classic Tower of Hanoi (ToH) with capacity constraints on the pegs. Thus, given a structure with 3 pegs and n disks, the first peg supports all n disks, while the second and third pegs support at most n-1 and n-2 disks, respectively. The goal is, starting from an arbitrary initial configuration, moving all disks to the first peg, respecting both the capacity constraints and the ToH game rules, always moving one disk at a time and never placing a larger disk on top of a smaller one. Depending on the initial configuration, the goal may not be achievable, which results in a nonconnected graph. Thus, the characterization of the ToM graph is given, which models all possible configurations of the game as vertices, and the valid transitions between them as edges. Properties of this graph, such as the number of vertices and connected components, are explored. An algorithm to solve the game when possible is also proposed, presenting an algorithm to decide whether the goal is achievable from a given configuration or not. Additionally, a compilation of graph modeling and algorithmic aspects of the main variations of ToH found in the literature is presented. Among them, the Towers of London and Oxford, which were known only as neurocognitive tests, are formalized as combinatorial games. Finally, a formalization of the recursive construction of the ToH graph is proposed, using only elements of Graph Theory, which was not yet known in the literature. 2024-12-05T22:43:48Z 2024-10-14 Dissertação MARTINS, Lia Alessandra da Silva. A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos. 2024. 98 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus (AM), 2024. https://tede.ufam.edu.br/handle/tede/10521 por Acesso Aberto https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática
institution TEDE - Universidade Federal do Amazonas
collection TEDE-UFAM
language por
topic CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO
Algoritmos
Caminhos
Complexidade computacional
Jogos combinatórios
Teoria dos grafos
Torre de Hanoi
spellingShingle CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO
Algoritmos
Caminhos
Complexidade computacional
Jogos combinatórios
Teoria dos grafos
Torre de Hanoi
Martins, Lia Alessandra da Silva
A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
topic_facet CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO
Algoritmos
Caminhos
Complexidade computacional
Jogos combinatórios
Teoria dos grafos
Torre de Hanoi
description Nesta dissertação é proposto um novo jogo baseado em torres, o Jogo da Torre de Manaus (ToM), sendo uma variação do jogo clássico da Torre de Hanoi (ToH), com restrições nas capacidades dos pinos. Assim, dada uma estrutura com 3 pinos e n discos, o primeiro pino suporta todos os n discos, enquanto o segundo e o terceiro pinos suportam no máximo n-1 e n-2 discos, respectivamente. O objetivo do jogo consiste em, partindo de uma configuração inicial aleatória, mover todos os discos para o primeiro pino respeitando-se tanto as restrições de capacidade quanto as regras do jogo da ToH, de sempre mover um disco por vez e nunca colocar um disco maior em cima de um menor. Dependendo da configuração inicial, o objetivo pode não ser alcançável, o que resulta em um modelo de grafos não conexo. Assim, é dada a caracterização do grafo da ToM, que modela todas as configurações possíveis do jogo como vértices, e as transições válidas entre elas como arestas. São exploradas propriedades desse grafo, como o número de vértices e de componentes conexas. É, também, proposto um algoritmo para solucionar o jogo quando possível, apresentando-se para isto um algoritmo para decidir se o objetivo é alcançável a partir de uma dada configuração ou não. Adicionalmente, é apresentada uma compilação de modelagem em grafos e aspectos algorítmicos das principais variações da ToH encontradas na literatura. Dentre elas, as Torres de Londres e de Oxford, que eram conhecidas apenas como testes neurocognitivos, são formalizadas neste trabalho como jogos combinatórios. Por fim, é proposta uma formalização da construção recursiva do grafo da ToH, usando-se apenas elementos de Teoria dos Grafos, o que ainda não se conhecia na literatura.
author_additional Rodrigues, Rosiane de Freitas
author_additionalStr Rodrigues, Rosiane de Freitas
format Dissertação
author Martins, Lia Alessandra da Silva
author2 http://lattes.cnpq.br/1657347391123253
author2Str http://lattes.cnpq.br/1657347391123253
title A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
title_short A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
title_full A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
title_fullStr A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
title_full_unstemmed A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos
title_sort torre de manaus e outros jogos de torres: propriedades em grafos e algoritmos
publisher Universidade Federal do Amazonas
publishDate 2024
url https://tede.ufam.edu.br/handle/tede/10521
_version_ 1831970383166701568
score 11.753735

Registros relacionados