Clase04 Complejidad

Complejidad de Algoritmos
COMPLEJIDAD DE ALGORITMOS
2019-1
Facultad de Ingeniería
5°Semestre Ing Clasede
03 sistemas
2018
Jaime Eduardo Cortés
jcortes@uco.edu.co
Jaime Eduardo Cortés
Ingeniero de Sistemas
Candidato Ms física aplicada
jcortes@uco.edu.co
3116322941
Contenido
● Clasificación de problemas(Trabilidad/Intratabilidad).
● Ejemplo de problema intratable.
● Intratabilidad.
● Reducciones de tiempo polinomial.
● Técnicas de Fuerza Bruta.
Ejemplo de problema Intratable.
Elija una carta de cada celda.
Verifique que cada borde coincida.
Si no coinciden trate otro arreglo

hasta que encuentre la solución
o todos los posibles arreglos sean
fuente: Simonas Saltenis, verificados.
Aalborg University.
Conteste “SI” si se encuentra una
solución o “NO” si se analizaron todos
los elementos y no se encontró una
solución.
Para la primera celda 9 posibilidades.
Para llenar la segunda celda 8.
Para llenar la tercera celda 7 cartas.

…..
así sucesivamente.
El número total de arreglos únicos para n=9 cartas es
9*8*7*6*5*4*3*2*1=362,880
Para n cartas el numero de arreglos a examinar es n! (n
factorial).
9*8*7*6*5*4*3*2*1=362,880
Si se analiza un arreglo en un microsegundo:

N Tiempo en analizar los arreglos
9 0.362 s
16 20922789.888 S
25 15511210043330985984S
4918572439 Siglos
Lo cual muestra que para n=25 tardaría 4918 siglos

Intratabilidad
De lo visto en el ejemplo anterior se dice que si un

problema admite una solución polinómica entonces es un
problema tratable; de lo contrario es intratable:
Algoritmos que son del tipo 𝑂(𝑛𝑘 ) para algún 𝑘 fijo son de
tiempo polinómico y son tratables, por ejemplo:
𝑂 1 , 𝑂 log 𝑛 , 𝑂 𝑛 , 𝑂 𝑛 log 𝑛 , 𝑂(𝑛2 )
Los demás algoritmos son de tiempo súper-polinomial

y son intratables, por ejemplo:
𝑂 2𝑛 , 𝑂 𝑛! , 𝑂(𝑛𝑛 )
Clasificación de problemas
Un problema se puede clasificar de acuerdo a los
recursos indispensables para su solución en:
• Tratable: Tiene solución para entradas grandes, y

una mejora algorítmica o de HW incrementa las
entradas que puede resolver.
• Intratable: No tiene solución para entradas

grandes, no puede ser resuelto por ningún
computador, no importa lo rápido que sea, cuanta
memoria tenga o cuanto tiempo se le de para que
resuelva la tarea.
Reducciones de tiempo polinomial.
Una reducción es una situación en la cual un algoritmo
desarrollado para resolver un problema A es utilizado para
resolver otro problema B.
Se tiene un software que puede solucionar ecuaciones

cuadráticas de la forma 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0 (1)
Entrada a, b, c
Salida r1,r2
Como ya se tiene un software, se quiere tratar de resolver

la ecuación 3𝑥 + 5 = 0 (2) utilizando la ecuación (1).
Reducciones de tiempo polinomial.
Será posible reducir el problema (2) al problema (1)?
Debemos transformar la entrada de la ecuación:
3𝑥 + 5 = 0 (2)
Es decir los valores 3 y 5 a los valores a,b,c utilizados por la

ecuación (1):
0𝑥 2 + 3𝑥 + 5 = 0 (1)
3x+5=0 𝑎𝑥 2 + 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0 + 𝑐 r1=-5/3
=0 (1)
Problema de Satisfacibilidad.
Es el mas representativo de todos los problemas NP, es sin
negarlo un problema NP completo.
Entrada: un conjunto de variables booleanas V y un

conjunto de clausulas C sobre las variables V.
Salida: Existirá una asignación de verdad satisfactoria para

C, una forma de configurar variables 𝑣1 , 𝑣2 , … , 𝑣𝑛
verdaderas o falsas de forma que cada clausula contenga al
menos un literal verdadero.
La entrada puede ser un conjunto de clausulas:
forma normal conjuntiva (CNF): (a v b)^(a v ¬b)
Forma normal disyuntiva (DNF): (a v b) v(a v ¬b)

Para la expresión: F=(a v b)^(a v ¬b)^(¬a v c)^(¬c v b)
Para a=1 b=1 c=1 la fórmula se satisface dando F=1
Pero para la expresión: F=(a v b)^(a v ¬b)^(¬a v c)^(¬c v¬a)

En este caso F no se satisface para cualquier asignación de
variables.
Teorema de Cook Levin.
El teorema de la Satisfacibilidad Booleana SAT
es NP-completo
La meta está en que si hay un algoritmo de tiempo

polinomial para la satisficibilidad booleana, entonces todos
los problemas en NP pueden ser resueltos en tiempo
polinomial.
De mecanismos a símbolos lógicos
Ver el video
https://www.youtube.com/watch?v=5S8bkZktcnw
Describa brevemente el funcionamiento de la pascalina
De mecanismos a símbolos lógicos
Ver el video
https://www.youtube.com/watch?v=-ZS_zFg4w5k
¿Cual es la diferencia entre el libro de instrucciones

presentado en este video y la pascalina presentado en el
video anterior?
¿En este video que representa cada página del libro?
¿En el video que es awareness?
¿En el video que es operation step?
Máquina de Turing no determinista.
Una máquina de Turing es un modelo computacional que

hace cómputos sobre valores de entrada y utiliza una cinta
de longitud infinita en la que se pueden leer escribir o
borrar símbolos.
Cuando en la máquina de Turing pueden existir varias

transiciones a partir del mismo estado se dice que es no
determinista.
Máquina de Turing no determinista.
Una maquina de Turing no determinista puede resolver

cualquier problema en NP, por lo tanto el primer paso en la
prueba es describir cada característica de la máquina en
términos de formulas lógicas, como aparecen en el
problema de satificibilidad booleana.
Técnicas de fuerza bruta
Es una técnica que consiste en enumerar sistemáticamente
todos los posibles candidatos para la solución de un
problema, con el fin de verificar, si dicho candidato es la
respuesta óptima. Pero no es una solución eficiente.
Ej: aplique un algoritmo de fuerza bruta para encontrar el

circuito hamiltoniano de mínimo costo en el siguiente
grafo. A
4 1 2
D
9 8
B 13 C
Recursión (ejemplo).
import edu.princeton.cs.algs4.StdOut;
public class exR1

{
public static String exR1(int n)
{
if (n <= 0) return " ";
return exR1(n-3) + n + exR1(n-2) + n;
}
public static void main(String[] args)
{
int a;
a=2;
StdOut.println(exR1(a));
}
}
Recursión.
Método que se llama a sí mismo teniendo en cuenta:
1. La recursión tiene un caso base: Se debe incluir una
declaración condicional como primera declaración del
programa. Esta declaración retorna un valor.
2. Las llamadas recursivas abordan sub-problemas que son

más pequeños, de forma que las llamadas recursivas
convergen al caso base.
3. Las llamadas recursivas no deben manejar sub-problemas

que se superpongan.
Nota: violar estas reglas origina resultados incorrectos ó programas

ineficientes
Búsqueda Binaria.
public class BinarySearch
{
public static int rank (int key, int[] a) { public static void main (String[] args){
int lo=0; int[] whitelist = In.readInts(args[0]);
int hi=a.length -1; Arrays.sort(whitelist);
while(lo <= hi) while(!StdIn.isEmpty())
{ {
int mid = lo + (hi-lo)/2; int key = StdIn.readInt();
if (key < a[mid]) hi = mid-1; if (rank(key,whitelist) == -1)
else if (key > a[mid]) lo =mid+1; StdOut.println(key);
else return mid; }
} }
return -1; }
}
Búsqueda Binaria recursiva.
public static int rank(int key, int[] a, int lo, int hi)
{
// Index of key in a[], if present, is not smaller than lo
// and not larger than hi.
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}
Análisis de búsqueda binaria
La implementación recursiva de la función Rank() establece

un límite superior en el número de comparaciones.
La búsqueda binaria en un array ordenado con N elementos

utiliza no mas de lgN+1 comparaciones para una búsqueda
(exitosa o no exitosa).
#pasos # ELEMENTOS NUMERO DE
PASOS
3 2
O(lgN) 7 3
15 4
100 7
100000 17
# elementos 1000000 20

Clase04 Complejidad

Cargado por

Copyright:

Formatos disponibles

Clase04 Complejidad

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Clase04 Complejidad

Cargado por

Copyright:

Formatos disponibles

Complejidad de Algoritmos

Verifique que cada borde coincida.

Si no coinciden trate otro arreglo

Para llenar la segunda celda 8.

Para llenar la tercera celda 7 cartas.

El número total de arreglos únicos para n=9 cartas es

Si se analiza un arreglo en un microsegundo:

Lo cual muestra que para n=25 tardaría 4918 siglos

De lo visto en el ejemplo anterior se dice que si un

Los demás algoritmos son de tiempo súper-polinomial

• Tratable: Tiene solución para entradas grandes, y

• Intratable: No tiene solución para entradas

Se tiene un software que puede solucionar ecuaciones

Como ya se tiene un software, se quiere tratar de resolver

Debemos transformar la entrada de la ecuación:

Es decir los valores 3 y 5 a los valores a,b,c utilizados por la

Entrada: un conjunto de variables booleanas V y un

Salida: Existirá una asignación de verdad satisfactoria para

forma normal conjuntiva (CNF): (a v b)^(a v ¬b)

Forma normal disyuntiva (DNF): (a v b) v(a v ¬b)

Pero para la expresión: F=(a v b)^(a v ¬b)^(¬a v c)^(¬c v¬a)

La meta está en que si hay un algoritmo de tiempo

¿Cual es la diferencia entre el libro de instrucciones

Una máquina de Turing es un modelo computacional que

Cuando en la máquina de Turing pueden existir varias

Una maquina de Turing no determinista puede resolver

Ej: aplique un algoritmo de fuerza bruta para encontrar el

public class exR1

2. Las llamadas recursivas abordan sub-problemas que son

3. Las llamadas recursivas no deben manejar sub-problemas

Nota: violar estas reglas origina resultados incorrectos ó programas

La implementación recursiva de la función Rank() establece

La búsqueda binaria en un array ordenado con N elementos

También podría gustarte