Reconocimiento de patrones

Principal > Docencia >Reconocimiento de patrones

 

 

CURSO 2008-2009

TRABAJOS de RECONOCIMIENTO DE PATRONES

Última actualización: Martes, 02-Dic-2008 11:01.

Trabajos finales.

  1. OBJETIVOS. Los objetivos de este trabajo, el más ambicioso del curso, son los siguientes:
    1. Ser capaz de resolver un problema casi “real”.
    2. Usar los algoritmos vistos en clase.
    3. Ser capaces de asimilar nuevos algoritmos.
    4. Ser capaces de leer bibliografía científica.
    5. Implementar algoritmos de reconocimiento de patrones.
    6. Tener en cuenta las complejidades a la hora de diseñar e implementar algoritmos.
    7. Redactar una memoria científica de manera correcta.
    8. Exponer vuestro trabajo en clase con eficacia comunicativa.
  2. LISTA DE LOS TRABAJOS:
    1. Àrboles de sufijos.
    2. Algoritmo de Boyer-Moore.
    3. Distancia de edición.
    4. Comparación de algoritmos.
    5. Buscador de documentos.
      Cada pareja, o si lo hace solo cada alumno, ha de elegir un trabajo entre los de la lista anterior.
  3. PARTES DEL TRABAJO:
    1. Lectura y comprensión de un artículo sobre RP.
    2. Implementación de los algoritmos.
    3. Prueba de los algoritmos.
    4. Resolución de un problema de RP.
    5. Redacción de la memoria.
    6. Exposición en clase del trabajo.
  4. MATERIAL DE LOS TRABAJOS.
    1. Cristina Martín: árboles de sufijos -1.
    2. Alfonso Roa: árboles de sufijos -2.
    3. Rocío Mañana y Carlos Vidal: distancia de permutación dirigida.
    4. Juan Almagro y Mónica González: distancia de transporte.
    5. Álvaro Valdiviejas: comparación de algoritmos.
Más información en la presentación del día 2 de diciembre.

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 (fmartin@eui.upm.es) 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.

 

Trabajo I: comparación de algoritmos de ordenación:

  1. IMPLEMENTACIÓN. Hay que implementar los siguientes algoritmos de ordenación:
    1. Quicksort, versión recursiva.
    2. Quicksort, versión iterativa.
    3. Quicksort, versión con la mediana (algoritmo de Floyd).
    4. Divide y vencerás, versión recursiva.
    5. Divide y vencerás, versión iterativa.
    6. Inserción (selección del máximo en cada paso).
    7. Recuento (counting sort).
  2. EXPERIMENTOS. Se han de diseñar de acuerdo a las siguientes instrucciones:
    1. Cada uno de los algoritmos ha de ejecutarse sobre un juego de n datos. Los valores de n son: 100, 200, ..., 10.000, esto es, aumentan de 100 en 100 hasta 10.000.
    2. El rango de valores para los datos es de de 1 a 10.000. Los datos se generarán aleatoriamente. Se permiten números repetidos.
    3. Para cada juego de datos, se ejecutarán los algoritmos anteriores y se guardarán los tiempos de ejecución. Con la pareja tamaño de entrada y tiempo de ordenación se generarán gráficas poligonales para comparar los tiempos de ejecución de cada uno; véase el ejemplo de más abajo.
    4. A partir de las gráficas, se estimarán las siguientes cantidades:
      1. El tamaño de entrada para el cual un algoritmo es más rápido que otro.
      2. Constantes que acompañan a las complejidades.

  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 y el ejecutable bien por correo electrónico (fmartin@eui.upm.es) 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 mejor y bajo qué circunstancias?
    2. ¿Es el algoritmo de recuento el mejor? Justifica la respuesta.
    3. Dar una clasificación de los algoritmos en términos de tiempo de acuerdo al tamaño de la entrada.
    4. Haciendo uso de la creatividad que se os supone, ofrecer vuestras propias conclusiones. Procurad que vayan acompañadas de razonamientos.
  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.
  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 7 de noviembre a las 23:59 horas.
  8. PREGUNTAS Y TUTORÍAS. Estoy dispuesto a responder preguntas sobre el algoritmo, su corrección, su complejidad y similares. No responderé preguntas sobre errores de codificación, pues pienso que, a estas alturas, es responsabilidad vuestra.