
Teoría de la Computación
Código: 107891Créditos: 6
| Titulación | Tipo | Curso |
|---|---|---|
| Ingeniería Informática | FB | 1 |
Profesor/a de contacto
- Nombre :
- Joan Serra Sagrista
- Correo electrónico :
- joan.serra@uab.cat
Equipo docente
- Joaquim Borges Ayats
- Marc Masdeu Sabate
- Sebastià Mijares i Verdú
Idiomas de los grupos
Puede consultar esta información al final del documento.
Prerrequisitos
Aviso sobre el idioma de impartición y las traducciones de la guía docente:
- En principio, el idioma de impartición de todos los grupos de esta asignatura es el catalán.
- Se ofrecen traducciones automáticas de la guía docente al inglés y al castellano con fines informativos.
- En caso de discrepancia o incoherencia entre las versiones en distintos idiomas, prevalecerá siempre la versión en catalán, como referencia oficial.
Aunque no hay prerrequisitos oficiales es fundamental que los alumnos tengan muy buen dominio de las nociones más básicas de las matemáticas, como:
- Dominar la manipulación del lenguaje matemático
- Dominar las demostraciones por inducción y por contradicción
- Dominar la capacidad de abstracción
El alumnado que no tenga un mínimo bagaje de matemáticas previas tendrá que hacer un esfuerzo en preocuparse por resolver estas deficiencias.
Objetivos
- Ordenar las propiedades de los modelos formales en que se basan los ordenadores
- Identificar las posibilidades y los límites de la computación
- Adquirir buenos hábitos de programación
Resultados de aprendizaje
- CM05 (Integrar técnicas basadas en modelos computacionales en problemas de la informática) Integrar técnicas basadas en modelos computacionales en problemas de la informática
- KM09 (Explicar procedimientos algorítmicos de la teoría computacional para la resolución de problemas de ingeniería informática) Explicar procedimientos algorítmicos de la teoría computacional para la resolución de problemas de ingeniería informática
- SM13 (Aplicar conocimientos de autómatas, gramáticas y de complejidad computacional para la resolución de problemas) Aplicar conocimientos de autómatas, gramáticas y de complejidad computacional para la resolución de problemas
Contenidos
1. Lenguajes formales y modelos abstractos de cálculo.
1.1. Alfabetos, palabras y lenguajes.
1.2. Problemas, lenguajes formales y modelos de cálculo.
1.3. Sistemas digitales.
1.4. Métodos de demostración.
2. Autómatas finitos y lenguajes regulares.
2.1. Autómatas finitos deterministas.
2.2. Autómatas finitos no deterministas.
2.3. Operaciones, expresiones y lenguajes regulares.
2.4. Autómatas con salida.
3. Gramáticas independientes del contexto.
3.1. Introducción.
3.2. Definiciones. Generación de lenguajes.
3.3. Simplificación de gramáticas.
3.4. Formas normales de Chomsky y Greibach.
4. Autómatas con pila.
4.1. Descripción.
4.2. Aceptación por estado final y por pila vacía.
4.3. Autómatas con pila y lenguajes independientes del contexto.
4.4. Propiedades de los lenguajes independientes del contexto.
5. Máquinas de Turing.
5.1. Descripción del modelo básico.
5.2. Lenguajes y funciones calculables.
5.3. Variantes de la máquina de Turing.
5.4. Hipótesis de Church. Máquina de Von Neumann.
6. Indecidibilidad.
6.1. Problemas y lenguajes decidibles e indecidibles.
6.2. Lenguajes recursivos y recursivamente enumerables.
6.3. Máquina universal de Turing y problemas indecidibles.
6.4. El problema de la correspondencia de Post y el problema de la parada.
6.5. Ejemplos de lenguajes no recursivos.
7. Complejidad computacional.
7.1. Introducción. Tipos de problemas.
7.2.Clases de complejidad.
7.3. NP-Completasa,
7.4. Algunos problemas NP-Completos.
Actividades formativas y Metodología
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Clases de Teoría y Problemas | 50 | 2 | CM05, KM09, SM13 |
| Preparación y trabajo autónomo | 26 | 1,04 | CM05, KM09, SM13 |
| Ejercicios propuestos en clase | 28 | 1,12 | CM05, KM09, SM13 |
| Estudio y preparación de las pruebas de evaluación | 38,5 | 1,54 | CM05, KM09, SM13 |
- Las sesiones se impartirán según la tipología de Prácticas de Aula (PAUL):
Discusión y realización de ejercicios y actividades en grupo o individuales.
- La metodología docente está orientada al aprendizaje de la materia de forma continuada. Actividades que se desarrollarán a lo largo del curso:
Sesiones de teoría y problemas, donde el profesorado suministrará información sobre los conocimientos y sobre estrategias para adquirir, ampliar y organizarlos. Se fomentará la participación activa del alumnado. Se realizará un seguimiento del aprendizaje mediante el desarrollo individual y/o en grupo de actividades de validación y logro.
Evaluación
Actividades de evaluación continuada
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Entrega de ejercicioys y/o actividades validación | 30 | 3,5 | 0,14 | CM05, KM09, SM13 |
| Prueba Parcial 1 | 35 | 2 | 0,08 | CM05, KM09, SM13 |
| Prueba Parcial 2 | 35 | 2 | 0,08 | CM05, KM09, SM13 |
- Durante el curso se irán haciendo una serie de entregas de ejercicios y/o actividades de validación. Las notas de estos ejercicios y/o actividades de validación supondrán el 30% de la nota final. Esta parte de la nota NO será recuperable.
- Habrá un primer examen parcial (Primer Parcial = P_1) antes de medio semestre en el que se evaluará el trabajo realizado hasta ese momento. La nota de este primer examen parcial aportará el 35% de la calificación final. Todos los estudiantes que hagan este examen ya no podrán ser calificados como NO EVALUABLE. Aquel estudiante que no haya hecho este examen no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, caso en que se permitirá hacer el examen de recuperación).
- Al final del semestre habrá un segundo examen parcial (Segundo parcial = P_2) en el que se evaluarán los conocimientos impartidos tras el primer parcial. La nota de este segunco examen parcial aportará el 35% de la calificación final. Todos los estudiantes que hagan este examen ya no podrán ser calificados como NO EVALUABLE. Aquel estudiante que no haya hecho este examen no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, caso en que se permitirá hacer el examen de recuperación).
- Aquel estudiante que no haya hecho ninguno de los dos exámens parciales será calificado como NO EVALUABLE a efectos académicos.
Calificación:
- Si la media de las notas (sobre 10) de los dos parciales M=(P_1+P_2)/2 es inferior a 2.5 el alumno ha suspendido la asignatura, con nota final M, sin derecho a ir al examen de recuperación.
- Si M es superior a 2,5 pero menor o igual 3.5 el alumno debe ir al examen de recuperación.
- Si M es superior o igual a 3,5, entonces si NF=0,7 M+ 0,3 S, (donde S es la nota media de la entrega de ejercicios y/o actividades de validación, sobre 10) es mayor o igual que 5 el alumno/a ha aprobado y tiene NF como nota final, en caso contrario debe ir al examen de recuperación.
- Si el alumno/a debe hacer el examen de recuperación, entonces si la nota de recuperación R, es inferior a 3.5, el alumno ha suspendido con nota final R; si R es superior o igual a 3,5 la nota final será min({0,7 R + 0,3 S},7) donde R es la nota del examen de recuperación (sobre 10).
- El uso de calculadora en los exámenes parciales y en el de recuperación NO está permitido.
- Podrán obtener la calificación de Matrícula de Honor el 5% de las notas más altas siempre que: la nota NF descrita antes supere 9. Estas condiciones de evaluación serán iguales para todos los estudiantes matriculados en la asignatura, independientemente de si son de primera matrícula o si ya se habían matriculado en cursos anteriores. La decisión final sobre la calificación de MH la decidirá el profesorado.
- Para cada actividad de evaluación (exámenes parciales y examen de recuperación), se indicará un lugar, fecha y hora de revisión en la que el estudiante podrá revisar la actividad con el profesorado. En este contexto, se podrán hacer reclamaciones sobre la nota de la actividad, que serán evaluadas por el profesorado responsable de la asignatura. Si el estudiante no se presenta a esta revisión, no se revisará posteriormente esta actividad. Las fechas de los exámenes parciales y del examen de recuperación se publicarán por parte de la Coordinación de la Titulación y pueden estar sujetas a posibles cambios de programación por motivos de adaptación a posibles incidencias; siempre se informará en el Campus Virtual (CV) sobre estos cambios, ya que se entiende que el CV es el mecanismo habitual de intercambio de información entre profesor y estudiantes.
- En esta asignatura, NO se permite el uso de ningún tipo de dispositivo digital en el aula (ni ordenadores, ni tablets, ni teléfonos móviles, ...); por consiguiente, no se perda el uso de tecnologíes de Inteligencia Artificial (IA) en el aula. Cualquier trabajo realizado en elaula que incluya fragmentos generados con IA será considerado una falta de honestidad académica y puede conllevar una penalización parcial o total en la nota de la actividad, o sanciones mayores en casos de gravedad. Se permite el uso de tecnologías de Inteligencia Artificial (IA) en las actividades autónomas fuera del aula.
- Sin perjuicio de otras medidas disciplinarias que se consideren oportunas y de acuerdo con la normativa académica vigente, las irregularidades cometidas por un estudiante que puedan conducir a una variación de la calificación se calificarán con un cero (0). Por ejemplo, plagiar, copiar, dejar copiar, tener dispositivos de comunicación (como teléfonos móviles, smart watches, etc.) en una actividad de evaluación, implicará suspender esta actividad de evaluación con un cero (0). Las actividades de evaluación calificadas de esta forma y por este procedimiento no serán recuperables. Si es necesario superar cualquiera de estas actividades de evaluación para aprobar la asignatura, esta asignatura quedará suspendida directamente, sin oportunidad de recuperarla en el mismo curso. La nota numérica del expediente será el valor menor entre 3.0 y la media ponderada de las notas en caso de que el estudiante haya cometido irregularidades en un acto de evaluación (y por tanto no será posible el aprobado por compensación). La evaluación de las competencias transversales está integrada en la rúbrica (o pauta de corrección de los problemas) de los exámenes parciales. La puntuación de los apartados de la rúbrica correspondientes a competencias transversales tiene un valor de entre el 5% y el 10% de la puntuación del problema correspondiente.
- Esta asignatura no contempla un tratamiento diferenciado por los estudiantes repetidores.
- Esta asignatura no contempla el sistema de evaluación única.
Bibliografía
BIBLIOGRAFIA BÁSICA
- Borges, J.; Serra, J i Arqués, J. M. (1996). Teoria d’autòmats. Materials 28, Publicacions de la UAB.
BIBLIOGRAFIA COMPLEMENTARIA
- Casas, R. i Màrquez, L. (2000). Llenguatges, gramàtiques i autòmats. Curs bàsic. Aula teòrica 41, UPC.
- Hopcroft, J. E.; Motwani, R. and Ullman, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley.
(https://docencia.eafranco.com/materiales/teoriacomputacional/books/TeoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf)
- Linz, P. (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers.
- Martin, J. C. (2004) [2003]. Lenguajes formales y teoría de la computación. McGraw-Hill Interamericana.
Software
No hay Prácticas de Laboratorio.
Grupos e idiomas de la asignatura
La información proporcionada es provisional hasta el 30 de noviembre. A partir de esta fecha, podrá consultar el idioma de cada grupo a través de este enlace. Para acceder a la información, será necesario introducir el CÓDIGO de la asignatura
| Tipo de docencia | Grupo | Idioma | Semestre | Turno |
|---|---|---|---|---|
| (PAUL) Prácticas de aula | 411 | Catalán | segundo cuatrimestre | manaña-mixto |
| (PAUL) Prácticas de aula | 412 | Catalán | segundo cuatrimestre | manaña-mixto |
| (PAUL) Prácticas de aula | 431 | Catalán | segundo cuatrimestre | manaña-mixto |
| (PAUL) Prácticas de aula | 432 | Catalán | segundo cuatrimestre | manaña-mixto |
| (PAUL) Prácticas de aula | 451 | Catalán | segundo cuatrimestre | tarde |
| (PAUL) Prácticas de aula | 452 | Catalán | segundo cuatrimestre | tarde |