Diferencia entre revisiones de «Final 10/3/2011 (Algoritmos II)»
Sin resumen de edición |
(Se ha deshecho la revisión 13913 de 200.127.76.114 (disc.)) Etiqueta: Deshacer |
||
Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos II}} | {{Back|Algoritmos y Estructuras de Datos II}} | ||
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). | 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). |
Revisión actual - 21:20 26 ago 2021
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 . (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+.
- pertenece sii incluido
- implica
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