Trabajo Práctico Final

Teoría de Algoritmos 1 - 1c 2024 Trabajo Práctico Final

Lineamientos básicos

  • El trabajo se realizará en grupos de cinco personas.

  • Se debe entregar el informe en formato pdf en el aula virtual de la materia.

  • El informe debe presentar carátula con el nombre del grupo, datos de los integrantes y fecha de entrega. Debe incluir número de hoja en cada página. No debe superar las 30 páginas + carátula + índice + referencias.

  • Al ser un trabajo de investigación debe OBLIGATORIAMENTE incluir las fuentes utilizadas. Utilizar el formato APA.

  • En caso de re-entrega, entregar un apartado donde se explicitan las correcciones realizadas.

Parte 1: Beam Search algorithm

Les solicitamos investigar el algoritmo conocido como Beam Search.

Se pide:

  1. Indicar que tipo de algoritmo es y para que se puede utilizar

  2. Brindar pseudocódigo y explicación de cómo funciona.

  3. Según los conceptos trabajados en clase, a que tipo de algoritmo corresponde? Justificar

  4. Realizar análisis de su ejecución (Tener en cuenta su complejidad y optimalidad).

  5. Realizar un ejemplo paso a paso de su utilización.

  6. Brindar un enunciado de un problema que se puede resolver con este algoritmo.

Parte 2: Una variante del problema Minimum spanning trees

Les solicitamos investigar el problema de “Minimum degree spanning trees” (optimización) o “Degree constrained minimum spanning trees” (decisión)

Se pide:

  1. Definir el problema

  2. Demostrar que corresponde a un problema NP-H en su versión de optimización y NP-C en su versión de decisión.

  3. Investigar al menos dos algoritmos de aproximación/heurísticos/randomizados que solucionen el problema. Explicar y brindar pseudocódigo.

  4. Realizar análisis de su ejecución (Tener en cuenta su complejidad y optimalidad).

  5. Realizar un ejemplo paso a paso de su utilización.

Parte 3: Autómatas finitos

Los siguientes lenguajes corresponden a la intersección de dos lenguajes más simples (los símbolos de los mismos corresponden a los números 0 y 1) :

lenguaje "a": {w| w comienza con “00” y tiene como mucho un “1”} 
lenguaje "b": {w| w tiene un número par de “0” y uno o dos “1”}

Se pide:

  1. Construir un autómata finito determinista (AFD) de forma formal para cada uno de los lenguajes simples.

  2. Basándose en los autómatas construidos generar de forma formal los dos autómatas finitos determinísticos de los lenguajes más complejos.

  3. Representar cada uno de los AFD mediante su representación gráfica

  4. Para cada AFD Brindar un ejemplo de una cadena que acepta y otra que rechaza. Explicarlos paso a paso.