Titulación | Tipo | Curso |
---|---|---|
Ingeniería Informática | FB | 1 |
Puede consultar esta información al final del documento.
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:
- Preservar la manipulación del lenguaje matemático
- Preservar las demostraciones por inducción y por contradicción
- Preservar 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.
- 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
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, expersiones y lenguajes regulares.
2.4. Minimización del número de estados internos.
2.5. 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.
5.5. Máquinas de Turing como enumeradores.
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 del paro.
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.
Título | Horas | ECTS | Resultados de aprendizaje |
---|---|---|---|
Tipo: Dirigidas | |||
Clases de Teoría y Problemas | 50 | 2 | CM05, KM09, SM13, CM05 |
Tipo: Supervisadas | |||
Ejercicios propuestos en clase | 28 | 1,12 | CM05, KM09, SM13, CM05 |
Tipo: Autónomas | |||
Estudio y preparación de las pruebas de evaluación | 38,5 | 1,54 | CM05, KM09, SM13, CM05 |
Preparación y trabajo autónomo | 26 | 1,04 | CM05, KM09, SM13, CM05 |
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.
Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.
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 al final de cada uno de los temas. Las notas de estos ejercicios y/o actividades supondrán el 30% de la nota final. Esta parte de la nota NO será recuperable.
Habrá un examen (Primer Parcial = P_1) antes de medio semestre en el que se evaluará el trabajo realizado hasta ese momento. La nota de este examen 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 constará como NO EVALUABLE a efectos académicos y no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, en caso en que se permitirá hacer el examen de recuperación).
Al final del semestre habrá un segundo examen parcial (que decimos P_2) en el que se evaluarán los conocimientos impartidos tras el primer parcial. La nota de este examen aportará otro 35% de la calificación final. Aquel estudiante que no haya hecho este examen no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, en caso en que se permitirá hacer el examen de recuperación).
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 semillas si NF=0,7 M+ 0,3 S, (donde S es la nota media del libramiento 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 lanota 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 de cada parcial no sea inferior a 9 y la nota NF descrita antes supere 9.1. 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, 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 se publicarán en el Campus Virtual (CV) y pueden estar sujetas a posibles cambios de programación por motivos de adaptación a posibles incidencias; siempre se informará al 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.
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.
No hay Prácticas de Laboratorio; en principio, no utilizaremos ningún software.
La información proporcionada es provisional hasta el 30 de noviembre de 2025. 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
Nombre | 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 |