Por lo que leí en el preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Esta es la definición de PTAS : Un esquema de aproximación de tiempo polinomial ( PTAS ) para el...
¿Cuándo decimos que una red neuronal artificial es un perceptrón multicapa ? ¿Y cuándo decimos que una red neuronal artificial es una multicapa ? ¿El término perceptrón está relacionado con la regla de aprendizaje para actualizar los pesos? ¿O está relacionado con las unidades...
Si P es igual a NP, ¿será posible diseñar un sistema de criptosistema donde el algoritmo de criptoanálisis óptimo tome, por ejemplo, el cuadrado del tiempo empleado por los algoritmos legítimos de cifrado y descifrado? ¿Ya existen tales
Mi profesor hizo la declaración Cualquier problema finito no puede ser NP-Complete Estaba hablando de Sudoku en ese momento diciendo algo similar a que para un Sudoku 8x8 hay un conjunto finito de soluciones, pero no puedo recordar exactamente lo que dijo. Escribí la nota que he citado pero...
Una expresión combinatoria (digamos en la base SK) puede considerarse como una función que asigna expresiones de cálculo combinador a expresiones de cálculo combinador. Es decir, se puede pensar en una expresión como una función X : L → L , donde L es el conjunto de todas las expresiones de...
Estaba pensando en pruebas y me encontré con una observación interesante. Por lo tanto, las pruebas son equivalentes a los programas a través del isomorfismo de Curry-Howard, y las pruebas circulares corresponden a una recursión infinita. Pero sabemos por el problema de detención que, en general,...
Parece que las "Expresiones regulares básicas" según lo definido por POSIX.1-2008 no admiten la alternancia a|b(aunque algunas implementaciones grep reconocen la versión escapada \|). Dado que los lenguajes regulares están cerrados bajo unión por definición, ¿significa esto que POSIX BRE tiene...
Una función heurística es ...h(n)h(n)h (n) Consistente si el costo estimado del nodo al objetivo no es mayor que el costo del paso para su sucesor n ' más el costo estimado del sucesor al objetivo.nnnn′n′n' Admisible si nunca sobreestima el costo real para el estado objetivo.h(n)h(n)h(n) El...
Sigo escuchando acerca de cómo uno debe aprender la teoría de categorías para comprender realmente la teoría del lenguaje de programación. Hasta ahora, he aprendido una gran cantidad de PL sin siquiera entrar en el ámbito de las categorías. Sin embargo, pensé que era hora de dar el salto para ver...
Parece que he encontrado una forma genérica de convertir cualquier procedimiento recursivo a recursión de cola: Defina un subprocedimiento auxiliar con un parámetro adicional "resultado". Aplique lo que se aplicaría al valor de retorno del procedimiento a ese parámetro. Llame a este procedimiento...
Mañana es mi presentación y quiero aclarar mis conceptos ... He leído que en DFA, "Para cada estado, se debe definir la transición en todos los símbolos posibles (alfabeto)". ¿Es obligatorio para cada estado definir la transición en todos los símbolos posibles en DFA? Si no es así, ¿puede dar...
Estoy estudiando lenguajes formales y sistemas de bases de producción (sistemas de bases de reglas) y estoy un poco confundido acerca de por qué estas dos palabras "producción" y "regla" significan lo mismo en tantos contextos en informática. En inglés no parecen significar lo mismo. No soy...
Mientras realizaba la tarea actual para mis cursos formales de idiomas y autómatas, me quedé atascado en ejercicios que involucran idiomas unarios (espero que sea el término correcto), es decir, idiomas que se basan en una sola letra. Sin embargo, no quiero preguntar sobre los ejercicios...
¿Hay algún algoritmo conocido para problemas formulados que requiera una complejidad ESPACIO de O (sqrt (N))? Sé que existen algoritmos con esa gran complejidad de
Si tengo dos matrices y B , de dimensiones 1000 × 2 y 2 × 1000 , respectivamente, y quiero calcular ( A B ) 5000 , es más eficiente reescribir primero la expresión como A ( B A ) 4999 B y solo entonces evalúe numéricamente, porque A B es de dimensión 1000 × 1000 pero B A es de dimensión 2 × 2...
Supongamos que hay una sesión de tutoría en una universidad. Tenemos un conjunto de kkk preguntas Q = { q 1 ... q k }Q={q1…qk}Q = \{ q_1 \ldots q_k \} y un conjunto de nnn estudiantes S = { s 1 ... s n }S={s1…sn}S = \{ s_1 \ldots s_n \} . Cada estudiante tiene una duda en un determinado...
Estaba pensando en gramáticas para lenguajes sensibles a la indendación y parece que las gramáticas CF funcionarían si se combinaran con parámetros. Como ejemplo, considere este fragmento para la gramática simplificada de Python en formato ANTLR: // on top-level the statements have empty...
Dadas dos cadenas, ¿cómo puede verificar si son una permutación entre sí utilizando el espacio O (1)? No se permite modificar las cadenas de ninguna manera. Nota: O (1) espacio en relación con la longitud de la cadena Y el tamaño del
Creo que estoy bastante confundido acerca de lo que se llama cálculo y lo que se llama lenguaje de programación. Tiendo a pensar, y podría haberme dicho, que un cálculo es un sistema formal para razonar sobre la equivalencia de los programas. Los programas tienen una semántica operativa...
La literatura es bastante clara que las RAM de costo unitario con multiplicación primitiva no son razonables, ya que no puede ser simulado por máquinas de Turing en tiempo polinómico puede resolver problemas completos de PSPACE en tiempo polinómico Sin embargo, todas las referencias que puedo...