Preguntas relacionadas con la combinatoria y las estructuras matemáticas discretas.
El problema 3SUM intenta identificar 3 enteros de un conjunto S de tamaño n tal que a + b + c = 0 .a , b , ca,b,ca,b,cSSSnortenna + b + c = 0a+b+c=0a + b + c = 0 Se conjetura que no hay mejor solución que la cuadrática, es decir, . O para decirlo de otra manera: o ( n log ( n ) + n 2 ) .o (...
Actualmente estoy leyendo un libro sobre algoritmos y complejidad. En este momento, estoy leyendo sobre funciones computables y no computables, y mi libro dice que hay muchas más funciones que no son computables que computables, de hecho, la mayoría no son computables, dice. En cierto sentido,...
(Soy un estudiante con algunos conocimientos matemáticos y me gustaría saber cómo contar el número de un tipo específico de árboles binarios). Mirando la página de Wikipedia para árboles binarios , noté esta afirmación de que el número de árboles binarios enraizados de tamaño sería este número...
Para un lenguaje regular , deje que sea el número de palabras en de longitud . Usando la forma canónica de Jordan (aplicada a la matriz de transición sin anotaciones de algunos DFA para L ), se puede demostrar que para n suficientemente grande , c_n (L) = \ sum_ {i = 1} ^ k P_i (n) \ lambda_i ^...
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...
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...
Inicialmente, matroides se introdujeron generalizar las nociones de independencia lineal de una colección de subconjuntos sobre algún motivo previsto Me . Ciertos problemas que contienen esta estructura permiten que los codiciosos algoritmos encuentren soluciones óptimas. El concepto de greedoids...
Un comercial de pizza afirma que puede combinar sus ingredientes en 34 millones de combinaciones diferentes. No lo creía, así que desempolvé mis oxidadas habilidades combinatorias e intenté resolverlo. Esto es lo que tengo hasta ahora: desde el sitio de pedidos en línea obtuve las...
Deje que sea un conjunto finito de caracteres de tamaño fijo. Deje que sea una cadena sobre . Decimos que una subcadena no vacía de es una repetición if para alguna cadena .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Ahora, mi pregunta es si se cumple...
¿Cuántos max-heaps diferentes existen para una lista de nnn enteros? Ejemplo: lista [1, 2, 3, 4] El max-heap puede ser 4 3 2 1: 4 / \ 3 2 / 1 o 4 2 3 1: 4 / \ 2 3
Un gráfico unipático es un gráfico dirigido de tal manera que existe como máximo una ruta simple desde cualquier vértice a cualquier otro vértice. Los gráficos unipáticos pueden tener ciclos. Por ejemplo, una lista doblemente vinculada (¡no circular!) Es un gráfico unipático; si la lista tiene...
Suponga que está obteniendo un número mmm (usando bits O(logm)O(logm)O(\log m) en codificación binaria). ¿Qué tan rápido puede encontrar (o determinar que tal no existe) ?n,k∈N,1<k≤n2:(nk)=mn,k∈N,1<k≤n2:(nk)=mn,k\in \mathbb N,
La combinatoria juega un papel importante en la informática. Con frecuencia utilizamos métodos combinatorios tanto en el análisis como en el diseño de algoritmos. Por ejemplo, un método para encontrar un conjunto de portadas de kkk vértices en un gráfico podría inspeccionar todos los subconjuntos...
Según Wikipedia , para cualquier lenguaje regular existen constantes y polinomios modo que para cada el número de palabras de longitud en satisface la
He estado trabajando en el siguiente problema de este libro . Un cierto lenguaje de procesamiento de cadenas ofrece una operación primitiva que divide una cadena en dos partes. Como esta operación implica copiar la cadena original, se necesitan n unidades de tiempo para una cadena de longitud n,...
Especificar cualquier cuadrícula arbitraria de 9x9 requiere dar la posición y el valor de cada cuadrado. Una codificación ingenua para esto podría dar 81 tripletes (x, y, valor), que requieren 4 bits para cada x, y, y valor (1-9 = 9 valores = 4 bits) para un total de 81x4x3 = 972 bits. Al numerar...
¿Existe una caracterización algebraica del número de palabras de una longitud dada en un idioma normal? Wikipedia establece un resultado algo impreciso: Para cualquier lenguaje regular LLL existen constantes λ1,…,λkλ1,…,λk\lambda_1,\,\ldots,\,\lambda_k y
Estoy tratando de construir todas las matrices equivalentes (o n × n si lo desea) con los elementos 0 o 1. La operación que da matrices equivalentes es el intercambio simultáneo de la fila i y j Y la columna i y j. p.ej. para 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) ∼ ( 1 0 1 0 0 0 0 1 0 )8×88×88\times...
Alguien en una discusión mencionó que (él cree) que puede haber al menos un número continuo de estrategias para abordar un problema específico. El problema específico eran las estrategias comerciales (no los algoritmos sino las estrategias), pero creo que eso no viene al caso en mi pregunta. Esto...
Estoy tratando de derivar el artículo clásico en el título solo por medios elementales (sin funciones generadoras, sin análisis complejo, sin análisis de Fourier) aunque con mucha menos precisión. En resumen, "solo" quiero demostrar que la altura promedio hnhnh_n de un árbol con nnn nodos (es...