He estado estudiando los tres y estoy declarando mis inferencias de ellos a continuación. ¿Podría alguien decirme si los he entendido con la suficiente precisión o no? Gracias. El algoritmo de Dijkstra se usa solo cuando tiene una sola fuente y desea conocer la ruta más pequeña de un nodo a otro,...
Entiendo que usar DFS "tal cual" no encontrará una ruta más corta en un gráfico no ponderado. Pero, ¿por qué ajustar DFS para permitirle encontrar caminos más cortos en gráficos no ponderados es una perspectiva tan desesperada? Todos los textos sobre el tema simplemente afirman que no se puede...
No tengo claro el uso de las frases lenguaje "infinito" o lenguaje "finito" en la teoría de computadoras. Creo que la raíz del problema es que un lenguaje como es infinito en el sentido de que puede generar un número infinito (pero contable) de cadenas. Sin embargo, todavía puede ser reconocido...
Me pregunto si esto es posible, ya que{anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL} . Por lo tanto, un PDA que puede distinguir una palabra del resto de podría aceptarla , lo que me parece contradictorio.w∈{anbncn∣n≥0}w∈{anbncn∣n≥0}w\in\{a^n b^n c^n \mid n \geq...
En esta pregunta solo consideramos las máquinas de Turing que detienen todas las entradas. Si entonces por denotamos la máquina de Turing cuyo código es .k ∈ N k∈Nk \in \mathbb{N}T kTkT_k kkk Considere la siguiente función s ( x , y ) = min { k ∣ | L ( T k ) ∩ { x , y } | = 1...
Tengo algunos objetos con prioridad que son de tipo compuesto y solo están parcialmente ordenados . Necesito seleccionar los objetos en orden de esta prioridad (es decir, producir un elemento mínimo cada vez). Pero en lugar de completar arbitrariamente el pedido, preferiría que la cola fuera...
Decimos que el lenguaje es denso si existe un polinomio p tal que | J c ∩ Σ n | ≤ p ( n ) para todo n ∈ N . En otras palabras, para cualquier longitud dada n sólo existen polinomialmente muchas palabras de longitud n que no están en J .J⊆Σ∗J⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|Jc∩Σn|≤p(n) |J^c...
En muchas discusiones sobre el almacenamiento dinámico binario, normalmente solo la tecla de disminución aparece como operación admitida para un almacenamiento dinámico mínimo. Por ejemplo, CLR capítulo 6.1 y esta página de wikipedia . ¿Por qué la clave de aumento normalmente no aparece en...
He usado FSM en diseños de circuitos secuenciales digitales. Pero no estoy familiarizado con Autómatas finitos. ¿Alguien puede ayudarme a comprender la diferencia 'básica' entre los dos?
Una pregunta común de la entrevista es dar un algoritmo para determinar si un árbol binario dado está equilibrado en altura (definición de árbol AVL). Me preguntaba si podemos hacer algo similar con los árboles rojo-negros. Dado un árbol binario arbitrario sin color (con nodos NULL), ¿existe un...
Dado es un gráfico plano y deje que G denote su incrustación en el plano st cada borde tiene una longitud 1 . Tengo además un conjunto C de puntos en los que cada punto c ∈ C está contenido en G . Además, para cualquier punto p en G, existe un c ∈ C con una distancia geodésica a p como máximo uno....
¿Por qué necesitamos voltear el núcleo en convolución 2D en primer lugar? ¿Cuál es el beneficio de esto? Entonces, ¿por qué no podemos dejarlo sin voltear? http://www.songho.ca/dsp/convolution/convolution2d_example.html entrada núcleo salida "Primero, voltea el núcleo, que es el cuadro...
Considere la siguiente pregunta de Google Code Jam ronda 1C : La Gran Muralla de China comienza como una línea infinita, donde la altura en todos los lugares es 000 . Algún número de tribus , atacarán el muro de acuerdo con los siguientes parámetros: un día de inicio, , una fuerza de inicio , una...
Me gustaría construir un sistema de aprendizaje automático en línea basado en la web, donde los usuarios puedan agregar continuamente muestras clasificadas y actualizar el modelo en línea. Me gustaría usar un perceptrón o un algoritmo de aprendizaje en línea similar. Pero los usuarios pueden...
Hace poco me enteré de la existencia de esta memoria temporal jerárquica (HTM) . Ya leí el documento Memoria temporal jerárquica: conceptos, teoría y terminología (por Jeff Hawkins y Dileep George), que parece bastante fácil de entender, pero una señal de alerta es que el documento no es revisado...
Cuando se utiliza A * (o cualquier otro algoritmo de búsqueda de mejor ruta), decimos que la heurística utilizada debe ser admisible , es decir, nunca debe sobrestimar la longitud (o movimientos) reales de la ruta de solución. ¿Cómo una heurística admisible garantiza una solución óptima?...
Llegué a saber que la unidad de procesamiento gráfico tiene algo llamado fusión de memoria. Al leerlo, no tenía claro el tema. ¿Está relacionado de alguna manera con el paralelismo del nivel de memoria? He buscado en Google pero no pude obtener una respuesta satisfactoria. Sería útil si alguien...
Se dice que la intersección de un lenguaje libre de contexto L con un lenguaje regular M siempre está libre de contexto. Entendí la prueba de construcción de productos cruzados, pero todavía no entiendo por qué es libre de contexto pero no regular. El lenguaje generado por tal intersección tiene...
Cuando observamos el Modelo de actor y los Procesos secuenciales de comunicación , vemos que ambos intentan hacer concurrencia en función del paso de mensajes , pero son distintos . (Vemos implementaciones del modelo CSP en las rutinas de go-lang (y core.async de Clojure ) y el modelo de actor en...
¿Por qué utilizamos otras bases que no son binarias (para computadoras) ni decimales (para humanos)? Las computadoras terminan representándolos en binario, y los humanos prefieren obtener su representación decimal. ¿Por qué no apegarse a estas dos