Acabo de empezar a leer sobre teoría de la computación. Si comparamos cuál es más poderoso (al aceptar cadenas), ambos son iguales. ¿Pero qué hay de la eficiencia? DFA será rápido en comparación con NFA, ya que solo tiene una ventaja saliente y no habrá ambigüedad. Pero en el caso de NFA, tenemos...
Soy un poco nuevo, pero estoy muy interesado en el campo de la informática y la teoría de la complejidad, y quiero aclarar mi comprensión sobre cómo clasificar los problemas, y qué tan fuertemente se relacionan los problemas con la máquina que se está utilizando para resolverlos. Mi punto de...
Supongamos que tengo una gráfica con el (desconocido) conjunto de perfectos matchings de . Suponga que este conjunto no está vacío, entonces, ¿qué tan difícil es muestrear uniformemente al azar de ? ¿Qué pasa si estoy de acuerdo con una distribución que es casi uniforme, pero no bastante uniforme,...
La función de desplazamiento máximo del castor ocupado, , tiene valores conocidos para n ≤ 4 . ¿Hay alguna razón estructural básica por la que es inconcebible que alguna vez encontremos S ( n ) para n > 4 ? ¿Qué tiene de diferente n = 4 que n = 5 ? O n = 6 ? En algún punto del camino debe haber...
Hay bins, el i ésimo bin contiene un i bolas. Las bolas tienen n colores, hay una i bolas de color i . Sea m = ∑ n i = 1 a i .nortenortenyoyoiunyounyoa_inortenortenunyounyoa_iyoyoim = ∑nortei = 1unyometro=∑yo=1norteunyom=\sum_{i=1}^n a_i Un intercambio es tomar una pelota de un contenedor e...
¿La salida de un analizador tiene que ser un árbol o también podría ser un gráfico general? Además, ¿hay algún lenguaje existente o plausible que use la representación gráfica general en lugar de árboles para su
He estado leyendo sobre las diferencias entre la serialización y la linealización , que son criterios de consistencia para los sistemas replicados, como las bases de datos replicadas. Sin embargo, no sé en qué casos sería necesaria la linealización, a pesar de que es más fuerte que la...
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 }...
¿Hay alguna forma natural o notable de relacionar o vincular grupos matemáticos y lenguajes formales de CS o algún otro concepto central de CS, por ejemplo, máquinas de Turing? Estoy buscando referencias / aplicaciones. Sin embargo, tenga en cuenta que conozco el vínculo entre los semigrupos y...
Estoy tratando de entender qué se entiende por "determinista" en expresiones como "gramática determinista sin contexto". (Hay "cosas" más deterministas en este campo). ¡Agradecería un ejemplo más que la explicación más elaborada! Si es posible. Mi principal fuente de confusión es no poder decir...
Usando el siguiente algoritmo recursivo de Fibonacci: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Si ingreso el número 5 para encontrar fib (5), sé que esto generará 5, pero ¿cómo examino la complejidad de este algoritmo? ¿Cómo calculo los pasos...
¿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 =(...
Estoy buscando un algoritmo eficiente para el siguiente problema o una prueba de dureza NP. Sea ΣΣ\Sigma un conjunto y A ⊆ P ( Σ )A⊆P(Σ)A\subseteq\mathcal{P}(\Sigma) un conjunto de subconjuntos de ΣΣ\Sigma . Encuentre una secuencia w ∈ Σ ∗w∈Σ∗w\in \Sigma^* de menor longitud tal que para cada L ∈...
Estaba leyendo la entrada de Wikipedia sobre la complejidad de Kolmogorov ( gracias a esta pregunta ), que dice: Se puede demostrar que la complejidad de Kolmogorov de cualquier cadena no puede ser mayor que unos pocos bytes mayor que la longitud de la cadena misma. ¿Por qué necesitarías algo...
La programación funcional tiene el muy elegante cálculo Lambda y sus variantes como teoría de respaldo. ¿Existe tal cosa para OOP? ¿Qué es una abstracción para el modelo orientado a
Me gustaría un ejemplo de quine en cálculo lambda puro . Me sorprendió bastante no poder encontrar uno buscando en Google. La página quine enumera quines para muchos idiomas "reales", pero no para el cálculo lambda. Por supuesto, esto significa definir lo que quiero decir con una quine en el...
Es un hecho bien conocido que "la correlación no es igual a la causalidad", pero el aprendizaje automático parece basarse casi por completo en la correlación. Estoy trabajando en un sistema para estimar el rendimiento de los estudiantes en preguntas basadas en sus actuaciones pasadas. A diferencia...
He leído en Wikipedia y algunos otros textos que El problema de detención es [...] decidible para autómatas lineales (LBA) [y] máquinas deterministas con memoria finita. Pero antes se escribe que el problema de detención es un problema indecidible y, por lo tanto, TM no puede resolverlo. Dado...
A propósito de la sugerencia de Raphael sobre la intersección de dos NPDA : Deje y A 2 NPDA para lenguajes libres de contexto L 1 y L 2 , respectivamente. Suponiendo que sabemos que L = L 1 ∩ L 2 no tiene contexto, ¿podemos (efectivamente) construir NPDA para
La página de Wikipedia sobre algoritmos de multiplicación menciona una interesante de Donald Knuth . Básicamente, implica combinar la multiplicación de transformada de Fourier con una tabla precalculada de multiplicaciones de tamaño logarítmico. Se ejecuta en tiempo lineal. El artículo actúa como...