Preguntas sobre instrucciones bien definidas para completar una tarea, y análisis relevantes en términos de tiempo / memoria / etc.
Paul Erdos habló sobre el "Libro" donde Dios guarda la prueba más elegante de cada teorema matemático. Esto incluso inspiró un libro (que creo que ahora está en su cuarta edición): Pruebas del libro . Si Dios tuviera un libro similar para algoritmos, ¿qué algoritmo (s) crees que sería un candidato...
Para demostrar la importancia de los algoritmos (por ejemplo, para estudiantes y profesores que no hacen teoría o incluso son de campos completamente diferentes), a veces es útil tener a mano una lista de ejemplos en los que se han implementado algoritmos centrales en empresas comerciales,...
Supongamos que Mario camina sobre la superficie de un planeta. Si comienza a caminar desde un lugar conocido, en una dirección fija, por una distancia predeterminada, ¿qué tan rápido podemos determinar dónde se detendrá? Más formalmente, supongamos que se nos da un politopo convexo en 3...
Se forma una mezcla de dos cadenas intercalando los caracteres en una nueva cadena, manteniendo los caracteres de cada cadena en orden. Por ejemplo, MISSISSIPPIes una combinación de MISIPPy SSISI. Permítanme llamar a un cuadrado de cadena si es una combinación de dos cadenas idénticas. Por ejemplo,...
La informática teórica ha proporcionado algunos ejemplos del "precio de la abstracción". Los dos más destacados son para la eliminación y clasificación gaussianas. A saber: Se sabe que la eliminación gaussiana es óptima para, por ejemplo, calcular el determinante si restringe las operaciones a...
En los últimos años se han desarrollado muchos algoritmos de búsqueda de rutas que pueden calcular la mejor ruta en respuesta a los cambios del gráfico mucho más rápido que A *: ¿qué son y en qué se diferencian? ¿Son para diferentes situaciones, o algunas otras obsoletas? Estos son los que he...
En una respuesta a una pregunta anterior , mencioné la creencia común pero falsa de que la eliminación "gaussiana" se ejecuta en el tiempo O(n3)O(n3)O(n^3) . Si bien es obvio que el algoritmo utiliza operaciones aritméticas O(n3)O(n3)O(n^3) , la implementación descuidada puede crear números con...
¿Cuáles son algunos algoritmos de utilidad legítima que son simplemente demasiado complejos para implementar? Permítanme ser claro: no estoy buscando algoritmos como el algoritmo de multiplicación de matriz óptima asintótica actual (Coppersmith-Winograd), que es razonable de implementar pero tiene...
antecedentes Hace varios años, cuando era estudiante universitario, nos dieron una tarea de análisis amortizado. No pude resolver uno de los problemas. Lo había pedido en teoría teórica , pero no se obtuvieron resultados satisfactorios. Recuerdo que el curso TA insistió en algo que no pudo probar,...
Se conjetura ampliamente que , el exponente óptimo para la multiplicación de matrices, es de hecho igual a 2. Mi pregunta es simple:ωω\omega ¿Qué razones tenemos para creer que ?ω = 2ω=2\omega = 2 Conozco algoritmos rápidos como Coppersmith-Winograd, pero no sé por qué estos podrían...
¿Conoce algoritmos sensibles que se ejecutan en tiempo polinómico en (Longitud de entrada + longitud de salida), pero cuyo tiempo de ejecución asintótico en la misma medida tiene un exponente / constante realmente enorme (al menos, donde el límite superior probado en el tiempo de ejecución está en...
Los algoritmos genéticos no tienen mucha tracción en el mundo de la teoría, pero son un método metaheurístico razonablemente bien utilizado (por metaheurístico me refiero a una técnica que se aplica genéricamente a muchos problemas, como el recocido, el descenso de gradiente y similares). De hecho,...
Para (versiones de búsqueda) de problemas completos de NP , verificar una solución es claramente más fácil que encontrarla, ya que la verificación se puede hacer en tiempo polinómico, mientras que encontrar un testigo lleva (probablemente) tiempo exponencial. En P , sin embargo, la solución...
Dos formas de analizar la eficiencia de un algoritmo son poner un límite superior asintótico en su tiempo de ejecución, y para ejecutarlo y recopilar datos experimentales. Me pregunto si hay casos conocidos en los que haya una brecha significativa entre (1) y (2). Con esto quiero decir que (a)...
Supongamos que tengo un gráfico acíclico dirigido con pesos de números reales en sus vértices. Quiero encontrar un orden topológico del DAG en el que, para cada prefijo del orden topológico, la suma de los pesos no sea negativa. O si prefiere la terminología de la teoría del orden, tengo un orden...
Siempre tuve problemas para comprender la importancia de la brecha de integralidad (IG) y sus límites. IG es la proporción de (la calidad de) una respuesta entera óptima a (la calidad de) una solución real óptima de la relajación del problema. Consideremos la cubierta de vértice (VC) como un...
Estoy buscando conjeturas sobre algoritmos y complejidad que muchos consideraron creíbles en algún momento, pero que luego fueron refutadas, o al menos no creídas, debido a la creciente evidencia contraria. Aquí hay dos ejemplos: Hipótesis de oráculo aleatorio: las relaciones entre clases de...
¿Qué explicaciones teóricas existen para el éxito práctico de los solucionadores de SAT, y alguien puede dar una descripción y explicación "estilo wikipedia" uniéndolos a todos? Por analogía, el análisis suavizado ( versión arXiv ) para el algoritmo simplex hace un gran trabajo explicando por...
Si pudieras cambiar el nombre de la programación dinámica, ¿cómo lo
En otro hilo , Joe Fitzsimons preguntó sobre "los mejores límites inferiores actuales en 3SAT". Me gustaría ir a otro lado: ¿Cuál es el mejor límite superior actual en 3SAT? En otras palabras, ¿cuál es la complejidad temporal del solucionador SAT más eficiente? En particular, ¿es concebible...