Fundamentos de Complejidad Algorítmica y Lógica Proposicional

Conceptos Fundamentales de Complejidad Algorítmica

• Complejidad en tiempo: Número de operaciones que debe realizar un algoritmo.
• Algoritmo: Conjunto finito de instrucciones precisas que resuelven un problema o realizan un cálculo.
• Tratable: Un problema es tratable si se puede resolver mediante un algoritmo con complejidad polinómica en el peor caso.
• Intratable: Un problema es intratable si no puede resolverse mediante un algoritmo con complejidad polinómica en el peor caso.
• Irresolubles: Problemas para los cuales se ha probado que no existen algoritmos capaces de resolverlos.
• Resolubles: Problemas para los cuales se ha probado que existen algoritmos capaces de resolverlos.

Notación Asintótica

• f(x) es O(g(x)): f(x) es O(g(x)) si y solo si existen constantes c y k tales que |f(x)| ≤ c|g(x)| para todo x > k.
• f(x) es Ω(g(x)): f(x) es Ω(g(x)) si y solo si existen constantes c y k tales que |f(x)| ≥ c|g(x)| para todo x > k.
• f(x) es Θ(g(x)): f(x) es Θ(g(x)) si f(x) es O(g(x)) y Ω(g(x)). Esto implica encontrar dos números reales C1 y C2 y un positivo k tal que: C1 |g(x)| ≤ |f(x)| ≤ C2 |g(x)| para todo x > k.

Ejemplo de Cálculo de Complejidad

Tomando n=3; f(n)=3+n(1+2(n-1)+4) = 2n² + 3n + 3, por lo tanto, f es Θ(n²). Tanto el mejor como el peor de los casos son Θ(n²).

• Mejor de los casos: f(n)=3+n(1+2n)=3+n+2n². Testigos: 1n² ≤ 3+n+2n² ≤ 3n² donde n² ≥ -3-n, lo que implica n² ≥ 3+n para todo n > 3=k.
• Peor de los casos: f(n)=3+n(1+3n)=3+n+3n². Testigos: 2n² ≤ 3+n+3n² ≤ 4n² donde n² ≥ -3-n, lo que implica n² ≥ 3+n para todo n > 3=k.

En este caso, el algoritmo es tratable ya que f(n) ∈ Θ(n²) (complejidad polinómica).

Propiedades de las Relaciones Binarias

• No simétrica: El código utiliza un solo bucle y comprueba si el inverso (b,a) de cada par (a,b)∈R no está en R. Ejemplo: !MemberQ[R, {b, a}].
• No antisimétrica: Utiliza un solo bucle buscando pares (a,b)∈R donde el inverso (b,a)∈R y además a≠b. Ejemplo: MemberQ[R, {b, a}] && a != b.
• No transitiva: Emplea bucles anidados para encontrar pares (a,b)∈R y (b,c)∈R tales que (a,c)∉R. Ejemplo: verifica !MemberQ[R, {a, c}] tras hallar (a,b) y (b,c).

Equivalencias en Lógica Proposicional

1. A ∨ B ⇔ (¬A) → B
2. A ∧ B ⇔ ¬(A → (¬B))
3. A → B ⇔ (¬A) ∨ B
4. A → B ⇔ ¬(A ∧ (¬B))
5. A ↔ B ⇔ (A → B) ∧ (B → A)
6. A ↔ B ⇔ ¬(A ⊕ B)
7. A ⊕ B ⇔ ¬(A ↔ B)
8. A ⊕ B ⇔ (A ∨ B) ∧ (¬(A ∧ B))
9. A ∧ B ⇔ ¬((¬A) ∨ (¬B))
10. A ∨ B ⇔ ¬((¬A) ∧ (¬B))
11. A ↑ B ⇔ ¬(A ∧ B)
12. A ↓ B ⇔ ¬(A ∨ B)
13. (¬A) ⇔ (A ↑ A) ⇔ (A ↓ A)
14. ¬(¬A) ⇔ A
15. ¬A ⇔ 1 ⊕ A