UNIVERSIDAD AUTÓNOMA AUTÓNOMA DE BAJA CALIFO CALIFORNIA SUR DEPARTAMENTO ACADÉMICO ACADÉMICO DE SISTEMAS COMPUTACIONALES
INGENIERÍA EN TECNOLOGÍA TECNOLOGÍA COMPUTACIONAL ASIGNATURA Teoría de la computación ÁREA DE Ciencias de la ingeniería CONOCIMIENTO ETAPA DE FORMACIÓN
Disciplinaria
CLAVE ICC504 SEMESTRE V CRÉDITOS CRÉDITOS 8 HORAS TEORÍA TEORÍA 4 HORAS PRÁCTICA 0 CARÁCTER DE LA OBLIGATORIA MATERIA TEÓRICA SERIACIÓN SERIACIÓN NINGUNA HORAS INFRAESTRUCTURA DE CÓMPUTO
2
RECURSOS Pizarrón NECESARIOS Plumones
INTRODUCCIÓN INTRODUCCIÓN La asignatura de Teoría de la Computación forma parte del área de conocimiento de “Ciencias de la Ingeniería”. Se imparte en el quinto semestre de la carrera. Esta asignatura contribuye a la formación básica del alumno en el dominio de herramientas, así como al desarrollo de un pensamiento crítico y reflexivo de resolución de problemas.
COMPETENCIA DEL CURSO Definir de manera formal lenguajes de programación sencillos y reconocer en los autómatas y máquinas de Turing el modelo matemático de las computadoras con la finalidad que el alumno desarrolle habilidades de análisis con un alto sentido de responsabilidad y de trabajo en equipo, bajo un ambiente de tolerancia y respeto hacia sus compañeros y a su medio.
CONOCIMIENTOS
UNIDAD
I
NOMBRE
INTRODUCCIÓN
COMPETENCIA DE LA UNIDAD Emplear con facilidad los conceptos y herramientas básicas para la teoría de lenguajes autómatas. TEMAS 1. Teoría de Conjuntos 1.1. Unión e intersección 1.2. Complemento y diferencia simétrica 1.3. Conjunto potencia 1.4. Operaciones arbitrarias 2. Relaciones y funciones 2.1. Funciones inyectivas y sobreyectivas 3. Inducción Matemáticas
UNIDAD
II
NOMBRE
AUTÓMATAS
FINITOS
Y
LENGUAJES
REGULARES
COMPETENCIA DE LA UNIDAD Definir lenguajes regulares y para transformar autómatas finitos determinísticos en expresiones regulares y viceversa. TEMAS 1. Lenguajes 1.1. Alfabetos 1.2. Cadenas de símbolos 1.3. Expresiones y lenguajes regulares 1.4. Lenguajes regulares 2. Autómatas finitos determinísticos 3. Transformación de LR en AFD
UNIDAD
III
NOMBRE
DETERMINISMO Y NO DETERMINISMO
COMPETENCIA DE LA UNIDAD Analizar el no determinismo y determinismo para modelar el cómputo paralelo y la equivalencia entre AFD y AFN. TEMAS 1. Autómatas finitos no determinístico (AFN) 2. Función de transición no determinística. 3. Equivalencia entre los AFD y AFN.
UNIDAD
IV
NOMBRE
AUTÓMATAS DE PILA Y GRAMÁTICAS LIBRES DE CONTEXTO
COMPETENCIA DE LA UNIDAD Reconocer en las gramáticas libres de contexto su función en la definición de lenguajes de programación y las diversas etapas de un proceso de compilación. TEMAS 1. Autómatas de pila 2. Gramáticas libres de contexto 3. Lenguajes libres de contexto 4. Autómatas de pila no determinísticos 5. Lenguajes ambiguos
UNIDAD
V
NOMBRE
MÁQUINAS DE TURING
COMPETENCIA DE LA UNIDAD Reconocer a la máquina de Turing como el modelo matemático de las computadoras actuales e identificar algunas aplicaciones y limitaciones del modelo. TEMAS 1. Definición de Máquina de Turing 2. MT no determinísticas 3. Lenguajes sensibles al contexto 4. Máquinas de Turing universales 5. El problema de la parada
HABILIDADES Pensamiento crítico y reflexivo, organización y planificación, solución de problemas, creatividad, comunicación y autoaprendizaje.
ACTITUDES Honestidad, responsabilidad, creatividad, trabajo en equipo, tolerancia y respeto hacia sus compañeros y a su medio.
ESTRATEGIAS DE APRENDIZAJE •
Estrategias de información
•
Estrategias organizativas
•
Estrategias analíticas
•
Estrategias inventivas
•
Estrategias evaluativas para la toma de decisiones
•
Estrategias de asimilación y retención de información
•
Estrategias comunicativas
•
Estrategias sociales
•
Estrategias psicomotoras
PRÁCTICAS •
Implementación de autómata finito determinista AFD.
•
Implementación de autómata finito no determinista AFN.
•
Conversión de expresiones regulares a AFN.
•
Diseño de gramáticas libres de contexto.
•
Representación de una máquina de Turing.
ESTRATEGIAS DE EVALUACIÓN •
Ejercicios de aplicación
•
Trabajos
•
Tareas
•
Exámenes de conocimiento
•
Participación en clase
•
Supervisión de actitudes y valores
EVIDENCIA DE DESEMPEÑO Aplicación de las máquinas de Turing. Exámenes de conocimientos
BIBLIOGRAFÍA No. 1
TITULO TEORÍA DE LA COMPUTACIÓN TEORÍA DE LENGUAJES