Me interesa la cuestión de cómo enseñar mejor la completitud de NP a los estudiantes de informática. En particular, ¿deberíamos enseñarlo usando reducciones de Karp o reducciones de Turing? Siento que los conceptos de NP-completitud y reducciones son algo que todo experto en informática debería...
En clase la semana pasada, mi profesor comentó y dijo que las máquinas de Turing se usan como una medida / modelo estándar de lo que es computable y son una base útil de discusión para ese tema. También dijo que se ha demostrado que todas las variantes de las máquinas de Turing son...
Si tengo alguna función por su complejidad, el tiempo es O ( mn ), donde m y n son los tamaños de sus dos entradas, tendría que llamar a su complejidad tiempo "lineal" (ya que es lineal en ambos m y n ) o "cuadrática" ( ya que es un producto de dos tamaños) ¿O algo mas? Siento que llamarlo...
Intenté algunos casos y descubrí que dos árboles de expansión de un gráfico simple tienen algunos bordes comunes. Quiero decir que no pude encontrar ningún contraejemplo hasta ahora. Pero tampoco pude probar o refutar esto. ¿Cómo probar o refutar esta
¿El análisis suavizado encontró su camino en el análisis principal de algoritmos? ¿Es común que los diseñadores de algoritmos apliquen análisis suavizados a sus
Sabemos que los DFA son equivalentes a los NFA en poder de expresividad; También hay un algoritmo conocido para convertir NFA a DFA (desafortunadamente ahora conozco al inventor de ese algoritmo), que en el peor de los casos nos da estados, si nuestro NFA tenía estados.2S2S2^SSSS Mi pregunta es:...
Esas terminologías me confunden. Según entiendo Solucionador SAT: decida la satisfacción de la lógica proposicional (usando DPLL o Búsqueda local). El procedimiento de decisión es un procedimiento para decidir la satisfacción de una determinada teoría de primer orden decidible. El solucionador...
Sea una fórmula booleana que consta de los operadores habituales AND, OR y NOT y algunas variables. Me gustaría contar el número de asignaciones para satisfacer B . Es decir, quiero encontrar el número de asignaciones diferentes de valores de verdad a las variables de para las cuales asume un valor...
Me parece que 'implica' en el idioma inglés no significa lo mismo que el operador lógico 'implica', de manera similar a cómo la palabra 'OR' en la mayoría de los casos significa 'OR exclusivo' en nuestro uso cotidiano del idioma. Tomemos dos ejemplos: Si hoy es lunes, mañana es martes. Esto...
En un artículo reciente de CACM [1], los autores presentan una implementación para funciones por etapas . Usan el término como si fuera bien conocido, y ninguna de las referencias parece una introducción obvia. Dan una breve explicación (el énfasis es mío y el número de referencia cambió; es 22 en...
Tengo dos formas de producir una lista de artículos en un orden aleatorio y me gustaría determinar si son igualmente justos (imparciales). El primer método que utilizo es construir la lista completa de elementos y luego barajarla (digamos barajar Fisher-Yates). El segundo método es más un método...
Esta pregunta se migró de Stack Overflow porque se puede responder en Computer Science Stack Exchange. Migrado hace 7 años . Estoy un poco confundido por alguna terminología que he encontrado con respecto a la complejidad de los problemas de optimización. En una clase de...
Dado un conjunto de monedas con diferentes denominaciones un valor v desea encontrar la menor cantidad de monedas necesarias para representar el valor v.c 1 , . . . , c ndo1,...,donortec1, ... , cn Por ejemplo, para el conjunto de monedas 1,5,10,20, esto da 2 monedas por la suma 6 y 6 monedas por...
Estoy tratando de tener una idea de cómo se debe interpretar la prueba de primalidad AKS a medida que la conozco, por ejemplo, un corolario para demostrar que PRIMES ⊆ P, o un algoritmo realmente práctico para pruebas de primalidad en computadoras. La prueba tiene tiempo de ejecución polinómico...
Dado un conjunto múltiple de números naturales X, considere el conjunto de todas las sumas posibles: sumas (X) = { ∑i ∈ AyoEl |A ⊆ X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Por ejemplo, sumas ( { 1 , 5 } )= { 0 , 1 , 5 , 6...
¿Todos los generadores de números pseudoaleatorios son en última instancia periódicos? ¿O son periódicas al final? Por periódico quiero decir que, al igual que los números racionales, al final generan una subsecuencia periódica ... Y seudoaleatorio significa generación algorítmica / matemática de...
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 6 años . Me he encontrado con muchas definiciones de lenguajes recursivos y recursivamente enumerables. Pero no pude...
¿Hay algún algoritmo que sea muy difícil de paralelizar o la investigación aún está activa? Quería saber sobre cualquier algoritmo o cualquier campo de investigación en computación paralela. Todo lo que busqué tiene una implementación "paralela". Solo quiero estudiar un poco sobre cualquier campo...
En un gráfico no ponderado, no dirigido, con vértices VVV y bordes EEE tales que 2V>E2V>E2V \gt E , ¿cuál es la forma más rápida de encontrar todos los caminos más cortos en un gráfico? ¿Se puede hacer más rápido que Floyd-Warshall que es O(V3)O(V3)O(V^3) pero muy rápido por iteración? ¿Qué...
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 . Acabo de tener esta pregunta interesante. ¿Cuál es la función de más rápido crecimiento conocida por el...