Teoría de Computación

Información General

El curso de pregrado en Teoría de la Computación es una exploración profunda y rigurosa de los fundamentos matemáticos que sustentan la ciencia de la computación. Diseñado para proporcionar a los estudiantes una comprensión sólida de los conceptos teóricos subyacentes a la resolución de problemas computacionales, este curso abarca áreas clave como la teoría de autómatas, la complejidad computacional y la teoría de lenguajes formales. Los estudiantes se sumergirán en la investigación de modelos abstractos de cómputo, como máquinas de Turing, y explorarán cómo estas abstracciones pueden utilizarse para analizar la solubilidad de problemas algorítmicos. A lo largo del curso, se fomenta el pensamiento analítico y la capacidad para abordar problemas complejos desde una perspectiva teórica, preparando a los estudiantes para aplicar estos conocimientos en el diseño y análisis de algoritmos en diversos contextos informáticos.

Además, el curso abordará temas avanzados como la teoría de la complejidad computacional, donde se explorarán clases de problemas y se analizará la dificultad intrínseca de los mismos. Los estudiantes aprenderán a clasificar problemas según su complejidad y a comprender la diferencia entre problemas resolubles de manera eficiente y aquellos que son inherentemente difíciles. Con un enfoque en la formalización de conceptos y la aplicación de la lógica matemática en la teoría de la computación, este curso proporcionará a los estudiantes las herramientas necesarias para abordar desafíos computacionales desde una perspectiva fundamentada en principios sólidos y conceptualmente ricos.

Objetivos

Comprender los Fundamentos Matemáticos: Proporcionar a los estudiantes una base sólida en conceptos matemáticos fundamentales, como la lógica, la teoría de conjuntos y la álgebra booleana, que son esenciales para el análisis teórico en ciencia de la computación.

Explorar Modelos de Cómputo Abstractos: Introducir y analizar modelos abstractos de cómputo, como máquinas de Turing y autómatas finitos, para comprender cómo representan y resuelven problemas algorítmicos.

Estudiar la Teoría de Lenguajes Formales: Profundizar en la teoría de lenguajes formales y gramáticas, permitiendo a los estudiantes comprender la estructura y la sintaxis de los lenguajes de programación y la base de compiladores.

Profesor

Taller Semana 3

Taller Semana 4

M.Sc., Alfonso Meléndez Profesor Titular UECI

Cronograma Semanal

Texto del Curso :

Michael Sipser: Introduction to the Theory of Computation

Slides Autómatas de Estado Finito Carnegie Mellon

Slides

	Descripción	Material de lectura	Problemas	Material Adicional
Semana 1	Introducción al Curso, El Hotel Infinito	Satán,Cantor y el Infinito		Video:The Infinite Hotel
Semana 2	Lenguajes Regulares Autómatas de Estado Finito	Sección 1-1	1.1-1.2-1.3	Video: Operaciones Regulares Taller 1
Semana 3	Lenguajes Regulares No Determinismo	Sección 1-2	1.4-1.5-1.6-1.12-1.13	Video: Autómatas no Determinísticos Slides Lenguajes Regulares Slides Expresiones Regulares
Semana 4	Lenguajes Regulares: Expresiones Regulares, Lema de Bombeo	Secciones 1-3 1-4	1.21-1.28-1.29	Slides Algoritmos Determinismo y Minimización Slides Autómata Det a Expresión Regular Video: DFA to regular Expression Video : Conversion of NFa to DFA Video: Minimization of a DFA Video : Lema de Bombeo
Semana 5	Lenguajes Libres de Contexto	Sección 2.1	2.1 a 2.4	Video : LLibres de Contexto Slides Propiedades de Clausura Slides Lema de Bombeo
Semana 6	Lenguajes Libres de Contexto: Autómatas de Pila	Sección 2.2	2.5-2.7-2.8	Video: Autómatas de Pila
Semana 7	Lenguajes Libres de Contexto: Limitaciones	Sección 2.3	2.18-2.24-2.27	Video: Lema de Bombeo para L Libres de Contexto
Semana 8	La tesis de Church-Turing			Video: La tesis de Church Turing
Semana 9	Máquinas de Turing			Video: Turing Machines
Semana 10	Máquinas de Turing
Semana 11	Máquinas de Turing
Semana 12	Problemas P Y NP
Semana 13	Decidibilidad
Semana 14	Reducibilidad
Semana 15	Tópicos Adicionales
Semana 16	Tópicos Adicionales