Notas sobre complejidad computacional

Abstract

Dos aspectos centrales del proyecto en curso del CAETI, de creacion de un ambiente de desarrollo de software basado en conceptos avanzados de modularizacion y sintesis de comportamiento, son la correctitud y la eficiencia. En relación al primer aspecto, en artículos anteriores describimos la verificación axiomática de programas. En este artículo nos enfocamos en la eficiencia, presentando una serie de notas que cubren sucintamente temas relevantes de la complejidad computacional, área de la teoría de la computación que estudia la dificultad inherente de los problemas. Se tratan los paradigmas determinístico, probabilístico y cuántico, incluyendo elementos vinculados con la criptografía, las pruebas y la desaleatorización de los algoritmos. El material integra los contenidos de la asignatura Métodos Formales en la Ingeniería de Software, que se dicta en el Doctorado en Informática de la Facultad de Tecnología Informática de la UAI.