Universidad
de
Cádiz
Programas Docentes de Asignaturas
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:
21714025 (P) - Mat.[27 [nuevos: 27 | repetidores: 0)]
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
REQ. Y RECOM.
PROFESORADO
IDIOMAS
MOVILIDAD
RESULTADOS FORM./APREN.
RES. DE APRENDIZAJE
ACT. Y MET. DOC.
SIST. DE EVALUACIÓN
TEMARIO
BIBLIOGRAFÍA
COMENTARIOS
Requisitos y recomendaciones
Requisitos previos
Recomendaciones
Profesorado
Primer apellido
Segundo apellido
Nombre
Categoría/Empresa
Coordinación
TOMEU
HARDASMAL
ANTONIO J.
PROFESOR TITULAR DE UNIVERSIDAD
Idiomas
Oferta en lengua extranjera
Idioma
Seleccione una opción
Inglés
Francés
Italiano
Alemán
Ruso
Árabe
Griego
Modo de impartición
Seleccione una opción
A impartir sólo en ese idioma según memoria (exclusividad).
A impartir en grupo dedicado a ese idioma.
A impartir en grupo mixto (un mismo grupo con ambos idiomas).
Nivel requerido
Seleccione una opción
A1
A2
B1
B2
C1
C2
Movilidad
Movilidad nacional (SICUE)
Presencialidad
Seleccione una opción
Presencial
Combinada
Virtual
Movilidad internacional
Presencialidad
Seleccione una opción
Presencial
Combinada
Virtual
Estudiante visitante nacional
Número de plazas
Presencialidad
Seleccione una opción
Presencial
Combinada
Virtual
Resultados del proceso de formación y aprendizaje
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
Resultados de aprendizaje
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.
Actividades y metodologías docentes
Horas totales de actividades de docencia presencial
60,00
Horas totales de otras actividades
90,00
Horas totales de la asignatura
150,00
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
Sistema de evaluación
Procedimientos de evaluación
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
Criterios de evaluación
Temario
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.
Bibliografía
Bibliografía
Comentarios
Comentarios/Observaciones adicionales
Volver
×
Cargando...
Realizando operación...
Esto puede tardar unos minutos. Por favor, espere hasta que termine.