Trabajo Práctico Final

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

Lineamientos básicos

  • El trabajo se realizará en grupos de cuatro o 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: Turnos en la fábrica

En la fábrica de Televisores “T.V. O’bien” se organizaron turnos de trabajo de 8 horas para los empleados que repiten día a día. Los horarios de entrada pactados con el sindicato son: 00:00 , 04:00 , 08:00 , 12:00 , 16:00 y 20:00. Asimismo existen franjas horarias donde se requieren un mínimo de operatorios presentes en la planta. Los requerimientos son:

0 a 4		15
4 a 8		35
8 a 12		65
12 a 16 	80
16 a 20		40
20 a 0		25

Se pide:

  1. Expresar y explicar el problema como un problema de programación lineal.

  2. Determinar si el problema se puede resolver en tiempo polinomial. Justificar.

  3. Explicar como resolver el problema utilizando Simplex. Brindar pseudocódigo y explicación de su propuesta. Expresar como se representa la solución.

  4. Analizar la complejidad temporal y espacial de cada uno de los pasos de su solución.

  5. Presente paso a paso la solución del problema.

  6. Programe su propuesta. Puede utilizar librerías para Simplex. (Ejemplos: ALGLIB o PulP)

Parte 2: Profundización iterativa

Les solicitamos investigar los algoritmos “iterative deepening depth-first search” y “iterative Deepening A*”.

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 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 (tiene al menos 2 “a” y al menos 3 “b”) y (tiene un número impar de “b”) } 
lenguaje "b": {w| w (tiene un número par de “a”) y (termina con 2 “b”)}

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.