Edición de «Algoritmos y Estructuras de Datos»
De Cuba-Wiki
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 97: | Línea 97: | ||
* ACM Vol. 32.3 (Julio de 1985), pags. 652--686. link: [https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf]. Es el paper que desarrolla los Splay Trees. | * ACM Vol. 32.3 (Julio de 1985), pags. 652--686. link: [https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf]. Es el paper que desarrolla los Splay Trees. | ||
* Ronald Fagin et al. ''Extendible Hashing—a Fast Access Method for Dynamic Files''. ACM Transactions on Database Systems 4.3 (sep. de 1979), págs. 315-344. issn: 0362-5915. doi:10.1145/320083.320092. Es el paper que desarrolla el método de Hashing Extensible (o Hashing Dinámico). | * Ronald Fagin et al. ''Extendible Hashing—a Fast Access Method for Dynamic Files''. ACM Transactions on Database Systems 4.3 (sep. de 1979), págs. 315-344. issn: 0362-5915. doi:10.1145/320083.320092. Es el paper que desarrolla el método de Hashing Extensible (o Hashing Dinámico). | ||
1) Verdadero o falso. justifique | |||
a) una operacion es observador basico porque se define mediante generadores. | |||
b) si una operacion rompe la congruencia debe transformarse en observador basico. | |||
c) una instancia de un tad puede no ser distinguible por la igualdad observacional y | |||
que una operacion las diferencie. | |||
d) si siempre que ocurre A ocurre B y B no puede ocurrir de otra manera, | |||
si aparece en la axiomatizacion A y B entonces la especificacion esta mal hecha. | |||
2) Suponga que tiene una implementacion de un diccionario D representado en una estructura E. | |||
Se quiere demostrar una propiedad P sobre el diccionario D. | |||
Tambien suponga que para todo elemento de la estructura E se cumple que: | |||
R(e) => Q(e) | |||
a) que mas necesitamos para poder demostrar la propiedad P sobre D? justifique | |||
b) se puede usar induccion estructural para demostrar los lemas del punto a? justifique | |||
3) para cada algoritmo de sorting que aparece abajo se pide: | |||
- complejidad temporal caso peor | |||
- complejidad temporal caso promedio | |||
- si se requiere memoria adicional | |||
- si es estable | |||
para cada item justifique en no mas de 3 o 4 renglones.si no sabe ponga ? y justifique | |||
4) Se cuenta con una implementacion de diccionario y se quiere hacer la operacion lista-ordenados | |||
que pone todos los elementos en orden creciente(ponele que devuelve una secuencia). | |||
hacer el algoritmo informalmente y indicar su complejidad sobre las tipicas implementaciones | |||
de diccionarios: AVL, arboles B, hashing, trie. | |||
5) escribir el codigo de huffman con las siguientes frecuencias: | |||
a 45%, b 12%, c 13%, d 16 %, e 9 %, f 11 % (o algo asi) | |||
comparar la longitud con la del codigo de longitud fija | |||
bueno algo asi era el final. | |||
== Enlaces externos == | == Enlaces externos == |