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/18176| Tipo: | Trabalho de conclusão de graduação |
| Título: | Obtendo concorrência mínima através de ciclos maximais sob a dinâmica de escalonamento por reversão de arestas |
| Título(s) alternativo(s): | Obtaining minimal concurrency through maximal cycles under the dynamics of scaling by edge reversal |
| Autor(es)/Inventor(es): | Marciano, Carlos Eduardo Lopes |
| Orientador: | França, Felipe Maia Galvão |
| Coorientador: | Simonetti, Luidi Gelabert |
| Resumo: | Uma solução algorítmica efetiva para problemas de compartilhamento de recursos em sistemas de alta carga é o algoritmo denominado Escalonamento por Reversão de Arestas, essencialmente provendo algum nível de concorrência ao descrever uma ordem de operação para os nós de um grafo. A concorrência resultante é uma métrica difícil de ser otimizada, tendo em vista que os problemas de decisão associados com a obtenção de seu máximo e mínimo são provadamente NP-completos. Este trabalho propõe uma nova técnica envolvendo ciclos maximais para a obtenção de concorrência mínima, sendo desejável para problemas associados com descontaminação em grafos e teoria musical. Experimentalmente, é mostrado que instâncias razoavelmente grandes do problema de concorrência mínima podem ser resolvidas à otimalidade provada sob tempos aceitáveis de CPU. Este trabalho também recorda diversos conceitos associados com Escalonamento por Reversão de Arestas, coletando algumas de suas aplicações propostas ao longo dos anos. |
| Palavras-chave: | Escalonamento multidimensional Grafos |
| Assunto CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::CIRCUITOS ELETRICOS, MAGNETICOS E ELETRONICOS |
| Unidade produtora: | Escola Politécnica |
| Editora: | Universidade Federal do Rio de Janeiro |
| Data de publicação: | Mar-2019 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Aparece nas coleções: | Engenharia de Computação e Informação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| monopoli10028018.pdf | 4.16 MB | 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.