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

De Cuba-Wiki
(Transcribo las aclaraciones)
 
(Transcribo ejercicio 1)
Línea 8: Línea 8:
*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.
*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 == --!>
== 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 (<math>palabra_1 \land palabra_2</math>) que devolverán el conjunto de documentos que contienen <b>ambas</b> palabras (tanto <math>palabra_1</math> como <math>palabra_2</math>).
 
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 <math>\land</math> ingenuo) y (el <math>\land</math> Eugenio!). Por el contrario, este documento no estará en el conjunto de respuestas si la búsqueda es (Eugenio! <math>\land</math> 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 <b>peor caso</b>:
 
*indexarDocumento(b, n, d)
<math>O(long(n) + long(d) * max_p(d) * docs(b) * max_n(b))</math>
*buscar(b, p1, p2)
<math>O(long(p_1) + long(p_2) + max_n(b) * docs(b))</math>
*texto(b, n)
<math>O(long(n))</math>

Revisión del 05:44 18 sep 2017

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)