5.20. CS211. Teoría de la Computación (Obligatorio)

• Semestre: 4to Sem. Créditos: 4
• Horas del curso: Teoría: 2 horas; Práctica: 2 horas; Laboratorio: 2 horas;

• Prerrequisitos:

  • CS1D1. Estructuras Discretas (2do Sem)

5.20.1. Justificación

La Teoría de la Computación proporciona los fundamentos matemáticos para entender qué puede ser computado y con qué eficiencia. Introduce lenguajes formales, autómatas y los límites de la resolubilidad algorítmica. Este conocimiento es fundamental para comprender la construcción de compiladores, la verificación formal y la complejidad inherente de los problemas computacionales.

5.20.2. Objetivos Generales

1.

Dominar los conceptos de autómatas finitos y expresiones regulares.

2.

Analizar gramáticas libres de contexto y autómatas de pila.

3.

Comprender la Máquina de Turing Universal como modelo de computación.

4.

Comprender los límites de la computabilidad y el Problema de la Parada.

5.

Diferenciar entre clases de complejidad como P y NP.

5.20.3. Contribución a los resultados (Outcomes)

AG-C08) Análisis de Problemas: Identifica, formula y analiza problemas complejos de computación. (Usage)

AG-C12) Aplica la teoría de la ciencia de la computación y los fundamentos de desarrollo de software para producir soluciones basadas en computadora. (Usage)

5.20.4. Contenido

5.20.4.1. Lenguajes Formales y Autómatas (18 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Hopcroft et al., 2013]

Temas

1.

Autómatas formales:

a)

Estado Finito

b)

Pila

c)

Linealmente Acotado

d)

Máquina de Turing

2.

Lenguajes formales, gramáticas y Jerarquía de Chomsky:

a)

Regulares (Tipo-3):

1)

Expresiones Regulares

b)

Libres de Contexto (Tipo-2)

c)

Sensibles al Contexto (Tipo-1)

d)

Recursivamente Enumerables (Tipo-0)

3.

Autómatas deterministas y no deterministas

4.

Demostraciones del Lema de Bombeo:

a)

Demostración de la limitación de Estado Finito/Lenguaje Regular

b)

Limitación de Autómatas de Pila/Lenguaje Libre de Contexto

Aprendizaje esperado (Learning Outcomes)

1.

Para cada autómata formal en esta unidad:

a)

Explicar su definición comparando sus características con los otros autómatas de esta unidad

b)

Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada

c)

Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.

[Explicar]

2.

Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]

3.

Desarrollar una expresión regular para un lenguaje regular dado expresado en lenguaje natural [Crear]

4.

Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]

5.

Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]

5.20.4.2. Lenguajes Formales y Autómatas (16 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Hopcroft et al., 2013]

Temas

1.

Autómatas formales:

a)

Estado Finito

b)

Pila

c)

Linealmente Acotado

d)

Máquina de Turing

2.

Lenguajes formales, gramáticas y Jerarquía de Chomsky:

a)

Regulares (Tipo-3):

1)

Expresiones Regulares

b)

Libres de Contexto (Tipo-2)

c)

Sensibles al Contexto (Tipo-1)

d)

Recursivamente Enumerables (Tipo-0)

3.

Formas Normales: Chomsky y Greibach

4.

Demostraciones del Lema de Bombeo:

a)

Demostración de la limitación de Estado Finito/Lenguaje Regular

b)

Limitación de Autómatas de Pila/Lenguaje Libre de Contexto

5.

Relaciones entre autómatas formales, lenguajes y gramáticas

Aprendizaje esperado (Learning Outcomes)

1.

Para cada autómata formal en esta unidad:

a)

Explicar su definición comparando sus características con los otros autómatas de esta unidad

b)

Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada

c)

Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.

[Explicar]

2.

Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]

3.

Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]

4.

Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]

5.

Construir GLCs para descripciones de lenguajes formales [Evaluar]

5.20.4.3. Lenguajes Formales y Autómatas (16 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Kozen, 2006]

Temas

1.

Autómatas formales:

a)

Estado Finito

b)

Pila

c)

Linealmente Acotado

d)

Máquina de Turing

2.

Lenguajes formales, gramáticas y Jerarquía de Chomsky:

a)

Regulares (Tipo-3):

1)

Expresiones Regulares

b)

Libres de Contexto (Tipo-2)

c)

Sensibles al Contexto (Tipo-1)

d)

Recursivamente Enumerables (Tipo-0)

3.

Decidabilidad, (in)computabilidad y parada

4.

La tesis de Church-Turing

5.

Reducibilidad y reducciones

6.

Modelos equivalentes de computación algorítmica:

a)

Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)

b)

Cálculo Lambda

c)

Funciones Mu-Recursivas

Aprendizaje esperado (Learning Outcomes)

1.

Para cada autómata formal en esta unidad:

a)

Explicar su definición comparando sus características con los otros autómatas de esta unidad

b)

Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada

c)

Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.

[Explicar]

2.

Explicar una Máquina de Turing universal y su operación [Explicar]

3.

Presentar a una audiencia de compañeros de trabajo y gerentes la imposibilidad de proporcionarles un programa que verifique todos los otros programas, incluyendo algunos aparentemente simples, en busca de bucles infinitos incluyendo una explicación del problema de la parada, por qué no tiene solución algorítmica y su importancia para la computación algorítmica del mundo real [Explicar]

4.

Explicar la Tesis de Church-Turing y su importancia para la computación algorítmica [Explicar]

5.

Aplicar aritmetización y diagonalización para demostrar que el Problema de la Parada para Máquinas de Turing es Indecidible [Aplicar]

6.

Dado un lenguaje indecidible conocido, aplicar una reducción por mapeo o historia computacional para demostrar que otro lenguaje es indecidible [Aplicar]

5.20.4.4. Lenguajes Formales y Autómatas (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Kozen, 2006]

Temas

1.

Lenguajes formales, gramáticas y Jerarquía de Chomsky:

a)

Regulares (Tipo-3):

1)

Expresiones Regulares

b)

Libres de Contexto (Tipo-2)

c)

Sensibles al Contexto (Tipo-1)

d)

Recursivamente Enumerables (Tipo-0)

2.

Relaciones entre autómatas formales, lenguajes y gramáticas

3.

Modelos equivalentes de computación algorítmica:

a)

Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)

b)

Cálculo Lambda

c)

Funciones Mu-Recursivas

4.

Lenguajes Sensibles al Contexto (Tipo-1) y aplicaciones

Aprendizaje esperado (Learning Outcomes)

1.

Para cada modelo formal en esta unidad:

a)

Explicar su definición comparando sus características con las otras en esta unidad

b)

Explicar ejemplos de entradas que son y no pueden ser aceptadas por el lenguaje/gramática.

[Explicar]

2.

Explicar las funciones Recursivas Primitivas y Generales (cero, sucesor, selección, recursión primitiva, composición y Mu), su importancia e implementaciones en Máquina de Turing [Explicar]

3.

Explicar cómo se realiza la computación en el Cálculo Lambda (por ejemplo, conversión alfa y reducción beta) [Explicar]

4.

Explicar el teorema de Rice y su importancia [Explicar]

5.20.4.5. Marco de Análisis de Complejidad (3 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Cormen et al., 2022]

Temas

1.

Marco de Análisis de Complejidad:

a)

Rendimiento de un algoritmo en el mejor caso, caso promedio y peor caso

b)

Mediciones empíricas y relativas (Orden de Crecimiento)

c)

Tamaño de entrada y operaciones primitivas

d)

Eficiencia de tiempo y espacio

Aprendizaje esperado (Learning Outcomes)

1.

Preparar una presentación que explique a estudiantes de primer año los conceptos básicos de complejidad algorítmica incluyendo comportamiento de algoritmo en mejor caso, caso promedio y peor caso, notaciones Big-O, Omega y Theta, clases de complejidad, compromisos tiempo-espacio, medición empírica e impacto en problemas prácticos [Explicar]

2.

Evaluar informalmente la clase de complejidad fundamental de algoritmos simples [Evaluar]

5.20.4.6. Notación Asintótica y Clases de Complejidad (4 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Cormen et al., 2022]

Temas

1.

Análisis de complejidad asintótica (cotas promedio y peor caso):

a)

Notaciones formales Big-O, Big-Omega y Big-Theta

b)

Clases de Complejidad Fundamentales y Ejemplos/Problemas Representativos:

1)

O(1) Constante (por ejemplo, acceso a arreglo)

2)

O(log ₂n) Logarítmica (por ejemplo, búsqueda binaria)

3)

O(n) Lineal (por ejemplo, búsqueda lineal)

4)

O(nlog ₂n) Log Lineal (por ejemplo, mergesort)

5)

O(n²) Cuadrática (por ejemplo, ordenamiento por selección)

6)

O(n^c) Polinomial (por ejemplo, O(n³) eliminación gaussiana)

7)

O(2ⁿ) Exponencial (por ejemplo, Mochila, Satisfactibilidad (SAT), Viajante de Comercio (TSP), todos los subconjuntos)

8)

O(n!) Factorial (por ejemplo, circuito hamiltoniano, todas las permutaciones)

Aprendizaje esperado (Learning Outcomes)

1.

Usando ejemplos, explicar cada una de las clases de complejidad fundamentales en esta unidad [Explicar]

2.

Explicar a una audiencia no técnica la importancia de los algoritmos tratables versus intratables usando una explicación intuitiva de la complejidad Big-O [Explicar]

5.20.4.7. Análisis de Complejidad II: Recursión, Amortización y Cotas Ajustadas (7 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Sipser, 2012, Cormen et al., 2022]

Temas

1.

Notaciones Little-o, Little-Omega y Little Theta

2.

Análisis recursivo formal

Aprendizaje esperado (Learning Outcomes)

1.

Usar relaciones de recurrencia para evaluar la complejidad de tiempo de algoritmos definidos recursivamente [Aplicar]

2.

Aplicar relaciones de recurrencia elementales usando una forma del Teorema Maestro [Aplicar]

5.20.4.8. Teoría de la Complejidad Computacional (6 horas) [Habilidades ]

Referencias Bibliográficas: [Sipser, 2012, Cormen et al., 2022]

Temas

1.

Tractabilidad e intractabilidad:

a)

Clases de Complejidad P, NP y NP-Completo

b)

Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)

c)

Reducciones

2.

Modelos de complejidad basados en Máquinas de Turing:

a)

Complejidad de tiempo:

1)

Clases P, NP, NP-C y EXP

2)

Teorema de Cook-Levin

b)

Complejidad de espacio:

1)

NSpace y PSpace

2)

Teorema de Savitch

Aprendizaje esperado (Learning Outcomes)

1.

Explicar la importancia de la NP-Completitud [Explicar]

2.

Explicar cómo NP-Duro es una cota inferior y NP es una cota superior para la NP-Completitud [Explicar]

3.

Explicar ejemplos de problemas NP-completos [Explicar]

4.

Explicar el Teorema de Cook-Levin y la NP-Completitud de SAT [Explicar]

5.

Explicar las clases P y NP [Explicar]

6.

Demostrar que un problema es NP-Completo reduciendo un problema NP-C clásico conocido a él (por ejemplo, 3SAT y Clique) [Crear]

7.

Explicar la clase P-espacio y su relación con la clase EXP [Explicar]

5.20.5. Referencias Bibliográficas

[Sipser, 2012]

[Hopcroft et al., 2013]

[Kozen, 2006]

[Cormen et al., 2022]