Please enable JavaScript.

Coggle requires JavaScript to display documents.

Entrega Final Verificación de algoritmos - Coggle Diagram

- - - - Precondición y poscondición
      - Uso de variables semánticas
      - Ejemplo: {Pre: a ≥ 0 ∧ b ≥ 0} mcd(a,b) {Pos: a = MCD(A,B)}
  - - - Vacía: wp(⌀, R) ≡ R
      - Asignación: wp(x:=E, R) ≡ R[x := E]
      - Condicional: wp(if C then A else B, R) ≡ (C ⇒ wp(A, R)) ∧ (¬C ⇒ wp(B, R))
      - Secuencia: wp(S1; S2, R) ≡ wp(S1, wp(S2, R))
  - - - sumatoria(n)
        
        suma := 0
        
        i := 1
        
        while i ≤ n
        
        suma := suma + i
        
        i := i + 1
        
        return suma
      - Invariante: suma = suma(1..i-1), i ∈ [1, n+1]
      - Cota: t = (n + 1) - i
  - - - Mejor caso
      - Peor caso
  - - - Divide en subproblemas, resuelve y combina
      - Ejemplo: Merge Sort
      - Usa Teorema Maestro para T(n)
    - - Usa memoria para evitar cálculos repetidos
      - Ejemplo: fib(n)
        
        F[0] := 0
        
        F[1] := 1
  - - - P: resolubles en tiempo polinomial
      - NP: verificables en tiempo polinomial
      - NP-Completo: no se sabe si son tratables
    - - Transformación en tiempo polinomial
      - Si A ≤ B y B ∈ P ⇒ A ∈ P