Diferencia entre revisiones de «Final 1C/2013 (Algoritmos II)»

De Cuba-Wiki
(Página nueva con el final de Algo II recién salido del horno. Y por horno claramente me refiero al aula 8.)
 
 
(No se muestran 2 ediciones intermedias de otro usuario)
Línea 3: Línea 3:


Tomaron el mismo las dos fechas, exactamente.
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.
Para considerarse aprobado deben estar bien al menos 3 ejercicios.
Línea 29: Línea 31:
''Generadores'':
''Generadores'':


nuevo_tacho : nat tamaño -> tacho
nuevo_tacho : nat tamaño tacho


''Observadores'':
''Observadores'':


cant_hielo : tacho -> nat
cant_hielo : tacho nat


cant_agua : tacho -> nat
cant_agua : tacho nat


''Otras operaciones'':
''Otras operaciones'':


aportar_calorias : tacho x nat -> tacho
aportar_calorias : tacho × nat tacho


disminuir_hielo : tacho x nat -> tacho
disminuir_hielo : tacho × nat tacho


aumentar_agua : tacho x 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.
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 51: Línea 53:
''Observadores'':
''Observadores'':


posicion : pelotita -> nat
posicion : pelotita nat


''Operaciones'':
''Operaciones'':


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


(...)
(...)
Línea 63: Línea 65:
(...)
(...)


top : pila -> <elem,bool>
top : pila <elem,bool>


(...)
(...)
Línea 71: Línea 73:
(...)
(...)


top : pila -> indicador
top : pila indicador


hay_elem? : indicador -> bool
hay_elem? : indicador bool


elemento : indicador i -> elem {hay_elem?(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

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 × 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)}

(...)