Preguntas etiquetadas con algorithms

Mi problema. Dado , quiero contar el número de conjuntos múltiples válida . Un multiset es válido sinnnSSSSSS La suma de los elementos de es , ySSSnnn Cada número de a se puede expresar de forma única como una suma de algunos de los elementos de .111nnnSSS Ejemplo. Por ejemplo, si entonces son...

Estoy trabajando en algoritmos de búsqueda de cadenas que admiten la búsqueda de patrones múltiples. Encontré dos algoritmos que parecen ser los candidatos más fuertes en términos de tiempo de ejecución, a saber, Aho-Corasick y Rabin-Karp . Sin embargo, no pude encontrar ninguna comparación...

¿Existe un algoritmo / procedimiento sistemático para evaluar si un idioma es regular? En otras palabras, dado un idioma especificado en forma algebraica (piense en algo como ), pruebe si el idioma es regular o no. Imagine que estamos escribiendo un servicio web para ayudar a los estudiantes con...

¿Cómo abordaría el problema de la mochila en una situación de programación dinámica si ahora tiene que limitar el número de elementos en la mochila por una constante ? Este es el mismo problema (peso máximo de , cada artículo tiene un valor peso ) pero solo puede agregar artículo (s) a la mochila y...

Sea nnn un número entero y ZZ\mathbb{Z} denote el conjunto de todos los enteros. Supongamos que [a,b][a,b][a,b] denota el intervalo de enteros {a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} . Busco a una estructura de datos para representar un mapa f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} ....

Se nos presentó en clase un algoritmo para encontrar el máximo en una matriz en paralelo en O(1)O(1)O(1) complejidad de tiempo con n2n2n^2 computadoras. El algoritmo fue: Dado un conjunto A de longitud n: Haga una matriz B de longitud n e inicialícela con ceros con nnn computadoras....

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...

¿Cuántas operaciones aritméticas se requieren para encontrar una matriz pseudoinversa de Moore-Penrose de un campo arbitrario? Si la matriz es invertible y tiene un valor complejo, entonces es solo lo inverso. Encontrar el inverso toma tiempo , donde es la constante de multiplicación de la...

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...

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...

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...

Me pregunto si hay duros que son "polinomiales" en el caso promedio. ¿Creo que hay dos formas de interpretar esto?NPNPNP Si , ¿puede haber un algoritmo que resuelva un problema duro con tiempo de ejecución amortizado (caso promedio) de para una constante ?N P O ( n k ) kP≠NPP≠NPP \neq...

En el caso de los gráficos sin etiquetar, el problema del isomorfismo del gráfico puede abordarse mediante una serie de algoritmos que funcionan muy bien en la práctica. Es decir, aunque el peor tiempo de ejecución es exponencial, generalmente se tiene un tiempo de ejecución polinómico. Esperaba...

¿Hay algún algoritmo conocido que muestre correctamente "sí" a un problema NP-completo sin generar implícitamente un certificado? Entiendo que es sencillo convertir un oráculo de satisfacción en un buscador de asignación satisfactoria: simplemente repita las variables, pidiéndole al oráculo de...

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...

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...

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...

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...

¿Hay alguna manera de calcular el tamaño de una coincidencia máxima en un gráfico bipartito no ponderado de manera más eficiente (por ejemplo, más rápido) que calcular una coincidencia máxima? Es una posibilidad remota, pero a menudo es un problema interesante para evitar cálculos desechables...

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...