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))$