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 50: |
Línea 50: |
| *texto(b, n) | | *texto(b, n) |
| <math>O(long(n))</math> | | <math>O(long(n))</math> |
|
| |
| donde <math>max_p(d)</math> es la longitud de la palabra más larga en <math>d</math>; <math>max_n(b)</math> es la longitud del nombre del documento más largo en <math>b</math>; y <math>docs(b)</math> es la cantidad de documentos indexados por <math>b</math> hasta el momento.
| |
|
| |
| a) Muestre la estructura de representación propuesta. Explique para qué sirve cada parte de la estructura, o utilice nombres autoexplicativos.
| |
|
| |
| b) Escriba el pseudocódigo del arlgoritmo buscar(in b: estr, in p1 : palabra, in p2 : palabra).
| |
|
| |
| Justifique claramente cómo y por qué los algoritmos, la estructura y los tipos soporte permiten satisfacer los requerimientos pedidos. No es necesario diseñar los módulos soporte, <b>pero sí describirlos, justificando por qué pueden (y cómo logran)</b> exportar los órdenes de complejidad que su diseño supone.
| |
|
| |
| == Ejercicio 2: Ordenamiento ==
| |
| a) FIGFA (Federación Intergaláctica de Fútbol Asociado) maneja la información de miles de millones de equipos que participan en los distintos torneos de fútbol de todo el universo. Para cada equipo se calcula un puntaje que sirve para elaborar el ránking universal de equipos, que puede consultarse en su página web. FIGFA es muy desorganizada y no tiene optimizada esta información, es decir que arma el ránking desde cero cada vez que alguien lo consulta. Por otra parte, los registros históricos de la página web muestran que, en prácticamente todos los casos, a los visitantes sólo les interesa conocer los primeros 100 equipos del ránking. Sugoera a FIGFA dos algoritmos de sorting que considere apropiados para la generación del ránking, y uno que considere inapropiado. Justifique por qué en cada caso.
| |
|
| |
| b1) La Real Academia Española mantiene un compendio completo del vocabulario español. Este compendio es simplemente la lista ordenada de todas las palabras del lenguaje. Al fina de cada año se enriquece el lenguaje con varias palabras nuevas. Esto se hace agregando al compendio del año anterior un conjunto desordenado de nuevas palabras. Obviamente, para obtener el nuevo compendio anual es necesario reordenarlo. Se estima que cada año se agrega una cantidad de palabras equivalente al 5% del tamaño completo del compendio del año anterior. Sugiera qué estrategias de ordenamiento son más apropiadas en esta situación. Justifique.
| |
|
| |
| b2) El hecho de que se agregue un 5% de palabras nuevas, ¿Es relevante? ¿Cambiaría su respuesta (y cómo) su cada año se agregase un 50% de palabras nuevas? ¿Y si fuese un 100%, es decir se duplicara el vocabulario cada año?
| |
|
| |
| == Ejercicio 3: Dividir y conquistar ==
| |
|
| |
| Dado un árbol binario de números enteros, se desea calcular la máxima suma de los nodos pertenecientes a un camino entre dos nodos cualesquiera del árbol. Un camino entre dos nodos <math>n_1</math> y <math>n_2</math> está formado por todos los nodos que hay que atravesar en el árbol para llegar desde <math>n_1</math> hasta <math>n_2</math>, incluyéndolos a ambos. Un camino entre un nodo y sí mismo está formado únicamente por ese nodo. El algoritmo debe recorrer <b>como máximo una vez</b> cada nodo del árbol, que no necesariamente es completo. Se considerará incorrecto a un algoritmo que no cumpla con esta condición.
| |
|
| |
| [[File:Grafo_de_ejemplo_Ej3_Recu_2p_1C_2015_AyED2.jpg|600px]]
| |
| <!-- Acá había un ejemplo de máxima suma, pero es una imagen, así que no la transcribí -->
| |
|
| |
| Se pide dar un algoritmo MáximaSumaCamino(a: ab(int)) -> int que resuelva el problema utilizando la técnica de Dividir y Conquistar, calculando y justificando claramente su complejidad. El algoritmo debe tener una complejidad temporal de peor caso igual o mejor que <math>O(n)</math> siendo <math>n</math> la cantidad de nodos del árbol.
| |
|
| |
| [[Categoría: Parciales]]
| |
| [[Categoría: Segundos Parciales]]
| |
