Diferencia entre revisiones de «Final 1C/2013 (Algoritmos II)»
Sin resumen de edición |
|||
| Línea 31: | Línea 31: | ||
''Generadores'': | ''Generadores'': | ||
nuevo_tacho : nat tamaño | nuevo_tacho : nat tamaño → tacho | ||
''Observadores'': | ''Observadores'': | ||
cant_hielo : tacho | cant_hielo : tacho → nat | ||
cant_agua : tacho | cant_agua : tacho → nat | ||
''Otras operaciones'': | ''Otras operaciones'': | ||
aportar_calorias : tacho | aportar_calorias : tacho × nat → tacho | ||
disminuir_hielo : tacho | disminuir_hielo : tacho × nat → tacho | ||
aumentar_agua : tacho | aumentar_agua : tacho × 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. | 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. | ||
| Línea 53: | Línea 53: | ||
''Observadores'': | ''Observadores'': | ||
posicion : pelotita | posicion : pelotita → nat | ||
''Operaciones'': | ''Operaciones'': | ||
empujar : pelotita | empujar : pelotita × nat i × distancia d → pelotita {d=2i} | ||
(...) | (...) | ||
| Línea 65: | Línea 65: | ||
(...) | (...) | ||
top : pila | top : pila → <elem,bool> | ||
(...) | (...) | ||
| Línea 73: | Línea 73: | ||
(...) | (...) | ||
top : pila | top : pila → indicador | ||
hay_elem? : indicador | hay_elem? : indicador → bool | ||
elemento : indicador i | elemento : indicador i → elem {hay_elem?(i)} | ||
(...) | (...) | ||
Revisión actual - 19:41 30 jul 2014
Plantilla:Back 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[editar]
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[editar]
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[editar]
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[editar]
¿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[editar]
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 × nat → tacho
disminuir_hielo : tacho × nat → tacho
aumentar_agua : tacho × 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 × nat i × 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)}
(...)
