Problemas del milenio por Un millón de dólares
- P versus NP
- La conjetura de Hodge
- La conjetura de Poincaré
- La hipótesis de Riemann
- Existencia de Yang-Mills y del salto de masa
- Las ecuaciones de Navier-Stokes
- La conjetura de Birch y Swinnerton-Dyer
Complejidad algorítmica
¿Ya tomaste el Curso de Pensamiento Computacional?
Introducción a la complejidad algorítmica
Abstracción
Notación asintótica
Clases de complejidad algorítmica
Algoritmos de búsqueda y ordenación
Búsqueda lineal
Búsqueda binaria
Ordenamiento de burbuja
Ordenamiento por inserción
Ordenamiento por mezcla
Ambientes virtuales
Ambientes virtuales
Graficado
¿Por qué graficar?
Graficado simple
Algoritmos de optimización
Introducción a la optimización
El problema del morral
Conclusiones
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Introducción a la optimización
14/16Recursos
Aportes 111
Preguntas 4
Ordenar por:
Seria muy interesante curso en platzi de este tema!!!
Me pase 4 dias viendo videos y problemas de n - np // mala idea profundirzar 😃
El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.
Revisen este video del canal derivando 😉 es buenisimo y explica bien.
si quieren indagar mas en optimizacion pueden buscar programacion lineal o no lineal, donde encontraran cosas como el metodo simplex. Recomiendo el libro taha o hillier son de “investigacion de operaciones”. Aqui encontraran muchos otros algoritmos para resolver problemas de minimos y maximos.
Existe la Metaheuristica, que da soluciones aproximadas:
En múltiples problemas de IA nos encontramos modelos asociados a problemas de optimización y búsqueda. Los algoritmos metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda.
Comparto este video sobre el Traveling Salesman Problem que lo explica de una forma visual muy buena:
https://www.youtube.com/watch?v=SC5CX8drAtU
Casualmente, hay un librería dePython llamada Gurobi que está optimizada para Programaci’no Lineal Entera que es una forma de programación que se utiliza para resolver Problemas como el del Travel Salesman
Aquí lo explican con más ejemplos. Es muy interesante sobretodo a partir del min 5.
https://www.youtube.com/watch?v=wsIru1p5fs0
https://github.com/karlbehrensg/poo-y-algoritmos-python
Introducción a la optimización
El concepto de optimización permite resolver muchos problemas de manera computacional. Cuando pensamos en un algoritmo de optimización debemos definir una función objetivo que debemos maximizar o minimizar, respetando una serie de limitantes que definamos.
Un solución no tan eficiente pero si un poco optima que lei al problema del travelling salesman es hacer conjuntos pequeño, es decir con 12 ciudades hacer 4 conjuntos de 3 ciudades, probar la ruta mas pequeña entre esas 3 ciudades y asi con cada conjunto, luego repetir esto con los conjutos, espero se haya entendido mi explicación
1M cash no questions asked. That’s what I like 😎
Para ver la película Traveling Salesman:
PROBLEMA DEL VENDEDOR VIAJERO
Consiste en un comerciante que quiere visitar n ciudades, empezando y terminando en la misma ciudad y debe determinar el recorrido a seguir para que la distancia sea minima.
Se engloba dentro de los denominados problemas de rutas.
“P versus NP” es algo más que un rompecabezas matemático abstracto. Su objetivo es determinar—de una vez por todas—qué tipo de problemas se pueden resolver con ordenadores, y cuáles no. Los problemas de clase “P” son “fáciles” de resolver para los ordenadores; es decir, las soluciones a estos problemas pueden ser calculadas en una cantidad razonable de tiempo, en comparación con la complejidad del problema.
La solución de este tipo de problemas es toda una rama de la inteligencia artificial conocida como Constraint Satisfaction Problems (CSP), aquí un ejemplo: https://www.youtube.com/watch?v=lCrHYT_EhDs
Si alguien esta interesado en saber mas sobre los tipos de optimización, les recomiendo el libro Introducción a la investigación de operaciones de Frederick S Hillier, Gerald J. Lieberman.
Para iniciar en mundo de la optimización es el método simplex.
He aquí una explicación del problema ¿P = NP?
https://www.youtube.com/watch?v=UR2oDYZ-Sao
Hola a todos, les comparto mi grafica, es el historico semanal de la cotización de bitcoin de yahoo finance. lo pueden obtener descargando yfinance o yahoo-finance en sus terminales. Gracias!
from WIKI:
El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.
El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas.
El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).
En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dado un largo “L”, la tarea es decidir cuál grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades.
Esto es Investigación de operaciones y programación lineal. Aquí todas las restricciones se expresan de forma matemática, ya sean ecuaciones o inecuaciones.
PROBLEMAS DE TIPO P:
-
Aquellos cuya solución puede encontrarse con rapidez.
-
Ejemplo: Dado un mapa de carreteras en el que aparecen n ciudades, ¿es posible ir desde cualquier ciudad hasta cualquier otra? Para un valor elevado de n, el número de pasos que necesita ejecutar un ordenador crece como n^2; es decir, como un polinomio en n.
-
Dado que el valor de un polinomio aumenta de manera relativamente modesta a medida que lo hace n, los ordenadores pueden resolver problemas de tipo P en un tiempo razonable.
PROBLEMAS NP:
-
Aquellos cuya solución puede verificarse con rapidez.
-
Ejemplo: Supongamos que sabemos que cierto número de n dígitos es el producto de dos números primos grandes y que deseamos hallar dichos factores. Si alguien nos los proporciona, podremos comprobar en tiempo polinómico (multiplicándolos) que constituyen la solución.
PROBLEMAS NP-COMPLETOS:
-
No deterministas en tiempo polinómico. Los más difíciles de resolver.
-
Ejemplo: Dado un mapa con n países, ¿será posible pintarlo con solo tres colores de modo que no haya países contiguos del mismo color? Si existiera un algoritmo para resolver este problema en tiempo polinómico, dicho algoritmo podría adaptarse para resolver cualquier otro problema de tipo NP (como el de la descomposición en factores primos).
En este sentido, los problemas NP-completos constituyen los problemas NP de máxima dificultad. Hasta hoy no se conoce ningún algoritmo capaz de resolver de manera eficiente un problema de tipo NP-completo.
¿Cuál es entonces el problema que tiene en jaque a gran parte de los matemáticos e informáticos? Pues el hecho es que se ha conseguido demostrar que si se puede encontrar fácilmente una solución para un problema NP, esta también se podrá verificar de manera sencilla, por lo que todo problema P es también NP. Pero no se ha conseguido demostrar que existan problemas NP que no sean P.
- Si alguien consiguiese demostrar que P=NP estaríamos ante una crisis a nivel mundial, los sistemas criptográficos quedarían invalidados y se marcaría una etapa sin precedentes en la historia.
En dicho caso… ¿existiría otra forma de resolver los problemas NP? 🤔
Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.
- El concepto de optimización permite resolver muchos problemas de manera computacional.
- Una función objetivo que debemos maximizar o minimizar.
- Una serie de limitantes que debemos respetar.
Muy interesante este tema.
Uf! Estas clases motivan, a investigar más sobre el traveling salesman.
El TSP yo lo he trabajado con algoritmos genéticos, sin embargo quiero aprender más sobre inteligencia artifical, como maching learning o redes neuronales.
Compañeros, profesor, en el siguiente link les comparto algo de mi trabajo …
Buscaré más acerca de Travelling Salesman
Optimización
Son algoritmos en los que buscamos la respuesta optima (maximizamos o minimizamos nuestros resultados). Respetando una serie de limitaciones que vienes de nuestro modelado.
Nota:
- No todos los problemas se pueden resolver (problema P/NP)
Les comparto este video, uno de los mejores videos
https://www.youtube.com/watch?v=1x4VbYerGsA
Algoritmo de Dijkstra
El algoritmo de Dijkstra, que es utilizado para encontrar el camino más corto desde un nodo de inicio hasta todos los demás nodos en un grafo ponderado y dirigido, no es adecuado para resolver directamente el Problema del Viajante (también conocido como TSP, por sus siglas en inglés “Traveling Salesman Problem”).
El Problema del Viajante es un problema NP-duro, lo que significa que no se ha encontrado una solución eficiente (polinomial) para resolverlo en todos los casos. El objetivo del Problema del Viajante es encontrar la ruta más corta que pase por todos los nodos (ciudades) visitándolos exactamente una vez y regresando al nodo de origen.
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo de inicio hasta todos los demás nodos, pero no garantiza que la ruta encontrada pase por todos los nodos exactamente una vez. En otras palabras, Dijkstra no resuelve el Problema del Viajante, ya que no tiene en cuenta la restricción de visitar todos los nodos una sola vez.
El Problema del Viajante se considera un problema de optimización combinatorial y requiere enfoques específicos, como algoritmos heurísticos (por ejemplo, el algoritmo del vecino más cercano, el algoritmo del vecino más cercano mejorado, el algoritmo de inserción, etc.) o algoritmos de programación dinámica para encontrar soluciones aproximadas o soluciones óptimas en ciertos casos.
El algoritmo de Dijkstra no es adecuado para resolver directamente el Problema del Viajante debido a que este último es un problema de optimización más complejo que requiere enfoques específicos y algoritmos especiales para encontrar soluciones aproximadas o soluciones óptimas.
Que tema tan brutal, gracias a los compañeros que han dejado tan buenos aportes.
Puntos vistos en esta clase
- Algoritmos de optimización
- Funciones a maximizar o minimizar
- Limitantes a considerar en optimización
- El problema del viajero
- Dificultad de resolución de algunos problemas de optimización
- La importancia de la eficiencia en algoritmos de optimización
- La relación entre algoritmos de optimización y empresas millonarias
- La existencia de problemas que no pueden resolverse de manera eficiente
- La importancia de investigar y reflexionar sobre los problemas de optimización
Muy buena clase.
Todo mundo sabe que P = NP para N = 1 😃
Optimization de verdad: https://developers.google.com/optimization/introduction/overview
Aquí dejo mi código comentado.
#Importamos librerías desde Bokeh. figure es para tener la ventana donde se muestra gráfico.
#output_file es para nombrar el archivo html a generar. show es para crear un servidos que mostrará el html.
from bokeh.plotting import figure, output_file, show
if __name__ == '__main__':
#Nombramos archivo de salida
output_file('graficado_simple.html')
#Generamos la figura, es decir, dónde pondremos el gráfico
fig = figure()
#Pedimos valores a graficar
total_vals = int(input('¿Cuántos valores quieres graficar?'))
#Con el número dado por el usuario creamos una lista de valores independientes
x_val = list(range(total_vals))
#Inicializamos lista de valores dependientes
y_val = []
#Pedimos al usuario valos dependientes
for x in x_val:
val = int(input(f'Valor y para {x}:'))
y_val.append(val)
#Aquí dibujamos la figura indicando los valores para el eje de las abscisas (x) y las ordenadas (y)
#En esta sentencia podemos poner los estilos que llevará el gráfico
fig.line(x_val, y_val, line_width=2)
#Para pedir a bokeh que nos muestre la figura
show(fig)
Madrugándole al Platzi, jaja
Yandere dev sale del chat
Si les interesa profundizar, hay una disciplina que estudia específicamente este tema y se llama Investigación de operaciones, aunque es recomendable primero entender álgebra lineal.
El concepto de optimización permite resolver muchos problemas de manera computacional. Cuando pensamos en un algoritmo de optimización debemos definir una función objetivo que debemos maximizar o minimizar, respetando una serie de limitantes que definamos.
Creo que estos son de los denominados problemas imposibles, tales como los que se usan para hacer encriptación.
Polinomiales*
Graficando la función Seno(x)
from bokeh.plotting import figure, output_file, show
import math
import numpy as np
if __name__ == '__main__':
output_file('graficado_simple.html')
fig = figure()
x_vals = np.arange(0,20,0.1)
y_vals = []
for x in x_vals :
val = math.sin(x)
y_vals.append(val)
fig.line(x_vals,y_vals,line_width=2)
show(fig)
También encontramos problemas dentro de nuestros conceptos algorítmicos, que todavía no se han resuelto, como la diferencia entre polinomineal vs no polinomineal.
The travelling sales man, es un problema, que todavía no tiene solución y que demuestra que hay problemas que el humano, todavía no es capaz de resolver por el momento.
Los problemas de optimización, no son solo cuestiones académicas. También son formas de modelar soluciones para el mundo real.
Hay que tener en cuenta todos los constraints, para encontrar valores dentro de esos parámetros.
Tenemos que repestar ciertas limitantes a la hora de optimizar.
Maximizar, se refiere a encontrar el input que devuelve el outpur más alto, mientras que minimizar, se refiere a el input que retorna el output más pequeño.
Pensar en algoritmos de optimización, pensamos en una función por maximizar o minimizar.
Los grandes problemas del mundo, se pueden reducir a problemas de optimización.
La optimización, nos permite comprender todo un amalgama de problemas computacionales.
La forma en cómo optimizamos nuestros algoritmos, es encontrando valores con ciertas características.
Seria muy interesante un curso de optimización computacional en Platzi.
Excelente clase! 😄
billones = miles de millones
Este video ayuda a entender el problema del agente viajero que nos mencionó David en la clase. O el famoso"Traveling salesman problem"
https://www.youtube.com/watch?v=LUuSLdBSejQ
Espero a alguien le pueda servir. Es explicación básica pero concisa.
Optimización
Rezolver muchos problemas de manera computacional.
Traveling salesman.
Premios Turing
El problema de Ruta de Transporte no se resuelve con derivadas debido a que el problema contiene demasiadas variables, para ello existen algoritmos clásicos pararesolverestos problemas. como Algoritmo de Esquina Noroeste, Ruta mas corta. Todos estos los puedes encontrar en cualquier libre de Investigacion de Operaciones, yo les recomiendo el Taha. si quieren profundizar mas en esto.
Optimizacion: En mi experiencia vi una materia en el 9no semetres de ingenieria de sistemas respecto a optimizacion de sistemas y algoritmos y pues me encontraba con problemas como el que explico el profesor uno por logica puede pensar de que si agarra la ruta A llegaras mas rapido a la ruta B, pero no es tan sencillo como parece en el ambito de la optimizacion se requiere utilizar muchos modelos matematicos y estadisticos para encontrar la solucion adecuada a este problema y a eso sumale la complejidad del algoritmo, lo que quiere decir si realmente este algoritmo es eficiente para este problema, por que no basta solamente con una respuesta sino saber si la respuesta es factible o no, realmente un campo muy bonito donde se ven las matematicas, estadisticas y logica computacional, para algunos puede ser complejos o aterrador pero una vez que lo entiendes o lo comprendes te daras de cuenta que es algo muy hermoso como los numeros te guian a la respuesta deseada.
¿Habrá algún curso enfocado a la optimización en profundidad? 🤓
Hay que diferenciar entre problemas de optimización y problemas de decisión para entender ciertos detalles interesantes. En los primeros se busca un máximo o mínimo, mientras que en los últimos se busca la existencia de un cierto objeto. El problema P vs NP es una pregunta sobre problemas de decisión.
El TSP (traveling salesman problem) es un problema de optimización en el cual se busca un mínimo. Es fácil ver que hay un problema de decisión asociado a el TSP: “Hay un camino de longitud menor o igual a X?” donde X es un numero positivo.
TSP es un problema NP-hard y el problema de decisión asociado a el es NP-complete.
Los problemas P son aquellos para los que existe un algoritmo determinista de tiempo polinomial que lo resuelve (el algoritmo puede construir en tiempo polinomial el objeto deseado). Los problemas NP son aquellos para los que existe un algoritmo no determinista de tiempo polinomial que lo resuelve (el algoritmo puede verificar en tiempo polinomial si un objeto es el objeto buscado, mas no necesariamente construye el objeto).
El problema P vs NP es la pregunta “A es un problema de decisión tal que para cualquier objeto, se puede verificar en tiempo polinomial si es el objeto deseado. Se puede construir el objeto deseado en tiempo polinomial?”
Curiosa calse. De esas que te generan más dudas que certezas e invitan a seguir investigando.
En los años 50 inicio la investigación de operaciones, y se crearon bastantes modelos matematicos que en esa epoca no eran posibles y que hoy pueden ser posibles
Excelente clase y bastante inspiradora
Esto lo relaciono con lo visto en programación lineal, un curso de la universidad en donde veíamos diferentes técnicas de optimización. De hecho estos problemas de optimización de recursos en diferentes sistemas, son pan de cada día en la investigación y desarrollo hecha por muchas organizaciones al rededor del mundo.
¿Cómo se relacionan las optimizaciones matemáticas (por ejemplo, el teorema de Lagrange) con la optimización de algoritmos a nivel práctico?
Apasionante
Profundizando en el tema ahora mismo!
Investigación de Operaciones
Que gran tema!! ❤️
problema planteado en 1930 por primera vez, resulta importante por su aplicación que puede funcionar en áreas de logística, electrónicos y genética.
A mi parecer podría ayudar muchísimo a entender mas el ADN y es uno de los campos que mas se están estudiando, pero el problema esta catalogado como NP-hard, que quiere decir muuuuuuy complicado
Que gran tema!!!
Tema muy interesante.
Pueden revisar este texto
"Advances in Combinatorial Optimization: Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems"
aquí un link
Que interesante saber que hayan problemas que hasta el momento con la teconologia de hoy en dia no se han podido resolver de manera eficiente, seria un reto enorme lograr algo asi.
Interesante tema y que buena clase.
Complicado, complicado hasta de entender el problema mas allá de lo intuitivo. Este million dolars no es para mi.
¡Muy interesante!
De hecho, en los problemas de Machine Learning se buscar minimizar una función de error por diferentes métodos de optimización, por ejemplo, mínimos cuadrados o gradiente descendiente.
Complejidad de un problema != complejidad de resolverlo
np conjunto problemas en que podemos comprobar en un tiempo razonable si la solución es correcta.
p conjunto de problemas que podemos resolver en un tiempo razonable.
p esta incluida en np.
La cuestión es si p = np ( y aún no hemos encontrado el algoritmo) o si p != np (es lo que cree la mayoría pero aún no se ha demostrado)
Bastante interesante el saber que aun hay problemas de optimizacion que no han podido ser resuelto.
Si a alguien le interesa leer sobre esto, tambien existe estrategias como la utilizacion de algoritmos geneticos para hallar la solucion mas optioma entre un rango definido de iteraciones.
https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b
https://developers.google.com/optimization/routing/tsp Aquí lo explican con Python, no está sencillo pero por si se quieren dar una idea.
Y me parece interesante que queden problemas por optimizar en el mundo a los cuales no se les ha encontrado un algoritmo correcto, pero al mismo tiempo es una oportunidad 😄
Recomiendo este vídeo explica muy bien porque el problema del Traveling Salesperson es tan complejo!
Coding Challenge #35.1: Traveling Salesperson
Me estoy planteando crear un gráfico dinámico en bokeh para implementar el código en python
Muy interesante
Tengo la solución (el algoritmo optimizado) para el problema del vendedor viajero, pero esta caja de texto es muy pequeña para mostrarla
P = PN ? tiene pinta de que no son iguales
Nosotros pensando en cómo optimizar y la naturaleza nos da siempre lecciones de optimización; ejemplo: la abejas. Las abejas construyen sus panales con celdas con la forma de un prisma hexagonal para colocar a sus larvas y almacenar la miel, de esta manera se minimiza mano de obra y material.
La optimización no sólo es maximizar y minimizar, también consiste en controlar aquellas variables que nos permitan modificar la dinámica de un sistema de tal forma que haga lo que nosotros queremos.
Uff Muy interesante!
Los algoritmos de optimización nos permiten encontrar las mejores opciones para algun problema, cual es el vuelo mas barato, la ruta con menos tráfico, etc.
Los algoritmos de optimización se pueden reducir a algoritmos p vs np (polinominiales vs no poliniominales)
¿Creen ustedes que si se crea una Inteligencia Artificial futura tipo “GPT-4” y le dan el comando de que resuelva este problema… lo haría?
¿Qué hubiese hecho Phileas Fogg scon una computadora? 🌐Definitivamente Julio Verne fue un adelantado de su época.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?