Edición de «Final 30/7/2015 (Algoritmos II)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{back|Algoritmos_y_Estructuras_de_Datos_II}}
'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik'''


'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik'''


== Ejercicio 1 ==
== Ejercicio 1 ==
El sistema de especificación TAD' es muy similar a los TADs que se utilizan en la materia, pero su única igualdad entre instancias se define así: dos instancias son iguales si y solo si aplicando axiomas se puede llegar de una a la otra.
Dado un sistemas de TADs TAD' que difiere de los tads comunes en que tiene solo axiomas y operaciones, y la igualdad se da por equivalencia de axiomas, es decir, se puede ir de t1 a tn aplicando los axiomas.
# Este sistema de especificación no tiene uno de los problemas formales más importantes que puede tener un TAD. ¿Cuál? ¿Por qué?
 
# ¿Qué dificultad presenta la especificación del TAD' conjunto en este formalismo?
* a) Qué problema grave de los TADs comunes evita esta especificación?
* b) Qué dificultad tiene escribir el tad conjunto con esta especificación?


== Ejercicio 2 ==
== Ejercicio 2 ==
Explíquele a un matemático por qué se puede aplicar el principio de inducción estructural sobre cualquier TAD.
Demostrar porque se puede hacer inducción sobre los TADS (explicale a un matemático).


== Ejercicio 3 ==
== Ejercicio 3 ==
Explique la relación entre invariante de representación y complejidad algorítmica, y entre función de abstracción y la demostración de que el diseño es correcto con respecto a la especificación.
Relación invariante de representación y complejidad algorítmica.
Relación función de abstracción con la demostración de que tu diseño es correcto.


== Ejercicio 4 ==
== Ejercicio 4 ==
Se desea implementar un TAD que permita representar un conjunto de números racionales, donde a las tradicionales operaciones de Agregar(S,x) y Borrar(S,x) se agrega la siguiente: CLOSERTOAVG(S), que toma como input un conjunto S y devuelve el valor contenido en S más cercano al promedio de los valores contenidos en S.
Era el de closerToAvg de otros parciales, conjunto de racionales, discutir 4 variantes sobre estructuras vistas en clase.
Discutir la implementación de este TAD utilizando variantes de al menos 4 estructuras de datos vistas en clase para representar conjuntos/diccionarios standard.


== Ejercicio 5 ==
== Ejercicio 5 ==
Se cuenta con n elementos que contienen una clave primaria y una secundaria. Hay m<<n claves secundarias distintas. Proponga dos formas eficientes y distintas que permitan ordenar los n elementos, en base a las dos claves (primero la primaria, luego la secundaria).
Dados N elementos, cada uno con clave primaria y secundaria, m << n, m ‪#‎claves‬ secundarias. Dar 2 formas eficientes de ordenarlos. (Primero por primarias, luego por secundarias.)
 
[[Categoría: Finales]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Final_30/7/2015_(Algoritmos_II)»