Programa de Asignatura: Computabilidad

Vista previa del material en texto

BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
 
INSTRUCTIVO PARA LA ELABORACIÓN 
DE PROGRAMAS DE ASIGNATURA 
DE LICENCIATURAS, PROFESIONAL ASOCIADO
(TÉCNICO SUPERIOR UNIVERSITARIO) Y TÉCNICO
Programa Educativo (PE):
LICENCIATURA EN CIENCIAS DE LA COMPUTACIÓN
Área:
Ciencias de la Computación
Programa de Asignatura: Computabilidad
Código: 
Créditos: 5
Fecha: 11 de Junio de 2009
1. DATOS GENERALES 
Nivel Educativo:
Licenciatura
Programa de Asignatura: “Computabilidad” 1
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Nombre del Programa Educativo: Licenciatura en Ciencias de la Computación
Modalidad Académica: Mixta
Nombre de la Asignatura: Computabilidad
Ubicación: Formativo
Correlación:
Asignaturas Precedentes: Lenguajes Formales y Autómatas
Asignaturas Consecuentes: Ninguna
Conocimientos, habilidades, actitudes y 
valores previos:
Conocimientos: Clasificación de lenguajes, máquinas 
de Turing, lógica matemática, funciones, relaciones.
Habilidades: Creatividad en la búsqueda de 
soluciones a problemas concretos. Habilidad para la 
lectura y comprensión de textos
Actitudes y Valores: Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud participativa. 
2. CARGA HORARIA DEL ESTUDIANTE
Concepto
Horas por periodo Total de 
horas por 
periodo
Número de 
créditosTeorías Prácticas
Horas teoría y práctica
Actividades bajo la conducción del docente 
como clases teóricas, prácticas de laboratorio, 
talleres, cursos por internet, seminarios, etc.
(16 horas = 1 crédito)
80 0 80 5
Horas de práctica profesional crítica.
Servicio social, veranos de la investigación, 
internado, estancias, ayudantías, proyectos de 
impacto social, etc.
(50 horas = 1 crédito)
Horas de trabajo independiente. 
En donde se integran aprendizajes de la 
asignatura y tiene como resultado un producto 
académico ejem. exposiciones, recitales, 
maquetas, modelos tecnológicos, asesorías, 
ponencias, conferencias, congresos, visitas, etc.
(20 horas = 1 crédito)
Total 80 0 80 5
Programa de Asignatura: “Computabilidad” 2
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
3. REVISIONES Y ACTUALIZACIONES 
Autores: José de Jesús Lavalle Martínez Jesús García Fernández
Fecha de diseño: Junio del 2000 / Julio del 2003
Fecha de la última actualización: Julio de 2009
Revisores:
Claudia Zepeda Cortés 
Alba Maribel Sánchez Gálvez 
Meliza Contreras González 
Mireya Tovar Vidal 
Darnes Vilariño Ayala
César Bautista Ramos 
Carlos Guillén Galván 
José Raymundo Marcial Romero 
Alfonso Garcés Báez 
José de Jesús Lavalle Martínez 
Sinopsis de la revisión y/o actualización: Actualización de las unidades así como de la bibliografía básica y complementaria
4. PERFIL DESEABLE DEL PROFESOR (A) PARA IMPARTIR LA ASIGNATURA:
Disciplina profesional: Ciencias de la Computación y áreas afines
Nivel académico: Maestría
Experiencia docente: Mínima de 2 años
Experiencia profesional: Mínima de 1 año
Nota: se consideran la disciplina profesional que debe tener, el grado académico, la experiencia disciplinaria y 
docente, las asignaturas que debe haber impartido y la formación o capacitación docente/disciplinaria que se 
juzgue adecuada.
5. OBJETIVOS:
5.1 Educacional: El estudiante valorará la factibilidad computacional de un problema planteado 
empleando modelos matemáticos para las ciencias de la computación.
5.2 General: El estudiante analizará la teoría de las funciones recursivas para determinar si la 
solución de un problema es un procedimiento efectivo (decidible, indecidible o parcialmente 
decidible). 
Programa de Asignatura: “Computabilidad” 3
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
5.3 Específicos: 
• Reconocer la representación de lenguajes y funciones en una máquina de Turing.
• Analizar el concepto de algoritmo o procedimiento efectivo. 
• Analizar los elementos esenciales de la teoría de la Computabilidad.
• Examinar los diferentes modelos para obtener nuevas funciones recursivas a partir de las 
funciones primitivas. 
• Ejemplificar una gama de funciones que poseen la característica de ser recursiva.
• Identificar los diferentes enfoques para la definición de computabilidad.
• Contrastar el concepto de computabilidad con el de URM-computabilidad y el concepto de 
programa con el de URM-programa. 
• Demostrar que la clase de las funciones recursivas es enumerable.
• Construir con un programa universal una función total computable que no es primitiva 
recursiva.
• Categorizar los problemas de tipo decidible contra los de tipo indecidible para identificar 
los límites de la computabilidad y con ello demostrar los límites teóricos del poder de las 
computadoras reales.
6. MAPA CONCEPTUAL DE LA ASIGNATURA:
Elaborar el mapa conceptual considerando la jerarquización de los conceptos partiendo de los más 
generales y que tienen una función más inclusiva hasta llegar a los que son más particulares y que 
tienen una menor generalidad.
Programa de Asignatura: “Computabilidad” 4
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Programa de Asignatura: “Computabilidad” 5
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
7. CONTENIDO
Unidad ObjetivoEspecífico
Contenido Temático/
Actividades de 
aprendizaje
Bibliografía
Básica Complementaria
Unidad 1 
MÁQUINAS DE 
TURING
 
Reconocer la 
representación de 
lenguajes y funciones en 
una máquina de Turing. 
1.1 El modelo de la 
máquina de Turing
John E. Hopcroft, 
Rajeev Motwani, 
Jeffrey D. Ullman 
(2007) Introduction to 
Automata Theory, 
Languages and 
Computation. Addison 
Wesley. 3ra. Ediction.
Minsky M.L. (1967) 
"Computation: Finite and 
Infinite Machines", 
Prentice Hall.
Rogers H. Jr., (2002) 
Theory of Recursive 
Functions and Effective 
Computability, Mc. Graw 
Hill
Davis Martin (1982) 
Computability and 
unsolvability
Mcgraw-Hill
1.2 Lenguajes 
computables y funciones
1.3 Técnicas para 
construcción de 
máquinas de Turing
1.4 Modificación a las 
máquinas de Turing
1.5 Las máquinas de 
Turing como 
enumeradores
1.6 Máquinas de Turing 
restringidas equivalentes 
al modelo básico
1.7 Propiedades de los 
lenguajes recursivos y
recursivamente 
enumerables
1.8 Máquina universal de 
Turing y el problema del 
paro
Unidad 2
FUNCIONES 
COMPUTABLES
Analizar el concepto de 
algoritmo o 
procedimiento efectivo. 
2.1 Algoritmos o 
Procedimientos 
Efectivos
2.2 La Máquina de 
Registros Ilimitados
Cutland N. J.(1980). 
Computability: An 
Introduction to 
Recursive Function 
Theory, Cambridge 
Davis Martin (1982) 
Computability and 
unsolvability
Mcgraw-Hill.
Programa de Asignatura: “Computabilidad” 6
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Unidad ObjetivoEspecífico
Contenido Temático/
Actividades de 
aprendizaje
Bibliografía
Básica Complementaria
Analizar los elementos 
esenciales de la teoría 
de la Computabilidad.
2.3 Funciones URM-
Computables
2.4 Predicados y 
Problemas Decidibles
2.5 Computabilidad en 
otros Dominios
University Press
Unidad 3 
GENERANDO 
FUNCIONES 
COMPUTABLES
Examinar los diferentes 
modelos para obtener 
nuevas funciones 
recursivas a partir de las 
funciones primitivas. 
Ejemplificar una gama 
de funciones que 
poseen la característica 
de ser recursiva.
3.1 Las Funciones 
Básicas
Cutland N(1980). 
Computability:An 
Introduction to 
Recursive Function 
Theory, Cambridge 
University Press
Boolos George (2007), 
Burgess John P., Jeffrey 
Richard C. Computability 
and logic. Edición: 5
Cambridge University 
Press
Davis Martin (1982) 
Computability and 
unsolvability
Mcgraw-Hill.
3.2 Unión de Programas
3.4 Substitución
3.5 Recursión
3.6 Minimalización
3.7 Tesis de Church
Unidad 4 
NUMERANDO 
FUNCIONES 
COMPUTABLES
Identificar los diferentes 
enfoques para la 
definición de 
computabilidad.
Contrastar el concepto 
de computabilidad con el 
de URM-computabilidad 
y el concepto de 
programa con el de 
URM-programa. 
Demostrar que la clase 
de las funciones 
4.1 Numerando 
Programas.
Cutland N(1980). 
Computability: An 
Introduction to 
Recursive Function 
Theory. Cambridge 
University Press
Boolos George (2007), 
Burgess John P., Jeffrey 
Richard C. Computability 
and logic. Edición: 5
Cambridge University 
Press
4.2 Numerando 
Funciones Computables
4.3 El Método Diagonal
4.4 El Teorema s-m-n
4.5 Conjuntos recursivos
Programa de Asignatura: “Computabilidad” 7
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Unidad ObjetivoEspecífico
Contenido Temático/
Actividades de 
aprendizaje
Bibliografía
Básica Complementaria
recursivas es 
enumerable.
Unidad 5 
PROGRAMAS 
UNIVERSALES
Construir con un 
programa universal una 
función total computable 
que no es primitiva 
recursiva.
5.1 Funciones 
Universales y Programas
Universales
Cutland N(1980). 
Computability: An 
Introduction to 
Recursive Function 
Theory. Cambridge 
University Press
5.2 Aplicaciones del 
Programa Universal
5.3 Operaciones 
Efectivas en
Funciones Computables
5.4 Computabilidad de la 
Función
GAMMA (n).
Unidad 6 
DECIDIBILIDAD, 
INDECIDIBILIDAD Y 
DECIDIBILIDAD
PARCIAL
Categorizar los 
problemas de tipo 
decidible contra los de 
tipo indecidible para 
identificar los límites de 
la computabilidad y con 
ello demostrar los límites 
teóricos del poder de las 
computadoras reales.
6.1 Problemas 
Indecidibles en 
computabilidad
Cutland N(1980). 
Computability: An 
Introduction to 
Recursive Function 
Theory. Cambridge 
University Press
Davis Martin (1982) 
Computability and 
unsolvability
Mcgraw-Hill.6.2 El Algoritmo de 
Sturm
6.3. Lógica Matemática
6.4 Predicados 
parcialmente decidibles
Nota: La bibliografía deberá ser amplia, actualizada (no mayor a cinco años) con ligas, portales y páginas de Internet, se recomienda usar los 
criterios del APA para referir la bibliografía.
8. CONTRIBUCIÓN DEL PROGRAMA DE ASIGNATURA AL PERFIL DE EGRESO
Programa de Asignatura: “Computabilidad” 8
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Unidad
Perfil de egreso
(anotar en las siguientes tres columnas a qué elemento(s)
del perfil de egreso contribuye esta asignatura)
Conocimientos Habilidades Actitudes y valores
Unidad 1 MAQUINAS DE 
TURING
Para la construcción de 
máquinas abstractas. 
Capacidad de análisis y síntesis.
Creatividad en el diseño de 
modelos matemáticos para un 
problema específico.
Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
participativa
Unidad 2 FUNCIONES 
COMPUTABLES
Conocimientos previos como 
conjuntos enumerables, 
funciones, aritmética, etc. 
Que permitan identificar, 
modelar y representar 
entidades o sistemas en 
diferentes niveles de 
abstracción.
Capacidad de análisis y síntesis. Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
participativa
Unidad 3 GENERANDO 
FUNCIONES COMPUTABLES
Conocimientos previos que 
permitan identificar, modelar 
y representar funciones en 
diferentes niveles de 
abstracción
Capacidad de análisis y síntesis.
Creatividad en el diseño de 
modelos matemáticos para un 
problema específico.
Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
participativa y crítica.
Unidad 4 NUMERANDO 
FUNCIONES COMPUTABLES
Concepto de programa, 
función computable, URM-
computable 
Capacidad para enumerar 
funciones.
Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
participativa.
Unidad 5 PROGRAMAS 
UNIVERSALES
Aplicar las técnicas 
necesarias que permitan 
con un programa universal 
la construcción de una 
función total computable que 
no sea primitiva recursiva.
Capacidad para construir 
funciones totales computables.
Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
participativa.
Unidad 6 DECIDIBILIDAD, 
INDECIDIBILIDAD Y 
Analizar diversos problemas 
y ser capaz de clasificarlos 
Capacidad para analizar un 
problema determinado y saber 
Responsabilidad, puntualidad, 
aprendizaje autónomo, actitud 
Programa de Asignatura: “Computabilidad” 9
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
Unidad
Perfil de egreso
(anotar en las siguientes tres columnas a qué elemento(s)
del perfil de egreso contribuye esta asignatura)
Conocimientos Habilidades Actitudes y valores
DECIDIBILIDAD
PARCIAL
en problemas decidibles e 
indecidibles.
categorizarlo participativa.
Programa de Asignatura: “Computabilidad” 10
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
9. ORIENTACIÓN DIDÁCTICO-PEDAGÓGICA. (Enunciada de manera general para aplicarse 
durante todo el curso)
Estrategias a-e Técnicas a-e Recursos didácticos
Estrategias de aprendizaje:
• Lectura y comprensión,
• Reflexión,
• Comparación,
• Resumen.
Estrategias de enseñanza:
• ABP,
• Aprendizaje activo,
• Aprendizaje cooperativo,
• Aprendizaje colaborativo,
• Basado en el descubrimiento.
Ambientes de aprendizaje:
• Aula,
• Simuladores.
Actividades y experiencias de 
aprendizaje:
Investigación de los nuevos modelos 
de computación
Técnicas 
• grupales,
• de debate,
• del diálogo,
• de problemas,
• de estudio de casos,
• cuadros sinópticos,
• comparación,
• síntesis,
• lluvia de ideas,
• analogías,
• exposición.
Materiales:
• Proyectores,
• TICs,
• Plumón y pizarrón,
Nota: ver glosario
10. CRITERIOS DE EVALUACIÓN
Criterios Porcentaje
• Exámenes 40%
• Participación en clase 10%
• Tareas 20%
• Exposiciones 10%
• Simulaciones
• Trabajos de investigación y/o de intervención
• Prácticas de laboratorio
• Visitas guiadas 
• Reporte de actividades académicas y culturales
• Mapas conceptuales
• Portafolio
• Proyecto final 20%
• Otros
Total
Nota: Se refiere a lo que se evaluará del proceso A-E, considerando sus finalidades, la información y las 
consecuencias que se derivan de este proceso, los resultados, los momentos, las orientaciones, las técnicas y 
Programa de Asignatura: “Computabilidad” 11
BENÉMERITA UNIVERSIDAD AUTÓNOMA DE PUEBLA
VICERRECTORÍA DE DOCENCIA
DIRECCIÓN GENERALDE EDUCACIÓN SUPERIOR
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
los instrumentos, todo esto nos conducirá al diálogo y reflexión sobre el aprendizaje del grupo. Los porcentajes 
serán establecidos por la academia de acuerdo a los objetivos de cada asignatura. 
11. REQUISITOS DE ACREDITACIÓN
Estar inscrito oficialmente como alumno del PE en la BUAP
Haber aprobado las asignaturas que son pre-requisitos de ésta
Aparecer en el acta
El promedio de las calificaciones de los exámenes aplicados deberá ser igual o mayor que 6
Cumplir con las actividades propuestas por el profesor 
Nota: Describe los requisitos que el estudiante debe cumplir para acreditar la materia.
Programa de Asignatura: “Computabilidad” 12
	Créditos: 5
	Licenciatura
	Formativo
	Mcgraw-Hill
	10. CRITERIOS DE EVALUACIÓN