Según CLRS, los algoritmos de Prim se implementan a continuación: MST-PRIM(G,w,r)MST-PRIM(G,w,r)\mathtt{\text{MST-PRIM}}(G,w,r) para cada dou∈V[G]u∈V[G]u \in V[G] key[u]←∞key[u]←∞\mathtt{\text{key}}[u] \leftarrow \infty π[u]←NILπ[u]←NIL\pi[u] \leftarrow \mathtt{\text{NIL}}...
Estoy buscando un algoritmo que proporcione una cadena canónica para un gráfico de color dado. Es decir. un algoritmo que devuelve una cadena para un gráfico, de modo que dos gráficos obtienen la misma cadena si y solo si son isomórficos. En particular, estoy buscando un algoritmo simple que sea...
Aquí hay una pregunta quizás ingenua que me ha estado hormigueando: ¿Hay un límite inferior asintótico para abordar aleatoriamente una memoria arbitrariamente grande? Mi causa de creencia es que el camino más corto a cualquier memoria almacenada físicamente debe ser a través del espacio...
Supongamos que quiero optimizar una función unimodal definida en algún intervalo real. Puedo usar el conocido algoritmo descrito en Wikipedia bajo el nombre de búsqueda ternaria . En el caso del algoritmo que reduce a la mitad los intervalos repetidamente, es común reservar el término búsqueda...
Recientemente he estado lidiando con un problema que me llevó a las siguientes preguntas: ¿Existe un buen algoritmo para enumerar todas las coincidencias máximas / perfectas en un gráfico general? ¿Existe un buen algoritmo para encontrar todas las coincidencias máximas / perfectas en un gráfico...
Dejar GsolGser un DAG Sabemos que algunos nodos en son "malos", mientras que otros son "buenos"; un descendiente de un nodo malo es malo mientras que los antepasados de un nodo bueno son buenos. También sabemos que los nodos defectuosos tienen un elemento mínimo único en que nos gustaría...
¿Se ha estudiado antes el siguiente problema? En caso afirmativo, ¿qué enfoques / algoritmos se desarrollaron para resolverlo? Problema ("Problema de altura máxima de apilamiento") Dados polígonos, encuentre su disposición estable y no superpuesta que maximice su altura de apilamiento en un...
Estoy trabajando en orientaciones acíclicas de gráficos no dirigidos y tengo las siguientes preguntas: Dado el gráfico simple no dirigido conectado , ¿cómo encontrar todas las orientaciones acíclicas posibles de ?solsolGsolsolG ¿Cuál es el número de orientaciones acíclicas? Se sabe (de aquí )...
Como entrada tengo dos conjuntos de puntos en R N , típicamente para N grande, por ejemplo N = 40. Supongamos que ambos conjuntos tienen m elementos: S = s 1 ... s m T = t 1 ... t m Semánticamente ambos conjuntos son iguales, pero debido al ruido (de cualquier tipo) en los puntos R ^ N, los...
Pregunta: Dado un bits número natural , cómo calcular utilizando sólo adiciones y cambios (BIT)?nnnNNN⌈N−−√⌉⌈N⌉\lceil \sqrt{N} \rceilO(n)O(n)O(n) El consejo es utilizar la búsqueda binaria. Sin embargo, no pude lograr la complejidad requerida (obtuve ).O(n2)O(n2)O(n^2) ¿Qué quiere decir con...
Queremos un algoritmo que, dada una matriz de longitud nnn de enteros, encuentre la diferencia mínima entre dos enteros en la matriz. Uno de estos algoritmos es ordenar la matriz y verificar pares de números adyacentes. Esto lleva tiempoO(nlogn)O(nlogn)O(n\log n). ¿Hay una forma más rápida, por...
\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty} El problema proviene directamente de las matemáticas computacionales y puede ser declarado de la siguiente manera: Dada una matriz regular , encuentre efectivamente todos los vectores modo que , donde \ n {Mv} sea el componente máximo...
En un gráfico , hacemos el siguiente proceso:G ( V, E)G(V,E)G(V,E) Inicialmente, todos los nodos en son incoloros.VVV Si bien hay nodos sin color en , cada nodo sin color hace lo siguiente: VVV Selecciona un número real aleatorio y lo envía a todos sus vecinos; Compara su número con el número de...
Tengo un gráfico no ponderado no dirigido y quiero seleccionar nodos de modo que estén en pares lo más lejos posible entre sí, en términos de distancia geodésica . En otras palabras, deben extenderse alrededor del gráfico como sea posible.GGGkkkGGG Que ser la longitud de un camino más corto entre...
Dado un gráfico bipartito donde cada vértice está coloreado de rojo o azul, estoy tratando de minimizar el número de vértices azules usando la siguiente operación:G = ( A , B , E)G=(A,B,E)G = (A,B,E) Elija un vértice envunavav_aUNAAA Voltee los colores de , lo que significa que y todos los...
Estaba leyendo CLRS y me pidió que mostrara que si es un primo de la forma y era un residuo cuadrático, entonces es una raíz cuadrada (también se puede mostrar fácilmente que es una raíz cuadrada).ppp4k+34k+34k+3aaaak+1ak+1a^{k+1}a−ka−ka^{-k} Me preguntaba si usar el hecho anterior y también que...
El problema de paridad de prefijo se puede definir de la siguiente manera. Te dan una cuerdaSSS de longitud nnn e inicialmente cada personaje es 000. Luego, desea crear una estructura de datos que pueda admitir actualizaciones como las siguientes. Para una dada iii cambio S[i]S[i]S[i] a...
Pruebas de identidad polinomio es el ejemplo típico de un problema conocido para estar en co-RP , pero no se sabe que en P . Sobre los circuitos aritméticos , de hecho parece difícil, ya que el grado del polinomio puede hacerse exponencialmente grande mediante la cuadratura repetida. Esta pregunta...
Entiendo lo que es, pero no veo cómo sirve para algoritmos ni nada. Tal vez me estoy perdiendo algo. Necesito que alguien me dé un ejemplo de cómo se puede usar para poder entenderlo
Estoy tratando de estimar la complejidad de un algoritmo que he escrito para el descompilador Reko , donde estoy tratando de "deshacer" la transformación realizada por un compilador a una división entera por una constantex / nX/ /nortex / n. El compilador ha convertido la división en una...