1. Triplas de Hoare
1.1. Es una expresión lógica compuesta por un programa y su especificación.
1.2. Se denotada como {Q}S{R}
1.3. Válida
1.3.1. Al ejecutar el programa desde un estado inicial que satisface Q, se alcanza un estado final que satisface R.
1.4. Inválida
1.4.1. El programa no termina correctamente.
1.4.1.1. Ya sea por un error en ejecución o porque queda estancado en un ciclo infinito.
1.4.2. El estado final alcanzado por el programa no satisface la poscondición R.
1.4.3. Conjunción de poscondiciones
1.4.3.1. Si {Q}S{R} y {Q}S{P} son válidas, entonces también es válida {Q}S{R ∧ P}
1.5. Esta tripla es válida
1.5.1. Si no se cumple esto, el programa es incorrecto.
1.6. Propiedades
1.6.1. Precondición vacía
1.6.1.1. {falso}S{R} es siempre válida
1.6.2. Ley del milagro excluido
1.6.2.1. {Q}S{falso} es válida si Q es falso
1.6.3. Fortalecimiento de precondición
1.6.3.1. Si {Q}S{R} es válida y P implica Q, entonces {P}S{R} es válida
1.6.4. Debilitamiento de poscondición
1.6.4.1. Si {Q}S{R} es válida y R implica P, entonces {Q}S{P} es válida
1.6.5. Disyunción de precondiciones
1.6.5.1. Si {Q}S{R} y {P}S{R}son válidas, entonces también es válida{Q ∨ P}S{R}
2. Verificación para instrucciones iterativas
2.1. Teorema de invarianza
2.1.1. Conjunto de reglas que permiten decidir si un programa iterativo es o no correcto.
2.1.2. 1
2.1.2.1. Demostrar que el predicado P es realmente invariante
2.1.2.1.1. P se cumple al inicio del ciclo
2.1.2.1.2. P se cumple después de cada iteración del ciclo
2.1.3. 2
2.1.3.1. Demostrar que la poscondición se satisface al finalizar del ciclo
2.1.3.1.1. Se debe demostrar que el estado final del programa satisface la poscondición R.
2.1.4. 3
2.1.4.1. Terminación del ciclo
2.1.4.1.1. Demostrar que el ciclo realmente finalizará
2.2. Programa iterativo/ciclico
2.2.1. Programa que contiene una instrucción de ciclo que repite un bloque de código un número finito de veces.
2.2.2. Cota de ciclo
2.2.2.1. Función entera que disminuye con cada iteración del ciclo y está acotada inferiormente.
2.2.3. Invariante de ciclo
2.2.3.1. Predicado que es cierto antes y después de cada iteración del ciclo.
3. Análisis de algoritmos
3.1. Estudio del comportamiento de los algoritmos en términos de tiempo y memoria.
3.2. Complejidad computacional
3.2.1. Medida de la cantidad de recursos que un algoritmo requiere para su ejecución.
3.2.1.1. Enfoque experimental
3.2.1.1.1. Factores que afecta la medición
3.2.1.1.2. Para que los resultados sean confiables se requieren de muchas pruebas y un posterior análisis robusto sobre los datos obtenidos
3.2.1.2. Enfoque teórico
3.2.1.2.1. Asume un modelo computacional general y consiste en un estudio directo de las instrucciones que componen el algoritmo.
3.2.2. Aplicaciones
3.2.2.1. Predicción de variables continuas
3.2.2.2. Análisis de regresión no lineal
3.2.2.3. Modelado de series temporales
3.2.2.4. Análisis de datos espaciales
3.3. Complejidad de un algoritmo
3.3.1. Medida del tiempo y recursos que requiere un algoritmo para ejecutarse.
3.3.2. Orden de complejidad
3.3.2.1. Clasificación de la complejidad de un algoritmo en función de su comportamiento a medida que aumenta el tamaño de la entrada.
3.3.3. Análisis de complejidad
3.3.3.1. Teorema maestro
3.3.3.1.1. Herramienta para analizar la complejidad de algoritmos dividir y conquistar.
3.3.3.1.2. Casos
3.4. Importancia
3.4.1. Permite evaluar la eficiencia de diferentes algoritmos para resolver un problema
3.4.2. Tomar decisiones informadas sobre la selección del algoritmo más adecuado para una aplicación específica
3.4.3. Comprender el comportamiento de los algoritmos a medida que aumenta el tamaño de la entrada
4. Algoritmos voraces
4.1. Codificación de Huffman
4.1.1. Se trata de transmitir mensaje con símbolos de un alfabeto minimizando tamaño de representación binaria
4.1.1.1. Proceso
4.1.1.1.1. Crear nodo por cada símbolo con su frecuencia
4.1.1.1.2. Asociar peso a cada nodo
4.1.1.1.3. Combinar los dos nodos con menor peso hasta obtener un único árbol
4.1.1.1.4. Asignar cadenas binarias a cada símbolo según el recorrido en el árbol
4.1.1.2. Propiedades
4.1.1.2.1. Representación más corta para símbolos más frecuentes
4.1.1.2.2. Códigos no son prefijos de otros, garantizando decodificación sin ambigüedad
4.1.1.2.3. Es un algoritmo voraz y óptimo para la codificación de mensajes
4.2. Es una trategia para resolver problemas por etapas.
4.2.1. Propiedades
4.2.1.1. Garantiza solución óptima
4.2.1.2. La solución puede ser subóptima pero aceptable
4.2.1.3. Divide el problema en etapas
4.2.1.4. Construcción incremental de soluciones
4.2.1.5. Optimizan localmente sin cambiar decisiones previas
4.2.1.6. Asociados a problemas de optimización
4.2.1.7. Soluciones aproximadas útiles en problemas intratables
4.3. Ayuda a la toma decisiones óptimas locales en cada etapa
4.3.1. Son menos complejos en diseño e implementación.
4.3.2. Decisiones independientes entre etapas
4.4. Problema de Cambio de Monedas
4.4.1. Máquina dispensadora debe dar cambio con monedas de denominaciones 50, 20, 10, 5 y 1
4.4.1.1. Objetivo
4.4.1.1.1. Minimizar el número de monedas
4.4.1.2. Alfotimo voraz
4.4.1.2.1. Iniciar con monto C
4.4.1.2.2. Calcular cantidad de monedas de 50, actualizar C
4.4.1.2.3. Repetir para denominaciones 20, 10, 5 y 1
4.4.1.3. Soluciones
4.4.1.3.1. Sistema de monedas canónico garantiza solución óptima
4.4.1.3.2. En sistemas no canónicos, la solución puede ser subóptima pero aceptable
5. Programa
5.1. Es un conjunto de instrucciones que se ejecutan en una computadora para realizar una tarea específica.
5.2. Especificación de un programa
5.2.1. Precondición
5.2.1.1. Predicado que define el conjunto de estados iniciales válidos de un programa.
5.2.1.1.1. Se expresa como: {Pre Q: <precondición>}
5.2.2. Postcondición
5.2.2.1. Predicado que define el conjunto de estados finales aceptados del programa.
5.2.2.1.1. Se expresa como: {Pos R: <poscondición>}
5.2.3. La precondición y poscondición de un programa forman su especificación.
5.3. Estado de programa
5.3.1. Es conjunto de valores de las variables del programa en un momento dado.
5.4. Variables
5.4.1. Entrada
5.4.1.1. Definen la instancia del problema a resolver.
5.4.2. Salida
5.4.2.1. Conforman la solución de la instancia computada.
5.4.3. Otras
5.4.3.1. Almacenan resultados intermedios.
5.4.4. Se hace referencia a ellas usando letras minúsculas.
5.5. Variables semánticas
5.5.1. Variables que no hacen parte del programa, pero sí de su especificación.
5.5.1.1. Usadas para hacer referencia a los valores iniciales de las variables de entrada en la poscondición.
5.5.2. Se hace referencia a ellas usando letras mayúsculas.
5.6. Un programa es correcto con respecto a su especificación.
5.6.1. Si y solo si al ser ejecutado sobre cualquier estado inicial que satisface la precondición.
5.6.2. Produce un estado final que satisface la poscondición.
5.7. Corrección del programa
5.7.1. Propiedad que indica que el programa cumple con su especificación.
6. Verificación para instrucciones simples
6.1. Precondición más débil
6.1.1. Condición más general que garantiza que la instrucción se ejecutará correctamente y producirá el resultado esperado, independientemente del estado inicial del programa.
6.1.2. Intrucción vacía
6.1.2.1. Se hace referencia generalmente a la ausencia de instrucciones.
6.1.2.2. No tiene ningún efecto sobre el estado del programa.
6.1.2.3. El predicado Q más débil que satisface [Q ⇒ R] es R: wp(<vacío>, R) ≡ R
6.1.3. Asignación
6.1.3.1. Instrucción de la forma <var>:=<exp>
6.1.3.2. Es una operación que cambia el valor de una variable a otro valor.
6.1.3.3. Reemplaza el valor de la variable <var> por el resultado de la evaluación de la expresión <exp>.
6.1.3.4. El predicado Q más débil que satisface [Q ⇒ R(x:=E)] es R(x:=E): wp(x:=E, R) ≡ R(x:=E)
6.1.4. Instrucción condicional
6.1.4.1. Instrucción de la forma if <condición C> then <conjunto de instrucciones A> else <conjunto de instrucciones B>
6.1.4.2. Una condicional permite que el programa elija entre dos conjuntos de instrucciones basándose en una condición.
6.1.4.3. El predicado Q más débil que satisface [Q ⇒ ((C ⇒ wp(A, R)) ∧ (¬C ⇒ wp(B, R)))] por lo tanto, wp(if C then A else B, R) ≡ ((C ⇒ wp(A, R)) ∧ (¬C ⇒ wp(B, R)))
6.1.5. Composición secuencial
6.1.5.1. Intrucciónm de la forma: <instrucción 1> <instrucción 2> ... <instrucción k>
6.1.5.2. Estructura de programación donde varias instrucciones se ejecutan una después de la otra en un orden específico.
6.1.5.3. El predicado Q más débil debe ser P más débil, entonces: P ≡ wp(<instrucción k>, R).
7. Algoritmos dividir y conquistar
7.1. Técnica de diseño de algoritmos que divide un problema en subproblemas más pequeños y similares, resuelve los subproblemas recursivamente y combina las soluciones de los subproblemas para obtener la solución del problema original.
7.1.1. Ejemplo: Ordenamiento por mezcla
7.1.1.1. Divide un arreglo en dos mitades, ordena recursivamente cada mitad y luego combina las mitades ordenadas en un solo arreglo ordenado.
7.1.2. Fases
7.1.2.1. División
7.1.2.1.1. Dividir el problema en subproblemas más pequeños.
7.1.2.2. Conquista
7.1.2.2.1. Resolver los subproblemas recursivamente.
7.1.2.3. Combinación
7.1.2.3.1. Combinar las soluciones de los subproblemas para obtener la solución del problema original.
7.2. Ventajas
7.2.1. Eficientes para problemas de gran tamaño.
7.2.2. Se pueden aplicar a una amplia gama de problemas.
7.2.3. Fáciles de entender y programar.
7.3. Desventajas
7.3.1. Mayor consumo de memoria que otros algoritmos.
7.3.2. Mayor overhead (costo adicional) que otros algoritmos.
7.4. Aplicaciones de algoritmos dividir y conquistar
7.4.1. Ordenamiento de arreglos
7.4.1.1. Procedimiento que organiza una colección de elementos en un orden específico.
7.4.2. Búsqueda de elementos en arreglos.
7.4.3. Multiplicación de matrices.
7.4.4. Evaluación de expresiones aritméticas.
8. Programación dinámica
8.1. Técnica de diseño de algoritmos que optimiza el rendimiento de algoritmos recursivos mediante la reutilización de resultados intermedios.
8.1.1. Principios
8.1.1.1. Uso de una estructura de datos para almacenar resultados intermedios.
8.1.1.2. Evaluación de subproblemas de menor a mayor tamaño.
8.1.2. Ejemplos resueltos con programación dinámica
8.1.2.1. Cálculo de la sucesión de Fibonacci
8.1.2.2. Distancia de edición entre cadenas de texto
8.2. Algoritmo recursivo
8.2.1. Algoritmo que utiliza la recursividad para resolver un problema.
8.2.2. Recursividad
8.2.2.1. Técnica de programación que consiste en definir una función en términos de sí misma.
8.2.3. Ecuación de recurrencia
8.2.3.1. Fórmula matemática que define el valor de una función recursiva.
8.3. Ventajas
8.3.1. Permite obtener soluciones eficientes para problemas con alta complejidad computacional.
8.3.2. Reduce el tiempo y recursos de ejecución de algoritmos recursivos.
8.3.3. Facilita la comprensión y análisis de algoritmos.
8.4. Desventajas
8.4.1. Requiere mayor espacio de memoria que algoritmos recursivos simples.
8.4.2. Puede ser más complejo de implementar que algoritmos recursivos simples.
8.5. Aplicaciones de la programación dinámica
8.5.1. Bioinformática
8.5.2. Procesamiento del lenguaje natural
8.5.3. Robótica
8.5.4. Optimización de rutas
8.5.5. Reconocimiento de patrones
9. Problema de decisión
9.1. Problema que tiene como salida un único valor booleano (verdadero o falso).
9.1.1. Ejemolos de problemas de decisión
9.1.1.1. Si un número natural n es o no primo.
9.1.1.2. Si una cadena S es subcadena de otra cadena T.
9.1.1.3. Si un elemento pertenece o no a un conjunto.
9.2. Clases de complejidad
9.2.1. Grupos de problemas con características comunes en cuanto a su dificultad inherente.
9.2.1.1. Clase P
9.2.1.1.1. Conjunto de problemas de decisión que pueden ser resueltos por un algoritmo con una complejidad O(nk), donde k es una constante.
9.2.1.2. Clase NP
9.2.1.2.1. Conjunto de problemas de decisión que pueden ser verificados por un algoritmo con una complejidad O(nk), donde k es una constante, en una máquina no determinista.
9.2.1.3. Clase NP-Completo
9.2.1.3.1. Subconjunto de la clase NP que contiene problemas que no se sabe si son o no tratables (pertenecientes a la clase P).
9.2.1.4. Problema intratable
9.2.1.4.1. Problema para el que no se conoce un algoritmo que lo resuelva en un tiempo razonable.
9.2.2. Relaciones entre las clases
9.2.2.1. P ⊆ NP, pero no se sabe si P = NP.
9.2.2.2. NP-Completo ⊆ NP.
9.2.3. Demostración de pertenencia a NP-Completo
9.2.3.1. Se realiza mediante una reducción de Karp desde un problema NP-Completo conocido a otro problema.
9.3. Reducción de Karp
9.3.1. Transformación en tiempo polinómico de una instancia de un problema de decisión en una instancia de otro problema, de manera que la salida de las instancias en cada problema es idéntica.