Titulación | Tipo | Curso |
---|---|---|
2502441 Ingeniería Informática | FB | 1 |
Puede consultar esta información al final del documento.
No hay requisitos previos. En cualquier caso es recomendable que el estudiante domine los temas más básicos del álgebra fundamental como la teoría de conjuntos y aplicaciones.
La Matemática Discreta es el área de las matemáticas dedicada al estudio de objetos discretos. Algunos de los temas que aborda son: combinatoria, teoría de grafos, diseño y análisis de algoritmos relacionados con estos problemas, criptografía, teoría de códigos correctores de errores, optimización, etcétera. De todos estos temas, nos centraremos en: teoría básica de grafos, optimización de recorridos, algoritmos sobre grafos y complejidad de algoritmos y problemas.
1. Conceptos previos: conjuntos, funciones y complejidad de algoritmos
1.1. Conjuntos y operaciones con conjuntos
1.2. Producto cartesiano y relaciones binarias
1.3. Elementos de combinatoria
1.4. Conjuntos finitos, infinitos y numerables
1.5. Complejidad de algoritmos y problemas
1.6. Funciones de complejidad. Complejidad polinómica y no polinómica
2. Fundamentos de grafos
2.1. Definiciones. Variantes de grafos
2.2. Caminos, circuitos y distancias
2.3. Grados y lema de los grados
2.4. Subgrafos y tipos importantes de grafos
2.5. Secuencias gráficas (Havel-Hakimi)
2.6. Representación de grafos
3. Rutas, caminos y árboles generadores óptimos
3.1. Exploración de grafos (DFS y BFS)
3.2. Camino de costo mínimo (Dijkstra, Floyd)
3.3. Caracterización de árboles
3.4. Árboles generadores óptimos (Kruskal)
4. Planaridad y coloración
4.1. Resultados básicos
4.2. Caracterización de grafos planarios
4.3. Coloración de grafos planarios
4.4. Anexo: el polinomio cromático
5. Grafos eulerianos y grafos hamiltonianos
5.1. Caminos y circuitos eulerianos
5.2. Método de Fleury (o Hierholzer)
5.3. El problema del cartero chino
5.4. Caminos y circuitos hamiltonianos
5.5. El problema del viajante de comercio
6. Complejidad computacional
6.1. Problemas de decisión, cálculo y optimización
6.2. Problemas resolubles e irresolubles
6.3. Clases de complejidad. Problemas NP-completos
6.4. Otros problemas intractables
Título | Horas | ECTS | Resultados de aprendizaje |
---|---|---|---|
Tipo: Dirigidas | |||
Clases de ejercicios | 15 | 0,6 | 3, 2, 4, 5, 7, 8 |
Clases de teoría | 30 | 1,2 | 1, 3, 2, 4, 5, 7, 8 |
Seminarios | 5 | 0,2 | 3, 2, 6, 7, 8 |
Tipo: Supervisadas | |||
Preparación de ejercicios y seminarios | 12,5 | 0,5 | 1, 3, 2, 4, 5, 6, 7, 8 |
Tutorías y consultas | 5 | 0,2 | 1, 3, 2, 4, 5, 6, 7, 8 |
Tipo: Autónomas | |||
Preparación del examen final | 25 | 1 | 1, 3, 2, 4, 5, 7, 8 |
Trabajo personal | 50 | 2 | 1, 3, 2, 4, 5, 7, 8 |
Las clases de teoría se basarán en clases magistrales, aunque se tratará de promover la participación del estudiante en la resolución de cálculos complejos, ejemplos, etcétera. En las clases de problemas, se seguirá una lista de ejercicios. Se promueve que los estudiantes intenten solucionar los ejercicios antes. Se promoverá también la exposición de la resolución de los problemas por parte de los estudiantes. En los seminarios se tratarán temas relacionados en profundidad: se realizarán varios ejercicios sobre algoritmos explicados en teoría aplicados a casos reales y en formato práctico. Se utilizará el Campus Virtual como medio de comunicación entre el profesorado y los estudiantes (material, actualizaciones, noticias, etc.)
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 |
---|---|---|---|---|
Dos pruebas parciales | 60% | 3 | 0,12 | 1, 3, 2, 4, 5, 7, 8 |
Pruebas basadas en ejercicios en la classe de problemas | 15% | 0,5 | 0,02 | 3, 2, 4, 5, 7, 8 |
Pruebas en grupo en seminarios | 25% | 4 | 0,16 | 3, 2, 6, 7, 8 |
Esta asignatura no contempla el sistema de evaluación única.
Las fechas para la avaluación continuada se publicarán en el Campus Virtual. Si se produce algún cambio de programación en las fechas, éste será comunicado a los estudiantes a través del Campus Virtual (CV), puesto que se entiende que el CV es el mecanismo habitual de comunicación entre el profesorado y los estudiantes.
La evaluación del curso, de 10 puntos, será de la siguiente forma:
Sin perjuicio de otras medidas disciplinarias 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). 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 superar la materia, este curso se suspenderá directamente, sin oportunidad de recuperar en el mismo curso. Las irregularidades contempladas incluyen, entre otras:
Para superar la asignatura es necesario que la evaluación de cada una de las partes supere el mínimo exigido y que la evaluación total seacomo mínimo de 5 puntos. En caso de no superar la asignatura devido a que alguna de las actividades de evaluació no llegue a la nota mínima requerida, la nota numérica del expediente será el valor menor entre 4.5 y la media ponderada de las notas. Si un estudiante se presenta a cualquiera de las pruebas parciales ya no puede ser considerado como "no evaluable". Si un estudiante se presenta al examen final tampoco puede ser considerado como “no evaluable”. No habrá ningún tratamiento especial para los estudiantes repetidores, salvo que la nota de los seminarios podrá ser convalidada del año anterior. Se otorgará la calificación "matrícula de honor" a todos aquellos estudiantes que tienen un excelente y entren dentro del porcentaje de la normativa para las mejores notas, con prioridad para aquellos que no hacen el examen de recuperación.
En el caso de las pruebas basadas en resoluciones de ejercicios, se puede solicitar una revisión después de la fecha de la actividad o la fecha de cierre de la prueba. Para todas las demás actividades de evaluación, se indicará el lugar, la fecha y la hora de la revisión, lo que permitirá a los estudiantes revisar la actividad. Si los estudiantes no participan en esta revisión, no habrá más oportunidades disponibles.
Normativa de evaluación de la UAB, aprobada por el Consejo de administración de la Universidad Autónoma de BARCELONA (30/09/2010): http://webs2002.uab.es/afers_academics/info_ac/0041.htm
Se utiliza python3 y para seguir los seminarios es necesario llevar un ordenador con un navegador web.
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 |
(PAUL) Prácticas de aula | 471 | Catalán | segundo cuatrimestre | tarde |
(SEM) Seminarios | 411 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 412 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 413 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 414 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 431 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 432 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 433 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 434 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 451 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 452 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 453 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 471 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 472 | Catalán | segundo cuatrimestre | manaña-mixto |
(SEM) Seminarios | 473 | Catalán | segundo cuatrimestre | manaña-mixto |
(TE) Teoría | 41 | Catalán | segundo cuatrimestre | manaña-mixto |
(TE) Teoría | 43 | Catalán | segundo cuatrimestre | manaña-mixto |
(TE) Teoría | 45 | Catalán | segundo cuatrimestre | tarde |
(TE) Teoría | 47 | Catalán | segundo cuatrimestre | tarde |