\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty} El problema proviene directamente de las matemáticas computacionales y puede ser declarado de la siguiente manera: Dada una matriz regular , encuentre efectivamente todos los vectores modo que , donde \ n {Mv} sea el componente máximo...
Quiero demostrar que la complejidad temporal de un algoritmo es poliglogarítmica en la escala de entrada. La relación de recurrencia de este algoritmo es , donde .T(2n)≤T(n)+T(na)T(2n)≤T(n)+T(na)T(2n) \leq T(n) + T(n^a)a∈(0,1)a∈(0,1)a\in(0,1) Parece que para algunos depende de . Pero no puedo...
Este es un problema de ejercicio (Ej. 3) de la excelente nota de lectura de Jeff Erickson Lectura 20: Árboles de expansión mínima [Fa'13] . Probar que un gráfico ponderado por el borde GGG tiene un árbol de expansión mínimo único si y solo si se cumplen las siguientes condiciones Para...
Supongamos que ΠΠ\Pi es un problema de decisión decidible. ¿ Π∉NPΠ∉NP\Pi\not \in NP implica ΠΠ\Pi is NPNPNP -Hard? Editar: si suponemos que existe Π∈coNP∖NPΠ∈coNP∖NP\Pi\in coNP\setminus NP entonces hemos terminado. ¿Podemos refutar el reclamo sin suposiciones...
Se dice que el Método de Incompresibilidad simplifica el análisis de algoritmos para el caso promedio. Por lo que entiendo, esto se debe a que no hay necesidad de calcular todas las combinaciones posibles de entrada para ese algoritmo y luego derivar una complejidad promedio. En cambio, se toma una...
¿Es posible minimizar los autómatas pushdown? Si no, ¿por qué? ¿Es porque para minimizar las clases de equivalencia deben tener un índice finito y no podemos garantizarlo para
Estoy tratando de vincular circuitos lógicos combinacionales (computadoras basadas solo en puertas lógicas) con todo lo que aprendí recientemente en Teoría de la Computación. Me preguntaba si los circuitos lógicos combinacionales pueden implementar cálculos de la misma manera que las máquinas de...
He leído muchos documentos y libros sobre ontologías y estoy tratando de entender cómo se usan en un proyecto real. Por ejemplo, ¿cómo se puede definir y utilizar la ontología para un robot jugador de fútbol con una arquitectura cognitiva para que sea inteligente? ¿Son las ontologías relaciones...
Estoy trabajando en mi propio lenguaje de programación con fines educativos, y me he encontrado con un pequeño problema. Hay algunas soluciones diferentes para ello, pero todas parecen poco elegantes, y por lo que entiendo, innecesarias. Pero leyendo los libros que tengo y las búsquedas en Google,...
En un gráfico , hacemos el siguiente proceso:G ( V, E)G(V,E)G(V,E) Inicialmente, todos los nodos en son incoloros.VVV Si bien hay nodos sin color en , cada nodo sin color hace lo siguiente: VVV Selecciona un número real aleatorio y lo envía a todos sus vecinos; Compara su número con el número de...
Parece que la distinción entre fibras e hilos es que las fibras se programan de forma cooperativa, mientras que los hilos se programan de forma preventiva. El punto del planificador parece ser una forma de hacer que un recurso de procesador en serie actúe de manera paralela, "compartiendo el...
Sé que la Comprobación de modelo simbólico es un recorrido de espacio de estado basado en representaciones de conjuntos de estados y relaciones de transición como fórmulas como en CTL usando modelos como Kripke Model. Conozco la teoría Pero me resulta difícil entender la aplicación real. ¿Dónde se...
Según la tesis de Church-Turing, es imposible diseñar un algoritmo para decidir el problema de detención. ¿La palabra algoritmo en este contexto incluye inteligencia artificial o no, es decir, la tesis de Church-Turing también se aplica a la inteligencia artificial? ¿Es posible diseñar un...
El ejercicio 4.29 de Computación cuántica e información cuántica de Nielsen y Chuang me tiene perplejo. Encuentre un circuito que contenga Toffoli, CNOT y compuertas qubit simples que implemente una compuerta (para ), sin utilizar qubits de trabajo.O (norte2)O(norte2)O(n^2)Cnorte(...
Me dan n objetos, y un conjunto de n permutaciones de estos n objetos (de n! Permutaciones totales). Hay una verdadera permutación subyacente, que sé que es una entre el conjunto de n permutaciones, pero no sé cuál. Sin embargo, un oráculo conoce la verdadera permutación. Para encontrar la...
Soy estudiante universitario y estoy deseando convertirme en académico; hacer todo el doctorado y comenzar a investigar. Estoy interesado en una variedad de cosas relacionadas con la informática, pero últimamente las tecnologías P2P realmente me han llamado la atención. Tengo la impresión de que...
El modelo de aprendizaje probablemente aproximadamente correcto (PAC) se define como: Se dice que una clase de concepto puede aprenderse con PAC si existe un algoritmo y una función polinómica tal que para cualquier ε> 0 y δ> 0 , para todas las distribuciones D en X y para cualquier concepto...
Aquí está la fuente de mi pregunta. Dado un árbol de auto-equilibrio (AVL), codifique un método que devuelva la mediana. (Mediana: el valor numérico que separa la mitad superior de una muestra de datos de la mitad inferior. Ejemplo: si la serie es 2, 7, 4, 9, 1, 5, 8, 3, 6 entonces la...
Tengo un gráfico no ponderado no dirigido y quiero seleccionar nodos de modo que estén en pares lo más lejos posible entre sí, en términos de distancia geodésica . En otras palabras, deben extenderse alrededor del gráfico como sea posible.GGGkkkGGG Que ser la longitud de un camino más corto entre...
Dado un gráfico bipartito donde cada vértice está coloreado de rojo o azul, estoy tratando de minimizar el número de vértices azules usando la siguiente operación:G = ( A , B , E)G=(A,B,E)G = (A,B,E) Elija un vértice envunavav_aUNAAA Voltee los colores de , lo que significa que y todos los...