Tengo la siguiente cita del curso de mi compilador (en el contexto de la coloración de gráficos): Debido a que es lento, la coloración de gráficos tiende a usarse en compiladores por lotes, mientras que el escaneo lineal tiende a usarse en compiladores JIT. No pude encontrar una definición...
Cada problema indecidible que conozco pertenece a una de las siguientes categorías: Problemas que son indecidibles debido a la diagonalización (autorreferencia indirecta). Estos problemas, como el problema de detención, son indecidibles porque podría usar un supuesto decisor para el lenguaje para...
Estoy tratando de entender los métodos de agrupamiento. Lo que creo que entendí: En el aprendizaje supervisado, los datos de categorías / etiquetas a los que se les asigna se conocen antes del cálculo. Por lo tanto, las etiquetas, clases o categorías se están utilizando para "aprender" los...
Soy ingeniero eléctrico, y solo tuve un curso de CS en la universidad hace 26 años. Sin embargo, también soy un usuario devoto de Mathematica. Tengo la sensación de que las máquinas de Turing son muy importantes en informática. ¿Es la importancia solo en la teoría de la informática? Si hay...
Si dos personas se pierden en un laberinto, ¿hay algún algoritmo que ambos puedan usar para encontrarse sin haber acordado previamente qué algoritmo usarán? Creo que hay algunas características que tendrá este algoritmo: Cada persona debe poder derivarlo utilizando una lógica que no haga...
Principalmente escribimos programas en lenguaje de alto nivel. Así que mientras estudiaba me encontré con el lenguaje ensamblador. Entonces, un ensamblador convierte el lenguaje ensamblador a lenguaje máquina y un compilador hace lo mismo con lenguaje de alto nivel. Encontré que el lenguaje...
Tengo un archivo que contiene números binarios ordenados de a 2 n - 1 :0 0002norte- 12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z no comprimió este archivo de manera muy eficiente (para n = 20, 22 MB se comprimieron a 300 kB). ¿Existen algoritmos que...
¿Cuál es la complejidad temporal de encontrar el diámetro de un gráfico ?G=(V,E)G=(V,E)G=(V,E) O(|V|2)O(|V|2){O}(|V|^2) O(|V|2+|V|⋅|E|)O(|V|2+|V|⋅|E|){O}(|V|^2+|V| \cdot |E|) O(|V|2⋅|E|)O(|V|2⋅|E|){O}(|V|^2\cdot |E|) O(|V|⋅|E|2)O(|V|⋅|E|2){O}(|V|\cdot |E|^2) El diámetro de un gráfico...
Estoy haciendo una presentación sobre las máquinas Turing y quería dar algunos antecedentes sobre los FSM antes de presentar las máquinas Turing. El problema es que realmente no sé qué es MUY diferente el uno del otro. Esto es lo que sé que es diferente: FSM tiene estados secuenciales...
Esta pregunta se migró de Software Engineering Stack Exchange porque se puede responder en Computer Science Stack Exchange. Migrado hace 6 años . ¿Podemos estudiar lenguajes de programación en el contexto de la lingüística? ¿Los lenguajes de programación evolucionan...
Estoy leyendo el libro: " Código: el lenguaje oculto del hardware y software de la computadora " y en el Capítulo 2 el autor dice: Se dice que el código Morse es un código binario (que significa literalmente dos por dos) porque los componentes del código consisten en solo dos cosas: un punto y...
Dado franjas horarias que gente quiere comprar. La persona tiene un valor para cada intervalo de tiempo . Cada persona solo puede comprar un bloque consecutivo de franjas horarias, que podrían estar vacías.nnnkkkiiih(i,j)≥0h(i,j)≥0h(i,j)\geq 0jjj ¿Existe un algoritmo de tiempo polinómico para...
Recientemente en mi clase de CS me presentaron a la máquina de Turing. Después de la clase, pasé más de 2 horas tratando de averiguar cuál es la relación entre una cinta y una máquina. No conocía por completo la existencia de cintas de computadora o cómo interactuaban las cintas y las máquinas...
A muchos se les ocurrió que en todas las pruebas de que he leído (que puedo recordar), siempre es trivial mostrar que hay un problema en , y mostrar que es -duro es la ... parte difícil. ¿Qué problemas -completos son estos cuyos verificadores de tiempo polinómico son altamente no...
Buscando una idea de las decisiones sobre el diseño del lenguaje recolectado basura. ¿Quizás un experto en idiomas podría iluminarme? Vengo de un fondo C ++, por lo que esta área es desconcertante para mí. Parece que casi todos los lenguajes modernos recolectados de basura con soporte de objetos...
Digamos que tiene dos polinomios: 3+x3+x3 + x y .2x2+22x2+22x^2 + 2 Estoy tratando de entender cómo FFT nos ayuda a multiplicar estos dos polinomios. Sin embargo, no puedo encontrar ningún ejemplo resuelto. ¿Alguien puede mostrarme cómo el algoritmo FFT multiplicaría estos dos polinomios? (Nota:...
Como se ve en esta reciente tira de XKCD y esta reciente publicación de blogde Peter Norvig (y una historia de Slashdot con este último), "regex golf" (que podría llamarse el problema de separación de expresiones regulares) es el rompecabezas de definir la expresión regular más corta posible que...
He estudiado mucho esto, y dicen que sobreajustar las acciones en el aprendizaje automático es malo, sin embargo, nuestras neuronas se vuelven muy fuertes y encuentran las mejores acciones / sentidos por los que pasamos o evitamos, además se pueden reducir / incrementar de mal / bueno por malos o...
El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no. ¿Cuáles son los ejemplos más simples (más pequeños) conocidos de tales
Estoy tomando un curso de complejidad y tengo problemas para encontrar reducciones entre los problemas de la APN. ¿Cómo puedo encontrar reducciones entre problemas? ¿Hay algún truco general que pueda usar? ¿Cómo debo abordar un problema que me pide que demuestre que un problema es...