Edición de «Final 1C/2013 (Algoritmos II)»

{{Back|Algoritmos y Estructuras de Datos II}}
'''Esteban Feuerstein y Fernando Schapachnik'''

Tomaron el mismo las dos fechas, exactamente.

Está redactado bien cabeza. Se aprecia si alguien se lo acuerda mejor y está menos quemado y lo alinda.

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

== Ejercicio 1 ==
Te pedía básicamente plantear el esquema de inducción estructural para un TAD genérico, y justificar que se puede usar inducción en los TADs.

== Ejercicio 2 ==
En un AVL:

a) Hacer el dibujo de una rotación simple y una doble.

b) Explicar para qué sirven las rotaciones en las operaciones de inserción y borrado, y en qué contexto se usan.

== Ejercicio 3 ==
En un problema de ''Divide & Conquer'', ¿cómo se relaciona el problema inicial que estás tratando de resolver con la ecuación de la recurrencia? (no hacía falta explicar cómo se resuelve la recurrencia también).

== Ejercicio 4 ==
¿Por qué está bueno tener una invariante de representación? ¿Para qué cosas sirve? Tirá aspectos en los que esté bueno tenerla, y ejemplificá.

== Ejercicio 5 ==
Tiraban 4 pedazos de TAD y pedían encontrar/arreglar errores:

a) Se tiene un tacho con hielo, en un sistema aislado. Lo único que pasa es que el tacho se calienta una cierta cantidad de calorías, y algo del hielo se convierte en agua.

''Generadores'':

nuevo_tacho : nat tamaño -> tacho

''Observadores'':

cant_hielo : tacho -> nat

cant_agua : tacho -> nat

''Otras operaciones'':

aportar_calorias : tacho x nat -> tacho

disminuir_hielo : tacho x nat -> tacho

aumentar_agua : tacho x nat -> tacho

b) Se tiene una pelotita a la que se le puede pegar, con una fuerza de cierta cantidad de kilos. Por cada kilo con el que se le pega, la pelotita se mueve 2 metros.

(...)

''Observadores'':

posicion : pelotita -> nat

''Operaciones'':

empujar : pelotita x nat i x distancia d -> pelotita {d=2i}

(...)

c) Se tiene una pila de elem, que tiene que permitir la operación ''top()'', pero debe avisar cuando la pila está vacía.

(...)

top : pila -> <elem,bool>

(...)

d) Idem al anterior:

(...)

top : pila -> indicador

hay_elem? : indicador -> bool

elemento : indicador i -> elem {hay_elem?(i)}

(...)