UniversidaddeCádiz

Programas Docentes de Asignaturas

Programa docente (2025-26) | <21714025 | MODELOS DE COMPUTACIÓN>

Asignatura: 21714025 | MODELOS DE COMPUTACIÓN

Titulación: 1725 | GRADO EN INGENIERÍA INFORMÁTICA

Centro: 17 | ESCUELA SUPERIOR DE INGENIERÍA

Departamento: C137 | INGENIERIA INFORMATICA

Área: 570 | LENGUAJES Y SISTEMAS INFORMATICOS

Compartidas:

Tipo estudio: GRADO

Ofertada: SÍ

Vigencia: VIGENTE

Créd. Teoría: 2,50

Créd. Prácticas: 5,00

Créd. ECTS: 6,00

Tipo asignatura: OPTATIVA

Módulo: MODULO IIIA - TECNOLOGÍA ESPECÍFICA COMPUTACIÓN

Materia: MATERIA IIIA.1 COMPUTABILIDAD Y COMPLEJIDAD

Matriculados 2024-25: 27

Matriculados 2025-26: 26

Duración: SEGUNDO SEMESTRE

Curso: 3, 4

Idioma: CASTELLANO

Mostrar información

Primer apellido	Segundo apellido	Nombre	Categoría/Empresa	Coordinación
TOMEU	HARDASMAL	ANTONIO J.	PROFESOR TITULAR DE UNIVERSIDAD

Resultado formación y aprendizaje	Competencia
Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática	ESPECÍFICA

ID/Orden	Resultado
1	El alumno sabrá determinar cuando una función es computable en sentido parcial o total mediante la construcción de una instancia de algún modelo de cálculo que así lo demuestre. Igualmente determinará la computabilidad de predicados.
2	El alumno será capaz de definir nuevas funciones computables mediante aplicación de las técnicas de composición y recursión primitiva (simple y generalizada). Igualmente conocerá la jerarquía de funciones computables, y será capaz de determinar si una función es recursiva primitiva, una clase de funciones es PRC, y de construir predicados recursivos primitivos aplicando operaciones iteradas y cuantificación acotada.
3	El alumno sabrá codificar pares de números mediante la función de emparejamiento y la numeración de Gdel, y conocerá la interpretación de los Teoremas de las Formas Normales y su consecuencias.
4	El alumno conocerá algunos resultados notables de interés como el problema de la parada o el Teorema de Universalidad, y sabrá determinar cuándo conjuntos básicos son recursivos enumerables y recursivos.
5	El alumno conocerá diferentes versiones de la máquina de Turing como modelo de computación estándar, y conocerá otros modelos de computación alternativos.

Código	Descripción	Horas	Detalle
01	Teoría	20	Exposición de los contenidos de la materia con ayuda ocasional de diapositivas, junto con la propuesta de ejemplos de afianzamiento desarrollados en aula. Se emplearán simuladores de algunos de los modelos de computación estudiados en el curso: Davis, URM, Máquinas de Turing.
02	Prácticas, seminarios y problemas	10	Las clases de problemas se dedicarán a desarrollar las soluciones a algunos de los ejercicios propuestos en las relaciones de problemas de la asignatura, que ampliarán en profundidad y complejidad a los ejemplos desarrollados en las clases teóricas.
03	Prácticas de informática	30	El alumno desarrollará las prácticas de la asignatura bajo dos vertientes de trabajo posibles: a) Utilizará simuladores de diversos modelos de computación para verificar la computabilidad de distintas funciones y predicados bajo cada uno de los modelos. b) Desarrollará, utilizando algún lenguaje de programación, programas que utilicen algún modelo aplicados a diferentes ámbitos del conocimiento.
10	Actividades formativas no presenciales	86	a) Lectura cuidadosa y razonada de las referencias bibliográficas y textos que sobre la materia indiquen los profesores indicadas por los profesores. b) Resolución de los ejercicios y/o problemas de afianzamiento de contenidos propuestos por los profesores. c) Estudio intenso y continuado con aplicación e interés.
12	Actividades de evaluación	4	Exámenes

ID/Orden	Tarea/Actividad	Medios, técnicas e instrumentos	Ponderación
1	Prueba de Medio Semestre	Prueba teórica escrita.	20
2	Asignaciones de Prácticas	Entrega de productos generados durante el desarrollo de las prácticas (normalmente código de programa) según los planteamientos de las asignaciones de prácticas. Rúbricas, etc.	10
3	Examen Final	Examen escrito	70

ID/Orden	Tema	Descripción
1	Tema 1: Modelos de Funciones Computables. Preliminares matemáticos. Concepto de Modelo. Modelos de Computación vs. lenguajes de programación. En qué se parecen y en qué se diferencian, y por qué son necesarios. El modelo de Davis: memoria, instrucciones e instancias. Estados, espacio de estados, y configuraciones. Trayectorias en el espacio de estados: computaciones. Funciones computables en sentido parcial y total. Ejemplos de funciones computables. Haciendo la vida más fácil: macros y su expansión. Predicados computables. El modelo URM de Sheperdson y Sturgis: análisis y definición de computabilidad. El modelo Loop de Meyer y Ritchie: análisis y definición de computabilidad. Alcance de los modelos estudiados y relaciones entre modelos.
2	Tema 2: Aproximaciones Funcionales a la Computabilidad. Lambda-cálculo: una nota elemental. La jerarquía de funciones: operadores de combinación de funciones computables: composición y recursión primitiva simple y generalizada. Teoremas de composición y recursión. Ejemplos. La teoría de funciones recursivas de Kleene: funciones iniciales y clases PRC. Computabilidad de las funciones iniciales. La clase PRC más simple: funciones recursivas primitivas. Un teorema de caracterización. Ejemplos de funciones recursivas primitivas. ¿Es posible expresar la computabilidad únicamente en base a la recursividad primitiva? Por qué no es posible. Límites de los operadores de combinación y necesidad de uno nuevo: operaciones iteradas, cuantificadores acotados y funciones de minimización acotada y no acotada. Por qué en Informática todo cálculo se reduce a reescritura: Teoremas de las Formas Normales. Algo sobre codificación: función de emparejamiento y numeración de Gdel.
3	Tema 3: Universalidad Codificación numérica en el modelo de Davis. Razonar sobre instancias del modelo de Davis y sobre números es lo mismo: codificación. Problemas de decisión; propiedades. Límites de la computabilidad: el problema de la parada y resultados similares. Por qué los computadores son programables: definición de las funciones universales y prueba del Teorema de Universalidad. Predicados contadores de pasos. Computabilidad en conjuntos: conjuntos recursivos enumerables y recursivos. Relaciones. Un teorema de caracterización. Teorema de Enumeración. Otros resultados de interés: teoremas s-m-n y de Rice. Aplicaciones del Teorema de Rice.
4	Tema 4: Máquinas de Turing. Computabilidad con cadenas. El modelo de Post. La gran intuición de Turing: la máquina de registros y control de estado, o cómo poner programas y datos juntos en memoria. Cómo todo conocimiento puede reducirse a una lista de caracteres carentes de significado. Definición de Turing-computabilidad y Tesis de Church-Turing en un contexto de funciones Turing-computables. ¿Son más potentes las máquinas de Turing que otros modelos? Modelos alternativos a la máquina estándar: máquinas no deterministas, de varias cintas, de varias pistas, etc., o de cómo rizar el rizo para acaba en el mismo sitio. Máquinas de Turing Universales y arquitectura de Von-Neumann: relaciones. Conjuntos r.e. y máquinas de Turing.
7	PROGRAMA DE PRÁCTICAS DE LA ASIGNATURA Desarrollo de modelos reticulares de sistemas complejos utilizando algún modelo de computación adecuado, y/o uso de simuladores de modelos funciones computables.

Volver

UniversidaddeCádiz

Programas Docentes de Asignaturas

Programas Docentes de Asignaturas

Programa docente (2025-26) | <21714025 | MODELOS DE COMPUTACIÓN>

Servicio de Organización Académica y Planificación PDI