En la multiplicación matricial de Strassen, afirmamos un hecho extraño (al menos para mí) de que la multiplicación matricial de dos 2 x 2 requiere 7 multiplicaciones. Pregunta: ¿Cómo demostrar que es imposible multiplicar dos matrices de 2 x 2 en 6 multiplicaciones? Tenga en cuenta que las...
¿Si hay una manera de identificar si dos conjuntos de puntos se pueden separar por una línea? Tenemos dos conjuntos de puntos y B si hay una línea que separa A y B de manera que todos los puntos de A y solo A en un lado de la línea, y todos los puntos de B y solo B en el otro...
Intento encontrar un enfoque para el siguiente problema: Dado el conjunto de puntos y el radio , encuentre el punto central del círculo, de modo que el círculo contenga el número máximo de puntos del conjunto. El tiempo de ejecución debe ser .r O ( n 2 )SSSrrrO ( n2)O(n2)O(n^2) Al principio...
Las identidades utilizadas en los algoritmos de multiplicación por Karatsuba (enteros) Gauss (números complejos) Strassen (matrices) Parece muy relacionado. ¿Existe un marco abstracto general /
Dado que solo hay una constante entre las bases de los logaritmos, ¿no está bien escribir f(n)=Ω(logn)f(n)=Ω(logn)f(n) = \Omega(\log{n}) , en lugar de , o cualquiera que sea la
El algoritmo Ramer-Douglas-Peucker para la simplificación de línea tiene el peor tiempo de ejecución . Para entradas aleatorias distribuidas adecuadamente, se espera una complejidad de tiempo de ejecución . En 2D, hay otros algoritmos con la peor complejidad de tiempo de ejecución , que calculan...
Considere el siguiente problema: Entrada: dos matrices y de longitud , donde está en orden.B n BAAABBBnnnBBB Consulta: ¿ y contienen los mismos elementos (con su multiplicidad)?BAAABBB ¿Cuál es el algoritmo determinista más rápido para este problema? ¿Se puede resolver más rápido que...
Estoy buscando un algoritmo de ordenación para matrices int que no asigne ningún byte que no sea el tamaño de la matriz, y se limita a dos instrucciones: SWAP: intercambia el siguiente índice con el actual; MOVER: mueve el cursor al índice +1 o -1; Es decir, no puede intercambiar índices no...
Cuando se prueban algoritmos, un enfoque común es la prueba aleatoria: generar una cantidad significativa de entradas de acuerdo con alguna distribución (generalmente uniforme), ejecutar el algoritmo en ellas y verificar la corrección. Los marcos de prueba modernos pueden generar entradas...
Estoy tratando de encontrar el conjunto máximo independiente de un gráfico de biparita. Encontré lo siguiente en algunas notas "13 de mayo de 1998 - Universidad de Washington - CSE 521 - Aplicaciones del flujo de red" : Problema: Dado un bipartito gráfico , encontrar un conjunto...
Noté que en algunos trabajos de investigación de CS, para comparar la eficiencia de dos algoritmos, se usa el número total de comparación clave en los algoritmos en lugar de los tiempos reales de computación. ¿Por qué no podemos comparar cuál es mejor ejecutando ambos programas y contando el tiempo...
Suponga que está obteniendo un número mmm (usando bits O(logm)O(logm)O(\log m) en codificación binaria). ¿Qué tan rápido puede encontrar (o determinar que tal no existe) ?n,k∈N,1<k≤n2:(nk)=mn,k∈N,1<k≤n2:(nk)=mn,k\in \mathbb N,
Dado un matriz A . Deje que la matriz inversa de A sea A - 1 (es decir, A A - 1 = I ). Suponga que un elemento en A cambia (digamos a i j a a ′ i j ). El objetivo es encontrar A - 1 después de este cambio. ¿Existe un método para encontrar este objetivo que sea más eficiente que volver a calcular la...
Gracias al teorema de corte mínimo de flujo máximo, sabemos que podemos usar cualquier algoritmo para calcular un flujo máximo en un gráfico de red para calcular un corte -min. Por lo tanto, la complejidad de calcular un corte mínimo ( s , t ) no es más que la complejidad de calcular un flujo...
Dado un dado sesgado del lado , ¿cómo puede generarse un número aleatorio en el rango manera uniforme? La distribución de probabilidad de las caras del dado no se conoce, todo lo que se sabe es que cada cara tiene una probabilidad distinta de cero y que la distribución de probabilidad es la misma...
Si hay un algoritmo que se ejecuta en el tiempo para algún problema A, y a alguien se le ocurre un algoritmo que se ejecuta en el tiempo, , donde , ¿se considera una mejora con respecto al algoritmo anterior?O ( f ( n ) / g ( n ) ) g ( n ) = o ( f ( n ) )O ( f( n ) )O(f(n))O(f(n))O ( f( n ) / g( n...
Tengo un problema de decisión NP-completo. Dada una instancia del problema, me gustaría diseñar un algoritmo que genere SÍ, si el problema es factible, y, de lo contrario, NO. (Por supuesto, si el algoritmo no es óptimo, cometerá errores). No puedo encontrar ningún algoritmo de aproximación para...
La combinatoria juega un papel importante en la informática. Con frecuencia utilizamos métodos combinatorios tanto en el análisis como en el diseño de algoritmos. Por ejemplo, un método para encontrar un conjunto de portadas de kkk vértices en un gráfico podría inspeccionar todos los subconjuntos...
Tiene una matriz de elementos distintos. Tiene acceso a un comparador (una función de la caja negro teniendo dos elementos un y b y devolver verdadero si y sólo si un < b ) y una fuente verdaderamente aleatoria de bits (una función de la caja negro sin argumentos y devolver un poco...
En su libro Algoritmos aleatorios , Motwani y Raghavan abren la introducción con una descripción de su función RandQS - Randomized quicksort - donde el pivote, utilizado para dividir el conjunto en dos partes, se elige al azar. He estado estacionando mis cerebros (ciertamente algo poco poderosos)...