Please enable JavaScript.

Coggle requires JavaScript to display documents.

Verificación, Diseño y Análisis de Algoritmos - Coggle Diagram

- - - - Notación: {Q} S {R}
      - Componentes:
        
        Q (Precondición): Un predicado que define los estados iniciales que se consideran válidos antes de ejecutar el programa S. Restringe los valores iniciales de las variables.
        
        S (Programa/Comando): El código o la secuencia de instrucciones que se va a verificar. Transforma un estado inicial en un estado final.
        
        R (Poscondición): Un predicado que define los estados finales aceptados una vez que S ha terminado. Restringe los valores finales de las variables y los relaciona con los valores iniciales.
      - Validez de una Tripla: Una tripla es válida si al ejecutarse S en un estado que satisface Q, el programa termina y el estado final resultante satisface R. No es válida si el programa no termina o si el estado final no cumple R.
      - Especificación de un Programa: El par de predicados (Q, R) establece QUÉ debe hacer el programa (el contrato), no el CÓMO lo hace.
    - - Estado del Programa: El conjunto de valores de todas las variables en un momento dado.
      - Variables Semánticas: Variables que no son parte del programa y no son modificadas por él. Se usan en la poscondición (R) para referirse a los valores INICIALES de las variables de entrada. Por convención, se usan mayúsculas.
    - - Ley del Milagro Excluido: {Q} S {falso} es válida si y solo si [Q ≡ falso].
      - Fortalecimiento de la Precondición: Si [P ⇒ Q] es válido y {Q} S {R} es válida, entonces {P} S {R} también es válida.
      - Debilitamiento de la Poscondición: Si [R ⇒ P] es válido y {Q} S {R} es válida, entonces {Q} S {P} también es válida.
      - Conjunción de Poscondiciones: Si {Q} S {R} y {Q} S {P} son válidas, entonces {Q} S {R ∧ P} es válida.
      - Disyunción de Precondiciones: Si {Q} S {R} y {P} S {R} son válidas, entonces {Q ∨ P} S {R} es válida.
- - - - Instrucción Vacía (<vacío>): wp(<vacío>, R) ≡ R.
      - Asignación (x := E): wp(x := E, R) ≡ R(x:=E) (R con x reemplazada por E).
      - Composición Secuencial (S1; S2): wp(S1; S2, R) ≡ wp(S1, wp(S2, R)).
      - Instrucción Condicional (if C then A else B): wp(if C then A else B, R) ≡ ((C ⇒ wp(A,R)) ∧ (¬C ⇒ wp(B,R))).
  - - - Conceptos Clave:
        
        Invariante de Ciclo (P): Un predicado que se satisface justo antes de la primera iteración y se mantiene satisfecho después de cada iteración. Debe contener información relevante del estado.
        
        Cota de Ciclo (t): Una función con valor entero que disminuye con cada iteración y está acotada inferiormente (ej. t ≥ 0). Sirve para garantizar la terminación del ciclo.
      - Obligaciones de Prueba (Reglas del Teorema)
        
        Inicialización: El invariante P se cumple al inicio del ciclo: {Q} <inicialización> {P}.
        
        Mantenimiento: El invariante P se mantiene después de cada iteración: {P ∧ <condición>} <instrucciones> {P}.
        
        Corrección Final: Al finalizar el ciclo, el invariante y la negación de la condición implican la poscondición: [(P ∧ ¬<condición>) ⇒ R].
        
        Terminación (Progreso): La cota del ciclo disminuye en cada iteración: {P ∧ <condición> ∧ t=T} <instrucciones> {t < T}.
        
        Terminación (Acotamiento): La cota está acotada inferiormente: [P ∧ <condición> ⇒ t ≥ Tmin].
- - - - División: El problema se divide en subproblemas. El número de subproblemas puede ser mayor a dos, como en el algoritmo de Strassen que lo divide en siete.
      - Conquista: Los subproblemas se resuelven de forma independiente, usualmente con llamadas recursivas hasta alcanzar un caso base trivial.
      - Combinación: Las soluciones de los subproblemas se unen para componer la solución del problema original. Esta suele ser la fase más importante del algoritmo.
    - - Ecuación de Recurrencia: El análisis de eficiencia de un algoritmo D&C resulta en una ecuación de la forma general T(n) = aT(n/b) + f(n).
        
        a: número de subproblemas.
        
        n/b: tamaño de cada subproblema.
        
        f(n): costo de las fases de división y combinación.
      - Casos del Teorema: Para una recurrencia de la forma T(n) = aT(n/b) + Θ(n^c).
        
        Si c < log_b(a), entonces T(n) = Θ(n^(log_b(a))).
        
        Si c = log_b(a), entonces T(n) = Θ(n^c * log n).
        
        Si c > log_b(a), entonces T(n) = Θ(n^c).
  - - - Se resuelven primero los problemas más pequeños (casos base).
      - A partir de ellos, se construyen las soluciones a subproblemas cada vez más grandes hasta obtener la solución original.
    - - Uso de Estructura de Datos (Memorización): Se utiliza una tabla o arreglo para mantener los valores ya calculados y así evitar realizarlos de nuevo.
      - Evaluación de menor a mayor: Se evalúan los subproblemas en un orden que garantiza que las soluciones necesarias ya han sido calculadas.
- - - - Ejemplo canónico de Dividir y Conquistar.
      - Divide el arreglo en dos mitades, las ordena recursivamente y las combina.
      - Su ecuación de recurrencia es T(n) = 2T(n/2) + Θ(n), lo que resulta en una complejidad de Θ(n log n).
  - - - La implementación recursiva directa fib(n-1) + fib(n-2) es exponencial.
      - La solución con PD usa un arreglo F para almacenar resultados intermedios, logrando una complejidad lineal Θ(n).
    - - Calcula el mínimo de cambios (inserción, eliminación, sustitución) para transformar una cadena en otra.
      - La solución con PD usa una matriz (m+1)x(n+1) para almacenar las distancias de los prefijos de las cadenas.
      - Su complejidad es Θ(mn).