| Grafos y complejidad | Código: 75.569 Créditos: 6 |
Muchas situaciones se pueden describir en forma de jerarquía o red entre diferentes entidades: red social, red de carreteras, cargos en una organización, red de computadores, conexiones en un circuito... Matemáticamente, esta noción de jerarquía o red se denomina grafo. En esta asignatura, estudiaremos el concepto de grafo, sus propiedades y los problemas más usuales que se pueden plantear. Estos conceptos serán de gran aplicación en muchos problemas del campo de la informática.
Por otro lado, algunos problemas que nos puede interesar resolver sobre un grafo son computacionalmente complejos: un ordenador necesitaría mucho tiempo de cálculo o espacio de memoria para resolverlos. En la segunda parte de la asignatura estudiaremos los límites prácticos de cálculo de un ordenador a partir de este concepto de dificultad computacional. Definiremos diferentes familias de problemas según su complejidad y presentaremos algunos ejemplos de problemas complejos, dentro y fuera de la teoría de grafos. Veremos que algunos de estos problemas complejos son muy frecuentes en el campo de la informática y que tienen aplicaciones a diferentes ámbitos, como por ejemplo la criptografía.
Grafos y Complejidad es una asignatura obligatoria del grado en Ingeniería Informática.
Antes de cursarla, se recomienda haber cursado previamente las asignaturas de Prácticas de programación (para estar familiarizado con el desarrollo de algoritmos) y Lógica (para estar familiarizado con la notación lógica).
El uso de grafos para modelar problemas es muy habitual en el campo de la informática. Por este motivo, utilizaréis los conceptos de grafos en múltiples asignaturas dentro del grado, como por ejemplo las asignaturas de redes de computadores o las asignaturas del itinerario de Computación.
Algunos de los problemas complejos que hemos estudiado en esta asignatura también aparecen en otras asignaturas:
- En las asignaturas, de Inteligencia Artificial y Aprendizaje Computacional se presentan estrategias para calcular soluciones aproximadas a problemas complejos de forma eficiente.
- En Criptografía se utilizan problemas computacionalmente complejos para garantizar la seguridad de los mecanismos de cifrado y autenticación.
- La asignatura Diseño de Estructuras de Datos aplica de forma práctica los conceptos de grafos y complejidad al campo de la programación. Diseño de Estructuras de Datos estudia como desarrollar programas eficientes: presenta diferentes estructuras de datos y algoritmos para problemas frecuentes (algunos de ellos, problemas sobre grafos), así como los criterios para elegir el más adecuado a cada situación.
- La asignatura Modelado de Sistemas estudia cómo resolver problemas de optimización complejos en el ámbito de la logística y la planificación, también conocido como investigación operativa (operations research).
Los conceptos de grafos se utilizan de forma transversal en muchos ámbitos de la informática, para modelar circuitos, redes, organizaciones jerárquicas, etc.
En cuanto a la complejidad, los conceptos de coste temporal y espacial son fundamentales para cualquier programador.
Los problemas más complejos presentados en la asignatura son relevantes por profesionales en el ámbito de la investigación operativa y la inteligencia artificial. También son importantes por profesionales de la seguridad informática, para saber evaluar la seguridad de algunos criptosistemas.
La asignatura requiere conocimientos básicos de algorítmica: la comprensión de algoritmos en pseudocódigo y la capacidad de proponer algoritmos que resuelvan problemas nuevos. También son muy útiles nociones sobre el cálculo del coste temporal de un algoritmo, aunque estos conceptos en el primer módulo de la asignatura.
Además, para el correcto seguimiento de la asignatura es importante entender la notación matemática y conocer los conceptos de conjunto y función.
Antes de cursar esta asignatura, es muy recomendable haber cursado previamente las asignaturas siguientes:
- Prácticas de programación
- Lógica
Las competencias generales del Grado que se ponen de manifiesto en esta asignatura son:
- Capacidad para utilizar los fundamentos matemáticos, estadísticos y físicos para comprender los sistemas TIC.
- Capacidad para analizar un problema en el nivel de abstracción adecuado a cada situación y aplicar las habilidades y conocimientos adquiridos para resolverlo.
Las competencias específicas de esta asignatura son:
- Conocer el concepto de grafo y los diferentes tipos de grafo (grafos orientados, grafos ponderados, pseudografos, multigrafos, ...).
- Conocer las principales propiedades de los grafos y saber analizarlas en un grafo concreto.
- Conocer los problemas más usuales sobre grafos (busca de caminos, distancia mínima, árbol de expansión mínim, ..), los algoritmos que los resuelven y saber aplicarlos en un grafo concreto.
- Ser capaz de representar y analizar un problema en términos de la teoría de grafos.
- Conocer el concepto de complejidad temporal y espacial de un algoritmo y saber analizarla en algoritmos concretos.
- Saber explicar los límites prácticos de cálculo en un ordenador (tratable vs intratable) y la jerarquía de clases de complejidad.
- Ser capaz de clasificar un problema dentro de la clase de complejidad apropiada.
- Ser capaz de comparar la complejidad de un problema con la otros problemas conocidos.
- Saber reconocer los problemas intratables más conocidos y frecuentes, especialmente en el campo de la teoría de grafos.
La asignatura se estructura en siete módulos:
|
Módulo |
Contenidos |
|
1. Conceptos previos: funciones y algoritmos |
1. Funciones 2. Algoritmos |
|
2. Fundamentos de grafos |
1. Caracterización de un grafo 2. Estructura y manipulación de grafos |
|
3. Recorridos y conectividad |
1. Recorridos 2. Algoritmos de exploración de grafos 3. Conectividad 4. Distancias en un grafo |
|
4. Árboles |
1. Conceptos básicos 2. Árboles generadores 3. Árboles con raíz |
|
5. Grafos eulerianos y grafos hamiltonianos |
1. Grafos eulerianos 2. Grafos hamiltonianos |
|
6. Complejidad computacional |
1. El concepto de problema 2. Medidas de complejidad 3. Reducción y completitud |
|
7. Problemas intratables |
1. Problemas intratables sobre grafos 2. Otros problemas intratables |
| Material | Soporte |
| Lógica de enunciados | |
| Recorridos y conectividad | |
| Grafos eulerianos y grafos hamiltonianos | |
| Fundamentos de grafos | |
| Árboles | |
| Conceptos previos: funciones y algoritmos | |
| Complejidad computacional | |
| Los números: números naturales, principio de inducción y números complejos | |
| Elementos de álgebra lineal y geometría | |
| Problemas intratables |
La asignatura se ha estructurado en siete módulos, cada uno de los cuales se desarrolla en estos apartados: la introducción, los objetivos, el cuerpo teórico con los ejercicios y los ejemplos correspondientes, una colección de ejercicios de autoevaluación, y bibliografía específica recomendada.
En cuanto a la forma en que se presentan estos contenidos, se utilizan cuatro tipos de material esencial:
- Módulos didácticos. Este material está constituido por los 7 módulos de la asignatura editado en papel por la UOC y disponibles también en formato PDF en el aula de la asignatura.
- Guía de estudio, disponible en el apartado Recursos del aula, proporciona un calendario detallado de estudio de los módulos y de realización de actividades de aprendizaje.
- Material interactivo ("Estudio de algoritmos") que consiste en un applet que permite estudiar algunas características y simular algoritmos asociados a los varios tipos de grafos que se estudiarán. Este material lo podéis encontrar al espacio del aula Recursos, concretamente en Herramientas de soporte - Explicaciones complementarias.
- Libro de problemas que podéis encontrar en la apartado Herramientas de soporte - Resumen de ejercicios de grafos y complejidad del espacio del aula Recursos. Es un material de especial interés con problemas de toda la asignatura, algunos totalmente resueltos y el resto con la solución indicada (gran parte de estos problemas han sido propuestos en las PECs y Exámenes Finales de ediciones anteriores de la asignatura).
Además, la asignatura dispone al espacio Recursos, consultable on-line desde el aula, varios tipos de material, organizados según su importancia y tipología. A lo largo del curso se darán estrategias para un uso adecuado de todos estos materiales y un mejor aprovechamiento de sus posibilidades.
Podéis encontrar más información en las siguientes referencias complementarias:
- Balakrishnan, V.K. (1991). Introductory Discrete mathematics. Nova Jersey: Prentice-Hall Int. Ed.
- Biggs, N.L. (1994). Matemática Discreta. (1a. edición, traducción de M. Noy). Barcelona: Ediciones Vicens Vives.
- Comellas, F.; Fàbrega, J.; Sànchez, A.; Serra, O. (1996). Matemàtica discreta. Barcelona: Edicions UPC.
- Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. (2001). Introduction to Algorithms. Cambridge: MIT Press.
- Garcia, C. (2002). Matemática Discreta. Materiales Didácticos 66. Palma de Mallorca: UIB.
- Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company.
- Grimaldi, R.P. (1989). Matemáticas discreta y combinatoria. Mèxic: Addison-Wesley Iberoamericana.
- Masià, R.; Pujol, J.; Rifà, J.; Villanueva, M. (2007). Matemática Discreta. Barcelona: Fundación para la Universitat Oberta de Catalunya.
- Papadimitriou, C.H. (1994). Computational Complexity. Reading (Massachussetts): Addison-Wesley.
- Skiena, S.S. (1998). The Algorithm Design Manual. Berlin: Springer-Verlag.
El estudio de la asignatura se centra en los módulos didácticos y el material complementario que se proporciona a través del campus virtual. La dedicación que se estima para esta asignatura es de 25 horas por crédito ECTS, es decir, aproximadamente unas diez horas semanales incluyendo todas las actividades relacionadas con el estudio (lectura de materiales, participación en el foro, resolución de ejercicios, etc.).
La metodología de trabajo se basa en el estudio detallado de cada uno de los módulos y la realización de los ejercicios propuestos para cada uno de los apartados. Es fundamental realizar los ejercicios de autoevaluación que figuran al final de cada módulo y comprobar los resultados en el solucionario o en los mensajes que el profesorado cuelgue en el tablero. Así mismo es importante que el estudiante resuelva los ejercicios del documento Libro de Problemas y participe en el foro de la asignatura comentando estos ejercicios con los compañeros de curso.
En las fechas que figuran en la tabla de Actividades de Evaluación del espacio del aula de Evaluación se enviará una colección de actividades que configurarán la evaluación continua. La solución será expuesta en el espacio Planificación del aula.
Es muy recomendable consultar cualquier duda al consultor de la asignatura (o los compañeros) a través del foro (lo más recomendable), o bien, a través del buzón personal.
El seguimiento activo de los espacios del aula (tablones, foro, planificación) es de primordial interés, dado que habitualmente se plantean dudas, se dan respuestas y se tratan temas relacionados con la materia de estudio.
Es importante intentar realizar un trabajo constante de estudio de los contenidos dado que esta es la vía habitual de asegurar el éxito para superar la asignatura. En este sentido van las propuestas de distribución temporal de aprendizajes incluidas en este documento y las otras que se puedan dar durante el curso.
Las PECs y el resto de ficheros que se tengan que transmitir al consultor se presentarán en formato PDF. El profesorado entregará los ficheros de las PECs también en formato PDF.
NOTA: en la dirección http://www.dopdf.com/ os podéis descargar un conversor gratuito a formato PDF. Otro conversor gratuito, en este caso online y para documentos con formato DOC, lo podéis encontrar a http://www.expresspdf.com/ .
La Normativa académica de la UOC dispone que el proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.
La falta de originalidad en la autoría o el mal uso de las condiciones en las que se hace la evaluación de la asignatura es una infracción que puede tener consecuencias académicas graves.
El estudiante será calificado con un suspenso (D/0) si se detecta falta de originalidad en la autoría de alguna actividad evaluable (práctica, prueba de evaluación continua (PEC) o final (PEF), o la que se defina en el plan docente), ya sea porque ha utilizado material o dispositivos no autorizados, ya sea porque ha copiado de forma textual de internet, o ha copiado de apuntes, de materiales, manuales o artículos (sin la citación correspondiente) o de otro estudiante, o por cualquier otra conducta irregular.
La calificación de suspenso (D/0) en la evaluación continua (EC) puede conllevar la obligación de hacer el examen presencial para superar la asignatura (si hay examen y si superarlo es suficiente para superar la asignatura según indique este plan docente).
Cuando esta mala conducta se produzca durante la realización de las pruebas de evaluación finales presenciales, el estudiante puede ser expulsado del aula, y el examinador hará constar todos los elementos y la información relativos al caso.
Además, esta conducta puede dar lugar a la incoación de un procedimiento disciplinario y la aplicación, si procede, de la sanción que corresponda.
La UOC habilitará los mecanismos que considere oportunos para velar por la calidad de sus titulaciones y garantizar la excelencia y la calidad de su modelo educativo.
|
Para superar la asignatura hay que hacer un examen (EX). La nota de la evaluación continua (EC) complementará esta calificación.
|
Nota final de asignatura: EX + EC
EX = 65 %
EC = 35 %
Notas mínimas:
· EX = 4
Esta fórmula de ponderación sólo se aplicará cuando la nota resultante mejore la obtenida en el EX. Cuando la nota obtenida en el EX sea inferior a 4 o la calificación resultante de la fórmula de ponderación no permita mejorar la nota obtenida en el EX, la calificación final de la asignatura será la nota obtenida en el EX.
En el caso de asignaturas con prácticas (Pr) que cruzan con el examen (EX), la fórmula de ponderación sólo se aplicará cuando la nota resultante mejore la obtenida en FE (FE=EX+Pr). Cuando la nota obtenida en el EX sea inferior a 4, la calificación resultante de la asignatura será la nota obtenida en el EX. Cuando la calificación resultante de la fórmula de ponderación no permita mejorar la nota obtenida en FE, la calificación final de la asignatura será la nota obtenida en FE.
La evaluación continua es el modelo de evaluación recomendado para el seguimiento y la superación de la asignatura, porque facilita la asimilación progresiva de las competencias. Este modelo consta de tres Pruebas de Evaluación Continua (PEC) con las siguientes características:
|
Actividad |
Módulos a los que |
Peso orientativo dentro de la |
|
PEC1 |
1 + 2 + 3 |
33% |
|
PEC2 |
4 + 5 |
33% |
|
PEC3 |
6 + 7 |
33% |
La nota final de la evaluación continua se determinará en función de las calificaciones parciales obtenidas, la participación del estudiante en el foro y haber demostrado un dominio suficiente en los aspectos fundamentales de la asignatura durante el semestre.
Se considera que un estudiante sigue la evaluación continua cuando hace la entrega de como mínimo el 50% de las Pruebas de Evaluación Continua (PEC) que se proponen. En esta asignatura hay 3 PEC y por lo tanto:
· Si un estudiante no entrega ningún PEC o entrega sólo una, la nota obtenida de la evaluación continua será una N.
· Si un estudiante entrega sólo dos PEC, se hará la media considerando que la PEC no entregada tiene una D.
· Si el estudiante entrega las tres PEC, se hará la media normalmente.
Las fechas de publicación de los enunciados de las pruebas y de entrega de los ejercicios se pueden consultar al calendario de la asignatura. Es ncesario indicar explícitamente qué fuentes se han utilizado en la preparación de la entrega, aportando información para localizar el recurso: URL, datos bibliográficos, etc.Tendréis que entregar cada PEC en formato PDF dentro de los plazos establecidos.
El seguimiento correcto de la asignatura os compromete a realizar las actividades de la evaluación continua de manera individual y según las indicaciones que pauta este Plan Docente. En caso de que no sea así, la evaluación continua se os evaluará con una D. En concreto: en caso de extrema similitud entre algún ejercicio de PEC de dos o más estudiantes que desacredite el hecho de haberla realizado individualmente, la nota final de AC será una D para todos ellos. Por otro lado, y siempre a criterio de los Estudios, el incumplimiento de este compromiso, puede suponer que no se os permita superar ninguna otra asignatura mediante evaluación continua ni en el semestre en curso ni en los siguientes.
Esta asignatura tiene un examen final obligatorio con una duración de 2 horas. Este examen pretende evaluar todas las competencias adquiridas a lo largo de la asignatura. El formato de los ejercicios será similar a los que aparecen en las PECs y en los módulos didácticos de la asignatura. A las pruebas presenciales no se podrá llevar ningún tipo de material ni calculadora.
La nota del examen es una calificación numérica con un decimal. Esta nota se cruzará con la nota de evaluación continua para obtener la nota final de la asignatura de la forma siguiente:
- Si la nota del examen es inferior a 4, la asignatura estará suspendida:
NFA = Nota examen
- En caso contrario, se aplicará la fórmula siguiente:
NFA = máximo (Nota examen, 0'65*Nota examen + 0'35*Nota AC)
En la relación al examen, queremos destacar lo siguiente:
· La mejor forma de prepararse por el examen es seguir la evaluación continua.
· No es necesario tener aprobada la evaluación continua para presentarse al examen.
· La nota de evaluación continua en ningún caso hará bajar la nota del examen, sólo la puede dejar igual o mejorarla.
Tal y como se ha indicado en la metodología de la asignatura, el consultor os guiará y orientará a través del tablón del aula para podáis hacer un buen seguimiento de la asignatura. Podéis dirigir vuestras dudas generales sobre la asignatura (contenidos, evaluación, etc.) al foro del aula. Si tenéis dudas más individuales, los podéis plantear en el buzón personal del consultor.
El consultor también hará un seguimiento personalizado de la evaluación continua, revisará todas las PEC entregadas y comentará de forma cualitativa a nivel grupal y/o individual la resolución. Estos comentarios os ayudarán a progresar en vuestro aprendizaje y a adquirir el conjunto de las competencias.