Trabajo Práctico Final

Teoría de Algoritmos 1 - 2c 2023 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.

  • Los videos generados deben incluir como primer parte un título del vídeo, el nombre de los integrantes que lo elaboraron, la fecha de elaboración, que corresponde a un trabajo práctico final y los datos de la materia.

  • Los videos entregados deben subirse a una cuenta de youtube y quedar en modo oculto (posterior a la aprobación el grupo puede optar por ponerlo público). Debe incluir en el informe los links a los videos. Además indicar con que programas lo realizó

  • 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.

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

Parte 1: Skip-lists

Les solicitamos investigar la estructura de datos Skip List propuesta por William Pugh.

Se pide:

  1. Indicar que tipo de estructura 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 cada una de sus operaciones (Tener en cuenta su complejidad y optimalidad).

  5. Realizar un ejemplo paso a paso de su utilización que contemple cada una de sus operaciones

  6. Realizar uno o varios videos (cada uno no debe superar los 15 minutos) pensados para explicar a otros estudiantes esta estructura.

Parte 2: Algoritmo de Christofides

Les solicitamos investigar el algoritmo de Christofides propuesta por Nicos Christofides

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. Realizar uno o dos videos (cada uno no debe superar los 15 minutos) pensados para explicar a otros estudiantes esta estructura.

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) :

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

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áficos

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