Final 10/3/2011 (Algoritmos II)

test

Si habías aprobado la parte práctica y los TPs, tenías que hacer solo los ejercicios 1 a 5. Los ejercicios 6 y 7 eran para la gente que rendía "final libre" (o sea, que habían aprobado los TPs pero desaprobado un parcial).

Ejercicio 1

Una fábrica de pinturas funciona de la siguiente manera: distintos colores de pintura se van produciendo de a tandas de 10kg. Cuando se inaugura la fábrica, se producen 100 kg de cada color, y cuando el stock disponible de un cierto color pasa a ser menos de 30 kg, una nueva tanda de ese color se prepara. A su vez, al iniciar la semana, se tira toda la pintura que lleva más de 4 semanas sin ser vendida. Interesa saber cuánto se lleva producido y vendido de cada color y cuál es el color más vendido.

• Encontrar los errores en la especificación e indicar cómo corregirlos.
• Describir a grandes rasgos cómo diseñaría este TAD y como implementaría cada una de las operaciones.

TAD fábrica_de_pinturas

generadores:
	crear: conj(color) x semana -> fábrica_de_pinturas
	iniciar_semana: fábrica_de_pinturas f x semana s -> fábrica_de_pinturas			(s > ultima_semana(f))
	vender_pintura: fábrica_de_pinturas f x color g x nat n -> fábrica_de_pinturas

observadores:
	ultima_semana: fábrica_de_pinturas -> semana
	colores: fábrica_de_pinturas -> conj(color)
	stock: fábrica_de_pinturas f x color g -> nat		(g pertenece colores(f))
	ultima_semana_prod: fábrica_de_pinturasf x color g -> semana
	ante_ultima_semana_prod: fábrica_de_pinturas f x color g -> semana
	vendido: fábrica_de_pinturas f x color g -> nat 	(g pertenece colores(f))
	más_vendido: fábrica_de_pinturas -> color

axiomas:
	ultima_semana(crear(c,s)) = s
	ultima_semana(iniciar_semana(f,s)) = s
	ultima_semana(vender_pintura(f,g,n)) = ultima_semana(h)

	colores(crear(c,s)) = c

	stock(crear(c,s),g) = 10.000
	stock(abrir_semana(h,s),g) = if s - ultima_semana_prod(h,g) > 4 then 10.000
					else if s - ante_ultima_semana_prod(h,g) > 4 then 10.000
					else stock(h,g) end if
	stock(vender_pintura(h,g,n),g) = if stock(h,g) - n < 3.000 then 10.000 + producido(h,g) - n
					else producido(h,g) end if

FIN
TAD semana es Nat
TAD color es Nat

Ejercicio 2

Responda verdadero o falso justificando

• Lo que hace que una operación sea observador básico es que deba escribirse en base a los generadores.
• Si una operación rompe la congruencia debe ser transformada en observador básico
• Dos instancias del mismo TAD pueden ser observacionalmente iguales y aún así ser distingibles por una operación.
• Si un enunciado dice "siempre que sucede A sucede inmeditamente B y B no puede suceder de ninguna otra manera" y la correspondiente axiomatización incluye las operaciones A y B entonces el TAD está mal escrito

Ejercicio 3

Suponer que tenemos un arreglo bidimensional A de m filas y n columnas. Suponemis que cada fila está ordenada en forma creciente. Describir un algoritmo que junta todos los elementos de A en un array de nm elementos en tiempo total $O(n*m*logm)$. (Sugerencia: ustilizar un heap como estructura auxiliar).

Ejercicio 4

Considerar un TAD Conjunto con las operaciones adicionales MINIMO(C) que dado un conjunto devuelve como resultado el elemento de mínima clave de C y SUC(x,C) que dado un elemento x perteneciente a C devuevle el sucesor inmediato de x en C si es que existe o un valor especial si no existe. Discutir la implementación de ambas operaciones en los casos en que el TAD se implemente con ABB, AVL, Árboles B y Hashing abierto. Incluir análisis de complejidad de ambas operaciones en cada caso.

Ejercicio 5

• ¿Cuántos caracteres DISTINTOS tiene que tener un texto como mínimo para que alguno de ellos reciba un código de longitud k en una codificación de Huffman (con k>1)? Jusificar.
• ¿Cuántos caracteres en total tiene que tener un texto como mínimo para que algún caracter reciba un código de longitud k en una codificación de Huffman (con k>1)? Justificar
• Responder a) y b) para códogs de longitud fija. Justificar.

Ejercicio 6

Demostrar las siguientes propiedades, donde f y g son funciones de N en R+.

• $f$ pertenece $O(g)$ sii $O(f)$ incluido $O(g)$
• $f(n)=\theta (g(n))$ implica $g(n)=\theta (f(n))$
• $max(f(n),g(n))=\theta (f(n)+g(n))$

Ejercicio 7

El diseño de un módulo requiere la utilización de un conjunto y un diccionaro con complejidad a lo sumo logarítmica para todas sus operaciones. ¿Alguna de las siguientes alternativas de diseño le parece más apropiada que las demás? Justifique. Si no, proponga una usted, justificando.

• conjunto sobre diccionario sobre AVL.
• conjunto sobre AVL, diccionario sobre AVL, AVL sobre punteros.
• AVL sobre ABB sobre AB sobre punteros, conjunto sobre AVL, diccionario sobre AVL
• Conjunto sobre AVL, diccionario sobre tabla de hashing abierta con conjuntos en las celdas