abstraccion y modelación en computación
DESCRIPTION
Se describen los elementos que distinguen la manera de abordar los problemas desde las ciencias de la computaciónTRANSCRIPT
-
Abstraccion y modelacion el computacion
Jose Galaviz Casas
Departamento de Matematicas,Facultad de Ciencias,
Universidad Nacional Autonoma de Mexico.
Noviembre 2009
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 1 / 54
-
Contenido
1 Abstraccion.
2 Problema 1: Percolacion.El fenomenoLos modelosAlgoritmoAplicaciones
3 Problema 2: Portafolios de inversion.El problemaEl modeloProblema intratable
4 Un panorama de la complejidad
5 Problemas intratables.
6 Conclusion
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 2 / 54
-
El mundo es un lugar complicado...
Cada pequeno objetoesta influido porinnumerables factores.
Imposible de abordar.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 3 / 54
-
El mundo es un lugar complicado...
Cada pequeno objetoesta influido porinnumerables factores.
Imposible de abordar.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 3 / 54
-
Un fenomeno simple?
Una canica de vidrio rodando sobre una mesa inclinada.Que determina su movimiento?
El angulo con el que la mesaesta inclinada y la aceleracionde la fuerza de gravedad de latierra.
La altitud a la que seencuentra la canica.
La rugosidad de la superficie dela mesa y de la canica.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 4 / 54
-
Factores
Los fotones son energa, as que tambien el ndice derefraccion de la canica, la reflectividad de la mesa y laintensidad de la luz que incide en ellas.
La fuerza de atraccion de la luna y el resto de los planetas.
La viscosidad del aire que rodea la canica.
La temperatura ambiental.
Los rayos cosmicos.
El grado de uniformidad en la densidad de la canica.
Etcetera.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 5 / 54
-
Abstraccion
Tratar de abordar en su totalidad aun el mas simple de losfenomenos es impensable.
Solo podemos simplificar.
Debemos poder discriminar lo importante de lo superfluo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 6 / 54
-
La frontera entre lo esencial y lo superfluo
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 7 / 54
-
La abstraccion adecuada
Depende
Cuando estudiamos el movimiento de la canica despreciamossu color, sus propiedades electrostaticas y magneticas, sundice de refraccion, su composicion.
Si nos interesara como altera un campo magnetico nosfijaramos en otras caractersticas y despreciaramos otras.
De haber considerado importante la temperatura de Pisa unatarde de primavera, Galileo no nos hubiera regalado el germende la gravitacion.
Como se a priori que importa y que no?
No hay regla infalible.
Depende de que lectura queremos hacer y como.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 8 / 54
-
Un par de buenas abstracciones
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 9 / 54
-
Fsica
Ante un acontecimiento de su interes, que ve un fsico?
Un fenomeno.
Un conjunto de objetos sometidos a las leyes de la naturaleza.
Leyes que desea conocer.
Saber la causa.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 10 / 54
-
Actuara
Ante un acontecimiento de su interes, que ve un actuario?
Uno de un conjunto de posibles hechos.
Cada uno con cierta probabilidad de ocurrir.
Algunos deseables y otros no.
Saber evaluar el riesgo de que ocurran los ideseables.
Saber que hacer para salir bien librados si ocurren.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 11 / 54
-
Matematicas
Ante un acontecimiento de su interes, que ve un matematico?
Un patron.
Un conjunto de relaciones entre objetos.
Relaciones con cierta estructura.
Que desea determinar.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 12 / 54
-
Computacion
Ante un acontecimiento de su interes, que ve un computologo?
Un proceso.
Que transforma un conjunto de objetos en otro.
Desea saber si el proceso es algortmico.
Y encontrar el algoritmo (optimo) que lo lleva a cabo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 13 / 54
-
La abstraccion en computacion
Determinar cuales son los objetos, que entran al proceso: laENTRADA.
Determinar cuales son los objetos, que salen del proceso: laSALIDA.
Determinar que caractersticas son las que determinan latransformacion y que pasos la llevan a cabo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 14 / 54
-
Algoritmo
Dado un dispositivo de computoM, un algoritmo es:
Una secuencia finita yordenada de pasos.
Comprensibles sinambiguedad y ejecutablespor M.
Que recibe un conjunto dedatos de entrada.
Y produce un conjunto dedatos de salida.
Los conjuntos de entrada y salidason discretos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 15 / 54
-
Recursos
Durante su ejecucion un algoritmo consume recursos:
Tiempo.
Memoria. La necesaria para almacenar datos que seprocesaran, resultados parciales, resultados.
Aveces otras cosas.
Un algoritmo es tanto mas eficiente cuanto menos recursosrequiera para llevar a cabo su labor.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 16 / 54
-
Percolacion
Desplazamiento de fluido atraves de un medio poroso.
Equivalentemente el flujo decorriente electrica a travesde un medio de resistenciaheterogenea (que cambiaaleatoriamente con laposicion).
Durante los ultimos 20 anosha sido estudiado por fsicosy matematicos.
Exhibe comportamientocomplejo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 17 / 54
-
Modelo
Como modelamos esto?
El medio es un campo de fuerza (oposicion al fluido) variable.
Modelo continuo basado en las ecuaciones que rigen elcomportamiento del campo.
y la fuerza con que el fluido trata de desplazarse.
MUY complicado.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 18 / 54
-
Pensando como computologo
Modelo discreto.
El medio es una latiz (malla)de puntos uniformementeespaciados.
La resistencia es un valorasociado con cada sitio de lamalla: {0, 1}.Cada sitio, con probabilidad pes resistente (permisivo conprobabilidad 1 p).El fluido entra en la mallapor un sitio determinado.
El tiempo avanza en pasos.
En cada paso el fluido buscalos sitios vecinos por dondepueda pasar.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 19 / 54
-
Umbral
Se observa que hay un valor crtico en la probabilidad (pc).
Si p < pc el numero de caminos por donde se puede fluirdecae exponencialmente con p.
Si p > pc siempre percola.
pc se llama punto de transicion de fase. Comportamientocualitativamente diferente antes y despues de pc .
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 20 / 54
-
Generalizando
Que tal si el valor de los sitiosya no es solo binario?
Ahora el problema es ver sihay una cadena de sitiossuficientemente debil.
El fluido tiende adesplazarse por los puntosde menor resistencia.
Configuracion de mnimaenerga.
Puntos = nodos de unagrafica.
Resistencias = costosasociados a las aristas de lagrafica.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 21 / 54
-
Algoritmo de Dijkstra
Dado un nodo distinguido s, encuentra el camino de costomnimo para ir de s a todos los demas nodos alcanzables.
Si los costos son no negativos.
Tarda un tiempo polinomial (depende de un polinomioevaluado en n, el numero de nodos).
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 22 / 54
-
Inicializacion
Entrada: la grafica y el nodo de partida s.
Inicializamos el registro de costos en:
Cero para s.Para los vecinos de s, el costo de la arista que los une con el.Infinito para todos los demas.
Salida: El registro de costos indicando, para cada nodo, elcosto mnimo para llegar a el desde s.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 23 / 54
-
Inicializacion (pseudocodigo)
Inicializa(G ,w , s)1 costo[s] 02 ant[s]3 Y {s}4 X V \ {s}5 for v X do6 if v G .vecinos(s) then7 costo[v ] w(s, v)8 ant[v ] s9 else
10 costo[v ]11 ant[v ]12 endif13 endfor14 return (costo, ant,X ,Y )15 end
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 24 / 54
-
Algoritmo
Dijkstra(G ,w , s)1 while X 6= do2 u costo.minimoCosto(X )3 X X \ {u}4 Y Y {u}5 for v G .vecinos(u) do6 d costo[u] + w(u, v)7 if d < costo[v ] then8 costo[v ] d9 ant[v ] u
10 endif11 endfor12 endwhile13 return (costo, ant)14 end
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 25 / 54
-
Ejecucion (1/2)
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 26 / 54
-
Ejecucion (2/2)
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 27 / 54
-
Para que sirve?
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 28 / 54
-
Extraccion terciaria
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 29 / 54
-
Otros usos
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 30 / 54
-
Portafolios de inversion
En el mercado de valores sevenden y compran accionesde acuerdo con la ley deoferta y demanda.
Todos los das unas suben yotras bajan.
Existen inversionistas quesustentan a las empresasemisoras de las accionescomprandolas.
Los inversionistas (sobradecirlo) quieren obtener losmayores beneficios posibles.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 31 / 54
-
No poner todos los huevos ...
...en la misma canasta.
Se corre un gran riesgo invirtiendo en una sola emisora.
Diversificar la inversion comprando una cantidad ci deacciones de N diferentes emisoras.
Cuantas compramos de cada una?, de cuales emisoras?
Cada emisora tiene diferente riesgo de perder valor.
Cada emisora tiene diferentes posibilidades de subir su valor.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 32 / 54
-
Los parametros
Medida de riesgo: VaR (Value at Risk).
Dada una emisora ei
Dado un periodo de tiempo t. Normalmente un da o dossemanas.
Dada una probabilidad p. Normalmente 0.01 o 0.05 (loseconomistas prefieren usar porcentajes: 1 % o 5 %respectivamente).
El VaR es el monto de dinero maximo que la emisora puededepreciarse en el horizonte de tiempo t con probabilidad p.
Por ejemplo: si el VaR un da 5 % de una compana es de 3millones de pesos, significa que esa compana tiene el riesgode perder 3 millones en un da con probabilidad de 0.05.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 33 / 54
-
Ilustrando
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 34 / 54
-
Modelo
El conjunto de elementos discretos son las acciones.
De all hay que elegir: problema de optimizacion combinatoria.
El numero de combinaciones puede ser muy grande: elconjunto potencia multiplicado por las combinaciones deproporciones de cada accion en el portafolio.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 35 / 54
-
Analisis
Explorar la explosion combinatoria de posibilidades:impensable.
Ventaja: no se nos imponen restricciones sobre la cantidad deacciones de una emisora que se pueden comprar.
Podemos decidir la proporcion de cada una arbitrariamente,hasta un cierto monto maximo determinado por la cantidadde acciones de la emisora circulando. Pero podemos comprarmenos que eso.
Apostar a la emisora que vale su riesgo en oro. Una buenarelacion costo beneficio.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 36 / 54
-
El algoritmo
Para cada emisora calcular el cociente rentabilidadVaR .
Medida de la relacion costo-benefcio.
Comprar todo lo que se pueda de la que tiene mayor cociente.Luego de la segunda mejor...
Tarda un tiempo proporcional al numero de emisoras a evaluar(n).
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 37 / 54
-
El problema de la mochila
Este es un caso particular delconocido como el problema de lamochila (0/1).
Un ladron posee una mochilacapaz de llevar cierta cargamaxima en kilogramos C .
Se encuentra en una casa en laque hay diversos artculos{a1, a2, . . . , an}.Cada artculo tiene un ciertovalor en el mercado negro{v1, v2, . . . , vn}Pregunta: Que artculos deborobar de tal forma que obtengael maximo beneficio sinsobrepasar el peso que puedecargar la mochila?
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 38 / 54
-
Condiciones diferentes
Por cada artculo solo se puede decidir si llevarlo o no, noque tanto de el llevar.
Es decir cada artculo implica una decision binaria.
Por eso no se puede aplicar el criterio del cocientebeneficio-costo anterior.
Es como si una vez que decidimos comprar acciones de unaemisora estuvieramos obligados a comprarlas todas. Todo onada.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 39 / 54
-
Ejemplo
Una mochila que puede cargar hasta 50 Kg y tres diferentesartculos:
1 Peso:10 Kg. Valor: $60. Relacion: 60/10 = 6.
2 Peso: 20 Kg. Valor: $100. Relacion: 100/20 = 5.
3 Peso: 30 Kg. Valor: $120. Relacion: 120/30 = 4.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 40 / 54
-
Con lo que sabamos
Escogeramos llevar todo el primer artculo. Llevamos 10 Kg.
Luego el segundo artculo. Ahora son 30 Kg.
Ya no podemos llevar el tercer artculo completo, perollevamos 20 de sus 30 Kg, lo que nos proporciona un beneficiode 23 120 = 80.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 41 / 54
-
Ilustrando
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 42 / 54
-
La vida real
Claro, nuestro problema original del portafolio de inversion estabasobre-simplificado.
No es trivial pronosticar el comportamiento de las acciones.
Se consideran otros factores como la volatilidad.
Muchas emisoras estan correlacionadas, el precio de susacciones no es una variable aleatoria independiente.
En general no es posible comprar las acciones que te venganen gana.
El hecho mismo de comprar o vender altera el valor de lasacciones.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 43 / 54
-
Analisis
El problema de la mochila (0/1) tampoco es trivial.
Se tienen n objetos que es posible llevar.
As que hay 2n posibles alternativas a evaluar.
Se pueden descartar muchos rapidamente.
Pero no importa en general.
Siempre se puede construir una entrada que haga que elalgoritmo que busca la solucion se tarde un tiempoproporcional a 2n.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 44 / 54
-
Y lo hay peores
No existe un algoritmo que...
Dado un programa cualquiera P y un conjunto de datos deentrada D, diga si P(D) termina en algun momento.
Dado un programa cualquiera P y un algoritmo cualquiera A,diga si P ejecuta A.
Dados un par de programas cualesquiera P y Q, diga si P y Qejecutan el mismo algoritmo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 45 / 54
-
Y lo hay peores
No existe un algoritmo que...
Dado un programa cualquiera P y un conjunto de datos deentrada D, diga si P(D) termina en algun momento.
Dado un programa cualquiera P y un algoritmo cualquiera A,diga si P ejecuta A.
Dados un par de programas cualesquiera P y Q, diga si P y Qejecutan el mismo algoritmo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 45 / 54
-
Y lo hay peores
No existe un algoritmo que...
Dado un programa cualquiera P y un conjunto de datos deentrada D, diga si P(D) termina en algun momento.
Dado un programa cualquiera P y un algoritmo cualquiera A,diga si P ejecuta A.
Dados un par de programas cualesquiera P y Q, diga si P y Qejecutan el mismo algoritmo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 45 / 54
-
Y lo hay peores
No existe un algoritmo que...
Dado un programa cualquiera P y un conjunto de datos deentrada D, diga si P(D) termina en algun momento.
Dado un programa cualquiera P y un algoritmo cualquiera A,diga si P ejecuta A.
Dados un par de programas cualesquiera P y Q, diga si P y Qejecutan el mismo algoritmo.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 45 / 54
-
Problemas computables y no computables
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 46 / 54
-
Y entre los computables... tambien hay clases
No todos los computables son igualmente difciles:
Encontrar el maximo de una lista de n numeros tarda untiempo proporcional a n.
Sumar dos matrices de orden n tarda un tiempo proporcionala n2 unidades de tiempo.
Dada una formula logica de n variables de la forma:(x1 x2 x3) (x2 x4 x7) . . . (normal conjuntiva),encontrar la asignacion de valores de verdad para las variables,que satisface la formula, si existe, tarda un tiempoproporcional a 2n ...
al menos eso creemos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 47 / 54
-
Y entre los computables... tambien hay clases
No todos los computables son igualmente difciles:
Encontrar el maximo de una lista de n numeros tarda untiempo proporcional a n.
Sumar dos matrices de orden n tarda un tiempo proporcionala n2 unidades de tiempo.
Dada una formula logica de n variables de la forma:(x1 x2 x3) (x2 x4 x7) . . . (normal conjuntiva),encontrar la asignacion de valores de verdad para las variables,que satisface la formula, si existe, tarda un tiempoproporcional a 2n ...
al menos eso creemos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 47 / 54
-
Y entre los computables... tambien hay clases
No todos los computables son igualmente difciles:
Encontrar el maximo de una lista de n numeros tarda untiempo proporcional a n.
Sumar dos matrices de orden n tarda un tiempo proporcionala n2 unidades de tiempo.
Dada una formula logica de n variables de la forma:(x1 x2 x3) (x2 x4 x7) . . . (normal conjuntiva),encontrar la asignacion de valores de verdad para las variables,que satisface la formula, si existe, tarda un tiempoproporcional a 2n ...
al menos eso creemos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 47 / 54
-
Y entre los computables... tambien hay clases
No todos los computables son igualmente difciles:
Encontrar el maximo de una lista de n numeros tarda untiempo proporcional a n.
Sumar dos matrices de orden n tarda un tiempo proporcionala n2 unidades de tiempo.
Dada una formula logica de n variables de la forma:(x1 x2 x3) (x2 x4 x7) . . . (normal conjuntiva),encontrar la asignacion de valores de verdad para las variables,que satisface la formula, si existe, tarda un tiempoproporcional a 2n ...
al menos eso creemos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 47 / 54
-
Y entre los computables... tambien hay clases
No todos los computables son igualmente difciles:
Encontrar el maximo de una lista de n numeros tarda untiempo proporcional a n.
Sumar dos matrices de orden n tarda un tiempo proporcionala n2 unidades de tiempo.
Dada una formula logica de n variables de la forma:(x1 x2 x3) (x2 x4 x7) . . . (normal conjuntiva),encontrar la asignacion de valores de verdad para las variables,que satisface la formula, si existe, tarda un tiempoproporcional a 2n ... al menos eso creemos.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 47 / 54
-
Problemas intratables
Aquellos para los cuales no hemos podido encontrar un algoritmoque ocupe un tiempo proporcional a alguna potencia de n (tiempopolinomial).
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 48 / 54
-
Categoras
P: los de solucion polinomial.
NP: los anteriores mas aquellospara los que no tenemos (hastaahora) solucion polinomial.
NP-completos: los mas difciles delos que estan en NP.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 49 / 54
-
Categoras
P: los de solucion polinomial.
NP: los anteriores mas aquellospara los que no tenemos (hastaahora) solucion polinomial.
NP-completos: los mas difciles delos que estan en NP.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 49 / 54
-
Categoras
P: los de solucion polinomial.
NP: los anteriores mas aquellospara los que no tenemos (hastaahora) solucion polinomial.
NP-completos: los mas difciles delos que estan en NP.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 49 / 54
-
Categoras
P: los de solucion polinomial.
NP: los anteriores mas aquellospara los que no tenemos (hastaahora) solucion polinomial.
NP-completos: los mas difciles delos que estan en NP.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 49 / 54
-
Los NP-completos
Todos son equivalentes:
La solucion de uno de ellos puede transformarse en la solucionde otro en tiempo polinomial.
Un ejemplar de uno de ellos puede transformarse en uno deotro en tiempo polinomial.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 50 / 54
-
Los NP-completos
Todos son equivalentes:
La solucion de uno de ellos puede transformarse en la solucionde otro en tiempo polinomial.
Un ejemplar de uno de ellos puede transformarse en uno deotro en tiempo polinomial.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 50 / 54
-
Los NP-completos
Todos son equivalentes:
La solucion de uno de ellos puede transformarse en la solucionde otro en tiempo polinomial.
Un ejemplar de uno de ellos puede transformarse en uno deotro en tiempo polinomial.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 50 / 54
-
Ejemplos
Agente viajero: Un conjunto de ciudades, costos de viaje entreellas. Se requiere el viaje redondo mas barato que pase portodas las ciudades.
Satisfactibilidad: Una expresion logica del tipo(x1 x2 x3) (x2 x4 x7) . . . Se requiere saber quevalor de verdad asignarle a cada variable para que toda laexpresion sea verdadera.
La mochila: Una cierta capacidad positiva C , un conjunto deobjetos con peso y valor. Se requiere encontrar el subconjuntode objetos que maximizan el valor son sobrepasar C en peso.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 51 / 54
-
Ejemplos
Agente viajero: Un conjunto de ciudades, costos de viaje entreellas. Se requiere el viaje redondo mas barato que pase portodas las ciudades.
Satisfactibilidad: Una expresion logica del tipo(x1 x2 x3) (x2 x4 x7) . . . Se requiere saber quevalor de verdad asignarle a cada variable para que toda laexpresion sea verdadera.
La mochila: Una cierta capacidad positiva C , un conjunto deobjetos con peso y valor. Se requiere encontrar el subconjuntode objetos que maximizan el valor son sobrepasar C en peso.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 51 / 54
-
Ejemplos
Agente viajero: Un conjunto de ciudades, costos de viaje entreellas. Se requiere el viaje redondo mas barato que pase portodas las ciudades.
Satisfactibilidad: Una expresion logica del tipo(x1 x2 x3) (x2 x4 x7) . . . Se requiere saber quevalor de verdad asignarle a cada variable para que toda laexpresion sea verdadera.
La mochila: Una cierta capacidad positiva C , un conjunto deobjetos con peso y valor. Se requiere encontrar el subconjuntode objetos que maximizan el valor son sobrepasar C en peso.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 51 / 54
-
Ejemplos
Agente viajero: Un conjunto de ciudades, costos de viaje entreellas. Se requiere el viaje redondo mas barato que pase portodas las ciudades.
Satisfactibilidad: Una expresion logica del tipo(x1 x2 x3) (x2 x4 x7) . . . Se requiere saber quevalor de verdad asignarle a cada variable para que toda laexpresion sea verdadera.
La mochila: Una cierta capacidad positiva C , un conjunto deobjetos con peso y valor. Se requiere encontrar el subconjuntode objetos que maximizan el valor son sobrepasar C en peso.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 51 / 54
-
El problema del agente viajero
n
f (n)
polinomial
n!
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 52 / 54
-
Que se hace en estos casos?
El problema proviene del hecho de tener que recorrer todo elespacio de busqueda para encontrar la solucion.
No hay atajos.
O no sabemos si hay, no los hemos visto.
Se requiere de explorar el espacio de busquedainteligentemente, sin revisar a todos sus elementos: Heurstica.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 53 / 54
-
A manera de conclusion
Los computologos, igual que el resto de los cientficos,tenemos nuestro estilo de abordar los problemas.
Dictado por las abstracciones de que disponemos.
Lo mejor es que esas abstracciones resultan utiles tambienotras ciencias.
Tienden a simplificar algunos fenomenos porque losdiscretizan en tiempo y espacio.
Y los someten a un proceso automatico.
Jose Galaviz Casas (Facultad de Ciencias, UNAM) Abstraccion y modelacion en computacion Nov/2009 54 / 54
Abstraccin.Problema 1: Percolacin.El fenmenoLos modelosAlgoritmoAplicaciones
Problema 2: Portafolios de inversin.El problemaEl modeloProblema intratable
Un panorama de la complejidadProblemas intratables.Conclusin