En mi club de squash local, hay una escalera que funciona de la siguiente manera. Al comienzo de la temporada, construimos una tabla con el nombre de cada miembro del club en una línea separada. Luego escribimos el número de juegos ganados y el número de juegos jugados al lado de cada nombre (en...
Está escrito en Wikipedia que "... el tipo de selección casi siempre supera al de burbuja y al de gnomos". ¿Alguien puede explicarme por qué el ordenamiento por selección se considera más rápido que el ordenamiento por burbujas aunque ambos tengan: La peor complejidad del tiempo del caso...
Considere gráficos dirigidos. Llamamos a un nodo vvv superestrella si y solo si no se puede alcanzar a otro nodo desde él, pero todos los demás nodos tienen una ventaja para . Formalmente:vvv \qquad \displaystyle v superstar :⟺outdeg(v)=0∧indeg(v)=n−1 superstar :⟺outdeg(v)=0∧indeg(v)=n−1 \text{...
Sabemos post-orden, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] y pre-orden pre L(x) => [x] pre N(x,l,r) => [x] ++ (pre l) ++ (pre r) y transversales en orden resp. secuencialización in L(x) => [x] in N(x,l,r) => (in l) ++ [x] ++ (in r) Se puede ver...
Digamos que tiene dos polinomios: 3+x3+x3 + x y .2x2+22x2+22x^2 + 2 Estoy tratando de entender cómo FFT nos ayuda a multiplicar estos dos polinomios. Sin embargo, no puedo encontrar ningún ejemplo resuelto. ¿Alguien puede mostrarme cómo el algoritmo FFT multiplicaría estos dos polinomios? (Nota:...
Si dos personas se pierden en un laberinto, ¿hay algún algoritmo que ambos puedan usar para encontrarse sin haber acordado previamente qué algoritmo usarán? Creo que hay algunas características que tendrá este algoritmo: Cada persona debe poder derivarlo utilizando una lógica que no haga...
¿Cuál es la complejidad temporal de encontrar el diámetro de un gráfico ?G=(V,E)G=(V,E)G=(V,E) O(|V|2)O(|V|2){O}(|V|^2) O(|V|2+|V|⋅|E|)O(|V|2+|V|⋅|E|){O}(|V|^2+|V| \cdot |E|) O(|V|2⋅|E|)O(|V|2⋅|E|){O}(|V|^2\cdot |E|) O(|V|⋅|E|2)O(|V|⋅|E|2){O}(|V|\cdot |E|^2) El diámetro de un gráfico...
Dado franjas horarias que gente quiere comprar. La persona tiene un valor para cada intervalo de tiempo . Cada persona solo puede comprar un bloque consecutivo de franjas horarias, que podrían estar vacías.nnnkkkiiih(i,j)≥0h(i,j)≥0h(i,j)\geq 0jjj ¿Existe un algoritmo de tiempo polinómico para...
Sé que el algoritmo de Euclides es el mejor algoritmo para obtener el GCD (gran divisor común) de una lista de enteros positivos. Pero en la práctica, puede codificar este algoritmo de varias maneras. (En mi caso, decidí usar Java, pero C / C ++ puede ser otra opción). Necesito usar el código más...
¿Cuándo son algunas instancias (relativamente) básicas (piense en estudiantes de CS de primer año de nivel universitario) cuando uno usaría la recursividad en lugar de solo un bucle?
Declaración informal del problema: Dada una cadena, por ejemplo, A CdoA B B A BACCABBABACCABBAB , queremos colorear algunas letras rojas y algunas letras azules (y algunas no en absoluto), de modo que leer solo las letras rojas de izquierda a derecha arroje el mismo resultado que leer solo las...
Tienes una moneda Puedes voltearlo tantas veces como quieras. Desea generar un número aleatorio tal que donde .rrra≤r<ba≤r<ba \leq r < br,a,b∈Z+r,a,b∈Z+r,a,b\in \mathbb{Z}^+ La distribución de los números debe ser uniforme. Es fácil si :b−a=2nb−a=2nb -a = 2^n r = a + binary2dec(flip n...
Estoy buscando un algoritmo para distribuir valores de una lista para que la lista resultante esté lo más "equilibrada" o "distribuida de manera uniforme" posible (entre comillas porque no estoy seguro de que estas sean las mejores formas de describirla ... más adelante proporcionaré una forma de...
No entiendo bien por qué la rotación en la estructura de datos del árbol de separación está teniendo en cuenta no solo al padre del nodo de calificación, sino también al abuelo (operación zig-zag y zig-zig). ¿Por qué no funcionaría lo siguiente? A medida que insertamos, por ejemplo, un nuevo nodo...
Aquí hay una pregunta de un examen anterior que estoy tratando de resolver: Para un gráfico no dirigido con pesos positivos , estoy tratando de encontrar el corte mínimo. No conozco otras formas de hacerlo además de usar el teorema de corte mínimo de flujo máximo. Pero el gráfico no está dirigido,...
Estoy tratando de tener una idea de cómo se debe interpretar la prueba de primalidad AKS a medida que la conozco, por ejemplo, un corolario para demostrar que PRIMES ⊆ P, o un algoritmo realmente práctico para pruebas de primalidad en computadoras. La prueba tiene tiempo de ejecución polinómico...
Tengo dos formas de producir una lista de artículos en un orden aleatorio y me gustaría determinar si son igualmente justos (imparciales). El primer método que utilizo es construir la lista completa de elementos y luego barajarla (digamos barajar Fisher-Yates). El segundo método es más un método...
¿Hay algún algoritmo que sea muy difícil de paralelizar o la investigación aún está activa? Quería saber sobre cualquier algoritmo o cualquier campo de investigación en computación paralela. Todo lo que busqué tiene una implementación "paralela". Solo quiero estudiar un poco sobre cualquier campo...
Dado un conjunto de monedas con diferentes denominaciones un valor v desea encontrar la menor cantidad de monedas necesarias para representar el valor v.c 1 , . . . , c ndo1,...,donortec1, ... , cn Por ejemplo, para el conjunto de monedas 1,5,10,20, esto da 2 monedas por la suma 6 y 6 monedas por...
¿El análisis suavizado encontró su camino en el análisis principal de algoritmos? ¿Es común que los diseñadores de algoritmos apliquen análisis suavizados a sus