NO EXISTEN CAMBIOS
La guía de la asignatura ha sido actualizada con los cambios que aquí se mencionan.
| NOMBRE DE LA ASIGNATURA |
| NOMBRE DE LA ASIGNATURA |
COMPLEJIDAD Y COMPUTABILIDAD |
| CÓDIGO |
| CÓDIGO |
71014017 |
| CURSO ACADÉMICO |
| CURSO ACADÉMICO |
2023/2024 |
| DEPARTAMENTO |
| DEPARTAMENTO |
INTELIGENCIA ARTIFICIAL
|
| TÍTULO EN QUE SE IMPARTE |
| TÍTULO EN QUE SE IMPARTE |
|
|
|
GRADO EN INGENIERÍA INFORMÁTICA
|
| CURSO |
| CURSO |
CUARTO
CURSO
|
| PERIODO |
SEMESTRE 1
|
| TIPO |
OBLIGATORIAS |
| Nº ECTS |
| Nº ECTS |
6 |
| HORAS |
| HORAS |
150 |
| IDIOMAS EN QUE SE IMPARTE |
| IDIOMAS EN QUE SE IMPARTE |
CASTELLANO |
La asignatura "Complejidad y computabilidad" se centra en el estudio de lo que es un algoritmo (y lo que no lo es) y su complejidad computacional. Todo ello desde un punto de vista formal y a la vez riguroso, lo que le da a la asignatura un aspecto matemático.
Esta asignatura forma parte del grado en Ingeniería Informática y pertenece a la materia de "Metodología de la Programación y Algoritmia" que está constituida por las asignaturas "Estrategias de programación y estructuras de datos" (primer curso, segundo semestre, carácter básico, 6 ECTS), "Programación y estructuras de datos avanzadas" (segundo curso, primer semestre, carácter obligatorio, 6 ECTS) y "Complejidad y computabilidad" (cuarto curso, primer semestre, carácter obligatorio, 6 ECTS). La asignatura "Complejidad y computabilidad" contribuye al futuro perfil profesional y/o investigador del estudiante en el aspecto fundamental de saber cuándo un problema es computable y cómo de complejo es su cómputo.
La presente guía contiene información de carácter general sobre la asignatura: requisitos y recomendaciones, equipo docente, horario de atención, competencias, resultados de aprendizaje, contenidos, metodología, plan de trabajo, sistema de evaluación, bibliografía básica, bibliografía complementaria, recursos de apoyo y glosario.
Es de destacar que en esta asignatura, la interacción con los alumnos es constante en la plataforma virtual y que se envían noticias sobre dicha interacción al correo de la UNED del alumno, por lo que conviene acceder a la plataforma y a dicho correo de forma regular (al menos una vez por semana). Esta interacción con los alumnos es muy bien valorada en las encuestas anónimas que realizan los estudiantes. A este respecto, conviene señalar que en dichas encuestas (en una escala de 0 a 100), en el curso 2022-2023 esta asignatura fue numéricamente la mejor valorada con precisión muy alta de todas las asignaturas del primer cuatrimestre de este Grado, con una puntuación de 86 siendo 16 superior a la titulación en dicho cuatrimestre. Además, en esta asignatura se obtuvieron las siguientes puntuaciones (en un total de 40 encuestas de 117 alumnos matriculados):
- Atención que el equipo docente presta a los foros: 96.
- Utilidad de las "Preguntas más Frecuentes" (FAQ) para la preparación de la asignatura: 93.
- Utilidad de la información y ejemplos de exámenes proporcionados por el equipo docente: 91.
- Utilidad de la información proporcionada sobre los criterios de evaluación: 89.
- Satisfacción global con el Equipo Docente: 89.
- Utilidad del curso virtual: 88.
A este respecto se puede consultar la información pública de los principales indicadores de rendimiento de esta asignatura (y del resto de asignaturas del Grado) en el:
Es conveniente haber estudiado previamente "Fundamentos de Programación", "Programación Orientada a Objetos", "Estrategias de Programación y Estructuras de Datos" y "Programación y Estructuras de Datos Avanzadas" para adquirir el enfoque práctico de la algoritmia en el trabajo diario de un Ingeniero Informático. A su vez, es conveniente haber estudiado la asignatura "Autómatas, Gramáticas y Lenguajes" para adquirir ciertas herramientas matemáticas útiles en el estudio formal de la complejidad y la computabilidad desde un punto de vista matemático. Además conviene tener presente las técnicas más comunes de demostración en Matemáticas (ver el Glosario de esta guía para acceder a un repaso eficaz y concreto de las mismas).
Como recomendación general para esta asignatura conviene tener en cuenta lo siguiente:
- El foro de la plataforma virtual es un espacio vivo en el que el equipo docente está presente de forma continua para ayudar a los estudiantes a progresar en su estudio.
- En el foro de la plataforma virtual, se va marcando un ritmo de estudio semanal para poder llevar al día la asignatura (para aquéllos que puedan y/o deseen).
- En todo momento es factible reengancharse a la asignatura gracias a los resúmenes que se van poniendo en la plataforma virtual dentro de las FAQ.
- Existen en la plataforma virtual exámenes resueltos de otros años. La forma de utilizarlos es intentar primero resolver los ejercicios sin mirar la solución. Está desaconsejado mirar la solución sin antes haber intentado resolver el ejercicio al menos durante 10 minutos.
- Habrá un examen ensayo voluntario en la plataforma virtual en la primera quincena de Enero.
- Es muy importante asistir en directo o en diferido a la sesión telemática de bienvenida en la primera quincena de Octubre.
Por último, conviene remarcar que es importante que el estudiante rellene las encuestas de satisfacción de esta asignatura (y de todas) dando sugerencias sobre el desarrollo de la asignatura porque éstas nos ayudan a ir mejorando la docencia en ella.
- D. Emilio Letón Molina
- Tfno: 91 398 9473 (martes lectivos, de 14:30 a 18:30 h.)
- C/ Juan del Rosal, 16 Despacho 3.04. ETSI Informática - UNED 28040 Madrid
- emilio.leton@dia.uned.es
- Curso virtual
- D. Félix Hernández del Olmo
- Tfno: 91 398 8345 (lunes lectivos, de 9:00 a 13:00 h.)
- C/ Juan del Rosal, 16 Despacho 3.06. ETSI Informática - UNED 28040 Madrid
- felixh@dia.uned.es
- Curso virtual
Las competencias genéricas son las siguientes:
- [G.2] Competencias cognitivas superiores: selección y manejo adecuado de conocimientos, recursos y estrategias cognitivas de nivel superior apropiados para el afrontamiento y resolución de diversos tipos de tareas/problemas con distinto nivel de complejidad y novedad: Análisis y Síntesis. Aplicación de los conocimientos a la práctica. Resolución de problemas en entornos nuevos o poco conocidos. Pensamiento creativo. Razonamiento crítico. Toma de decisiones.
- [G.5] Competencias en el uso de las herramientas y recursos de la Sociedad del Conocimiento: Manejo de las TIC. Competencia en la búsqueda de información relevante. Competencia en la gestión y organización de la información. Competencia en la recolección de datos, el manejo de bases de datos y su presentación.
Las competencias específicas son las siguientes:
- [BC.1] Capacidad para diseñar, desarrollar, seleccionar y evaluar, aplicaciones y sistemas informáticos, asegurando su fiabilidad, seguridad y calidad, conforme a los principios éticos y a la legislación y normativa vigente.
- [BC.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.
- [BC.7] Conocimiento, diseño y utilización de forma eficiente de los tipos y estructuras de datos más adecuados a la resolución de un problema.
- [BC.8] Capacidad para analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, eligiendo el paradigma y los lenguajes de programación más adecuados.
- [BTEc.1] Capacidad para tener un conocimiento profundo de los principios fundamentales de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
- [BTEc.3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
- [FB.03] Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para el tratamiento automático de la información por medio de sistemas computacionales y para la resolución de problemas propios de la ingeniería.
- [FB.04] 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.
Los resultados de aprendizaje que se adquieren en esta asignatura son los siguientes:
- R5: Conocer y aplicar diversos algoritmos, considerando la relación entre coste computacional y sencillez de un determinado algoritmo para resolver un problema.
- R6: Conocer y saber aplicar los conceptos de complejidad computacional e indecidibilidad aplicados a problemas susceptibles de recibir solución algorítmica.
Tema 1. Máquinas de Turing
- La máquina de Turing (MT) básica.
- Extensiones de la MT básica.
Tema 2: Computabilidad
- Lenguajes recursivos.
- Lenguajes recursivamente enumerables (RE) y no-RE.
- Codificación de MT.
- Enumeración de MT.
- Vector característico.
- Lenguajes Ld y Lnd.
- Lenguajes Lu y Lnu.
- Lenguajes Le y Lne.
- Teorema de Rice.
- PCP y PCPM
- Otros problemas indecidibles.
Tema 3: Complejidad
- P, NP y NP-Completo.
- SAT, CSAT y 3SAT.
- Otros problemas NP-completos.
Tema 4: Otros tipos de problemas
- Co-P, Co-NP y Co-NP-Completo.
- PS, NPS y PS-Completo.
- RP y ZPP.
- Aritmética modular, congruencias y Teorema pequeño de Fermat
- Problema de la primalidad.
La metodología docente propuesta para la asignatura "Complejidad y computabilidad" sigue el
modelo de educación a distancia de la UNED. Dicha metodología incluye trabajo con contenidos teóricos y actividades de evaluación continua. La evaluación continua en esta asignatura se hace a través de la participación en el foro y de la grabación de un "Mini-vídeo docente modular" (MDM). Estas dos formas de evaluación continua se detallan a continuación.
1. Participación en el foro
La puntuación de la participación en el foro será de 0 a 10.
Por cada participación relevante, el equipo docente dará un punto al alumno. Se entiende por participación relevante cuando se contesta de manera acertada la pregunta de otro alumno o cuando se comunica un aspecto interesante relacionado con la asignatura. No se considera relevante preguntar simplemente una pregunta con una duda en el foro.
El equipo docente para favorecer que cualquier estudiante pueda participar en el foro irá también haciendo preguntas cada semana, por lo que todo el mundo podrá optar a puntuar en este apartado, incluso aunque se incorpore tarde al estudio de la asignatura. No se tendrán en cuenta contestaciones repetidas de otros alumnos. Señalar, por último, que la experiencia demuestra que no es difícil conseguir la máxima puntuación y que no hay que agobiarse por conseguirla en las primeras semanas: ¡¡hay tiempo suficiente!!
El último día que se considera para poder puntuar en la participación en el foro es el 13-Ene. En la plataforma virtual estará publicada una tarea desde el último viernes de Octubre para que el estudiante rellene la fecha de su última aportación relevante. Esto permite que el equipo docente pueda decirle su nota con anterioridad a examinarse y en caso de que hubiera tiempo, incluso podría mejorarla.
2. Grabación de un MDM
La puntuación de la grabación de un MDM será de 0 a 10.
Los MDM de reciente introducción, están caracterizados por unos elementos concretos en términos de duración (5-10 minutos), soporte (transparencias minimalistas), metodología (pizarra digital), filosofía (Yo trabajo /Tú trabajas), formato (web y dispositivos móviles) e interconexión (modularidad).
En esta actividad de evaluación continua se trata de que cada alumno grabe un MDM a partir de una pregunta relacionada con los contenidos de la asignatura y cuya respuesta puede ser verdadera o falsa (pregunta V/F). El equipo docente a finales de Octubre asignará a cada alumno dicha pregunta publicando en la plataforma un listado con dicha asignación.
El último día para entregar el MDM es el 7-Ene.
A modo de ejemplo, la pregunta V/F podría ser:
Si se considera el PCP planteado sobre los siguientes dos pares (w_1,x_1)=(1,11) y (w_2,x_2)=(01,0), se tiene que el PCPM tiene respuesta negativa en esta instancia:
a) Verdadero.
b) Falso.
La respuesta para esta pregunta V/F sería la a). El MDM que se podría preparar para esta pregunta sería el dado en el enlace MDM de Ejemplo 2: PCP y PCPM. En el enlace ejemplos con MDM de Complejidad y Computabilidad se encuentran más ejemplos de MDM de esta asignatura.
En el enlace guía para diseñar un MDM, se detalla paso a paso cómo diseñar las transparencias minimalistas que se utilizaron en el enlace MDM de abarcando a pi
A la hora de grabar un MDM se puede hacer siguiendo el enlace MDM para grabar un mini-vídeo si se tienen pocos recursos o el enlace MDM para grabar un mini-vídeo si se tienen muchos recursos.
No se tendrá en cuenta si se han utilizado muchos o pocos recursos, sólo si la pregunta está bien resuelta y si se ha seguido la filosofía MDM. El MDM grabado habrá que subirlo a YouTube y comunicar la url al equipo docente.
Aspectos a tener en cuenta para realizar las transparencias minimalistas
- Número de transparencias menor o igual a 10.
- Número de líneas en cada transparencia es menor o igual a 7.
- Hay espacio para subtítulos.
- Hay espacio para escribir sobre cada transparencia.
- Se ha reservado la esquina superior derecha para la imagen en pequeño del profesor del MDM.
- Se ha reservado la esquina inferior derecha para la posible imagen en grande de alguien que interprete el lenguaje de signos.
- Hay una transparencia para hacer el resumen.
- Hay una carátula y una contraportada.
Rúbrica para evaluar el grado de MDM
- Duración:
- Está entre 5-10 minutos: si es así, dar 0,5 puntos.
- Se aprecia un esfuerzo de síntesis: si es así, dar 0,5 puntos.
- Soporte:
- Las transparencias son minimalistas: si es así, dar 0,5 puntos.
- Hay espacio para subtítulos: si es así, dar 0,5 puntos.
- Metodología:
- Se escribe sobre las transparencias minimalistas: si es así, dar 0,5 puntos.
- Se ve bien lo que se va escribiendo: si es así, dar 0,5 puntos.
- Filosofía:
- El profesor plantea alguna pregunta que luego resuelve: si es así, dar 0,5 puntos.
- Al final el profesor pide hacer un resumen: si es así, dar 0,5 puntos.
- Formato:
- Se puede ver bien en un dispositivo móvil lo que estaba escrito: si es así, dar 0,5 puntos.
- Se puede ver bien en un dispositivo móvil lo que se va escribiendo: si es así, dar 0,5 puntos.
- Interconexión:
- Se puede usar en múltiples asignaturas: si es así, dar 0,5 puntos.
- Están disponibles los subtítulos: si es así, dar 0,5 puntos.
- Respuesta correcta
- La pregunta de la que trata el MDM está resuelta de forma correcta: si es así, dar 4 puntos.
Finalmente, conviene remarcar que el equipo docente sólo evaluará la participación en el foro y la grabación del mini-vídeo durante el cuatrimestre en el que se imparte la asignatura. No obstante, debe tenerse en cuenta que para la convocatoria de septiembre, se mantendrá la nota obtenida en dicha evaluación continua durante el cuatrimestre en el que se imparte la asignatura. Por otra parte, en la convocatoria de Septiembre habrá una tarea equivalente a la participación en el foro y una tarea equivalente a la grabación del MDM. Estas tareas se describirán en el curso virtual a finales de Abril.
TIPO DE PRUEBA PRESENCIAL
|
| Tipo de examen |
| Tipo de examen |
Examen de desarrollo |
| Preguntas desarrollo |
| Preguntas desarrollo |
7 |
| Duración |
| Duración |
120 (minutos) |
| Material permitido en el examen |
| Material permitido en el examen |
Ninguno. |
| Criterios de evaluación |
| Criterios de evaluación |
El examen (tanto en primera como en segunda semana) consta de 6 preguntas de verdadero/falso para justificar y una pregunta de desarrollo. En el examen se indica que las preguntas no acertadas se puntúan con un 0, las acertadas sin justificación o con justificación incorrecta puntúan con un 0.1 y que las acertadas con justificación completa mediante una demostración o un contraejemplo se puntúan hasta con un 1.5. La pregunta de desarrollo puntúa un máximo de un punto. |
| % del examen sobre la nota final |
| % del examen sobre la nota final |
80 |
| Nota mínima del examen para aprobar sin PEC |
| Nota mínima del examen para aprobar sin PEC |
6,3 |
| Nota máxima que aporta el examen a la calificación final sin PEC |
| Nota máxima que aporta el examen a la calificación final sin PEC |
8 |
| Nota mínima en el examen para sumar la PEC |
| Nota mínima en el examen para sumar la PEC |
0 |
| Comentarios y observaciones |
| Comentarios y observaciones |
|
PRUEBAS DE EVALUACIÓN CONTINUA (PEC)
|
| ¿Hay PEC? |
| ¿Hay PEC? |
Si |
| Descripción |
| Descripción |
La evaluación continua en esta asignatura se hace a través de la participación en el foro y de la grabación de un "Mini-vídeo docente modular" (MDM). La información detallada se encuentra en el apartado de "Metodología". |
| Criterios de evaluación |
| Criterios de evaluación |
La participación en el foro y la grabación de un MDM se evalúan de 0 a 10. Los criterios detallados se encuentran en el apartado de "Metodología". |
| Ponderación de la PEC en la nota final |
| Ponderación de la PEC en la nota final |
La ponderación de la participación en el foro es de un 10% y la de la grabación de un MDM de un 10%. |
| Fecha aproximada de entrega |
| Fecha aproximada de entrega |
La fecha última para optar a la nota de participación en el foro es el 13-Ene y para entregar el MDM el 7-Ene. |
| Comentarios y observaciones |
| Comentarios y observaciones |
|
OTRAS ACTIVIDADES EVALUABLES
|
| ¿Hay otra/s actividad/es evaluable/s? |
| ¿Hay otra/s actividad/es evaluable/s? |
No |
| Descripción |
| Descripción |
|
| Criterios de evaluación |
| Criterios de evaluación |
|
| Ponderación en la nota final |
| Ponderación en la nota final |
0 |
| Fecha aproximada de entrega |
| Fecha aproximada de entrega |
|
| Comentarios y observaciones |
| Comentarios y observaciones |
|
¿Cómo se obtiene la nota final?
|
Si se denota por F la nota obtenida en la participación en el foro, por MDM la nota del mini-vídeo grabado y por Ex la nota del examen presencial, la nota final NF es NF = 0,10 * F + 0,10 * MDM + 0,80 * Ex. No es obligatoria ni la participación en el foro, ni la realización del MDM. No obstante, si no se realizan, se obtiene un cero en esos apartados. Para la convocatoria de septiembre hay tareas equivalentes al foro y al MDM que se explican en el curso virtual. La nota del foro y del MDM se guardan para septiembre en el caso de que no se apruebe la asignatura en febrero. |
Para este libro se recomienda visitar el enlace Página web oficial del libro Hopcroft et al. ,donde se encontrarán soluciones a los ejercicios marcados con un símbolo *, una fe de erratas y otros materiales que pueden resultar de interés (todo este material está en inglés). Las ediciones segunda y tercera de este texto se encuentran traducidas al castellano. Cualquiera de las dos puede utilizarse para preparar la asignatura. No así la primera edición (sólo en inglés y muy anterior), que es sustancialmente distinta.
SIPSER, M.: Introduction to the Theory of Computation
Sería una excelente alternativa al actual, si estuviera traducido al español.
Se recomienda el uso de un simulador de autómatas, gramáticas y máquinas de Turing. Se encuentra disponible en el enlace página web de jflap y en el grupo de trabajo de la asignatura ('curso virtual'), junto con ejercicios y otros materiales docentes.
