template-browser-not-supported

Doble Grado en Ingeniería Informática del Software / Grado en Matemáticas

Back Back

Autómatas y Matemáticas Discretas

Código asignatura
2GIISMAT-1-009
Curso
Primero
Temporalidad
Segundo Semestre
Carácter
Formación Básica
Créditos
6
Pertenece al itinerario Bilingüe
Yes
Actividades
  • Clases Expositivas (28 Hours)
  • Prácticas de Aula/Semina (14 Hours)
  • Prácticas de Laboratorio (14 Hours)
  • Tutorías Grupales (2 Hours)
Guía docente

La Asignatura de Autómatas y Matemáticas Discretas está incluida en la materia del Grado denominada Fundamentos Informáticos, dentro del módulo de Formación Básica. Puede considerarse como una asignatura básica de servicio dentro del Grado de Informática. Los conceptos y métodos que en ella se presentan sirven de ayuda para la comprensión y justificación de cuestiones tratadas en otras materias. Así, diversos aspectos de la teoría de grafos son aprovechados en asignaturas como Estructuras de Datos (2º curso), en el estudio de las estructuras no lineales y algunas estrategias de búsqueda; o en Algoritmia (2º curso) en la presentación de algunas de las técnicas de diseño de algoritmos. El estudio de los Lenguajes Formales, así como los correspondientes dispositivos reconocedores ó generadores,  resulta de gran utilidad a la hora de comprender algunas de las tareas presentes en todo proceso de compilación de un programa, y más concretamente el análisis sintáctico y semántico del mismo. Estas cuestiones se tratan en profundidad en la asignatura de Diseño de Lenguajes de Programación (3º curso) y en menor medida en algunos aspectos de Sistemas Inteligentes (4º curso). En lo que respecta a asignaturas del mismo curso, Autómatas y Matemáticas Discretas tiene interrelación con la asignatura de Álgebra Lineal. Los conceptos básicos sobre funciones, como el dominio, rango o las propiedades de inyectividad y suprayectividad, resultan de gran utilidad para la asignatura de Autómatas. Asimismo las técnicas de demostraciones ó métodos de prueba y la dinámica notacional, son de gran importancia para la buena comprensión de algunas de las demostraciones teóricas que se realizan. Finalmente, la asignatura de Autómatas tiene una continuación natural en la asignatura de segundo curso denominada Computabilidad. El conjunto de las dos asignaturas constituye la justificación teórica de aspectos importantes de la Informática y debería hacer reflexionar al alumno sobre cómo se produjo el origen y desarrollo de la misma.

La formación que aporta el bachillerato por la rama tecnológica es suficiente para el seguimiento de la asignatura. En cualquier caso al ser ésta una asignatura del segundo semestre del primer curso, el alumno ya ha cursado Fundamentos de Informática, con lo que también posee los conocimientos suficientes de programación y manejo de ordenadores a nivel usuario para la realización de las tareas propias de Autómatas y Matemáticas Discretas. Asimismo, sería recomendable haber cursado con éxito la asignatura de Algebra, que también se imparte en el primer semestre, donde se adquieren conocimientos de utilidad para la comprensión de los conceptos que se imparten en Autómatas y Matemáticas Discretas.

Según la memoria de verificación, las competencias a alcanzar por los estudiantes en cuyo desarrollo colabora la asignatura de Autómatas y Matemáticas Discretas son las siguientes:

Competencias generales

CG3:   Abstracción

CG5:   Análisis, selección y utilización de herramientas informáticas básicas y de apoyo

CG7:   Destreza en la expresión escrita

CG18: Sentido de la responsabilidad

CG19:  Hábitos de trabajo efectivos

Competencias específicas de formación básica

Bas.3:Capacidad para comprender y dominar los conceptos básicos de Autómatas y matemáticas discretas y su aplicación para la resolución de problemas propios de la ingeniería.

Bas.4 Conocimientos básicos sobre el uso y programación de los ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.

Competencias específicas comunes a la rama de informática

Com 6: 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

Los resultados de aprendizaje esperados, relacionados con la asignatura son los siguientes:

  1. Comprender y dominar los conceptos básicos de matemática discreta, y de los lenguajes formales, así como sus correspondientes dispositivos generadores ó reconocedores.
  2. Adquirir conocimientos básicos sobre uso y programación de aplicaciones informáticas relacionadas con la manipulación de estructuras asociadas a los lenguajes formales.
  3. Saber diseñar soluciones apropiadas para los problemas relacionados con la asignatura.
  4. Elaborar documentos técnicos que describan adecuadamente las soluciones a los problemas planteados

Tema 1 Lenguajes Regulares

  1. Introducción y conceptos básicos
  2. Expresiones regulares
  3. Autómatas finitos deterministas, no deterministas y con l-movimientos
  4. Propiedades de los lenguajes regulares

Tema 2 Lenguajes Libres de Contexto

  1. Introducción y conceptos básicos
  2. Gramáticas libres de contexto
  3. Simplificación de gramáticas y formas normales
  4. Autómatas con pila
  5. Propiedades de los lenguajes libres de contexto

Tema 3 Grafos

  1. Introducción y conceptos básicos
  2. Accesibilidad y conexión
  3. Recorridos en grafos
  4. Árboles
  5. Planaridad y coloreado

Tema 4 Lenguajes Recursivos y Recursivamente Enumerables

  1. Introducción y conceptos básicos
  2. Máquinas de Turing
  3. Jerarquía de Chomsky

De acuerdo con las pautas que establece el EEES, la asignatura se desarrollará mediante actividades presenciales y trabajo autónomo del estudiante.

Las actividades presenciales son aquellas en las que estará siempre presente el profesor. Se dividen en clases expositivas, seminarios, prácticas de laboratorio, tutorías grupales y sesiones de evaluación.

  • Clases expositivas: Impartidas al grupo completo, no necesariamente como lección magistral, sino procurando una participación activa del alumno en la dinámica de las mismas. En estas clases se desarrollarán contenidos teóricos de la asignatura, combinados con alguna resolución de pequeños ejercicios. Se utilizará la pizarra y los diferentes medios audiovisuales.
  • Seminarios: Impartidos a grupos más reducidos, aproximadamente la mitad de un grupo completo. En estas sesiones se tratarán de afianzar los conocimientos presentados en las clases expositivas, describiendo ejemplos y realizando ejercicios así como algunas de las demostraciones de los resultados más importantes. La participación del alumno será de mayor intensidad en los seminarios.
  • Prácticas de Laboratorio:Dedicadas a resolver problemas prácticos utilizando el PC.  Se desarrollarán en varios grupos, de manera eminentemente participativa.
  • Tutorías grupales:Dedicadas a la aclaración de dudas sobre teoría, problemas o trabajos en curso, estas actividades podrán servir para ir comprobando de forma continuada el grado de adquisición de competencias y destrezas por parte del alumno. Se desarrollarán en varios grupos, disponiendo por tanto los estudiantes de una atención algo más personalizada por parte  del profesor
  • Sesiones de evaluación:Se dedicarán exclusivamente a la realización de pruebas escritas o bien con un PC, con las que se pueda valorar de forma objetiva el nivel alcanzado por los estudiantes en la adquisición de algunas de las competencias previstas.

Por su parte, a fin de cumplir los principios referentes a ECTS, establecidos en el Real Decreto 1393/2007, el estudiante deberá desarrollar un trabajo autónomo paralelo (actividades no presenciales), dirigido por el profesor.

La metodología docente a emplear estará fuertemente basada en la participación activa del alumno. Así, de manera periódica, se propondrán entregables que el alumno deberá realizar. Dichos entregables serán claros en su enunciado, supondrán tareas asequibles y sobre todo irán acompañados de un tiempo de ejecución. La estrategia a seguir es plantear los entregables siguiendo estas pautas y siendo estrictos en cuanto a la fecha de entrega de los mismos, con el objeto de que el alumno también sea consciente de la necesidad de asumir unos compromisos con los cuales cumplir posteriormente.

El proceso general de actuación del alumno para las actividades no presenciales relacionadas con la elaboración de los entregables propuestos, puede seguir las siguientes pautas:

  1. Selección y lectura del material necesario.
  2. Planteamiento de las dudas surgidas, si las hubiera.
  3. Elaboración del enunciado de la cuestión o problema a proponer, si procede.
  4. Resolución del problema propuesto.
  5. Reflexión sobre la resolución del problema y descripción de las dificultades encontradas.
  6. Preparación de la documentación a entregar.
  7. Anotación del tiempo empleado en cada una de las actividades, así como el tiempo total.

Asimismo, al final de cada uno de los temas se realizarán pequeños controles sobre los mismos, con el objeto de conocer el grado de adquisición de las competencias cognitivas más relacionadas con los contenidos de la asignatura.

Con respecto a las prácticas de laboratorio, al finalizar cada una de las prácticas programadas, el alumno debe elaborar un informe para entregarlo posteriormente al profesor. También podrían plantearse ocasionalmente algunos ejercicios para entregar al final de la sesión de prácticas.

            A continuación se presentan una serie de tablas que especifican la temporalidad de las actividades tanto presenciales como no presenciales:

Volumen de trabajo estimado para el estudiante

MODALIDADES

Horas

ECTS

%

Presencial

Clases expositivas

28

1.12

18.8%

Seminarios

14

0.56

9.3%

Prácticas de Laboratorio

14

0.56

9.3%

Tutorías grupales

2

0.08

1.3%

Sesiones de evaluación

2

0.08

1.3%

Total

60

2.40

40%

No presencial

Estudio de teoría

30

1.20

20%

Resolución de problemas

25

1.00

17%

Preparación de prácticas de ordenador

25

1.00

17%

Preparación de entregables

10

0.40

6%

Total

90

3.60

60%

Total

150

6.00

100%

Distribución del trabajo por temas

TRABAJO PRESENCIAL

TRABAJO NO

PRESENCIAL

Temas

Horas totales

Clase Expositiva

Prácticas de aula /Seminarios/

Prácticas de laboratorio

Tutorías grupales

Sesiones de Evaluación

Total

Trabajo autónomo

Total

Lenguajes Regulares

50

9

5

6

20

30

30

Lenguajes Libres de Contexto

49

9

4

6

19

30

30

Leng. R. y R.E.

5

1

1

2

3

3

Grafos

42

9

4

2

15

27

27

4

2

2

4

Total

150

28

14

14

2

2

60

90

90

Evaluación en la convocatoria ordinaria

En la evaluación ordinaria se utilizarán diversos procedimientos que permitirán el seguimiento continuo del proceso de aprendizaje del alumno. 

            Los diferentes procedimientos evaluadores serán los siguientes:

1.    Dos tests (20% en total) al final de los dos primeros temas y un entregable (20%) al final del último tema. 

2.    Examen final (30%)

3.    Prácticas de laboratorio (30%): formado por dos controles prácticos con un peso del 12% el primero y un 18% el segundo.

La calificación final de la asignatura se calculará sumando las notas ponderadas obtenidas en los apartados anteriores. Aquellos alumnos que no hayan asistido al menos al 80% de las sesiones prácticas no obtendrán ningún punto en ese apartado.Es condición necesaria para aprobar, obtener al menos 4 puntos sobre 10 en la parte de parte de prácticas y en el conjunto de la parte teórica (entregables, tests y examen final). En caso contrario, la nota de la asignatura será el mínimo entre 4 y la media ponderada Para superar la convocatoria la calificación final debe ser de al menos un 5 sobre 10.

Se considerará que un alumno se ha presentado en la convocatoria ordinaria siempre que haya realizado actividades de evaluación que supongan, en total, más del 50% de la nota final.   

En caso de no aprobar la asignatura durante la convocatoria ordinaria, las notas obtenidas en la parte de teoría y de práctica podrán conservarse, si son iguales o superiores a 4, para la convocatoria extraordinaria del mismo curso académico.

Evaluación en las convocatorias extraordinarias

En las convocatorias de carácter extraordinario el alumno debe realizar los siguientes exámenes:

  1. Examen teórico (70% de peso en la nota final)
  2. Examen de prácticas (30% de peso en la nota final)

Al igual que en el caso de la convocatoria ordinaria, es condición necesaria para aprobar obtener al menos 4 puntos sobre 10 tanto en el examen de prácticas como en el de teoría. En caso contrario, la nota de la asignatura será el mínimo entre 4 y la media ponderada Para superar la convocatoria la calificación final debe ser de al menos un 5 sobre 10.

Evaluación diferenciada

Los estudiantes con régimen de dedicación a tiempo parcial, semipresencial y no presencial que lo hayan solicitado previamente tendrán derecho a una evaluación diferenciada. Esta evaluación constará de un examen teórico y uno práctico, con los siguientes porcentajes sobre la nota final:

  • Examen de teoría: 70%
  • Examen de prácticas: 30%

Es condición necesaria para aprobar obtener al menos 4 puntos sobre 10 tanto en el examen de prácticas como en el de teoría. En caso contrario, la nota de la asignatura será el mínimo entre 4 y la media ponderada Para superar la convocatoria la calificación final debe ser de al menos un 5 sobre 10.

  1. Rosen, K.H.: Discrete Mathematics and its applications. 5th edition. McGraw-Hill, 2003
  2. Hopcroft, J.E.; Motwanni, R.; Ullman, J.D., Introducción a la Teoría de Autómatas, Lenguajes y Computación. Segunda edición, Ed. Addison-Wesley, 2001.
  3. Kelley, D., Teoría de Autómatas y Lenguajes Formales. Ed. Prentice Hall, 1995.