Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/23623| Tipo: | Trabalho de conclusão de graduação |
| Título: | Independência e dominação em caminhos: variantes para situações cotidianas |
| Autor(es)/Inventor(es): | Moreira, Roberto Leonie Ferreira |
| Orientador: | Sá, Vinícius Gusmão Pereira de |
| 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. |
| Palavras-chave: | Teoria dos grafos Grafo caminho Graph theory Path graph |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade produtora: | Instituto de Computação |
| Editora: | Universidade Federal do Rio de Janeiro |
| Data de publicação: | 23-Ago-2024 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| RLFMoreira.pdf | 300.12 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.