TEORIA DE COMPUTACION - 503306
- Descripción :Este curso presenta aspectos de la teoria de automatas, lenguajes y gramaticas formales, y profundiza conocimientos de computabilidad y complejidad. Se proporciona conceptos y herramientas conceptuales para abordar problemas formales complejos.
Esta asignatura aporta a las siguientes competencias del perfil de egreso:
? Aplicar principios de matematicas, ciencias de la ingenieria y ciencias de la computacion, a problemas de ingenieria informatica.
? Involucrarse en procesos de auto-aprendizaje continuo que le permita adaptarse a la evolucion de la teoria y tecnologia.
- Resultados aprendizaje esperados :1. Reconocer los distintos tipos de automatas, lenguajes y gramaticas y ser capaz de entender las relaciones que existen entre ellos.
2. Explicar los limites teoricos sobre las soluciones computacionales de problemas intrinsecamente complejos e indecidibles.
3. Comprender definiciones formales de modelos de maquinas y lenguajes.
4. Describir aspectos de indecibilidad y/o complejidad de distintos problemas.
- Contenidos :1. Lenguajes y gramaticas
a. Definiciones
b. Lenguajes y Maquinas de computo
c. Gramaticas
2. Automatas
a. Automatas finitos
b. Determinismo y no-determinismo
c. Clases de equivalencia en Lenguajes Regulares
d. Automatas de pila
e. Lenguajes y Jerarquia de Chomsky
3. Gramaticas y Lenguajes
a. Tipos de Gramaticas y Reconocedores
b. Ambiguedad
c. Analisis top-down y bottom-up
d. Tecnicas de analisis gramatical
4. Computabilidad
a. Maquinas de Turing
b. Decidibilidad
c. Funciones
5. Complejidad
a. Reduccion de problemas
b. Clases P y NP
- Metodología :Esta asignatura se desarrolla en base a clases presenciales teoricas y practicas.
- Evaluación :La asignatura consta de al menos tres evaluaciones usando algunas de las siguientes modalidades: evaluaciones escritas, tareas y proyectos.
- Facultad :INGENIERIA
- Departamento :INFORMATICA Y CS COMPUTACION
- Creditos :4
- Cupos :30
- Campus :CONCEPCION