Diferencia entre revisiones de «Recuperatorio Segundo Parcial 1C/2015 (Algoritmos II)»

De Cuba-Wiki
m (Agrega el template back)
(Termina posta de transcribir el ejercicio 1.)
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 necesarui 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.

Revisión del 19:25 18 sep 2017

Plantilla:Back

17 de julio de 2015

Aclaraciones

  • El parcial es a libro abierto
  • Entregar cada ejercicio en hojas separadas
  • Incluir en cada hoja el número de orden asignado, número de hoja, apellido y nombre.
  • Al entregar el parcial, completar el resto de las columnas en la planilla.
  • Cada ejercicio se calificará con MB, B, R o M, y podrá recuperarse independientemente de los demás. La cursada podrá aprobarse con hasta 1 (un) ejercicio R (regular) en cada parcial (post-recuperatorios), siempre y cuando ninguno de ellos sea un ejercicio 1. Para más detalles, ver "Información sobre la cursada" en el sitio Web.

Ejercicio 1: Diseño

Una importante empresa de software intenta insertarse en el mercado de los buscadores web. Para eso desean diseñar un motor de búsqueda, que inicialmente será muy rudimentario. En esta primera versión, el motor de búsqueda sólo podrá indexar documentos y realizar búsquedas por dos palabras clave.

Un documento no es más que una secuencia de palabras, y las palabras son cadenas de caracteres del alfabeto castellano (más los símbolos de puntuación usuales). En todo momento pueden indexarse nuevos documentos, que nunca de desindexan. Cada documento tiene, además, un nombre único que lo identifica que, eventualmente, podrá cambiarse. Los nombres de los documentos tienen una longitud no acotada. Lo mismo puede suceder con los documentos, que pueden tener cualquier cantidad de palabras, y estas palabras pueden ser de cualquier longitud.

Como en todo motor de búsqueda, el objetivo es encontrar documentos a partir de palabras clave. En esta versión sólo se podrán hacer búsquedas del tipo () que devolverán el conjunto de documentos que contienen ambas palabras (tanto como ).

Por ejemplo, un documento que consiste en la secuencia de palabras "¡Qué genio tiene el ingenuo de Eugenio!" será parte del conjunto de respuestas para las búsquedas (genio ingenuo) y (el Eugenio!). Por el contrario, este documento no estará en el conjunto de respuestas si la búsqueda es (Eugenio! ornitorrinco).

   TAD Documento ES Secu(Palabra)
   TAD Nombre ES String
   TAD Palabra ES String
   
   TAD Buscador
   
   generadores:
   iniciar: -> buscador
   indexarDocumento: buscador b X nombre n X secu(palabra) d -> buscador {n !E documentos(b)}
   cambiarNombre: buscador b X nombre n1 X nombre n2 -> buscador {n1 E documentos(b) ^ n2 !E documentos(b)}
   
   observadores básicos:
   documentos:buscador -> conj(nombre)
   texto: buscador b X nombre n -> secu(palabra) {n E documentos(b)}
   
   otras operaciones:
   buscar: buscador b X palabra p1 X palabra p2 -> conj(nombre)
   
   axiomas: ...
   
   Fin TAD


Diseñe el TAD Buscador respetando los siguientes requerimientos de complejidad temporal en el peor caso:

  • indexarDocumento(b, n, d)

  • buscar(b, p1, p2)

  • texto(b, n)

donde es la longitud de la palabra más larga en ; es la longitud del nombre del documento más largo en ; y es la cantidad de documentos indexados por 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 necesarui diseñar los módulos soporte, pero sí describirlos, justificando por qué pueden (y cómo logran) exportar los órdenes de complejidad que su diseño supone.