ASIGNATURA: MATEMÁTICA DISCRETA

I. IDENTIFICACIÓN Y CARACTERÍSTICAS DE LA ASIGNATURA

Denominación y código Matemática Discreta
Curso y Titulación 2º Ingeniería en Informática
Área Matemática aplicada
Departamento Matemáticas
Tipo y ctos. LRU Obligatoria 6 (t:4’5 + p:1’5)
Coeficientes Agrupación (2) Practicidad (3)
Duración ECTS (créditos) 5’45(136 h)
Distribución ECTS (rangos) Grupo Grande: Seminario-Lab.: Tutoría ECTS: No presenciales:
30% 10% 5% 55%
40 horas 14 horas 7 horas 70 horas
Descriptores Contenidos propios de matemática discreta
(según BOE)
Coordinador-Profesor/es Juan Luis García Zapata

II. OBJETIVOS DE LA ASIGNATURA: MATEMÁTICA DISCRETA

RELACIONADOS CON COMPETENCIAS ACADÉMICAS Y DISCIPLINARES VINCULACIÓ
N
Descripción CETi
1. Familiarizarse con la descripción algebraica de estructuras discretas como grafos, 1,5,6,7
árboles, sistemas numéricos y esquemas combinatorios.
2. Utilizar la descripción abstracta de objetos discretos para modelar cuestiones 1,3,5,6
prácticas como: planificación de tareas, diseño de programas, recuento, control y
detección de errores en codificación, seguridad de los sistemas informáticos, etc.
3. Conocer los algoritmos más usados para el cálculo y procesamiento de estructuras 1,3,6,10
discretas
4. Comprender las demostraciones de efectividad de los algoritmos, y poder 1,3,5,10
modificarlas para adaptarlas a casos particulares o técnicas diversas.
5. Capacidad para relacionar las estructuras y métodos expuestos con los 1,5,10
equivalentes en otras asignaturas del título.
6. Resolver problemas o analizar casos usando los métodos estudiados. 3,5,6
7. Fomentar el uso de recursos didácticos, tradicionales o tecnológicos, para la 2,7,8,9,12
integración y desarrollo de los materiales de la asignatura.

RELACIONADOS CON OTRAS COMPETENCIAS PERSONALES Y PROFESIONALES VINCULACIÓ

N
Descripción CET
8. Ampliar el conocimiento, habilidad y autoexigencia de razonamiento formal. 3,6,8,11
9. Reforzar el hábito de plantear interrogantes, y la resolución de problemas, como 2,7,11
práctica científica.
10. Dominar la notación, método y vocabulario matemáticos para la modelización y 1,3,6
estudio de casos.
11. Mejorar la capacidad de comunicación escrita y oral. 5,7,12
12. Trabajar con constancia, madurez, creatividad y confianza. Transversal
13. Trabajar en equipo. Transversal
 III. CONTENIDOS
Secuenciación de bloques temáticos y temas
1. Grafos I
1. Grafos: Definiciones y nociones básicas. Ejemplos.
2. Tipos de grafos. Subgrafo y grafo parcial.
3. Grafos y relaciones.
4. Grafos bipartitos. Planaridad.
5. Representaciones matriciales y mediante listas.

2. Grafos II
1. Recorridos sobre un grafo. Caminos, cadenas, circuitos y ciclos.
2. Grados. Rango.
3. Accesibilidad y conexidad.
4. Algoritmos para obtener las componentes conexas de un grafo.
5. Grafo cociente y reducción. Grafo sin circuitos.

3. Árboles
1. Árboles. Caracterización de árboles.
2. Árboles generadores de un grafo. Algoritmos de Prim y de Kruskal.
3. Árboles binarios. Algoritmos de ordenación.
4. Recorrido de vértices. Búsqueda en profundidad y en anchura.
5. Técnicas de enumeración de soluciones mediante descomposición en subproblemas.

4. Grafos valorados
1. Grafos valuados. Funciones de valor en caminos.
2. Problema del camino mínimo. Algoritmos de Dijkstra y de Floyd.
3. Redes y caminos críticos. Problema del flujo máximo y el corte mínimo. Algoritmo de Ford-Fulkerson
4. Aplicaciones con diversas funciones de valor.

5. Aritmética
1. Números enteros. División con resto.
2. Divisores y múltiplos. Máximo común divisor.
3. Algoritmo de Euclides. Identidad de Bezôut. Ecuaciones diofánticas.
4. Números primos. Teorema fundamental de la Aritmética.
5. Congruencias. Módulo. Reglas de divisibilidad en diversas bases.
6. Funciones aritméticas

6. Combinatoria
1. Principios generales: Dirichlet, inclusión-exclusión, producto.
2. Combinaciones, variaciones. Interpretación conjuntista.
3. Números combinatorios. Triángulo de Tartaglia.
4. Binomio de Newton. Fórmulas de sumatorio.
5. Generación de combinaciones.

7. Recurrencia y sucesiones
1. Sucesión. Sucesión aritmética. Sucesión geométrica. Sucesión recurrente.
2. Función generatriz de una sucesión.
3. Operaciones con series de potencias formales. Descomposición en fracciones simples.
4. Término general de una sucesión de recurrencia lineal en los casos homogéneo y no homogéneo.

8. Codificación
1. Definición. Ejemplos.
2. Efectividad de códigos: distancia, peso y corrección
3. Códigos matriciales. Códigos polinómicos.
 Interrelación
Requisitos (Rq) y redundancias (Rd) Tema Procedencia
Conjuntos y relaciones Rq 1,4,5,6 Álgebra (1º I.I.)
Operaciones con vectores y matrices Rq 1, 4, 7, 8 Álgebra (1º I.I.)
Algoritmos en grafos y árboles Rd 1-4 Estructura de Datos y
Algoritmos (2º I.I.)

IV. METODOLOGÍA DOCENTE Y PLAN DE TRABAJO DEL ESTUDIANTE

Actividades de enseñanza-aprendizaje Vinculación

ii
Descripción y secuenciación de actividades Tipo D Tema Objet.
iii

1. Presentación del plan docente de la asignatura GG C-E 0.5 Todos Todos

2. Exposición de prerrequisitos y redundancias GG C-E 0.5 Todos Todos
3. Trabajo personal de compilación de materiales previos NP T-P 1 Todos Todos
4. Exposición de contenidos: definiciones y desarrollos teóricos (tema 1) GG T(II) 2 1 1,5,8,10
5. Estudio de los contenidos explicados NP T-P 3 1 1,5,8,10
6. Exposición y resolución de ejercicios tipo GG P(IV) 2 1 1,5,6,8,11,12
7. Resolución personal de ejercicios del fondo propuesto NP P(IV) 3 1 1,5,6, 8,11,12
8. Tutorización y evaluación de la actividad anterior S C-E 1 1 1,5,6, 8,11,12
9. Explicación, discusión y ejemplificación en clase GG T(III),P 1 1 1,5,6,
8,11,12,13
10. Exposición del entorno GRAPHVIZ para visualización de grafos S P(V) 1 1-4 1,5,7,9
11. Uso de GRAPHVIZ para la representación de grafos de los ejercicios S P(V) 2 1-4 1,5,7,9
de la actividad 7
12. Tutorización y evaluación de la actividad anterior. Tut C-E 1 1-4 1,5,7,9
13. Exposición de contenidos del tema 2 GG T(II) 2 2 1,5,8,10
14. Estudio de los contenidos explicados NP T-P 3 2 1,5,8,10
15. Exposición y resolución de ejercicios tipo GG P (IV) 2 2 1,2,5,6,8,11,
16. Resolución personal de ejercicios del fondo propuesto NP P (IV) 3 2 1,2,5,6,8,11
17. Tutorización y evaluación de la actividad anterior S C-E 1 2 1,2,5,6,8,11
18. Explicación, discusión y ejemplificación en clase GG T(III),P 1 2 1,2,5,6,8,11,
19. Exposición de contenidos del tema 3 GG T(II) 2 3 1,3,4,5,8,10
20. Estudio de los contenidos explicados NP T-P 3 3 1,3,4,5,8,10
21. Exposición y resolución de ejercicios tipo GG P (IV) 2 3 1,2,5,6,10,12
22. Resolución personal de ejercicios del fondo propuesto NP P (IV) 3 3 1,2,5,6,10,12
23. Tutorización y evaluación de la actividad anterior S C-E 1 3 1,2,5,6,10,12
24. Exposición de contenidos del tema 4 GG T(II) 2 4 1,3,4,5,8,10
25. Estudio de los contenidos explicados NP T-P 3 4 1,3,4,5,8,10
26. Exposición y resolución de ejercicios tipo GG P (IV) 2 4 1,2,5,6,
27. Resolución personal de ejercicios del fondo propuesto NP P (IV) 3 4 1,2,5,6,
28. Tutorización y evaluación de la actividad anterior S C-E 1 4 1,2,5,6,
29. Explicación, discusión y ejemplificación en clase GG T(III),P 1 4 1,2,5,6,9,13
30. Exposición del paquete software COMBINATORICA para la S P(V) 1 4,6 1,3,5,7,9,12
representación animada de algoritmos en grafos
31. Uso de COMBINATORICA para la animación de los algoritmos de NP P(V) 2 4,6 1,3,5,6,7,9,12
las actividades anteriores
32. Tutorización y evaluación de la actividad anterior Tut. C-E 1 4,6 1,3,5,79,12
33. Exposición de contenidos del tema 5 GG T(II) 2 5 1,3,4,8,10
34. Estudio de los contenidos explicados NP T-P 3 5 1,3,4,8,10
35. Exposición y resolución de ejercicios tipo GG P (IV) 2 5 1,2,6,8,11,12
36. Resolución personal de ejercicios del fondo propuesto NP P (IV) 3 5 1,2,6,8,11,12
 37. Tutorización y evaluación de la actividad anterior S C-E 1 5 1,2,6,8,11,12
38. Explicación, discusión y ejemplificación en clase GG T(III),P 1 5 1,2,6,13
39. Exposición de una aplicación para el cálculo en precisión arbitraria S P(V) 1 5 1,7,9,12
como BC
40. Uso de BC para la comprobación de los ejercicios anteriores NP P(V) 2 5 1,7,9,12
41. Tutorización y evaluación de la actividad anterior Tut. C-E 1 5 1,9,12
42. Exposición de contenidos del tema 6 GG T(II) 2 6 1,8,10
43. Estudio de los contenidos explicados NP T-P 3 6 1,8,10
44. Exposición y resolución de ejercicios tipo GG P(IV) 2 6 1,2,6,9,12
45. Resolución personal de ejercicios del fondo propuesto NP P(IV) 3 6 1,2,6,9,12
46. Tutorización y evaluación de la actividad anterior S C-E 1 6 1,2,6,9,12
47. Explicación, discusión y ejemplificación en clase GG T(III),P 1 6 1,2,6,9,12
48. Uso de COMBINATORICA para la representación de los ejercicios NP P(V) 2 4,6 1,7,10,12
de las actividades anteriores
49. Tutorización y evaluación de la actividad anterior Tut. C_E 1 4,6 1,7,10,12
50. Exposición de contenidos del tema 7 GG T(II) 2 7 1,8,10
51. Estudio de los contenidos explicados NP T-P 3 7 1,8,10
52. Exposición y resolución de ejercicios tipo GG P(IV) 2 7 1,2,6,9,12
53. Resolución personal de ejercicios del fondo propuesto NP P(IV) 3 7 1,2,6,9,12
54. Tutorización y evaluación de la actividad anterior S C-E 1 7 1,2,6,9,12
55. Explicación, discusión y ejemplificación en clase GG T(III),P 1 7 1,2,6,9,12
56. Exposición de contenidos del tema 8 GG T(II) 2 8 1,8,10
57. Estudio de los contenidos explicados NP T-P 3 8 1,8,10
58. Exposición y resolución de ejercicios tipo GG P(IV) 2 8 1,2,6,9,12
59. Resolución personal de ejercicios del fondo propuesto NP P(IV) 3 8 1,2,6,9,12
60. Tutorización y evaluación de la actividad anterior S C-E 1 8 1,2,6,9,12
61. Preparación de un trabajo de ampliación de la asignatura (opcional) NP T-P (8) Todos Todos
62. Tutorización del trabajo (opcional) Tut. T-P (1) Todos Todos
63. Debate y exposición oral del trabajo de ampliación, y evaluación del Tut. T(II,III), P, (1) Todos Todos
mismo (opcional) C-E
64. Estudio y preparación del examen final NP T-P 15 Todos Todos
65. Tutorización docente Tut. T 1 Todos Todos
66. Examen final GG C-E 3 Todos Todos

Distribución del tiempo (ECTS) Dedicación del alumno Dedicación del

profesor
Distribución de actividades Nº H. presenciales H. no presenc. H. H. no presenc.
alumnos presenciales
Coordinac./evaluac. (I) 60 4 1(+8) 4 30+6+(48)
Grupo grande Teóricas (II y III) 60 16 24 16 7.5
(Más de 20 33 36 33 7.5
Prácticas (IV, V y VI) 60
alumnos)
Subtotal 60 43 61(+8) 43 51+(48)
Coordinac./evaluac. (I) 20 - 180
Seminario- Teóricas (II y III) 20 3 9
Laboratorio Prácticas (IV, V y VI) 20 9 27 30
(6-20 alumnos) 12 36 210
Subtotal 20
Coordinac./evaluac. (I) 5 (2) (12) 0
Tutoría ECTS Teóricas (II y III) 5 2 24 -
(1-5 alumnos) Prácticas (IV, V y VI) 5 2 24 -
Subtotal 5 4(+2) 48(+12) -
Tutoría comp. y preparación de ex. 1 1 15 9
(VII)
Totales 59 (2’45 76(+8)(3 ECTS) 127(+12) 261+(48)
ECTS)
 V. EVALUACIÓN

CRITERIOS DE EVALUACIÓN* VINCULACIÓN

*
Descripción Objetivo
CCiv
1. Demostrar el conocimiento y uso de estructuras discretas y algoritmos para el planteamiento 1, 2, 3, No
y resolución de problemas 8,10 compensable
2. Saber adaptar las demostraciones genéricas de efectividad de algoritmos a situaciones 3, 4,
concretas de un problema dado. 8,9,10
40%
3. Saber modelar matemáticamente una situación, así como para resolver problemas con 1, 2, 3, 7, 20%
técnicas matemáticas que mejor se ajusten a las características dadas. 8,9,10
4. Desarrollar, analizar e implementar algoritmos, para resolver problemas de cierta 4, 5, 6,7 30%
envergadura, no abordables en pizarra

5. Desarrollar unas mínimas capacidades de abstracción, concreción, concisión, imaginación, 4, 7, 8, 9,

intuición, razonamiento, participación, crítica, objetividad, síntesis y precisión tanto a la hora 10 10%
de elaborar y exponer trabajos de ampliación-innovación, como en la propuesta, revisión y
análisis de resultados prácticos.

Actividades e instrumentos de evaluación

Seminarios Seguimiento y valoración del desarrollo y participación en las prácticas de laboratorio y relaciones de
problemas.
y tutorías Registro y valoración del cuaderno de prácticas y relaciones de problemas. 30%(NR)
ECTS
Examen final Prueba de desarrollo escrita de carácter teó[Link]áctico donde ¼ se destina a la comprensión de 70%
conceptos, ½ a la aplicación de los mismos en casos prácticos, y ¼ a valorar la capacidad de
abstracción , intuición y razonamiento del alumno.
Opcional Elaboración y exposición oral de un proyecto de ampliación-innovación. (10%)

Opcional Para aquellos alumnos cuya nota en la evaluación alternativa esté comprendida entre 4,5 y
5, se contemplará la posibilidad de que superen la asignatura exponiendo de manera oral un
problema de carácter especial

VI. BIBLIOGRAFÍA

Bibliografía de apoyo seleccionada

* Abellanas, M., Lodares, D. Análisis de Algoritmos y Teoría e Grafos, 1990.
* Grimaldi, Ralph . Matematicas discreta y combinatoria 3a. ed.1998 S519.1GRImat
* Lipschutz, S. Teoría y 600 problemas resueltos de Matemática Discreta.. Serie Schaum, Mc. Graw-Hill, 1990.
* Lipschutz, S. Matemáticas para ciencias de la computacion. Serie Schaum, Mc. Graw-Hill, 1983.
* Pelegrín, B., Cánovas,L., Fernández, P. Algoritmos en Grafos y Redes. Editorial PPU, Barcelona, 1992.
* Ross, K., Wright, Ch. Matematicas discretas. Prentice-Hall, 1990.
Códigos del Plan Docente

i CET. Competencias Específicas del Título (véase el apartado de Contextualización curricular)

ii Tipos de actividades. GG (Grupo Grande); S (Seminario o Laboratorio); Tut (Tutoría ECTS); No presenciales (NP); C-E, I
(Coordinación o evaluación); T, II (Teórica de carácter expositivo o de aprendizaje a partir de documentos); T, III (Teórica de
discusión); P, IV (Prácticas basadas en la solución de problemas); P, V (Prácticas basadas en la observación, experimentación,
aplicación de destrezas, estudio de casos…); P, VI (Prácticas con proyectos o trabajos dirigidos); T-P, VII (Otras teórico-prácticas).

iii D. Duración en sesiones de 1 hora de trabajo presencial o no presencial (considerando en cada hora 50-55 minutos de trabajo
neto y 5-10 de descanso).

iv CC. Criterios de Calificación (ponderación del criterio de evaluación en la calificación cuantitativa final).