•objetivos1]introduccion.pdf · complexity ©d.moshkovitz 2 introducción •objetivos: –...
TRANSCRIPT
![Page 1: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/1.jpg)
Complexity©D.Moshkovitz
1
Introducción
![Page 2: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/2.jpg)
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…
![Page 3: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/3.jpg)
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
![Page 4: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/4.jpg)
Complexity©D.Moshkovitz
4
Solución para este ejemplo
Alice
Bob
Jane
John
Mary
![Page 5: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/5.jpg)
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.
![Page 6: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/6.jpg)
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!
![Page 7: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/7.jpg)
Complexity©D.Moshkovitz
7
ViajesProblema Planear un viaje que visite cada lugar una sola vez.
![Page 8: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/8.jpg)
Complexity©D.Moshkovitz
8
Solución para este ejemplo
![Page 9: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/9.jpg)
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
![Page 10: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/10.jpg)
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
![Page 11: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/11.jpg)
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)
![Page 12: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/12.jpg)
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?
![Page 13: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/13.jpg)
Complexity©D.Moshkovitz
13
Grado de crecimiento
10n
n2
2nn! =2O(n lg n)tiempo
Longitud de la entrada
![Page 14: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/14.jpg)
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)
![Page 15: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/15.jpg)
Complexity©D.Moshkovitz
15
¿Puede ser un problema (intrínsecamente) más difícil
que otro?
ViajesTea party
?
![Page 16: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/16.jpg)
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
![Page 17: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/17.jpg)
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
![Page 18: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/18.jpg)
Complexity©D.Moshkovitz
18
¿Cuál es más difícil?
ViajesTea party
?
![Page 19: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/19.jpg)
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…”
![Page 20: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/20.jpg)
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.
![Page 21: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/21.jpg)
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
. . . . . .
![Page 22: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/22.jpg)
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
. . . . . .
![Page 23: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/23.jpg)
Complexity©D.Moshkovitz
23
Línea divisoria
El problema “Tea Party” es, al menos,tan difícil como el problema “Viajes”.
![Page 24: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/24.jpg)
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.
![Page 25: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/25.jpg)
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”.
![Page 26: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/26.jpg)
Complexity©D.Moshkovitz
26
Para pensar…
• ¿Sabes reducir el problema “Tea party” al problema “Viajes”?
![Page 27: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/27.jpg)
Complexity©D.Moshkovitz
27
NPC
NPCContiene centenares de
problemas distintos
algoritmos exponenciales
algoritmos polinómicos?
Todos son reducibles entre ellos
![Page 28: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/28.jpg)
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?
![Page 29: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/29.jpg)
Complexity©D.Moshkovitz
29
¿Qué más?
• Algunas otras cuestiones que se estudiarán en este curso.
![Page 30: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/30.jpg)
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
![Page 31: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/31.jpg)
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
![Page 32: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/32.jpg)
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?
![Page 33: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/33.jpg)
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
![Page 34: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/34.jpg)
Complexity©D.Moshkovitz
34
Diccionario
Arroz
Zorro Oasis
Nieto
Zarzal
Sillón
Lesión
![Page 35: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/35.jpg)
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
![Page 36: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/36.jpg)
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?
![Page 37: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/37.jpg)
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.
![Page 38: •Objetivos1]Introduccion.pdf · Complexity ©D.Moshkovitz 2 Introducción •Objetivos: – Introducir algunos conceptos básicos de la Teoría de la complejidad. • Resumen: –](https://reader034.vdocumento.com/reader034/viewer/2022050415/5f8b53ac972bcd5d3e74b558/html5/thumbnails/38.jpg)
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