Guía docente de la asignatura

Modelos de Computación

Curso 2021 / 2022
Fecha última actualización: 21/06/2021
Fecha de aprobación: 21/06/2021

Grado

Grado en Ingeniería Informática (Ceuta)

Rama

Ingeniería y Arquitectura

Módulo

Formación Específica de Rama

Materia

Programación e Ingeniería del Software

Curso

3

Semestre

1

Créditos

6

Tipo

Obligatoria

Profesorado

Teoría

  • Carlos Cano Gutiérrez. Grupos: A
  • Francisco Javier Rodríguez Díaz. Grupos: A

Tutorías

Carlos Cano Gutiérrez

carloscano@ugr.es
  • Primer semestre
    • Lunes de 15:30 a 17:30 (Ceuta)
    • Martes de 10:00 a 14:00 (Ceuta)
  • Segundo semestre
    • Martes de 10:00 a 14:00 (Ceuta)
    • Miércoles de 10:00 a 12:00 (Ceuta)

Francisco Javier Rodríguez Díaz

fjrodriguez@ugr.es
  • Primer semestre
    • Jueves de 10:30 a 13:30 (Ceuta)
    • Miércoles de 10:30 a 13:30 (Ceuta)
  • Segundo semestre
    • Martes de 15:30 a 21:30 (Ceuta)

Prerrequisitos y/o Recomendaciones

Los estudiantes no tendrán que tener asignaturas, materias o módulos aprobados como requisito indispensable para cursar el módulo. No obstante, se recomienda la superación de los contenidos y adquisición de competencias de las materias de formación básica.

Breve descripción de contenidos (Según memoria de verificación del Grado)

  • Introducción a la Computación.
  • Autómatas Finitos y Expresiones Regulares.
  • Gramáticas Libres del Contexto.
  • Autómatas con PILA.
  • Lenguajes Libres del Contexto Determinísticos.
  • Lenguajes Dependientes del Contexto.

Competencias asociadas a materia/asignatura

Competencias generales

  • CG09 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.

Competencias específicas

  • CE12 - Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.

Resultados de aprendizaje (Objetivos)

  • Usar con soltura el lenguaje matemático, comprender y generar demostraciones relacionadas con los contenidos.
  • Clasificar los lenguajes según el tipo de gramática o máquina requerido.
  • Conocer las relaciones de jerarquía entre clases de lenguajes.
  • Analizar cuál es el lenguaje generado por una gramática, descrito por una expresión regular o reconocido por una máquina teórica.
  • Diseñar autómatas finitos, con pila o máquinas de Turing como modelos para resolver problemas relacionados con el reconocimiento de lenguajes.
  • Conocer la relación entre lenguajes y entre máquinas, así como la equivalencia entre distintos tipos de máquinas teóricas y la equivalencia entre máquinas y gramáticas.
  • Aplicar algoritmos para realizar conversiones entre especificaciones igual de potentes para un lenguaje.
  • Evaluar cuál es la máquina más adecuada para reconocer un lenguaje, atendiendo a la dificultad de tratamiento computacional.
  • Conocer los límites de los procesos computacionales y la implicación práctica de la irresolubilidad o intratabilidad de un problema abstracto.
  • Conocer la relación entre problemas, funciones y algoritmos, así como la equivalencia entre distintos modelos de computación.
  • Aplicar diversos modelos de computación para el cálculo de funciones numéricas o con cadenas.

Programa de contenidos teóricos y prácticos

Teórico

Tema 1: Introducción a la computación.

  • Conceptos Elementales
  • Modelos de Cálculo
  • La noción de Gramática Generativa
  • Operaciones con Lenguajes

Tema 2: Autómatas Finitos y Expresiones Regulares

  • Autómatas Finitos Deterministas
  • Autómatas No-Deterministas
  • Expresiones Regulares
  • Gramáticas Regulares

Tema 3: Propiedades de los Conjuntos Regulares

  • Lema de Bombeo y Aplicaciones
  • Minimización de Autómatas

Tema 4: Gramáticas Independientes del Contexto

  • Introducción
  • Arboles de Derivación. Ambigüedad
  • Simplificación de Gramáticas
  • Formas Normales

Tema 5: Autómatas con Pila

  • Definiciones
  • Autómatas con Pila y Lenguajes Libres del Contexto
  • Autómatas con Pila Deterministas

Tema 6. Propiedades de los Lenguajes Independientes del Contexto.

  • Lema de Bombeo.
  • Propiedades de Clausura.
  • Algoritmos.

Tema 7. Máquinas de Turing

  • Máquinas de Turing
  • Lenguajes recursivos y recursivamente enumerables
  • El problema de la parada para máquinas de Turing

Práctico

Prácticas

  • PRÁCTICA 1: Resolución de problemas relacionados con Autómatas Finitos y Expresiones Regulares
  • PRÁCTICA 2: Resolución de problemas relacionados con Gramáticas Independientes del Contexto y Autómatas con Pila.
  • PRÁCTICA 3: Resolución de Problemas relacionados con Máquinas de Turing.

Seminarios

  • SEMINARIO 1: LEX
  • SEMINARIO 2: JFLAP

Bibliografía

Bibliografía fundamental

  • A.V. Aho, J.D. Ullman, Foundations of Computer Science. W.H. Freeman and Company, New York (1992).
  • M. Alfonseca, J. Sancho. M. Matínez, Teoría de Autómatas y Lenguajes Formales. Publicaciones R.A.E.C., Textos Cátedra (1997).
  • J.G. Brookshear, Teoría de la Computación. Lenguajes formales, autómatas y complejidad. Addison Wesley Iberoamericana (1993).
  • J. Carrol, D. Long, Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall (1989)
  • D.I. Cohen, Introduction to Computer Theory. John Wiley, Nueva York (1991).
  • M.D. Davis, E.J. Weyuker, Computability, Complexity, and Languages. Academic Press (1983)
  • M.D. Davis, R. Sigal, E.J. Weyuker, Computability, Complexity, and Languages, 2 Edic.. Academic Press (1994)
  • M. Harrison, Introduction to Formal Language Theory. Addison-Wesley (1978)
  • J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)
  • J.E. Hopcroft, R. Motwani, J.D. Ullman, Introducción a la Teoría de Autómatas, Lenguajes y Computación. Addison Wesley (2002).
  • J.M. Howie, Automata and Languages. Oxford University Press, Oxford (1991)
  • D. Kelley, Teoría de Autómatas y Lenguajes Formales. Prentice Hall, Madrid (1995)
  • H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice Hall (1981)
  • G.E. Revesz, Introduction to Formal Laguages. Dover Publications, Nueva York (1991)
  • T.A. Sudkamp, Languages and Machines. Addison Wesley, Reading (1988)

Bibliografía complementaria

  • R.V. Book, F. Otto, String rewriting systems. Springer-Verlag, Nueva York (1993).
  • N.J. Cutland, Computability An introduction to recursive function theory, Cambridge University Press (1980).
  • D. Grune, C.J. Ceriel, Parsing techniques: a practical guide. Ellis Horwood, Chichester (1990).
  • B.I. Plotkin, J.L. Greenglaz, A.A. Gvarami, Algebraic structures in automata and database theory World Scientific, River Edge (1992).

Enlaces recomendados

Metodología docente

  • MD01 Lección Magistral (Clases Teóricas-Expositivas) 
  • MD02 Actividades Prácticas (Resolución de Problemas, Resolución de Casos Prácticos, Desarrollo de Proyectos, Prácticas en Laboratorio, Taller de Programación, Aula de Informática, Prácticas de Campo). 
  • MD03  Seminarios (Debates, Demos, Exposición de Trabajos Tutelados, Conferencias, Visitas Guiadas, Monografías). 
  • MD04 Actividades no presenciales Individuales. 
  • MD05 Actividades no presenciales Grupales. 
  • MD06 Tutorías Académicas. 

Evaluación (instrumentos de evaluación, criterios de evaluación y porcentaje sobre la calificación final)

Evaluación ordinaria

Para la parte teórica se realizará un examen final. La ponderación de este bloque es del 50%.

Para la parte práctica se realizarán prácticas de laboratorio, resolución de problemas y desarrollo de proyectos (individuales o en grupo), y se valorarán las entregas de los informes/memorias realizados por los alumnos, o en su caso las entrevistas personales con los alumnos, las sesiones de evaluación, asistencia y participación. La ponderación de este bloque es del 50%, compuesto por:

  • Notas de problemas: 30%.
  • Trabajos Personales, participación en clase y/o Exposición: 20%

La calificación global corresponderá por tanto a la puntuación ponderada de los diferentes aspectos y actividades que integran el sistema de evaluación. Por tanto, el resultado de la evaluación será una calificación numérica obtenida mediante la suma ponderada de las calificaciones correspondientes a una parte teórica, una parte práctica y, en su caso, una parte relacionada con el trabajo autónomo de los alumnos, los seminarios impartidos. Se exigirá una nota mínima de 3.5 sobre 10 puntos tanto en la parte práctica como en la teórica para realizar la suma ponderada.

La asistencia a clase no es obligatoria. Por tanto, la no asistencia no repercutirá en la nota final.

Todo lo relativo a la evaluación se regirá por la normativa sobre planificación docente y organización de exámenes vigente en la Universidad de Granada.

El sistema de calificaciones se expresará mediante calificación numérica de acuerdo con lo establecido en el art. 5 del R. D 1125/2003, de 5 de septiembre, por el que se establece el sistema europeo de créditos y el sistema de calificaciones en las titulaciones universitarias de carácter oficial y validez en el territorio nacional.

Evaluación extraordinaria

En la convocatoria extraordinaria habrá un examen de teoría y otro de prácticas. Cada uno se evaluará sobre 10. La nota final será la media aritmética de las dos notas. Se necesitará un mínimo de 3.5 en cada una de las partes.

Evaluación única final

De acuerdo a lo establecido en la Normativa de evaluación y de calificación de los estudiantes de la Universidad de Granada vigente, la evaluación será preferentemente continua. No obstante, el estudiante que no pueda acogerse a dicho sistema por motivos laborales, estado de salud, discapacidad, programas de movilidad o cualquier otra causa debidamente justificada podrá acogerse a la evaluación única final. Para ello deberá solicitarlo al Director del Departamento o al Coordinador del Máster en las dos primeras semanas de impartición de la asignatura o, excepcionalmente, en las dos primeras semanas tras la matriculación en la asignatura.

Esta modalidad de evaluación se realizará en un único acto académico en la fecha establecida por el Centro y consistirá en un examen escrito (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente.

Información adicional

ESCENARIO A (ENSEÑANZA-APRENDIZAJE PRESENCIAL Y TELE-PRESENCIAL)

Horario (Según lo establecido en el POD)

Pulse el siguiente enlace para consultar lugar y horario de tutorías: https://decsai.ugr.es/index.php?p=profesores

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

La atención tutorial se realizará preferentemente online mediante las plataformas y herramientas que recomiende la Universidad de Granada.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

  • La proporción entre clases virtuales y presenciales dependerá de las circunstancias sanitarias. En las clases virtuales se concentraría la enseñanza de índole teórica, en las presenciales se primará la impartición de prácticas.
  • Las sesiones prácticas y de teoría se impartirán utilizando aulas de tamaño suficiente para cumplir las directrices sanitarias. En el caso que no se disponga de aulas con el aforo efectivo suficiente las sesiones prácticas se impartirán virtualmente.
  • Las clases virtuales se impartirán utilizando las plataformas que recomiende la Universidad de Granada. Se primará la impartición síncrona, aunque las circunstancias sanitarias (enfermedad del profesor o familiar, conciliación familiar…) podrían imponer un escenario asíncrono, en cuyo caso, las clases se complementarían con actuaciones de seguimiento y retorno formativo específicas para ese fin (tutorías, tareas, entregas…)
  • Como medida adicional, se prestará especial atención en facilitar material docente a los estudiantes a través de las plataformas online que recomiende la Universidad de Granada.

Evaluación ordinaria

Para la parte teórica se realizará un examen final. La ponderación de este bloque es del 50%.

Para la parte práctica se realizarán prácticas de laboratorio, resolución de problemas y desarrollo de proyectos (individuales o en grupo), y se valorarán las entregas de los informes/memorias realizados por los alumnos, o en su caso las entrevistas personales con los alumnos, las sesiones de evaluación, asistencia y participación. La ponderación de este bloque es del 50%, compuesto por:

  • Notas de problemas: 30%.
  • Trabajos Personales, participación en clase y/o Exposición: 20%

La calificación global corresponderá por tanto a la puntuación ponderada de los diferentes aspectos y actividades que integran el sistema de evaluación. Por tanto, el resultado de la evaluación será una calificación numérica obtenida mediante la suma ponderada de las calificaciones correspondientes a una parte teórica, una parte práctica y, en su caso, una parte relacionada con el trabajo autónomo de los alumnos, los seminarios impartidos. Se exigirá una nota mínima de 3.5 sobre 10 puntos tanto en la parte práctica como en la teórica para realizar la suma ponderada.

La asistencia a clase no es obligatoria. Por tanto, la no asistencia no repercutirá en la nota final.

Las pruebas tendrán lugar, si la situación lo permite, de forma presencial. Si no fuese posible las pruebas se llevarán a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.

Evaluación extraordinaria

En la convocatoria extraordinaria habrá un examen de teoría y otro de prácticas. Cada uno se evaluará sobre 10. La nota final será la media aritmética de las dos notas. Se necesitará un mínimo de 3.5 en cada una de las partes.

Las pruebas tendrán lugar, si la situación lo permite, de forma presencial. Si no fuese posible las pruebas se llevarán a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.

Evaluación única final

Esta modalidad de evaluación se realizará en un único acto académico en la fecha establecida por el Centro y consistirá en un examen escrito (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente.

Las pruebas tendrán lugar, si la situación lo permite, de forma presencial. Si no fuese posible las pruebas se llevarán a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.

ESCENARIO B (SUSPENSIÓN DE LA ACTIVIDAD PRESENCIAL)

Horario (Según lo establecido en el POD)

Pulse el siguiente enlace para consultar lugar y horario de tutorías: https://decsai.ugr.es/index.php?p=profesores

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

La atención tutorial se realizará preferentemente online mediante las plataformas y herramientas que recomiende la Universidad de Granada.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

Todas las clases serán virtuales. Se impartirán utilizando las plataformas que recomiende la Universidad de Granada. Se primará la impartición síncrona, aunque las circunstancias sanitarias (enfermedad del profesor o familiar, conciliación familiar…) podrían imponer un escenario asíncrono, en cuyo caso, las clases se complementarían con actuaciones de seguimiento y retorno formativo específicas para ese fin (tutorías, tareas, entregas…)

Como medida adicional, se prestará especial atención en facilitar material docente a los estudiantes a través de las plataformas online que recomiende la Universidad de Granada.

Evaluación ordinaria

Para la parte teórica se realizará un examen final. La ponderación de este bloque es del 50%.

Para la parte práctica se realizarán prácticas de laboratorio, resolución de problemas y desarrollo de proyectos (individuales o en grupo), y se valorarán las entregas de los informes/memorias realizados por los alumnos, o en su caso las entrevistas personales con los alumnos, las sesiones de evaluación, asistencia y participación. La ponderación de este bloque es del 50%, compuesto por:

  • Notas de problemas: 30%.
  • Trabajos Personales, participación en clase y/o Exposición: 20%

La calificación global corresponderá por tanto a la puntuación ponderada de los diferentes aspectos y actividades que integran el sistema de evaluación. Por tanto, el resultado de la evaluación será una calificación numérica obtenida mediante la suma ponderada de las calificaciones correspondientes a una parte teórica, una parte práctica y, en su caso, una parte relacionada con el trabajo autónomo de los alumnos, los seminarios impartidos. Se exigirá una nota mínima de 3.5 sobre 10 puntos tanto en la parte práctica como en la teórica para realizar la suma ponderada.

La asistencia a clase no es obligatoria. Por tanto, la no asistencia no repercutirá en la nota final.

La prueba se llevará a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.

Evaluación extraordinaria

En la convocatoria extraordinaria habrá un examen de teoría y otro de prácticas. Cada uno se evaluará sobre 10. La nota final será la media aritmética de las dos notas. Se necesitará un mínimo de 3.5 en cada una de las partes.

La prueba se llevará a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.

Evaluación única final

Esta modalidad de evaluación se realizará en un único acto académico en la fecha establecida por el Centro y consistirá en un examen escrito (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente.

La prueba se llevará a cabo a través de la plataforma online seleccionada por la Universidad de Granada, siempre siguiendo las instrucciones que se dicten al respecto por la Universidad de Granada.