Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/18176
| Type: | Trabalho de conclusão de graduação |
| Title: | Obtendo concorrência mínima através de ciclos maximais sob a dinâmica de escalonamento por reversão de arestas |
| Other Titles: | Obtaining minimal concurrency through maximal cycles under the dynamics of scaling by edge reversal |
| Author(s)/Inventor(s): | Marciano, Carlos Eduardo Lopes |
| Advisor: | França, Felipe Maia Galvão |
| Co-advisor: | Simonetti, Luidi Gelabert |
| Abstract: | 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. |
| Keywords: | Escalonamento multidimensional Grafos |
| Subject CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::CIRCUITOS ELETRICOS, MAGNETICOS E ELETRONICOS |
| Production unit: | Escola Politécnica |
| Publisher: | Universidade Federal do Rio de Janeiro |
| Issue Date: | Mar-2019 |
| Publisher country: | Brasil |
| Language: | por |
| Right access: | Acesso Aberto |
| Appears in Collections: | Engenharia de Computação e Informação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| monopoli10028018.pdf | 4.16 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.