Recuperatorio Segundo Parcial 1C/2015 (Algoritmos II)

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 ($palabra_{1}\land palabra_{2}$) que devolverán el conjunto de documentos que contienen ambas palabras (tanto $palabra_{1}$ como $palabra_{2}$).

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 $\land$ ingenuo) y (el $\land$ Eugenio!). Por el contrario, este documento no estará en el conjunto de respuestas si la búsqueda es (Eugenio! $\land$ 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)

$O(long(n)+long(d)*max_{p}(d)*docs(b)*max_{n}(b))$

• buscar(b, p1, p2)

$O(long(p_{1})+long(p_{2})+max_{n}(b)*docs(b))$

• texto(b, n)

$O(long(n))$

donde $max_{p}(d)$ es la longitud de la palabra más larga en $d$; $max_{n}(b)$ es la longitud del nombre del documento más largo en $b$; y $docs(b)$ es la cantidad de documentos indexados por $b$ 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.