Show simple item record

dc.contributor.advisorHoppen, Carlospt_BR
dc.contributor.authorCalegari, Rafaelpt_BR
dc.date.accessioned2023-01-06T05:01:57Zpt_BR
dc.date.issued2022pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/253478pt_BR
dc.description.abstractDiante de instâncias intratáveis de problemas de decisão, assim en- tendidas como entradas para os respectivos algoritmos que sejam tão longas, que não permitem que se assegure o processamento de tal algoritmo sobre a dada cadeia num tempo aceitável por um computador real, uma das estratégias co- mumente empregadas consiste em aceitarmos uma probabilidade de erro numa margem tolerável em troca de garantia de execução assintoticamente mais rápida ou menos dependente de armazenamento de informação, seja no pior caso, seja no caso médio. Nesta linha, encontram-se as técnicas de testabilidade de propri- edades de estruturas discretas. Neste trabalho, busca-se apresentar modelos de testabilidade estudados na literatura e contribuir com o aprofundamento e sis- tematização de determinada abordagem do estudo da testabilidade de algumas destas estruturas discretas sob a ótica de uma teoria de isomorfismos.pt_BR
dc.description.abstractIn face of intractable instances of decision problems, so understood as entries for the respective algorithms that are so long that do not enable to en- sure the processing of such algorithm on the given chain in an acceptable time by a real computer, one of the commonly employed strategies consists in accepting a probability of error in a tolerable margin in exchange of an asymptotically faster performance guarantee, or less dependent on the storage of information, whether in the worst case or in the average case. In this line, are found the techniques of testability of properties of discrete structures. In this work, it is sought to present models of testability studied in the literature and contribute with the deepening and systematization of certain approach of the study of testability of some of these discrete structures under the perspective of a theory of isomorphisms.en
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectMatemática discretapt_BR
dc.subjectGrafospt_BR
dc.subjectEstruturas discretaspt_BR
dc.subjectAlgoritmospt_BR
dc.titleTestabilidade de propriedades de estruturas discretaspt_BR
dc.typeDissertaçãopt_BR
dc.identifier.nrb001159603pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemática e Estatísticapt_BR
dc.degree.programPrograma de Pós-Graduação em Matemática Aplicadapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2022pt_BR
dc.degree.levelmestradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record