Complejidad esencial

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La complejidad esencial se refiere a una situación donde todas las soluciones razonables a un problema deben ser complicadas (y posiblemente confusas) porque las soluciones "simples" no resolverían adecuadamente el problema. Esto contrasta con la complejidad accidental, que surge puramente de desajustes en la elección particular de herramientas y métodos aplicados en la solución.

Este término ha sido usado desde, al menos, mediados de la década de 1980. El ganador del Premio Turing, Fred Brooks, ha usado este término y su antónimo, complejidad accidental, desde mediados de la década de 1980. Brooks también ha actualizado, en 1995, sus visiones para una edición de aniversario de The Mythical Man-Month, capítulo 17 "'No hay balas de plata' Redisparado".[1] [2] [3]

Complejidad ciclomática[editar]

La complejidad esencial también es usada con un significado distinto en relación con la complejidad ciclomática. En este contexto, la complejidad esencial se refiere a la complejidad ciclomática después de reemplazar iterativamente todas las estructuras de control bien estructuradas con una única instrucción. Estructuras tales como if-then-else y bucles while son considerados bien estructurados. El uso ilimitado de sentencias goto puede producir programas que no se pueden reducirse de esta manera.

Por ejemplo, el siguiente fragmento de programa en C tiene una complejidad esencial de 1, porque la sentencia if interna y el for pueden ser reducidos:

 for(i=0;i<3;i++) {
    if(a[i] == 0) b[i] += 2;
 }

El siguiente fragmento de programa en C tiene una complejidad esencial de más de uno. Este código encuentra la primera fila de z que tiene todos sus elementos en cero y pone su índice en i; Si no hay ninguna, pone -1 en i.

     for(i=0;i<m;i++) {
         for(j=0;j<n;j++) {
             if(z[i][j] != 0) goto no_cero;
         }
         goto encrontrado;
     }
 no_cero:
     i = -1;
 encontrado:

Lectura adicional[editar]

  • Brooks, Fred P. (1986). «No Silver Bullet - Essence and Accident in Software Engineering». Proceedings of the IFIP Tenth World Computing Conference:  pp. 1069–1076. 
  • — (April 1987). «No Silver Bullet - Essence and Accidents of Software Engineering». IEEE Computer 20 (4):  pp. 10–19. 
  • — (1995). Chap. 17. «'No Silver Bullet' Refired». The Mythical Man Month (Anniversary Edition with four new chapters edición) (Addison-Wesley). ISBN 0-201-83595-9. 

Referencias[editar]

  1. Brooks, Proc. IFIP
  2. Brooks, IEEE Computer
  3. Brooks, Mythical Man-Month, Silver Bullet Refired

Véase también[editar]