Aquí está mi intento de solución para el problema 8-15 del Manual de diseño de algoritmos:
a) Demuestre que [matemáticas] E (1, n) = n [/ matemáticas]
Si solo tenemos un huevo, que si lo dejamos caer primero desde cualquier posición menor que n, podría romperse y no podremos saber si se rompe para la posición n o no. Entonces, la primera posición que debemos sondear es n. Entonces [matemáticas] E (1, n) = E (1, n-1) +1 [/ matemáticas]. Trivialmente E (1,0) = 0, entonces por inducción E (1, n) = n.
b) Demuestre que [matemáticas] E (k, n) = \ Theta (n ^ \ frac {1} {k}) [/ matemáticas]
Observe primero que si usamos un huevo para evaluar el nivel my SE ROMPA, entonces tenemos todos los niveles m + 1, m + 2, …, n como candidatos para el nivel máximo. Hay nm tales niveles. Entonces, si el huevo se rompe, entonces nuestro número total de pruebas será 1 + E (k-1, nm). Si no se rompe, tenemos los niveles candidatos 1,2, …, m-1, lo que arroja 1 + E (k, m-1) número total de ensayos.
Dado que queremos el número de ensayos en el peor de los casos, podemos suponer que cada vez que probamos el nivel m, obtendremos un resultado (romper o sobrevivir) que es el peor en términos del número máximo restante de ensayos.
- ¿Qué significa shift / reduce en el análisis?
- Cómo probar [matemáticas] p (a \ cup b \ cup c) \ leq p (a) + p (b) + p (c) [/ math]
- ¿Cómo se descubre la estructura en patrones bidimensionales?
- ¿Puede un niño de diez años aprender Java, si es bueno en matemáticas?
- ¿Cómo va NP-hard dentro de NP-complete? Si encontramos un algoritmo no determinista para NP-hard, ¿sería un NP-complete?
Dado que queremos minimizar el número total de ensayos, podemos tener:
E (k, n) = MIN {m = 1..n} (1+ MAX [E (k-1, nm), E (k, m-1)]).
Dado que (a), por hipótesis de inducción tenemos [matemáticas] E (k, j) = \ Theta (j ^ \ frac {1} {k}) [/ matemáticas] para j <n.
Observe también que k <= n. No proporciona ayuda adicional que tengamos más huevos que el número máximo de pruebas que podemos hacer. De hecho, lo mejor de E [n, k] es Theta (log n), ya que si tuviéramos un número ilimitado de huevos, lo óptimo sería buscar binariamente el espacio del piso que sería óptimo. Por lo tanto, también tenemos k <= log n (para k más grande, la respuesta sigue siendo E [n, log n]). De hecho, el k máximo requerido será menor dada nuestra fórmula de inducción: (k_max = [math] \ frac {log n} {log log n} [/ math]). Esto fue solo una trivia.
Ahora mostraremos cuándo cada cantidad es mayor: E (k-1, nm) o E (k, m-1) a medida que variamos m (¡con k y n fijos!).
Necesitamos comparar:
E (k-1, nm): E (k, m-1)
IZQUIERDA = [matemáticas] \ Theta ((nm) ^ \ frac {1} {k-1}]): \ Theta ((m-1) ^ \ frac {1} {k}) = DERECHA [/ matemáticas]
Deje LEFTe = [matemática] (nm) ^ \ frac {1} {k-1} [/ matemática], DERECHA = [matemática] (m-1) ^ \ frac {1} {k} [matemática].
Observe que dado que nm disminuye con m (pero aún es> 1), también lo hace LEFTe.
Tenga en cuenta que dado que m-1 aumenta con m, también lo hace RIGHTe.
Observe que LEFTe (2)> RIGHTe (2).
Por estas tres observaciones tenemos que:
IZQUIERDA (1)> DERECHA (1), IZQUIERDA (2)> DERECHA (2),…, IZQUIERDA (x)> DERECHA (x)
luego
DERECHA (x + 1)> IZQUIERDA (x + 1),…, DERECHA (n)> IZQUIERDA (n), para algunos x <= n.
Asi que:
E (k, n) = MIN {m = 1..x} (1+ IZQUIERDA (m)), MIN {m = x + 1..n} {1 + DERECHA (m)}.
Como IZQUIERDA (m) disminuye con m, su valor más pequeño estará en m = x.
Como RIGHT (m) aumenta con m, su valor más pequeño estará en m = x + 1.
Entonces E (k, n) = [matemáticas] 1 + MIN (\ Theta ((nx) ^ \ frac {1} {k-1}), Teta (x ^ \ frac {1} {k})) [/ mates].
Ahora sabemos que x seguramente existe, así que vamos a encontrarlo.
Consideremos [matemáticas] R = E (k-1, nx) / E [k, x] [/ matemáticas].
Entonces [matemática] R = [A1 / A2] * \ frac {(nx) ^ \ frac {1} {k-1}} {x ^ \ frac {1} {k}} [/ matemática].
R = [matemáticas] [[A1 / A2] ^ k * \ frac {(nx) ^ \ frac {k} {k-1}} {x}] ^ \ frac {1} {k} [/ matemáticas].
Para R <1 necesitamos que [matemáticas] [A1 / A2] ^ k * \ frac {(nx) ^ \ frac {k} {k-1}} {x} <1 [/ matemáticas].
Tomando log, tenemos: k * (log (A1) -log (A2)) + [math] \ frac {k} {k-1} * log (nx) -log (x) <0 [/ math].
Escribimos nx = n / (2 ^ l). Entonces [matemáticas] x = n * (1- \ frac {1} {2 ^ l}) [/ matemáticas].
Entonces [math] log (x) = (1- \ frac {1} {2 ^ l}) + log n [/ math].
Reescribiendo obtenemos:
k * (log (A1) -log (A2)) + [matemáticas] \ frac {k} {k-1} * [logn – l] – (1- \ frac {1} {2 ^ l}) – logn <0 [/ matemática].
k * (log (A1) -log (A2)) + [matemáticas] (\ frac {k} {k-1} -1) * logn – l * \ frac {k} {k-1} -1 + 1 / 2 ^ l <0 [/ matemáticas].
[matemáticas] \ frac {k * (log (A1) -log (A2)) + (\ frac {k} {k-1} -1) * logn + 1/2 ^ l -1} {\ frac {k } {k-1}] <l [/ matemáticas].
l> (log (A1) -log (A2)) * (k-1) + [math] [1- \ frac {k-1} {k}] * logn – \ Theta (1) [/ math]. // Con un factor oculto muy pequeño en Theta (1): menos de 1.
l> (log (A1) -log (A2)) * (k-1) + [math] \ frac {1} {k} * logn – \ Theta (1) [/ math].
Ignoremos por un momento los factores de corrección A1, A2. (Diga log (A1 / A2) = 0 o log (A1 / A2) = 1 / (k-1)). Por esta hipótesis obtenemos
[matemáticas] l = 1 / k * log n [/ matemáticas] .
Corregimos el factor pequeño Theta (1) tomando l como el valor redondeado de la fórmula anterior.
Entonces tenemos:
[matemáticas] nx = \ frac {n} {2 ^ \ frac {logn} {k}} = \ frac {n} {n ^ \ frac {1} {k}} = n ^ (1- \ frac {1 } {k}) = n ^ (\ frac {k-1} {k}) [/ math].
Asi que
IZQUIERDA (x) = [matemáticas] A1 * (n ^ \ frac {k-1} {k}) ^ \ frac {1} {k-1} = A1 * n ^ \ frac {1} {k} = \ Theta (n ^ \ frac {1} {k}) [/ math].
También:
[matemáticas] x = n * (1- \ frac {1} {2 ^ \ frac {logn} {k}}) = n * (1- \ frac {1} {n ^ \ frac {1} {k} }) [/ matemáticas]
Asi que
[matemáticas] DERECHA (x) = A2 * n ^ \ frac {1} {k} * (1- \ frac {1} {n ^ \ frac {1} {k}}) ^ \ frac {1} {k } [/ matemáticas]
[matemáticas] DERECHA (x)> A2 * n ^ \ frac {1} {k} * (1- \ frac {1} {2 ^ \ frac {1} {k}}) ^ \ frac {1} {k } [/ matemáticas]. El último término en el producto tiene límite 1 cuando k -> + inf y mínimo 1/2 para k = 1 (ver ((1-1 / 2 ^ (1 / k)) ^ 1 / k) – Wolfram | Alpha) . Esto significa que el factor original (sin tener n reemplazado por 2) tendrá un límite 1 y un mínimo> 1/2.
Para ser completamente rigurosos necesitaríamos encontrar una fórmula A2 = A2 (n, k) que tendrá un límite constante inferior A2min y un límite superior constante A2max y para el cual tendremos [matemática] A2 (n * (1- \ frac {1} {n ^ \ frac {1} {k}}), k) * (1- \ frac {1} {n ^ \ frac {1} {k}}) ^ \ frac {1} {k } = A2 (n, k) [/ math], de modo que preservamos los factores constantes.
Al final [matemática] DERECHA (x)> n ^ \ frac {1} {k} * \ Omega (1) [/ matemática].
Además, [matemática] DERECHA (x) <A2 * n ^ \ frac {1} {k} * 1 [/ matemática] entonces [matemática] DERECHA <n ^ \ frac {1} {k} * O (1) [ /mates].
Por lo tanto, [matemática] DERECHA (x) = \ Theta (n ^ \ frac {1} {k}) [/ matemática].
Para ser completamente rigurosos necesitaríamos manejar el redondeo para nx yx y también verificar que tratamos los factores constantes para DERECHO correctamente.
El resultado final es, por lo tanto, 1 + MIN (Theta (n ^ (1 / k)), Theta (n ^ (1 / k)) = Theta (n ^ (1 / k)).
do)
Siempre preguntaremos por el nivel x = n * (1-1 / n ^ (1 / k)), redondeado al entero más cercano y obtendremos una respuesta ‘no-break’. Esto funciona ya que tenemos una fórmula cerrada para x, no un rango.
Entonces E [k, n] = 1 + E [k, x]. Como siempre agregamos solo 1 y el valor total es Theta (n ^ (1 / k)), la recurrencia tomará Theta (n ^ (1 / k)) para calcularla directamente.
