Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/18555
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorSampaio, Rudini Menezes-
dc.contributor.authorDantas, Rennan Ferreira-
dc.date.accessioned2016-07-21T16:06:22Z-
dc.date.available2016-07-21T16:06:22Z-
dc.date.issued2014-
dc.identifier.citationDANTAS, Rennan Ferreira. Problemas de código de identificação em grades. 2014. 69 f. Dissertação (Mestrado em ciência da computação) - Universidade Federal do Ceará, Fortaleza-CE, 2014.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/18555-
dc.description.abstractThe identifying code problem was introduced in 1998 by Karpovsky as a way to help fault diagnosis in multiprocessor computer systems Since then the study of this problem and its variants has been developed Antoine Lobstein maintains a bibliography with more than 200 articles on this subject The idea of the problem is to identify any vertex of the graph using just its identifying set which are the vertices of its closed neighborhood in the identifying code Many recent papers have investigated infinite graphs and then the main objective is to obtain identifying codes in these infinite graphs with the smallest possible density In 2005 Ben-Haim and Litsyn proved that the density of an optimum identifying code in the infinite rectangular grid is 7/20 In this dissertation we present a bibliographical study showing several existing results and we provide an alternative proof to the density 7/20 for optimum identifying codes in infinite rectangular grids using the discharging method.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectCódigos de identificaçãopt_BR
dc.subjectGrade triangularpt_BR
dc.subjectGrade quadradapt_BR
dc.subjectGrade infinitapt_BR
dc.subjectIdentifying codespt_BR
dc.titleProblemas de código de identificação em gradespt_BR
dc.typeDissertaçãopt_BR
dc.description.abstract-ptbrO problema do código de identificação foi introduzido em 1998 por Karpovsky com a finalidade de ajudar no diagnóstico de falhas em sistemas computacionais com multiprocessadores Desde então o estudo sobre esses códigos e suas variantes tem sido desenvolvido Antoine Lobstein mantém uma bibliografia com mais de 200 artigos sobre o assunto A ideia do problema consiste em identificar qualquer vértice do grafo utilizando apenas o seu conjunto de identificação que são os vértices de sua vizinhança fechada que estão no código de identificação Muitos estudos recentes se concentraram em grafos infinitos e com isso o objetivo é obter códigos de identificação nesses grafos infinitos com a menor densidade possível Em 2005 Ben-Haim e Litsyn provaram que a densidade de um código de identificação ótimo da grade retangular infinita é 7/20. Nessa dissertação fazemos um estudo bibliográfico apresentando vários resultados existentes e fornecemos uma prova alternativa para a densidade 7/20 de códigos ótimos em grades retangulares infinitas usando o método da descarga.pt_BR
dc.title.enIdentifying code problems in gridespt_BR
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2014_dis_rfdantas.pdf1,01 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


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