Obtendo concorrência mínima através de ciclos maximais sob a dinâmica de escalonamento por reversão de arestas

Marciano, Carlos Eduardo Lopes

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

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	França, Felipe Maia Galvão	-
dc.contributor.author	Marciano, Carlos Eduardo Lopes	-
dc.date.accessioned	2022-08-05T13:32:12Z	-
dc.date.available	2023-12-21T03:00:21Z	-
dc.date.issued	2019-03	-
dc.identifier.uri	http://hdl.handle.net/11422/18176	-
dc.language	por	pt_BR
dc.publisher	Universidade Federal do Rio de Janeiro	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Escalonamento multidimensional	pt_BR
dc.subject	Grafos	pt_BR
dc.title	Obtendo concorrência mínima através de ciclos maximais sob a dinâmica de escalonamento por reversão de arestas	pt_BR
dc.title.alternative	Obtaining minimal concurrency through maximal cycles under the dynamics of scaling by edge reversal	en
dc.type	Trabalho de conclusão de graduação	pt_BR
dc.contributor.advisorCo1	Simonetti, Luidi Gelabert	-
dc.contributor.referee1	Lucena Filho, Abilio Pereira	-
dc.contributor.referee2	Esperança, Claudio	-
dc.description.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.	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	Escola Politécnica	pt_BR
dc.publisher.initials	UFRJ	pt_BR
dc.subject.cnpq	CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::CIRCUITOS ELETRICOS, MAGNETICOS E ELETRONICOS	pt_BR
dc.embargo.terms	aberto	pt_BR
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

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository