Apéndice B. Solución del parcial 1 · Estructuras de Datos¶
Las dos preguntas abiertas del parcial del 25 de septiembre, con la solución completa y el puntaje de cada parte. Son las mismas en las versiones A, B y C.
La parte de opción múltiple vale 60 de los 100 puntos y estas dos, 20 cada una.
16. Cota con testigos — 20 puntos¶
El programa del enunciado:
int mezcla(int n) {
int t = 0;
int i = 0;
int j = 0;
while (i < n) {
t = t + 1;
i = i + 1;
}
i = 0;
while (i < n) {
j = 0;
while (j < i) {
t = t + 1;
j = j + 1;
}
i = i + 1;
}
return t;
}
\(T(n)\) es el número de veces que se ejecuta t = t + 1, para \(n \geq 1\).
i. \(T(n)\) como suma de las dos partes — 6 puntos¶
El primer ciclo recorre \(i\) desde 0 hasta \(n-1\) y ejecuta t = t + 1 una vez
por vuelta. El segundo lo hace una vez por cada vuelta del ciclo interno, que
para un \(i\) fijo recorre \(j\) desde 0 hasta \(i-1\).
El primer sumando es el ciclo simple y el segundo, el anidado.
ii. La expresión cerrada — 4 puntos¶
La primera sumatoria suma \(n\) veces el 1, de donde \(\sum_{i=0}^{n-1} 1 = n\). En la segunda, la sumatoria interna vale \(i\) porque suma \(i\) veces el 1, así que queda \(\sum_{i=0}^{n-1} i\), y esa es la suma de los primeros \(n-1\) naturales:
Reemplazando y sacando denominador común:
iii. \(T(n) \in O(n^2)\) — 10 puntos¶
Teorema. \(T(n) = \dfrac{n^2+n}{2} \in O(n^2)\).
Demostración. Se procede de forma directa: se acota el sumando de primer grado por uno de segundo grado y se exhiben los testigos.
Desarrollo. La definición exige encontrar \(c > 0\) y \(k \geq 0\) tales que \(T(n) \leq c\,n^2\) para todo \(n \geq k\). Se separan los dos sumandos:
Sea \(n \geq 1\). Multiplicando los dos lados de \(n \geq 1\) por \(n\), que es positivo y por lo tanto no invierte la desigualdad, se obtiene \(n^2 \geq n\). Dividiendo entre 2, que también es positivo:
Esa desigualdad acota el segundo sumando. Reemplazándola en la suma:
Conclusión. Para todo \(n \geq 1\) se cumple \(T(n) \leq 1 \cdot n^2\). Por lo tanto, se puede concluir que \(T(n) \in O(n^2)\) con testigos \(c = 1\) y \(k = 1\).
Cualquier pareja con \(c \geq 1\) y \(k \geq 1\) sostiene la demostración, siempre que el desarrollo justifique la desigualdad que la produce.
17. Una función contra el contrato de Cola — 20 puntos¶
Escribir Elemento maximo(Cola &c), que devuelve el mayor elemento de la cola
y la deja exactamente como estaba, usando solo encolar, desencolar,
frente, tamano y vacia.
i. La precondición — 3 puntos¶
Una cola vacía no tiene mayor elemento, y además frente() exige que haya al
menos uno. La precondición va escrita antes de la función:
// exige !c.vacia()
ii. La función — 10 puntos¶
// exige !c.vacia()
Elemento maximo(Cola &c) {
int n = c.tamano();
Elemento mayor = c.frente();
int i = 0;
while (i < n) {
Elemento actual = c.frente();
if (actual > mayor) {
mayor = actual;
}
c.desencolar();
c.encolar(actual);
i = i + 1;
}
return mayor;
}
Cada vuelta saca el frente y lo vuelve a encolar al final, de modo que la cola
rota un lugar. Después de \(n\) vueltas todos los elementos pasaron por el frente
exactamente una vez y volvieron en el mismo orden relativo: la cola queda como
estaba. La variable mayor arranca en el frente, que existe por la
precondición, y se actualiza cada vez que aparece uno más grande.
Sobre \(\langle 4, 9, 2, 7 \rangle\) devuelve 9 y la cola queda en \(\langle 4, 9, 2, 7 \rangle\).
iii. Por qué el ciclo se controla con el tamaño — 4 puntos¶
Cada vuelta desencola uno y encola uno, así que c.tamano() vale \(n\) al
empezar, al terminar y en todo momento intermedio. El tamaño nunca cambia.
Con while (!c.vacia()) la condición sería cierta siempre y el ciclo no
terminaría: la cola nunca se vacía porque lo que sale vuelve a entrar. Leer \(n\)
antes de empezar fija cuántas rotaciones hacen falta para devolver la cola a su
estado original, que es exactamente \(n\).
iv. Costo — 3 puntos¶
El ciclo da \(n\) vueltas y cada una hace una cantidad fija de operaciones del
contrato. Si encolar, desencolar y frente cuestan \(\Theta(1)\) —como en la
cola sobre arreglo circular y en la enlazada con puntero al último— entonces:
| Tiempo | \(\Theta(n)\) |
| Espacio aparte de la cola | \(\Theta(1)\): n, mayor, actual e i |
No se usa ninguna cola auxiliar: la propia rotación es lo que preserva el contenido. Sobre una implementación donde las operaciones del contrato costaran \(\Theta(n)\), la misma función quedaría en \(\Theta(n^2)\).
Código¶
- mezcla.c — el programa de la pregunta 16 contra la expresión cerrada, para \(n = 1\) a \(10\) y para \(n = 100\).
- maximo.cpp — la función de la 17, con los casos de un solo elemento y de elementos repetidos.
- cola_nodos.h — la cola enlazada sobre la que corre, la misma de El TAD Cola por dentro.
Se compilan con gcc -Wall -Wextra y g++ -Wall -Wextra.