Verificación de programas
Complejidad
aumenta o disminuye de acuerdo a las decisiones
Formas de medir la complejidad
Clase P
Clase NP
Clase NP completo
Reduccion de Karp
Matemática
Verificación de modelos
se enfoca en reconocer
el modelo matemático
Sea infinito
Sea finito
Método de Sistematización
Ordena enunciados
individuales
simplifica teorias
Convicción
se basa en
demostración de enunciados
conjeturas desconocidas
Explicación
Verdadera o falsa
de sí una afirmación es
centrarse en el por qué
Se caracteriza por
arreglos
Ordenamiento
Teorema maestro
Dividir y conquistar
Metodo burbuja
se tiene varios tipos de ordenamiento como:
Caracteristicas
Debe tener Salida o fin
Debe tener entrada o inicio
Debe ser finito
Debe estar correctamente definido
Orden en la realización
Precisión
Estados
de aserción
Es un predicado que expresa la relación que tienen que cumplir los valores de ciertas variables
Son sentencias lógicas
que hacen referencia aun estado del sistema
de un algoritmo
en un momento determinado de su ejecución
Es el valor que tienen todas sus variables libres
de una varible
Es el valor que tiene una variable en un momento
Determinado de la ejecución de un algoritmo
Especificación de un programa
Poscondición
Es un predicado que define el conjunto de estados finales aceptados del programa
Precondición
Es un predicado que define el conjunto de estados iniciales válidos de un programa
Triplas de Hoare (Q) S (R)
Propiedades:
Precondición vacia
Ley del milagro excluido
Fortalecimiento de (Q)
Debilitamiento de (R)
Conjunción de (R)
Disyunción de (Q)
(R): Poscondición
S: Programa
(Q): Precondición
Programa y estado
Conjunto de valores
que toman las variables
en un determinado momento
la información esta representada por variables
las cuales pueden ser
de salida
de entrada
