Lo siento de antemano si esta pregunta suena tonta ... Hasta donde sé, construir un algoritmo usando programación dinámica funciona de esta manera: expresa el problema como una relación de recurrencia; implementar la relación de recurrencia ya sea mediante la memorización o mediante un enfoque...
Es bien sabido que este algoritmo 'ingenuo' para barajar una matriz intercambiando cada elemento con otro elegido al azar no funciona correctamente: for (i=0..n-1) swap(A[i], A[random(n)]); Específicamente, dado que en cada una de las iteraciones, se realiza una de las elecciones (con...
Este programa de 579 bits en el cálculo binario de Lambda tiene un estado de detención
Estoy buscando ayuda para comprender el algoritmo de detección de ciclo de Floyd. He revisado la explicación en wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ) Puedo ver cómo el algoritmo detecta el ciclo en el tiempo O (n). Sin embargo, no puedo visualizar el hecho de...
Ni siquiera soy un estudiante de CS, así que esta podría ser una pregunta estúpida, pero por favor tengan paciencia conmigo ... En la era anterior a la computadora, solo podemos implementar una estructura de datos de matriz con algo así como una matriz de cajones. Dado que uno tiene que ubicar el...
Digamos que necesito simular la siguiente distribución discreta: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} La forma más obvia es dibujar bits aleatorios y...
Digamos que y b 1 b 2 ... b n son dos cadenas de la misma longitud. Una anagramación de dos cadenas es un mapeo biyectivo p : [ 1 ... n ] → [ 1 ... n ] tal que a i = b p ( i ) para cada i .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots...
¿Cuál sería la forma más rápida de hacer esto (desde una perspectiva algorítmica, así como una cuestión práctica)? Estaba pensando algo en las siguientes líneas. Podría agregar al final de una matriz y luego usar bubbleort, ya que tiene un mejor caso (matriz totalmente ordenada al inicio) que...
¿Qué diferencias y relaciones hay entre los algoritmos aleatorios y los algoritmos no deterministas? De Wikipedia UNA algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica. El algoritmo generalmente utiliza bits aleatorios uniformes como entrada...
Al implementar un diccionario ('Quiero buscar datos de clientes por sus ID de cliente'), las estructuras de datos típicas utilizadas son tablas hash y árboles de búsqueda binarios. Sé, por ejemplo, que la biblioteca C ++ STL implementa diccionarios (los llaman mapas) usando árboles de búsqueda...
Me asignaron un ejercicio en mi universidad. Me lo llevé a casa e intenté programar un algoritmo para resolverlo, supongo que era algo relacionado con gráficos, encontrar componentes conectados. Luego hice lo más trivial que se me ocurrió y luego se lo mostré a mi profesor. Después de una breve...
Me gustaría enumerar todos los gráficos no dirigidos de tamaño nnn , pero solo necesito una instancia de cada clase de isomorfismo . En otras palabras, quiero enumerar todos los gráficos no isomorfos (no dirigidos) en nnn vértices. ¿Cómo puedo hacer esto? Más precisamente, quiero un algoritmo que...
Tengo curiosidad por determinar un enfoque para abordar un algoritmo de "amigos sugeridos". Facebook tiene una función en la que le recomendará personas que cree que puede conocer. Estos usuarios normalmente (excluyendo los casos extremos en los que un usuario recomienda específicamente a un amigo...
Tengo un algoritmo codicioso que sospecho que podría ser correcto, pero no estoy seguro. ¿Cómo verifico si es correcto? ¿Cuáles son las técnicas a utilizar para probar que un algoritmo codicioso es correcto? ¿Existen patrones o técnicas comunes? Espero que esto se convierta en una pregunta de...
Estoy buscando un algoritmo para generar una matriz de N números aleatorios, de modo que la suma de los N números sea 1, y todos los números se encuentren dentro de 0 y 1. Por ejemplo, N = 3, el punto aleatorio (x, y, z) debe estar dentro del triángulo: x + y + z = 1 0 < x < 1 0 < y <...
Estoy implementando un conjunto de algoritmos de búsqueda de rutas como Dijkstra, Depth First, etc. Al principio usé un par de gráficos hechos por mí mismo, pero ahora me gustaría llevar el desafío un poco más allá y, por lo tanto, estoy buscando gráficos utilizados en puntos de...
Hay un algoritmo polinomial fácil para decidir si hay una ruta entre dos nodos en un gráfico dirigido (solo haga un recorrido de rutina del gráfico con, por ejemplo, búsqueda de profundidad primero). Sin embargo, parece que, sorprendentemente, el problema se vuelve mucho más difícil si en lugar de...
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...
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...