Dado un conjunto de conjuntos, me gustaría encontrar un conjunto de tal manera que cada conjunto en contiene al menos un elemento de . También me gustaría que contenga la menor cantidad posible de elementos sin dejar de cumplir este criterio, aunque puede existir más de una más pequeña con esta...
Supongamos que se nos dan dos números y y que queremos encontrar para l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r El algoritmo ingenuo simplemente verifica todos los pares posibles; por ejemplo en ruby tendríamos: def max_xor(l, r) max = 0...
He realizado algunas pruebas de diferentes temperaturas iniciales en mi algoritmo de recocido de simulación y noté que la temperatura inicial tiene un efecto en el rendimiento del algoritmo. ¿Hay alguna forma de calcular una buena temperatura
Estoy familiarizado con la idea de la eliminación básica de la recursividad de la cola, donde las funciones que devuelven el resultado directo de una llamada pueden reescribirse como bucles iterativos. foo(...): # ... return foo(...) También entiendo que, como un caso especial, la función aún...
Tengo un problema algorítmico TTTnnnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Por ejemplo: Si = [1, 3, 4, 1, 3, 6], entonces puede ser [3, 3, 6] o [3, 4, 6] o [4, 3, 6].STTTSSS En = [7, 5, 1, 1, 7, 4], entonces es [7, 5, 7, 4].STTTSSS He intentado esta función recursiva. function(T): if...
Si tengo dos matrices y B , de dimensiones 1000 × 2 y 2 × 1000 , respectivamente, y quiero calcular ( A B ) 5000 , es más eficiente reescribir primero la expresión como A ( B A ) 4999 B y solo entonces evalúe numéricamente, porque A B es de dimensión 1000 × 1000 pero B A es de dimensión 2 × 2...
Un juego simple que generalmente juegan los niños, el juego de Guerra lo juegan dos personas usando una baraja estándar de 52 cartas. Inicialmente, el mazo se baraja y todas las cartas se reparten entre los dos jugadores, de modo que cada uno tiene 26 cartas al azar en un orden aleatorio....
¿Cuál es la complejidad de MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} y MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? ¿Están en P? ¿Son NP-hard? Para formalizar esto más precisamente, dejemos Φ ( x ) = ∧norteyoCyo,Φ(x)=∧inCi,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, donde x =(...
Deje que el lenguaje sea regular.L ⊆ Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Una factorización de es un par máximo ( X , Y ) de conjuntos de palabras conLL\mathcal{L}( X, Y)(X,Y)(X,Y) X⋅ Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} ,X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y donde | x ∈ X , y ∈ Y }...
En 1962, podría ganar un premio de $ 10 000 (aproximadamente $ 80 000 en dinero de hoy) si encuentra la solución a un problema de vendedor ambulante euclidiano definido en 33 ciudades. http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html Mirando la imagen, el problema parece bastante...
Me dieron el siguiente problema en una entrevista (que ya no pude resolver, sin tratar de engañarme): El juego comienza con un número entero positivo . (Por ejemplo, A 0 = 1234. ) Este número se convierte en representación binaria, y N es el número de bits establecido en 1 . (Por ejemplo, A 0 = b...
Alice, una estudiante, tiene mucha tarea en las próximas semanas. Cada tarea le lleva exactamente un día. Cada artículo también tiene una fecha límite y un impacto negativo en sus calificaciones (suponga un número real, puntos de bonificación solo por asumir la comparabilidad), si no cumple con...
Tengo un conjunto de puntos , y tengo la distancia entre cada punto . Estas distancias son euclidianas, pero los puntos están realmente en un espacio de características.CCCD(Pi,Pj)D(Pi,Pj)D(P_i,P_j) De los puntos quiero elegir un subconjunto de puntos. Llame a este subconjunto . Quiero elegir este...
La pregunta general, como sugiere el título, es: ¿Cuál es la diferencia entre DS y OR / optimización? A nivel conceptual, entiendo que DS intenta extraer conocimiento de los datos disponibles y utiliza principalmente técnicas estadísticas de aprendizaje automático. Por otro lado, OR utiliza los...
Me gustaría aprender algo sobre este problema de optimización: para números enteros no negativos dados , encuentre una función minimice la expresiónai,j,kai,j,ka_{i,j,k}fff maxk∑iai,f(i),kmaxk∑iai,f(i),k\max_k \sum_i a_{i,f(i),k} Un ejemplo que utilice una formulación diferente podría aclararlo:...
He leído que los sistemas operativos como Android e iOS están optimizados de alguna manera para mejorar la duración de la batería. Según tengo entendido, una CPU ejecuta una cierta cantidad de operaciones en un tiempo determinado, por lo que creo que puede acelerar las aplicaciones reduciendo la...
Supongamos que yo soy dado un conjunto finito de puntos en el plano, y se le pidió que dibujara una curva C ( P ) dos veces diferenciable a través de los p i 's, de modo que su perímetro sea lo más pequeño posible. Suponiendo que p i = ( x i , y i ) y x i < x i + 1 , puedo formalizar este...
¿Qué es un algoritmo de aproximación de bicriteria? Esto sigue apareciendo en el caso de la agrupación de flujo de datos. ¿Está esto relacionado con la optimización de objetivos múltiples? Aquí es donde lo encontré: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. El documento trata sobre una...
¿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...
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...