Use este identificador para citar ou linkar para este item: http://riu.ufam.edu.br/handle/prefix/4848
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisor1Rosiane de Freitas Rodrigues-
dc.creatorAyan Perez de Abeu-
dc.date.accessioned2016-09-23T15:54:56Z-
dc.date.available2016-09-23T15:54:56Z-
dc.date.issued2015-07-31-
dc.identifier.urihttp://riu.ufam.edu.br/handle/prefix/4848-
dc.description.resumoEste projeto de pesquisa envolve problemas clássicos em grafos bem resolvidos computacionalmente, ou seja, problemas pertencentes à classe P de complexidade computacional, para os quais existe pelo menos um algoritmo para cada problema que o resolve na otimalidade em tempo polinomial de processamento. Exemplos de tais problemas clássicos são: problema da árvore geradora mínima (do inglês, minimum spanning tree); prolema do emparelhamento máximo (do inglês, maximum matching); problema do caminho mínimo (do inglês, shortest path problem); dentre váios outros. O interesse deste projeto é o de investigar variações de tais problemas que envolvem restrições adicionais, ou seja, variantes sob restrições disjuntivas, positivas ou negativas. Isto envolve o levantamento dos resultados existentes para diversas classes de grafos existentes, bem como grafos cíclicos, bipartidos, completos, caminhos, entre outros, com o intuito de se refazer provas, algoritmos e de encontrar um ponto de contribuição. Um grafo é um par ordenado G=(V,E), onde V é um conjunto de n elementos denominados de vértices, e E é um conjunto de m pares não ordenados de elementos de V, denominados de arestas. Restrições disjuntivas em problemas clássicos em teoria dos grafos podem ser do tipo negativas ou positivas. Onde as restrições disjuntivas negativas obedecem a regra de que há incompatibilidade entre um par de arestas, e que esse par de arestas não podem pertencer simultaneamente a uma solução viável. E as restrições disjuntivas positivas respeitam o princípio de que pelo menos uma aresta de um dado par de arestas proposto devem compor uma solução viável. Partindo dos conceitos apresentados é comum de se ver problemas modelados nesses tipos de estruturas, tal como o problema de casamentos estáveis, que consiste em casar n homens com n mulheres de modo que cada homem ordene as n mulheres em ordem de preferência, e cada mulher faça o mesmo com os homens. E um casamento (homem, mulher) é denominado estável se não está incluso no conjunto dos pares (homem, mulher) onde a mulher prefere o homem à seu esposo atual, e o homem prefere a mulher à sua esposa atual. Para esse problema existe um algoritmo de Gale-Shapley, que encontra um casamento particular em tempo polinomial tal que pode ser especificado. Além desse problema, existem inúmeros outros que se modelam com essa estrutura de grafos com restrições disjuntivas, tal como casamentos estáveis com casais proibidos [FONSECA, 2000], colocação de professores [TOMÀS, 2005], programação de operações com restrições disjuntivas, entre outros.pt_BR
dc.description.sponsorshipCNPQpt_BR
dc.formatPDF-
dc.languagept_BRpt_BR
dc.publisherUniversidade Federal do Amazonaspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentCiências da Computaçãopt_BR
dc.publisher.departmentInstituto de Ciências Exataspt_BR
dc.publisher.programPROGRAMA PIBIC 2014pt_BR
dc.publisher.initialsUFAMpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmos-
dc.subjectOtimização combinatóriapor
dc.subjectTeoria dos grafospor
dc.subject.cnpqCIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃOpt_BR
dc.titleSobre problemas clássicos em grafos sob restrições disjuntivaspt_BR
dc.typeRelatório de Pesquisapt_BR
dc.pibic.cursoCiência da Computaçãopt_BR
dc.pibic.nrprojetoPIB-E/0206/2014-
dc.pibic.projetoSobre problemas clássicos em grafos sob restrições disjuntivas-
dc.pibic.dtinicio2014-08-01-
dc.pibic.dtfim2015-07-31-
Aparece nas coleções:Relatórios finais de Iniciação Científica - Ciências Exatas e da Terra

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Ayan Perez de Abeu.pdf212,05 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Recomendar este item


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.