Please enable JavaScript.

Coggle requires JavaScript to display documents.

VERIFICACIÓN Y ANÁLISIS DE ALGORITMOS Y PROGRAMAS - Coggle Diagram

- - - - Variables
        
        De Salida (conforman la solución)
        
        Auxiliares (almacenan resultados intermedios)
        
        De Entrada (definen instancia del problema)
      - Programa
        
        Un programa es un algoritmo que se define por sus variables y por lo que hace
      - Estado de programa
        
        El estado de un programa se determina por sus variables de entrada y sus variables de salida
    - - La especificación permite establecer claramente el comportamiento esperado del programa
        
        Precondición (Q):
        
        Condiciones deben cumplirse antes de ejecutar el programa .
        
        Notación: {Pre Q: <predicado>}
        
        Variables Semánticas (ej. A, B): Para referirse a valores iniciales en la poscondición.
        
        Poscondición (R):
        
        Condiciones deben cumplirse al finalizar el programa .
        
        Notación: {Pos R: <predicado>}
        
        Especificación Completa: Pareja {Pre Q, Pos R} (Define qué debe hacer el programa).
    - - Notación: {Q} S {R}
        
        S: Programa
        
        Q: Precondición
        
        R: Poscondición
      - Semántica (Significado): Si Q es verdadera antes de S, y S termina, entonces R será verdadera después de S.
        
        Implica corrección del programa S respecto a su especificación Q y R.
      - Validez de una Tripla:
        
        Un programa es correcto si su tripla de Hoare correspondiente es válida.
        
        No es válida si
        
        El programa no termina correctamente (error, ciclo infinito).
        
        El estado final no satisface R.
      - Propiedades Útiles de las Triplas de Hoare:
        
        Precondición Vacía (Imposible): {falso}S{R} es siempre válida.
        
        Ley del Milagro Excluido: {Q}S{falso} es válida ⇔ [Q ≡ falso].
        
        Fortalecimiento de Precondición: Si [P ⇒ Q] y {Q}S{R} es válida → {P}S{R} es válida.
        
        Debilitamiento de Poscondición: Si {Q}S{R} es válida y [R ⇒ P] → {Q}S{P} es válida.
        
        Conjunción de Poscondiciones: Si {Q}S{R₁} y {Q}S{R₂} son válidas → {Q}S{R₁ ∧ R₂} es válida.
        
        Disyunción de Precondiciones: Si {Q₁}S{R} y {Q₂}S{R} son válidas → {Q₁ ∨ Q₂}S{R} es válida.
- - - - Análisis línea por línea (costo oᵢ por línea i).
      - Conteo de ejecuciones de cada línea (bucles).
      - Resultado T(n) = an² + bn + c (función cuadrática).
  - - - n → se duplica.
      - n² → se cuadruplica.
      - 2ⁿ → se eleva al cuadrado.
  - - - Funcionamiento (intercambios adyacentes).
      - Pseudocódigo (con esta_ordenado y ultimo_no_ordenado).
      - Mejor Caso (arreglo ordenado): T(n) es lineal.
      - Peor Caso (arreglo inversamente ordenado): T(n) es cuadrático.
  - - - f(n) = O(g(n)) si ∃ c > 0, n₀ > 0 t.q. f(n) ≤ c * g(n) para n > n₀.
      - Uso: Comúnmente para el peor caso.
      - Ej: n = O(n²), 10n³ = O(n³).
    - - f(n) = Ω(g(n)) si ∃ c > 0, n₀ > 0 t.q. f(n) ≥ c * g(n) para n > n₀.
      - Uso: Comúnmente para el mejor caso.
      - Ej: n² = Ω(log₂n), 0.001n³ = Ω(n³).
    - - f(n) = Θ(g(n)) si f(n) = O(g(n)) Y f(n) = Ω(g(n)).
      - Uso: Cuando la tasa de crecimiento es la misma para peor y mejor caso (o para el análisis general).
      - Ej: an + b = Θ(n), an² + bn + c = Θ(n²).
- - - - Expresión natural de wp para ciclos es compleja (relación de recurrencia).
      - Necesidad de un método alternativo: Teorema de Invarianza.
    - - Invariante de Ciclo (P):
        
        Definición: Predicado satisfecho justo antes de la primera iteración y justo después de cada iteración completa del cuerpo del ciclo.
        
        Función: Debe contener información relevante sobre el estado del programa que progresa hacia la solución.
        
        Un ciclo puede tener múltiples invariantes (ej. true), pero se busca el más útil.
      - Cota de Ciclo (t) o Variante de Bucle:
        
        Definición: Función entera cuyo valor:
        
        Disminuye estrictamente con cada iteración del ciclo.
        
        Está acotada inferiormente (es siempre ≥ Tmin, usualmente Tmin=0) mientras la condición del ciclo se cumple.
        
        Función: Garantiza la terminación del ciclo.
    - - Para probar {Q_inicial} <inicialización>; while B do S_cuerpo endwhile {R_final}:
      - Establecimiento del Invariante: La inicialización establece P.
        
        {Q_inicial} <inicialización> {P}
      - Preservación del Invariante: P se mantiene a través de una iteración.
        
        {P ∧ B} S_cuerpo {P}
      - Terminación del Ciclo (uso de la Cota t):
        
        t decrece: {P ∧ B ∧ t=T_actual} S_cuerpo {t < T_actual}
        
        t está acotada inferiormente mientras B es verdadera: [P ∧ B ⇒ t ≥ T_min]
      - Satisfacción de la Poscondición al Finalizar: Al salir del ciclo (¬B), el invariante P implica la poscondición R.
        
        [ (P ∧ ¬B) ⇒ R_final ]
    - - Ejemplo 1 (Sumatoria): Cálculo de suma de 1 a n.
        
        P: suma = Σ(k=1 hasta i-1) ∧ 1 ≤ i ≤ n+1
        
        t: (n+1) - i
      - Ejemplo 2 (Fibonacci): Cálculo de Fn.
        
        P: a = F_i ∧ b = F_(i+1) ∧ 0 ≤ i ≤ n
        
        t: n - i
      - Ejemplo 3 (Logaritmo entero): Cálculo de ⌊log₂n⌋.
        
        P: 2^(k-1) ≤ n
        
        t: n - 2^k (o alguna variante que asegure decrecimiento entero y acotamiento)
      - Conexión: Estos ejemplos muestran cómo definir P y t, y las 4 obligaciones de prueba.
- - - - Definición: El predicado Q más débil (menos restrictivo) tal que {Q}S{R} es válida (para corrección total).
      - Relación con Validez de Triplas: {Q_dada} S {R} es válida ⇔ [Q_dada ⇒ wp(S,R)].
    - - Instrucción Vacía (skip o ausencia de código efectivo):
        
        wp(skip, R) = R
        
        Conexión: La poscondición R debe ser verdadera antes, ya que skip no cambia el estado.
      - Asignación (x := E):
        
        wp(x := E, R) = R[E/x] (R con todas las ocurrencias libres de x reemplazadas por E).
        
        Conexión: Para que R sea verdadera después de la asignación, la condición R[E/x] debe serlo antes.
      - Instrucción Condicional (if C then S₁ else S₂):
        
        wp(if C then S₁ else S₂, R) = (C ⇒ wp(S₁, R)) ∧ (¬C ⇒ wp(S₂, R))
        
        Conexión: Si C es V, se debe cumplir wp(S₁,R); si C es F, se debe cumplir wp(S₂,R).*
      - Composición Secuencial (S₁; S₂):
        
        wp(S₁; S₂, R) = wp(S₁, wp(S₂, R))
        
        Conexión: Se calcula de atrás hacia adelante: primero la wp para S₂ respecto a R, y luego la wp para S₁ respecto al resultado anterior.*
    - - (Aquí puedes listar los ejemplos del Escenario 2 donde se demuestra o refuta la validez de triplas usando el cálculo de wp, como ejemplo_2, ejemplo_3, ejemplo_4, ejemplo_5 (valor absoluto), ejemplo_6 (intercambio con sumas y restas)).
      - Conexión: Estos ejemplos aplican las fórmulas de wp para probar la corrección.*
- - - - a: número de subproblemas
      - b: factor de reducción
      - f(n): costo de dividir y combinar
    - - Caso I: f(n) < n^log_b(a) → T(n) = Θ(n^log_b(a))
      - Caso II: f(n) ≈ n^log_b(a) → T(n) = Θ(n^log_b(a) · log n)
      - Caso III: f(n) > n^log_b(a) → T(n) = Θ(f(n))
    - - Merge Sort: T(n) = Θ(n log n)
      - Strassen: T(n) = 7T(n/2) + Θ(n²)
      - Selección de Hoare: T(n) = T(n/2) + Θ(n)
  - - - Subproblemas más pequeños y similares
      - Ej: Strassen → 7 subproblemas
    - - Resolución recursiva
      - Casos base: tamaño 0 o 1
    - - Combina soluciones parciales
      - Fase más compleja y creativa
- - - - Ecuación: fib(n) = fib(n−1) + fib(n−2)
      - Cálculos repetidos
      - Complejidad: Θ(2ⁿ)
    - - Arreglo F[0..n]
      - Algoritmo iterativo
      - Complejidad: Θ(n)
  - - - Transformar S en T con mín. cambios
      - Operaciones: insertar, eliminar, sustituir
    - - Considera coincidencia o diferencia final
      - Complejidad: exponencial
    - - Matriz D[m+1][n+1]
      - Evalúa desde casos base
      - Complejidad: Θ(mn)
- - - - Transformación en tiempo polinómico entre problemas
      - Si A se reduce a B y B ∈ P → A ∈ P
    - - Está en NP
      - Todo problema NP se reduce a él
      - Si uno está en P, entonces P = NP
      - Se cree que no son tratables
  - - - Fórmulas booleanas con 3 literales por cláusula
      - Demostrado por Cook (1971)
    - - Visitar cada vértice exactamente una vez
    - - Subconjunto de vértices todos conectados
      - ¿Existe un clique de tamaño k?
- - - - Minimizar número de monedas
      - Sistema canónico: $1, $5, $10, $20, $50
      - Dividir monto desde la mayor denominación
    - - Óptimo en sistemas canónicos
      - Subóptimo en sistemas no canónicos
      - Ej: con $1, $3, $4, $5 da resultado no óptimo
  - - - Codificar símbolos con menor número de bits
      - Se basa en frecuencia de los símbolos
    - - Nodo por símbolo con frecuencia
      - Construir árbol uniendo nodos con menor peso
      - Recorrer árbol y asignar códigos
      - Asociar cada símbolo con código binario
    - - Códigos más cortos para símbolos más frecuentes
      - Sin prefijos: no hay ambigüedad
      - Óptimo para codificación por símbolo