logo UGR Departamento de Ciencias de la Computación e Inteligencia Artificial
Universidad de Granada
Escuela Técnica Superior de Ingenierías Informática y de Telecomunicación
c/. Daniel Saucedo Aranda, s/n 18071 Granada España
logo decsai

Ingeniería Informática

Modelos de Computación II (Extinta)

Curso 2017/2018


Curso: 2º, Segundo Cuatrimestre

Créditos de Teoría: 0, Créditos de Prácticas: 0

PROGRAMA DE TEORÍA
Tema 1. Introducción a la computabilidad

    * Planteamiento del problema
    * Breve historia de la computabilidad

Tema 2. Programas y Funciones Calculables

    * Un lenguaje de programación ()
    * Ejemplos de programas
    * Sintaxis
    * Funciones Computables
    * Macros

Tema 3: Funciones Recursivas

    * Composición
    * Recursividad
    * Clases PRC (cerradas por recursividad primitiva)
    * Algunas funciones recursivas primitivas
    * Predicados primitivos recursivos
    * Operaciones iteradas y cuantificadores acotados
    * Minimización

Tema 4. Codificación de Programas. Programa Universal

    * Números de código de Gödel
    * Codificación de programas mediante números
    * El problema de la parada
    * Universalidad
    * Conjuntos recursivamente enumerables
    * El teorema del parámetro
    * El segundo teorema de recursión
    * El teorema de Rice

Tema 5. Cálculo con cadenas

    * Representación de cadenas usando números
    * Un lenguaje de programación para el cálculo con cadenas
    * Equivalencia entre y
    * Programas de Post-Turing (el lenguaje
    * Simulación de en
    * Simulación de en .
    * Tesis de Church-Turing

Tema 6. Máquinas de Turing

    * Máquinas de Turing
    * Máquinas de Turing Universales
    * Lenguajes recursivos y recursivamente enumerables
    * El problema de la parada para máquinas de Turing
    * Máquinas de Turing no determinísticas
    * Máquinas de Turing modificadas

Tema 7. Introducción a la Complejidad Algorítmica

    * Planteamiento del problema. Complejidad en tiempo y en espacio.
    * Equivalencia polinomial de modelos de cómputo
    * P versus NP: NP-completitud

Tema 8. Introducción a las redes neuronales

    * Procesadores elementales. Redes Neuronales Artificiales.
    * Fundamentos de RNA.
    * Métodos de entrenamiento.
    * Modelos de Redes Neuronales.

PROGRAMA DE PRÁCTICAS
  Se realizarán ejercicios en clase, y prácticas sobre modelos de RNAs en el laboratorio.
BIBLIOGRAFÍA
    * N.J. CUTLAND: Computability An introduction to recursive function theory. Cambridge University Press (1980).
    * M.D. DAVIS y E.J. WEYUKER: Computability, Complexity, and Languages. Academic Press (1983).
    * H.R. LEWIS y C.H. PAPADIMITRIOU: Elements of the Theory of Computation. Prentice-Hall (1981).
    * M. R. GAREY y D.S. JOHNSON: Computers and Intractability A Guide to the theory of NP-Completeness. Freeman (1979).
    * B. MULLER y J. BEINHARDT. Neural Network an Introduction. Springer-Verlag, 1990.
MÉTODO DE EVALUACIÓN
Se entregará una práctica individual, se realizará un examen al final del curso, y además se podrán entregar diversos trabajos voluntarios sugeridos a lo largo del curso . El examen estará dividido en parte de teoría y parte de problemas (al cincuenta por ciento para el calculo de la nota). Las prácticas podrán modificar la nota del examen hasta en un 40 por ciento. Los trabajos voluntarios podrán incrementar la nota final hasta 2 puntos