A menudo interactúo con personas que desean solicitar un algoritmo para un problema computacional (o su complejidad), pero no lo expresan de manera rigurosa para que nosotros (los científicos informáticos) lo comprendamos. Remitirlos a libros como CLRS no es útil porque los ejemplos allí...
En el libro de Andrew W. Appel, Modern Compiler Implementation in ML , dice en el capítulo 17 que la teoría de la computabilidad muestra que siempre será posible inventar nuevas transformaciones optimizadoras y procede a demostrar que un compilador completamente optimizador resolverá el problema de...
Algunos algoritmos complicados ( union-find ) tienen la función inversa de Ackermann casi constante que aparece en la complejidad de tiempo asintótica, y son óptimos en el peor de los casos si se ignora el término de Ackermann inverso casi constante. ¿Hay ejemplos de algoritmos conocidos con...
Esta pregunta se migró de Intercambio de pila de inteligencia artificial porque se puede responder en el intercambio de pila de informática. Migrado hace 5 años . En la mayoría de las implementaciones de algoritmos genéticos, el enfoque está en el cruce y la mutación....
Bien, antes de comenzar, me doy cuenta de que esto está al margen del tema (he leído la ayuda de Preguntas para este sitio), particularmente porque este no es un problema del mundo real. Sin embargo: No puedo encontrar nada relevante en Google ¿Desde un punto de vista purista seguramente debe...
Sé lo que es la computación en un sentido vago (es lo que hacen las computadoras), pero me gustaría una definición más rigurosa. Dictionary.comLas definiciones de computación, computación, cálculo y computación son circulares, por lo que no ayuda. Wikipediadefine el cálculo como "cualquier tipo...
Bueno, esta es una pregunta general. Y si alguien quiere hacer que su implementación sea específica, preferiré cosas relacionadas con Unix. Pero primero necesita saber los siguientes problemas en general: Leí que el proceso único puede tener múltiples hilos. Múltiples hilos del mismo proceso...
A menudo escucho que el polimorfismo de fila es un enfoque mejor que el subtipo, pero tengo dificultades para encontrar algo que los compare en detalle. Estoy especialmente interesado en la perspectiva de un usuario del sistema. Me encontré con esta publicación de blog, pero me deja con más...
Solo por interés, traté de resolver un problema de la categoría "Reciente" del Proyecto Euler ( secuencia de suma de dígitos ). Pero no puedo pensar en una forma de resolver el problema de manera eficiente. El problema es el siguiente (en la secuencia de preguntas original hay dos al principio,...
Comparando un par ordenado (x, y) con un par desordenado {x, y} (conjunto), entonces la información teóricamente, la diferencia es solo un bit, ya que si x viene primero o y requiere exactamente un solo bit para representar. Entonces, si se nos da un conjunto {x, y} donde x, y son dos enteros...
Un artículo llamado La derivada de un tipo regular es su tipo de contextos de un agujero muestra que la "cremallera" de un tipo, sus contextos de un agujero, siguen las reglas de diferenciación en álgebra de
Estoy buscando una estructura de datos que empuje su elemento más antiguo / último si se inserta un nuevo elemento. Por ejemplo, vamos a Drepresentar la estructura. Dcontiene 3 elementos de los Number Dvalores predeterminados del tipo que se inicializarán en 1, 2y 3. D = [ 1 , 2 , 3 ]re=[1,2,3]D =...
El operador de diferencia de conjuntos (p. Ej., EXCEPTEn algunas variantes de SQL) es uno de los muchos operadores fundamentales del álgebra relacional. Sin embargo, hay algunas bases de datos que no admiten el operador de diferencia de conjunto directamente, pero que admiten LEFT JOIN(una especie...
Muchas referencias de sistemas operativos dicen que con la multitarea cooperativa (en lugar de preventiva), un proceso mantiene la CPU hasta que se suspende voluntariamente de forma explícita. Si un proceso en ejecución realiza una solicitud de E / S que no puede satisfacerse de inmediato (por...
Estoy comenzando una investigación bibliográfica personal sobre algoritmos de verificación de tipos y quiero algunos consejos. ¿Cuáles son los algoritmos, estrategias y técnicas generales de verificación de tipos más utilizados? Estoy particularmente interesado en algoritmos complejos de...
He estado trabajando en programación dinámica por algún tiempo. La forma canónica de evaluar una recursión de programación dinámica es creando una tabla de todos los valores necesarios y llenándola fila por fila. Ver por ejemplo Cormen, Leiserson et al: "Introducción a los algoritmos" para una...
Hay una reducción en el libro de Sipser "Introducción a la teoría de la computación" en la página 286 de 3SAT al problema del camino hamiltoniano. ¿Hay una reducción más simple? Por simple quiero decir una reducción que sería más fácil de entender (para estudiantes). ¿Existe una reducción...
Soy un estudiante graduado que está tomando un curso de teoría de la computación y tengo serios problemas para producir contenido una vez que me lo piden. Puedo seguir el libro de texto (Introducción a la teoría de la computación de Michael Sipser) y las conferencias; sin embargo, cuando se me pide...
Nuestro profesor nos pidió que pensáramos en una función en OCaml que tenga el tipo 'a -> 'b es decir, una función de un argumento que podría ser cualquier cosa, y que puede devolver una cosa diferente. Pensé en usar raiseuna función que ignora su argumento: let f x = raise Exit Pero el...
En Algorithmics for Hard Problems de Hromkovič (2a edición) existe este teorema (2.3.3.3, página 117): Hay un problema de decisión (decidible) tal que para cada algoritmo A que resuelve P hay otro algoritmo A ' que también resuelve P y además cumplePAGPPUNAAPAGPPA′A′A'PPP...