Post on 03-Aug-2020
transcript
Complexity©D.Moshkovitz
1
Introducción
Complexity©D.Moshkovitz
2
Introducción
• Objetivos:– Introducir algunos conceptos básicos de la Teoría
de la complejidad.• Resumen:
– Algunos problemas clásicos– Tiempo de ejecución– Reducciones– … y más…
Complexity©D.Moshkovitz
3
El problema “Crazy Tea Party”Problema sentar a todos los comensales alrededor de una mesa, de forma que todos se encuentren rodeados de amigos.
Alice
Alice
Jane
Bob
Mary
John
JaneBobMaryJohn
Complexity©D.Moshkovitz
4
Solución para este ejemplo
Alice
Bob
Jane
John
Mary
Complexity©D.Moshkovitz
5
Algoritmo• Por cada orden posible de los comensales
alrededor de la mesa– verificar que cada comensal tiene amigos a
ambos costados.
Complexity©D.Moshkovitz
6
¿Cuál es el coste en tiempo? (caso peor)
comensales pasos
n (n-1)!
5 24
15 87178291200
100 ≈9·10155
Si nuestra máquina es capaz de realizar 1010
instrucciones por segundo, tardaría ≈
¡3·10138 años!
Complexity©D.Moshkovitz
7
ViajesProblema Planear un viaje que visite cada lugar una sola vez.
Complexity©D.Moshkovitz
8
Solución para este ejemplo
Complexity©D.Moshkovitz
9
Algoritmo (Backtracking)
• Por cada sitio– Elige visitar un lugar accesible desde donde
estás que no hayas visitado– Márcalo a visitado y continúa por
backtrackingTermina el proceso cuando hayas visitado todo
Complexity©D.Moshkovitz
10
¿Cuánto tiempo tarda?pasos
n!
120
1307674368000
≈9·10157
Si nuestro ordenador realiza 10,000
instrucciones por segundo, tardaría
¡cuatro años!
lugares
n
5
15
100
Complexity©D.Moshkovitz
11
¿Un problema es tratable?a) ¡SI! y aquí está un algoritmo
eficiente para resolverlo
b) ¡NO! y puedo probarlo
¿Qué ocurre si no estás ni en el caso a) ni en el caso b)
Complexity©D.Moshkovitz
12
Para pensar…
• ¿Podrías diseñar un algoritmo eficiente para el problema del viaje, si la conexión entre los sitios a visitar no contuviera ciclos?
Complexity©D.Moshkovitz
13
Grado de crecimiento
10n
n2
2nn! =2O(n lg n)tiempo
Longitud de la entrada
Complexity©D.Moshkovitz
14
El mundo según la Teoría de la complejidad
Tratable = Eficiente
Intratable = Ineficiente
exponencial ≡ 2nO(1)polinómico ≡ nO(1)
Complexity©D.Moshkovitz
15
¿Puede ser un problema (intrínsecamente) más difícil
que otro?
ViajesTea party
?
Complexity©D.Moshkovitz
16
Relación entre problemas
Suponiendo que existe un procedimiento eficiente para resolver el problema A, entonces existe un procedimiento eficiente para resolver el problema B
El problema B no puede ser (intrínse_ camente) más difícil que el problema A
Complexity©D.Moshkovitz
17
Reducciones
≤pB A
El problema B no puede ser (intrínsecamente) más difícil que el problema A
En otras palabras: A es al menos tan difícil como B
Complexity©D.Moshkovitz
18
¿Cuál es más difícil?
ViajesTea party
?
Complexity©D.Moshkovitz
19
Reducción de Viajes a Tea PartyPrimera observación: Los problemas no son muy diferentes
lugar comensal
“directamente conectada a…” “amigo de…”
Complexity©D.Moshkovitz
20
Reducción de Viajes a Tea PartySegunda observación: Completando el círculo
• Invita a la fiesta a una persona muy popular,• Es decir, es amiga de todo el mundo.
Complexity©D.Moshkovitz
21
Reducción de Viajes a Tea Party
• Si existe un circuito entre lugares, hay una forma de sentar a todos los comensales alrededor de la mesa.
Comensal popular
. . . . . .
Complexity©D.Moshkovitz
22
Reducción de Viajes a Tea Party
• Si existe una forma de sentar a los comensales, podemos encontrar un circuito entre los lugares
Comensal popular
. . . . . .
Complexity©D.Moshkovitz
23
Línea divisoria
El problema “Tea Party” es, al menos,tan difícil como el problema “Viajes”.
Complexity©D.Moshkovitz
24
Discusión
• Aunque no podamos encontrar algoritmos eficientes para determinados problemas,
• ni probar que no existan tales algoritmos,• aprenderemos una herramienta que nos
permitirá relacionar los problemas atendiendo a su grado de dificultad.
Complexity©D.Moshkovitz
25
Discusión
• Es interesante adelantar que podemos reducir el problema “Viajes” al problema “Tea Party”.
• Más aún, existe una clase de problemas de forma que todos son reducibles entre ellos.
• Desde el punto de vista de la complejidad, todos los problemas de esta clase son “equivalentes”.
Complexity©D.Moshkovitz
26
Para pensar…
• ¿Sabes reducir el problema “Tea party” al problema “Viajes”?
Complexity©D.Moshkovitz
27
NPC
NPCContiene centenares de
problemas distintos
algoritmos exponenciales
algoritmos polinómicos?
Todos son reducibles entre ellos
Complexity©D.Moshkovitz
28
¿Cómo hacerse millonario estudiando Teoría de la Complejidad?
• P vs. NP es la cuestión abierta más importante en ciencias de la computación .
• Resolver esta cuestión sería un gran honor• … y supondría una gran fortuna…
www.claymath.org/prizeproblems/pvsnp.htm• Filosóficamente: Si P=NP
– El ingenio humano es innecesario– ¡No se necesitan matemáticos!
• ¿Es la naturaleza no determinista?
Complexity©D.Moshkovitz
29
¿Qué más?
• Algunas otras cuestiones que se estudiarán en este curso.
Complexity©D.Moshkovitz
30
El problema de los viajes generalizado
• Añade costes entre los lugares a visitar• Encuentra el circuito de menor coste
$8
$10$13$12
$19
$3$17
$13
Complexity©D.Moshkovitz
31
Aproximación
• ¿Se puede encontrar una aproximación del circuito de mínimo coste?
$8
$10$13$12
$19
$3$17
$13
Complexity©D.Moshkovitz
32
¿Es el tiempo de ejecución el único recurso a tener en
cuenta?• ¿Y la memoria usada (espacio)?• ¿Hay otros recursos?
Complexity©D.Moshkovitz
33
Juegos• Cada jugador debe encontrar una palabra
que comience con la misma letra con la que terminaba le palabra anterior. No pueden repetir.
Arroz ZorroOasis SillónNieto OllaAlas Salón
Complexity©D.Moshkovitz
34
Diccionario
Arroz
Zorro Oasis
Nieto
Zarzal
Sillón
Lesión
Complexity©D.Moshkovitz
35
Árbol de juego
Zorro Oasis NietoArroz Zarzal SillónLesión
OasisZorro ZarzalNieto NietoSillón Oasis Lesión
Sillón Sillón
Nieto
Nieto
Oasis
Sillón
Nieto Oasis
Sillón
Oasis Oasis Lesión Sillón Nieto Sillón Nieto Oasis
Arroz
Zorro Oasis
Zarzal
SillónNieto
Lesión
Complexity©D.Moshkovitz
36
Estrategias ganadoras• ¿Cómo podemos encontrar una estrategia
ganadora para este juego?• ¿Cuánto espacio es necesario para calcular
el árbol de juego?
Complexity©D.Moshkovitz
37
Resumen
• Hemos introducido dos problemas:– Crazy Tea party (Circuito Hamiltoniano)– Viajes (Camino Hamiltoniano)
• Aunque no sabemos mucho de ellos podemos asegurar que la dificultad computacional de ambos está relacionada.
• Aún más: sabemos que ambos pertenecen a la clase de complejidad denominada NPC.
Complexity©D.Moshkovitz
38
Resumen
• También hemos mencionado dos asuntos que se tratarán en este curso:– Algoritmos de Aproximación– Computación acotada en espacio