Independência e dominação em caminhos: variantes para situações cotidianas

Moreira, Roberto Leonie Ferreira

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/23623

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Sá, Vinícius Gusmão Pereira de	-
dc.contributor.author	Moreira, Roberto Leonie Ferreira	-
dc.date.accessioned	2024-09-06T14:10:08Z	-
dc.date.available	2024-09-08T03:00:17Z	-
dc.date.issued	2024-08-23	-
dc.identifier.uri	http://hdl.handle.net/11422/23623	-
dc.language	por	pt_BR
dc.publisher	Universidade Federal do Rio de Janeiro	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Teoria dos grafos	pt_BR
dc.subject	Grafo caminho	pt_BR
dc.subject	Graph theory	pt_BR
dc.subject	Path graph	pt_BR
dc.title	Independência e dominação em caminhos: variantes para situações cotidianas	pt_BR
dc.type	Trabalho de conclusão de graduação	pt_BR
dc.contributor.referee1	Menasché, Daniel Sadoc	-
dc.contributor.referee2	Jardim, Maria Helena Cautiero Horta	-
dc.description.resumo	O presente trabalho analisa algumas situações do cotidiano que podem ser modeladas como problemas de otimização de cardinalidade em alguns conjuntos específicos de uma determinada classe de grafos, com ênfase nos grafos caminho. Em particular, serão investigados o conjunto independente e o conjunto dominante. Diversas variantes serão empregadas para abordar o problema de ocupação de espaços, com o objetivo de, em geral, evitar ocupações consecutivas e, assim, maximizar ou minimizar a cardinalidade desses conjuntos em cada uma delas. Em vez de simplesmente encontrar o maior ou menor subgrafo induzido por um conjunto de vértices com características específicas, serão estabelecidas métricas de interesse que correspondem com fenômenos observados no mundo real, como uma quantidade que mede o desconforto que um indivíduo sente com a proximidade de outros indivíduos. Essas métricas conduzirão a variantes que, embora possam apresentar soluções convergentes, podem divergir em eficiência. Dado que tais fenômenos podem ser modelados como problemas de otimização, eles sugerem funções-objetivo e conjunto de restrições originais. As variantes propostas serão comparadas por meio de experimentações computacionais para determinar qual delas é mais eficiente na modelagem de um simulador de preenchimento destes espaços, de modo a mantê-lo fidedigno às situações do mundo real, permitindo, se necessário, o relaxamento da restrição de evitar ocupar espaços consecutivos, conforme o desejo do usuário.	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto de Computação	pt_BR
dc.publisher.initials	UFRJ	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Ciência da Computação

Files in This Item:

File	Description	Size	Format
RLFMoreira.pdf		300.12 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository