Leí en muchos lugares que algunos problemas son difíciles de aproximar (es NP-difícil aproximarlos ). Pero la aproximación no es un problema de decisión: la respuesta es un número real y no Sí o No. Además, para cada factor de aproximación deseado, hay muchas respuestas correctas y muchas...
Podría haber una disculpa por hacer otra pregunta sobre los requisitos previos, pero estaba confundido acerca de los puntos de partida. Me he encontrado con varios términos como "Lógica modal", "Lógica temporal", "Lógica de primer orden", "Lógica de segundo orden" y "Lógica de orden...
La programación lineal (LP) está en P y la programación entera (IP) es NP-hard. Pero dado que las computadoras solo pueden manipular números con precisión finita, en la práctica una computadora usa números enteros para la programación lineal. Debido a esto, ¿no deberían LP e IP estar en la misma...
En la teoría de los autómatas, todos leemos autómatas como autómatas finitos, desde el principio. Lo que quiero saber es, ¿por qué los autómatas son finitos? Para ser claros, ¿qué hay en un autómata que es finito: el alfabeto, el idioma, las cadenas hechas con expresiones regulares o qué? ¿Y hay...
Supongamos que tengo una lista de funciones, por ejemplo nloglog(n),2n,n!,n3,nlnn,…nloglog(n),2n,n!,n3,nlnn,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots ¿Cómo los ordeno asintóticamente, es decir, después de la relación definida por f≤Og⟺f∈O(g)f≤Og⟺f∈O(g)\qquad f \leq_O g \iff f...
Tengo problemas para encontrar buenos recursos que den el peor de los casos en su lugar estableO ( n lnn )O(norteEnnorte)O(n \ln n) algoritmo de clasificación . ¿Alguien sabe de algún buen recurso? Solo un recordatorio, en su lugar significa que usa la matriz que se pasa y el algoritmo de...
Como educador de CS de nivel universitario, la cuestión de qué lenguaje de programación enseñar en el primer curso de programación a menudo se debate. Hay miles de idiomas para elegir, y mucha fiebre religiosa (o fevour) que apoya un campamento de idiomas sobre otro. Todo este sesgo subjetivo que...
Aquí está el pseudocódigo estándar para la primera búsqueda de amplitud: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!empty(q)) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Aquí pushy popse...
Soy nuevo en la comprensión de algoritmos informáticos. Entiendo el proceso de la búsqueda binaria, pero estoy teniendo un ligero malentendido con su eficiencia. En un tamaño de elementos, tomaría, en promedio, pasos para encontrar un elemento en particular. Tomar el logaritmo de base 2 de ambos...
De acuerdo con Wikipedia : La entropía de Shannon mide la información contenida en un mensaje en oposición a la parte del mensaje que se determina (o es predecible). Ejemplos de esto último incluyen redundancia en la estructura del lenguaje o propiedades estadísticas relacionadas con las...
Sé que Idris tiene tipos dependientes pero no está completo. ¿Qué no puede hacer al renunciar a la integridad de Turing, y esto está relacionado con tener tipos dependientes? Supongo que esta es una pregunta bastante específica, pero no sé mucho sobre los tipos dependientes y los sistemas de tipos...
La mayoría de nosotros aprendimos programación usando lenguajes de programación "textuales" como Basic, C / C ++ y Java. Creo que es más natural y eficiente para los humanos pensar visualmente. La programación visual permite a los desarrolladores escribir programas manipulando elementos gráficos....
Clásicamente, hay 3 formas populares de pensar en la computación: la máquina de Turing, los circuitos y el cálculo lambda (lo uso como una trampa para la mayoría de las vistas funcionales). Los 3 han sido formas fructíferas de pensar sobre diferentes tipos de problemas, y diferentes campos utilizan...
Entiendo que la "estructura" de los datos depende totalmente del álgebra booleana, pero: ¿Por qué se considera que los datos son una entidad matemática discreta en lugar de una entidad continua? Relacionado con esto: ¿Cuáles son los inconvenientes, o invariantes, que se violan al...
Un colega mío y yo acabamos de tocar algunas notas de uno de nuestros profesores. Las notas indican que hay tareas que son posibles de resolver en tiempo polinomial (están en la clase de PF) pero que NO son verificables en tiempo polinomial (NO están en la clase de NPF). Para elaborar sobre estas...
Al ver que en la Jerarquía de Chomsky, los lenguajes Tipo 3 pueden ser reconocidos por una máquina de estado sin memoria externa (es decir, un autómata finito), el Tipo 2 por una máquina de estado con una sola pila (es decir, un autómata pushdown) y el Tipo 0 una máquina de estados con dos pilas...
¿Hay algún problema conocido en N PNP\mathsf{NP} (y no en PAGSP\mathsf{P} ) que no sea N PNP\mathsf{NP} Complete? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad. Si hay un problema que es NPNP\mathsf{NP} (y no PP\mathsf{P} )...
Puede sonar como una pregunta estúpida, pero tengo mucha curiosidad por saber cómo una computadora sabe que . Además, ¿cómo sabe una computadora que el orden de los enteros es 1 , 2 , 3 , 4 , 5 , ... y el alfabeto es A, B, C, D, ...? ¿Está almacenado en algún lugar en el hardware o el sistema...
Veo que la mayoría de las definiciones de lo que es ser Turing completo son tautológicas hasta cierto punto. Por ejemplo, si buscas en Google "qué significa ser Turing completo", obtienes: Una computadora está completa en Turing si puede resolver cualquier problema que una máquina de Turing...
Me pregunto si hay una forma estándar de medir la "clasificación" de una matriz. ¿Se consideraría una matriz que tiene el número medio de posibles inversiones máximamente sin clasificar? Con eso quiero decir que está básicamente lo más lejos posible de ser ordenado o