• ES Español
• EN English

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

5.20.1. Justificación ↑ Volver arriba

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 ↑ Volver arriba

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) ↑ Volver arriba

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 ↑ Volver arriba

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

Referencias Bibliográficas: (Sipser, 2012; Hopcroft et al., 2013)

Temas

1. Autómatas formales:
2. Estado Finito
3. Pila
4. Linealmente Acotado
5. Máquina de Turing enumerate
6. Lenguajes formales, gramáticas y Jerarquía de Chomsky:
7. Regulares (Tipo-3):
8. Expresiones Regulares enumerate
9. Libres de Contexto (Tipo-2)
10. Sensibles al Contexto (Tipo-1)
11. Recursivamente Enumerables (Tipo-0) enumerate
12. Autómatas deterministas y no deterministas
13. Demostraciones del Lema de Bombeo:
14. Demostración de la limitación de Estado Finito/Lenguaje Regular
15. Limitación de Autómatas de Pila/Lenguaje Libre de Contexto enumerate

Aprendizaje esperado (Learning Outcomes)

1. Para cada autómata formal en esta unidad:
2. Explicar su definición comparando sus características con los otros autómatas de esta unidad
3. Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
4. Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata. enumerate [Explicar]
5. Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]
6. Desarrollar una expresión regular para un lenguaje regular dado expresado en lenguaje natural [Crear]
7. Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]
8. 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] ↑ Volver arriba

Referencias Bibliográficas: (Sipser, 2012; Hopcroft et al., 2013)

Temas

1. Autómatas formales:
2. Estado Finito
3. Pila
4. Linealmente Acotado
5. Máquina de Turing enumerate
6. Lenguajes formales, gramáticas y Jerarquía de Chomsky:
7. Regulares (Tipo-3):
8. Expresiones Regulares enumerate
9. Libres de Contexto (Tipo-2)
10. Sensibles al Contexto (Tipo-1)
11. Recursivamente Enumerables (Tipo-0) enumerate
12. Formas Normales: Chomsky y Greibach
13. Demostraciones del Lema de Bombeo:
14. Demostración de la limitación de Estado Finito/Lenguaje Regular
15. Limitación de Autómatas de Pila/Lenguaje Libre de Contexto enumerate
16. Relaciones entre autómatas formales, lenguajes y gramáticas

Aprendizaje esperado (Learning Outcomes)

1. Para cada autómata formal en esta unidad:
2. Explicar su definición comparando sus características con los otros autómatas de esta unidad
3. Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
4. Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata. enumerate [Explicar]
5. Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]
6. Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]
7. Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]
8. Construir GLCs para descripciones de lenguajes formales [Evaluar]

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

Referencias Bibliográficas: (Sipser, 2012; Kozen, 2006)

Temas

1. Autómatas formales:
2. Estado Finito
3. Pila
4. Linealmente Acotado
5. Máquina de Turing enumerate
6. Lenguajes formales, gramáticas y Jerarquía de Chomsky:
7. Regulares (Tipo-3):
8. Expresiones Regulares enumerate
9. Libres de Contexto (Tipo-2)
10. Sensibles al Contexto (Tipo-1)
11. Recursivamente Enumerables (Tipo-0) enumerate
12. Decidabilidad, (in)computabilidad y parada
13. La tesis de Church-Turing
14. Reducibilidad y reducciones
15. Modelos equivalentes de computación algorítmica:
16. Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)
17. Cálculo Lambda
18. Funciones Mu-Recursivas enumerate

Aprendizaje esperado (Learning Outcomes)

1. Para cada autómata formal en esta unidad:
2. Explicar su definición comparando sus características con los otros autómatas de esta unidad
3. Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
4. Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata. enumerate [Explicar]
5. Explicar una Máquina de Turing universal y su operación [Explicar]
6. 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]
7. Explicar la Tesis de Church-Turing y su importancia para la computación algorítmica [Explicar]
8. Aplicar aritmetización y diagonalización para demostrar que el Problema de la Parada para Máquinas de Turing es Indecidible [Aplicar]
9. 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] ↑ Volver arriba

Referencias Bibliográficas: (Sipser, 2012; Kozen, 2006)

Temas

1. Lenguajes formales, gramáticas y Jerarquía de Chomsky:
2. Regulares (Tipo-3):
3. Expresiones Regulares enumerate
4. Libres de Contexto (Tipo-2)
5. Sensibles al Contexto (Tipo-1)
6. Recursivamente Enumerables (Tipo-0) enumerate
7. Relaciones entre autómatas formales, lenguajes y gramáticas
8. Modelos equivalentes de computación algorítmica:
9. Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)
10. Cálculo Lambda
11. Funciones Mu-Recursivas enumerate
12. Lenguajes Sensibles al Contexto (Tipo-1) y aplicaciones

Aprendizaje esperado (Learning Outcomes)

1. Para cada modelo formal en esta unidad:
2. Explicar su definición comparando sus características con las otras en esta unidad
3. Explicar ejemplos de entradas que son y no pueden ser aceptadas por el lenguaje/gramática. enumerate [Explicar]
4. 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]
5. Explicar cómo se realiza la computación en el Cálculo Lambda (por ejemplo, conversión alfa y reducción beta) [Explicar]
6. 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] ↑ Volver arriba

Referencias Bibliográficas: (Sipser, 2012; Cormen et al., 2022)

Temas

1. Marco de Análisis de Complejidad:
2. Rendimiento de un algoritmo en el mejor caso, caso promedio y peor caso
3. Mediciones empíricas y relativas (Orden de Crecimiento)
4. Tamaño de entrada y operaciones primitivas
5. Eficiencia de tiempo y espacio enumerate

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] ↑ Volver arriba

Referencias Bibliográficas: (Sipser, 2012; Cormen et al., 2022)

Temas

1. Análisis de complejidad asintótica (cotas promedio y peor caso):
2. Notaciones formales Big-O, Big-Omega y Big-Theta
3. Clases de Complejidad Fundamentales y Ejemplos/Problemas Representativos:
4. \(O(1)\) Constante (por ejemplo, acceso a arreglo)
5. \(O(\log_2 n)\) Logarítmica (por ejemplo, búsqueda binaria)
6. \(O(n)\) Lineal (por ejemplo, búsqueda lineal)
7. \(O(n \log_2 n)\) Log Lineal (por ejemplo, mergesort)
8. \(O(n^2)\) Cuadrática (por ejemplo, ordenamiento por selección)
9. \(O(n^c)\) Polinomial (por ejemplo, \(O(n^3)\) eliminación gaussiana)
10. \(O(2^n)\) Exponencial (por ejemplo, Mochila, Satisfactibilidad (SAT), Viajante de Comercio (TSP), todos los subconjuntos)
11. \(O(n!)\) Factorial (por ejemplo, circuito hamiltoniano, todas las permutaciones) enumerate enumerate

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: Recursión, Amortización y Cotas Ajustadas (7 horas) [Habilidades AG-C08,AG-C12] ↑ Volver arriba

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 ] ↑ Volver arriba

Referencias Bibliográficas: (Sipser, 2012; Cormen et al., 2022)

Temas

1. Tractabilidad e intractabilidad:
2. Clases de Complejidad P, NP y NP-Completo
3. Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)
4. Reducciones enumerate
5. Modelos de complejidad basados en Máquinas de Turing:
6. Complejidad de tiempo:
7. Clases P, NP, NP-C y EXP
8. Teorema de Cook-Levin enumerate
9. Complejidad de espacio:
10. NSpace y PSpace
11. Teorema de Savitch enumerate enumerate

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 ↑ Volver arriba

Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3rd edition.

Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2013). Introduction to Automata Theory, Languages, and Computation. Pearson, 3rd edition.

Kozen, D. C. (2006). Theory of Computation. Springer.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms. MIT Press, 4th edition.