Testabilidade de propriedades de estruturas discretas

Abstract

Diante 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.

In 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.