Correção (ciência da computação)

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Na ciência da computação teórica , um algoritmo está correto em relação a uma especificação se ele se comporta como especificado. O melhor explorado é a correção funcional , que se refere ao comportamento de entrada-saída do algoritmo (ou seja, para cada entrada ele produz uma saída que satisfaça a especificação). [1]

Dentro desta última noção, a correção parcial , exigindo que se uma resposta for retornada ela seja correta, é diferenciada da correção total , que adicionalmente requer que uma resposta seja eventualmente retornada, ou seja, o algoritmo termina. Da mesma forma, para provar a correção total de um programa, é suficiente provar sua correção parcial e seu término. [2] Este último tipo de prova ( termination proof ) nunca pode ser totalmente automatizado, pois o problema da parada é indecidível .

Programa C parcialmente correto para encontrar
o número perfeito menos ímpar,
sua exatidão total é desconhecida a partir de 2021
// retorna a soma dos divisores próprios de n 
static int divisorSum ( int n ) {    
   int i , soma = 0 ;    
   para ( i = 1 ; i < n ; ++ i )   
      se ( n % i == 0 )     
         soma + = ;  
   soma de retorno ; 
}
// retorna o número perfeito menos ímpar 
int lessPerfectNumber ( void ) {  
   int ; _ 
   para ( n = 1 ; ; n += 2 )   
      if ( n == divisorSoma ( n ))   
         retornar n ; 
}

Por exemplo, pesquisando sucessivamente os inteiros 1, 2, 3, … para ver se podemos encontrar um exemplo de algum fenômeno – digamos um número perfeito ímpar – é muito fácil escrever um programa parcialmente correto (veja o quadro). Mas dizer que este programa está totalmente correto seria afirmar algo atualmente desconhecido na teoria dos números .

Uma prova teria que ser uma prova matemática, assumindo que tanto o algoritmo quanto a especificação são dados formalmente. Em particular, não se espera que seja uma afirmação de correção para um determinado programa que implementa o algoritmo em uma determinada máquina. Isso envolveria considerações como limitações na memória do computador .

Um resultado profundo na teoria da prova , a correspondência de Curry-Howard , afirma que uma prova de correção funcional na lógica construtiva corresponde a um determinado programa no cálculo lambda . Converter uma prova dessa maneira é chamado de extração de programa .

A lógica de Hoare é um sistema formal específico para raciocinar rigorosamente sobre a correção de programas de computador. [3] Ele usa técnicas axiomáticas para definir a semântica da linguagem de programação e argumentar sobre a correção dos programas por meio de afirmações conhecidas como triplas de Hoare.

Teste de software é qualquer atividade destinada a avaliar um atributo ou capacidade de um programa ou sistema e determinar se ele atende aos resultados exigidos. Embora crucial para a qualidade do software e amplamente implantado por programadores e testadores, o teste de software ainda permanece uma arte, devido à compreensão limitada dos princípios do software. A dificuldade no teste de software decorre da complexidade do software: não podemos testar completamente um programa com complexidade moderada. Testar é mais do que apenas depurar. O objetivo do teste pode ser garantia de qualidade, verificação e validação ou estimativa de confiabilidade. O teste também pode ser usado como uma métrica genérica. Teste de correção e teste de confiabilidade são duas áreas principais de teste. O teste de software é uma troca entre orçamento, tempo e qualidade. [4]

Veja também

Notas

  1. ^ Dunlop, Douglas D.; Basili, Victor R. (junho de 1982). "Uma análise comparativa de correção funcional" . Comunicações da ACM . 14 (2): 229–244. doi : 10.1145/356876.356881 .
  2. ^ Maná, Zohar; Pnueli, Amir (setembro de 1974). "Abordagem axiomática para correção total de programas". Acta Informatica . 3 (3): 243-263. doi : 10.1007/BF00288637 .
  3. ^ Hoare, CARRO (outubro de 1969). "Uma base axiomática para programação de computadores" (PDF) . Comunicações da ACM . 12 (10): 576-580. CiteSeerX 10.1.1.116.2392 . doi : 10.1145/363235.363259 . Arquivado do original (PDF) em 4 de março de 2016.  
  4. ^ Pan, Jiantao (Primavera de 1999). "Teste de Software" (curso). Universidade Carnegie Mellon . Recuperado em 21 de novembro de 2017 .

Referências