Trabajo II: algoritmo de Karp-Rabin, algoritmo Z y algoritmo de

autómatas finitos.

  1. DESCRIPCIÓN. En este trabajo deberéis implementar los siguientes algoritmos:
    1. Algoritmo de Karp-Rabin.
    2. Algoritmo Z.
    3. Algoritmo de autómatas finitos.
  2. EXPERIMENTOS. Cada uno de los algoritmos anteriores tendrá que ejecutarse sobre los ficheros que aparecen más abajo. Por ejemplo, el fichero Patron1.txt contiene un patrón que hay que buscar en el fichero Texto1.txt, y así sucesivamente.
    PATRÓN
    Comodín
    TEXTO Alfabeto
    Patron1.txt No Texto1.txt Binario
    Patron2.txt Sí, car.=X Texto2.txt Binario
    Patron3.txt No Texto3.txt Binario
    Patron4.txt No Texto4.txt Ascii
    Patron5.txt Sí, car.=ASCII(128) Texto5.txt Ascii
    Patron6.txt No Texto6.txt Dna
    Patron7.txt Sí, car.="0" Texto7.txt Dna
    • Un fichero zip con todos los ficheros anteriores se encuentra aquí. Los patrones pueden contener un carácter comodín; véase el problema 34.1-5 de la página 857 del libro de Cormen. En los casos en que aparezca el carácter comodín hay que resolver el problema de reconocimiento de patrones con comodín.
    • La salida de los programas ha de contener la respuesta a las preguntas:
      1. ¿Está el patrón P en el texto T?;
      2. ¿Cuántas veces está el patrón en el texto?
      3. Para cada algoritmo se reflejarán sus características relevantes. Por ejemplo, para el algoritmo de Rabin-Karp, se contará el número de falsos positivos.
    • Se tomarán los tiempos de ejecución de los algoritmos. Para el algoritmo Z y los autómatas finitos se medirán los tiempos de preprocesamiento y aparte se medirán los tiempos de búsqueda del patrón en el texto.
  3. LENGUAJE. La implementación se puede realizar en el lenguaje que se prefiera (C, Pascal, Maple, C++, etc.). Hay que entregar el código, el ejecutable y la memoria bien por correo electrónico (Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.) o en persona (despacho 2004).
  4. MEMORIA. Se redactará una memoria en que se explicarán brevemente las implementaciones de los algoritmos, la realización práctica del experimento y, finalmente, se interpretarán los datos del experimento y se obtendrán conclusiones. Se responderán, al menos, a las siguientes preguntas:
    1. ¿Qué algoritmo es más fácil de implementar? Da razones.
    2. ¿Qué algoritmos son mejores y en qué condiciones? Razona la respuesta.
    3. Da una lista de las dificultades técnicas con que te has encontrado al programar los algoritmos.
    4. Describe la estrategia de prueba de los programas.
  5. PUNTUACIÓN. Descontaré puntos si la memoria:
    1. Tiene faltas de ortografía.
    2. Está plagada de material irrelevante.
    3. Falta claridad de pensamiento.
    4. Es más larga de lo necesario o es más corta de lo necesario.
    5. Hace afirmaciones irreflexivas.
  6. ERRORES DE CÓDIGO. Descontaré puntos si el código:
    1. No está comentado debidamente.
    2. No está estructurado claramente.
    3. Las variables tienen nombres absurdos.
    4. Tiene errores de ejecución.
    5. La interfaz es infame.
  7. FECHA LÍMITE. La fecha límite es el 2 de diciembre a las 23:59 horas.
  8. PREGUNTAS Y TUTORÍAS. Estoy dispuesto a responder preguntas sobre los algoritmos y sus posibles estrategias de codificación. No responderé preguntas sobre errores de codificación; tal cosa, a estas alturas, es responsabilidad vuestra.
Go to top