Final 2C/2012 (Algoritmos II)

Plantilla:Back Esteban Feuerstein y Fernando Schapachnik

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

Ejercicio 1

Se deben ordenar los parciales de 500 alumnos, en base a su apellido. Para facilitar la práctica, los m docentes deciden dividir la tarea entre ellos. Recomiende dos posibles métodos para que utilicen. Tenga en cuenta que:

• Debe ser realizado por personas
• Por más de una
• Se pretende además que sea eficiente (por ejemplo, tratando de que no haya gente sin hacer nada durante mucho tiempo)

Calcule la complejidad de los métodos propuestos.

Ejercicio 2

Se tiene un diccionario de idioma castellano representado en un TRIE. Se desea poder manejar palabras acentuadas, de manera tal que cuando se realiza una búsqueda se obtienen los resultados correspondientes a la versión con y sin acento. Por ejemplo se busca "está" y se obtiene "esta: pronombre..." "está: verbo estar, primera persona..." etc. Suponga que se cuenta con una función llamada normalizar() que dada una letra acentuada devuelve su equivalente sin acento.

a) ¿Qué modificaciones deberían realizarse en la estructura y en los algoritmos para poder contemplar dicha funcionalidad?

b) Este diccionario va a adaptarse para una variante del checo donde sonmuchos los caracteres que pueden acentuarse. Proponga una variación de la estructura que permita realizar la consulta mencionada en una sola pasada.

Ejercicio 3

Se tiene el siguiente TAD:

TAD PUNTO

generadores:

comenzar: → punto

subir: punto × nat → punto

derecha: punto × nat → punto

observadores:

X: punto → nat

Y: punto → nat

otras operaciones:

mover: punto × nat n × nat m → punto

axiomas:

X(comenzar) = 0

Y(comenzar) = 0

X(subir(p,n)) = X(p)

Y(subir(p,n)) = Y(p)+n

X(derecha(p,n)) = X(p)+n

Y(derecha(p,n)) = Y(p)

mover(p,n,m) = subir(derecha(p,n),m)

¿Se puede plantear la demostración por inducción estructural de una propiedad sobre el TAD punto utilizando en los teoremas a demostrar sólo comenzar(), mover(), X() e Y()? Justifique.

Ejercicio 4

Se diseña un conjunto C de tamaño no acotado sobre una estructura acotada A. Para cada una de las siguientes afirmaciones indique si deberían estar de alguna manera en el invariante de C sobre A, en la función de abstracción de A en C, en ambas o en ninguna. Justifique sus respuestas.

• Todos los elementos de C están en A
• Todos los elementos de A están en C
• En A no hay repeticiones
• En C no hay repeticiones
• C no tiene más elementos que los que entran en A
• Los elementos de C tienen que tener un orden (por si A es un AVL)
• Algunas de las características del invariante de A

Ejercicio 5

Especifique el TAD vela, que debe modelar la simulación discreta de una vela. Al comenzar se indica la longitud de la vela en centímetros, que corresponde a la parte cubierta de cera. El cabo mide al comienzo 10 mm. Una vez que se enciende, el cabo disminuye 1 mm por cada pulsación de un reloj. Cuando disminuye el trecho final del cabo (el último milímetro), se derrite instantáneamente 1 cm más de cera, descubriendo el cabo nuevamente.