Se requiere uno para encontrar la potencia (número entero positivo) de la matriz de números reales. Existen muchos algoritmos eficientes de multiplicación de matrices (por ejemplo, algunos algoritmos paralelos son Cannon's, DNS ) pero ¿existen algoritmos que estén destinados exactamente a encontrar...
Dada una matriz de números naturales , donde es una constante, quiero responder en consultas de la forma: "¿cuántas veces aparece en la matriz entre los índices y "?a1,…,ana1,…,ana_1,\ldots,a_n≤k≤k\leq kkkkO(1)O(1)O(1)mmmiiijjj La matriz debe ser preprocesada en tiempo lineal. En particular, me...
En el problema de la estación de servicio , se nos dan ciudades y carreteras entre ellas. Cada camino tiene longitud y cada ciudad define el precio del combustible. Una unidad de carretera cuesta una unidad de combustible. Nuestro objetivo es ir de una fuente a un destino de la manera más barata...
Minimizar los autómatas finitos deterministas (DFA) es un problema que se ha estudiado a fondo en la literatura, y se han propuesto varios algoritmos para resolver el siguiente problema: Dado un DFA , calcule un DFA mínimo correspondiente que acepte el mismo lenguaje que . La mayoría de estos...
Programación dinámica con gran cantidad de subproblemas. Así que estoy tratando de resolver este problema desde Interview Street: Caminata de cuadrícula (Puntuación 50 puntos) Está situado en una cuadrícula dimensional en la posición . Las dimensiones de la cuadrícula son ). En un paso, puede...
¿"Inductivamente" y "recursivamente" significan muy similares? Por ejemplo, si hay un algoritmo que determina un vector n-dim mediante la determinación de sus primeros componentes k + 1 en función de que se hayan determinado sus primeros componentes k, y se inicializa con el primer componente,...
El ésimo número de Fibonacci se puede calcular en tiempo lineal utilizando la siguiente recurrencia:nortenn def fib(n): i, j = 1, 1 for k in {1...n-1}: i, j = j, i+j return i El ésimo número de Fibonacci también puede calcularse como [ φ n / √nortenn. Sin embargo, esto tiene problemas con...
Soy un estudiante principiante de CS y estoy aprendiendo algoritmos. Escuché que incluso con las computadoras cuánticas, los algoritmos generales de clasificación nunca pueden ser mejores que time. Sin embargo, también sé que los algoritmos de factorización serían mucho más rápidos. En términos...
Estoy tratando de reproducir las redes sintéticas (gráficos) descritas en algunos documentos. Se afirma que el modelo Barabasi-Albert se utilizó para crear "redes sin escala con distribuciones de grado de ley de potencia, ".PAGUNA( k ) ∝ k- λPA(k)∝k−λP_A(k) ∝ k^{-λ} es una distribución de...
Lo que sabemos es que π es infinito y es muy probable que contenga todas las cadenas de dígitos finitos posibles ( secuencia disyuntiva ). Recientemente he visto algún prototipo de πfs que supone que cada archivo que ha creado (o cualquier otra persona) o que creará, ya está allí, por lo que es...
Durante una entrevista para un puesto de desarrollador de Java, me preguntaron lo siguiente: Escribe una función que tome dos parámetros: una cadena que representa un documento de texto y un número entero que proporciona la cantidad de artículos a devolver. Implemente la función de...
Digamos que tenemos 10 personas, cada una con una lista de libros favoritos. Para una persona determinada, X, me gustaría encontrar un subconjunto especial de libros de X que le guste solo a X, es decir, no hay otra persona a la que le gusten todos los libros del subconjunto especial de X. Pienso...
Considere un gráfico dirigido en el que se pueden agregar bordes dinámicamente y hacer algunas consultas específicas.GGG Ejemplo: bosque disjunto Considere el siguiente conjunto de consultas: arrow(u, v) equiv(u, v) find(u) el primero agrega una flecha al gráfico, el segundo decide si , el...
Tengo dos conjuntos de puntos en el plano bidimensional. Quiero encontrar el par de puntos más cercano s , t tal que s ∈ S , t ∈ T , y la distancia euclidiana entre s , t sea lo más pequeña posible. ¿Cuán eficientemente se puede hacer esto? ¿Se puede hacer en O ( n log n ) tiempo, donde n = | S |...
¿Quieres mejorar esta publicación? Proporcione respuestas detalladas a esta pregunta, incluidas citas y una explicación de por qué su respuesta es correcta. Las respuestas sin suficiente detalle pueden ser editadas o eliminadas. Me encargaron construir una biblioteca de...
Esta es una especie de pregunta de edición de distancia, y es muy fácil. Estoy completamente muerto de cerebro sobre este tema y no puedo entenderlo hasta ahora. Dada una serie de números, por ejemplo [3, 1, 1, 1] ¿Cómo podría uno convertir más eficientemente todos los números en el mismo...
Cerrada . Esta pregunta está basada en la opinión . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que pueda ser respondida con hechos y citas editando esta publicación . Cerrado hace 4 años . Soy un...
Dados dos vectores de enteros de longitudes posiblemente desiguales, ¿cómo puedo determinar el resultado máximo posible al acumular la elección del máximo entre los pares de números correspondientes entre los dos vectores con ceros adicionales insertados en el vector más corto para compensar la...
¿Cómo detectaría algorítmicamente para una foto determinada si el sol brillaba cuando se tomó la foto? Ejemplos Una muestra de esta cámara web en la cima de una montaña: Claramente el sol está brillando. En esta otra muestra es mucho menos obvio: Probablemente se podría detectar con...
La afirmación habitual del problema de la tarta justa supone que todos los jugadores obtienen su parte al mismo tiempo. Sin embargo, en muchos casos los jugadores llegan de forma incremental. Por ejemplo, podemos dividir un pastel entre jugadores, pero luego llega un nuevo jugador y quiere...