Me gustaría comenzar la pregunta diciendo que soy programador y que no tengo muchos antecedentes en teoría de la complejidad. Una cosa que he notado es que si bien muchos problemas son NP completos, cuando se extienden a problemas de optimización, algunos son mucho más difíciles de aproximar que...
Es bien sabido que la inferencia de tipo Hindley-Milner (el cálculo tipo simple con polimorfismo) tiene una inferencia de tipo decidible: puede reconstruir tipos de principios para cualquier programa sin ninguna anotación.λλ\lambda Agregar clases de tipo de estilo Haskell parece preservar esta...
Quizás mi comprensión limitada del tema es incorrecta, pero esto es lo que entiendo hasta ahora: La programación funcional se basa en el cálculo Lambda, formulado por Alonzo Church. La programación imperativa se basa en el modelo de máquina de Turing, realizado por Alan Turing, estudiante de...
En el sitio web de Algoritmos de clasificación , se realiza el siguiente reclamo: El algoritmo de ordenación ideal tendría las siguientes propiedades: Estable: las claves iguales no se reordenan. Opera en su lugar, requiriendo espacio extra.O(1)O(1)O(1) El peor de los casos comparaciones...
Recientemente me topé con el siguiente artículo interesante que afirma comprimir eficientemente conjuntos de datos aleatorios en siempre más del 50%, independientemente del tipo y formato de los datos. Básicamente, usa números primos para construir de manera única una representación de fragmentos...
Encuentre la menor cantidad de comparaciones necesarias para ordenar (ordenar) cinco elementos e idee un algoritmo que clasifique estos elementos usando esta cantidad de comparaciones. Solución : ¡ Hay 5! = 120 resultados posibles. Por lo tanto, un árbol binario para el procedimiento de...
Pregunta: ¿Existe algún procedimiento o teoría establecida para generar código que aplique eficientemente una multiplicación matriz-vector, cuando la matriz es densa y está llena de ceros y unos? Idealmente, el código optimizado haría un uso sistemático de la información previamente calculada para...
Sé que, en los lenguajes de programación imperativos, un bucle while-do es suficiente como una construcción de flujo de control para completar el lenguaje Turing (en lo que respecta al flujo de control, por supuesto, también necesitamos memoria ilimitada y ciertos operadores ...) . La esencia de mi...
Considere la siguiente tarea algorítmica: Entrada: un entero positivo , junto con su factorización prima Encontrar: enteros positivos que minimizan , sujeto a la restricción de quex , y , znnnx,y,zx,y,zx,y,zx y z = nxy+yz+xzxy+yz+xzxy+yz+xzxyz=nxyz=nxyz=n ¿Cuál es la complejidad de este...
Dado un gráfico ponderado y no dirigido G: ¿Qué condiciones deben ser ciertas para que haya múltiples árboles de expansión mínima para G? Sé que el MST es único cuando todos los pesos son distintos, pero no puede revertir esta afirmación. Si hay varias aristas con el mismo peso en el gráfico,...
Me estoy preparando para una entrevista de codificación y realmente no puedo encontrar la forma más eficiente de resolver este problema. Digamos que tenemos dos matrices que consisten en números que no están ordenados. La matriz 2 contiene un número que la matriz 1 no tiene. Ambas matrices tienen...
¿Cuándo se usó Big O por primera vez en informática y cuándo se convirtió en estándar? La página de Wikipedia sobre esto cita a Knuth, Big Omicron y Big Omega y Big Theta , SIGACT de abril a junio de 1976, pero el comienzo de ese artículo dice La mayoría de nosotros nos hemos acostumbrado a la...
Me gustaría saber si hay una regla para probar esto. Por ejemplo, si uso la ley distributiva solo obtendré .( A ∨ A ) ∧ ( A ∨ ¬ B )(A∨A)∧(A∨¬B)(A \lor A) \land (A \lor \neg
Considere un tipo inductivo que tiene algunas ocurrencias recursivas en una ubicación anidada, pero estrictamente positiva. Por ejemplo, árboles con ramificación finita con nodos que utilizan una estructura de datos de lista genérica para almacenar los elementos secundarios. Inductive LTree : Set...
Que yo sepa, hay tres álgebras de procesos principales que han inspirado una amplia gama de investigaciones sobre modelos formales de concurrencia. Estos son: CCS y cálculo ambos por Robin Milnerππ\pi CSP por Tony Hoare y ACP por Jan Bergstra y Jan Willem Klop Los tres parecen tener hasta el...
Sé que desde ~ 2004, la ley de Moore dejó de funcionar para la velocidad del reloj de la CPU. Estoy buscando un gráfico que muestre esto, pero no puedo encontrarlo: la mayoría de los gráficos muestran el recuento de transistores o la capacidad por año. ¿Dónde puedo encontrar algunos datos que...
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . En el script que estoy leyendo actualmente sobre el cálculo lambda, la equivalencia beta se define así: La...
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . ¿Cuál es un buen libro de ciencias de la computación para principiantes para un adulto joven, digamos, un...
Esta pregunta se migró de Intercambio teórico de apilamiento de informática porque se puede responder en Intercambio apilado de informática. Migrado hace 7 años . Quiero probar o refutar la existencia de un algoritmo que, dada una matriz de enteros, encuentra tres índices...
Si un gráfico ponderado tiene dos árboles de expansión mínima diferentes y , entonces es cierto que para cualquier borde enT 1 = ( V 1 , E 1 ) T 2 = ( V 2 , E 2 ) e E 1 E 1 e e E 2 eGGGT1=(V1,E1)T1=(V1,E1)T_1 = (V_1, E_1)T2=(V2,E2)T2=(V2,E2)T_2 = (V_2, E_2)eeeE1E1E_1 , el número de bordes en con el...