Última actualización: 26/03/2019


Curso Académico: 2019/2020

Matemática Discreta
(13887)
Titulación: Doble Grado en Ingeniería Informática y Administración de Empresas (233)


Coordinador/a: SALAS MARTINEZ, JESUS

Departamento asignado a la asignatura: Departamento de Ciencia e Ingeniería de Materiales e Ingenieria Química

Tipo: Formación básica
Créditos: 6.0 ECTS

Curso:
Cuatrimestre:

Rama de Conocimiento: Ingeniería y Arquitectura



Materias que se recomienda haber superado
Cálculo y Álgebra
Competencias que adquiere el estudiante y resultados del aprendizaje.Más información en este enlace
COMPETENCIAS GENERALES Y TRANSVERSALES (PO: a). CGB3: Capacidad para comprender y dominar los conceptos básicos de matemática discreta y su aplicación para la resolución de problemas propios de ingeniería. COMPETENCIAS ESPECÍFICAS. El objetivo del curso es proporcionar al alumno las herramientas necesarias para la comprensión de los principios científicos y matemáticos de la Ingeniería Informática. Los RESULTADOS DE APRENDIZAJE que se adquieren en Matemática Discreta son del tipo RA1 (conocimiento y comprensión). En particular se incluyen en el apartado RA1.1: "Conocimiento y comprensión de los principios científicos y matemáticos de la Ingeniería Informática". Las competencias específicas de la materia las hemos divido en tres apartados: A) Conocimientos (RA1.1, PO: a) 1. Conocer los conceptos básicos acerca de la teoría de conjuntos, relaciones binarias y retículos, así como su importancia en las aplicaciones informáticas. 2. Conocer las técnicas de recuento elementales, entender el concepto de recurrencia y saber cómo resolver relaciones de recurrencia lineales. 3. Comprender el concepto de función generatriz y su relevancia en combinatoria y saber cómo usar esta técnica para resolver problemas sencillos. 4. Entender el lenguaje propio de la teoría de grafos y aprender cómo modelizar problemas reales en términos de grafos. 5. Aprender a resolver problemas típicos de teoría de grafos usando métodos algorítmicos. B) Capacidades específicas (RA1.1, PO: a) 1. Capacidad para manejar las propiedades abstractas de la teoría de conjuntos y de las relaciones binarias. 2. Capacidad de resolver problemas de ordenación y enumeración. 3. Capacidad para modelizar problemas reales mediante técnicas de teoría de grafos y resolverlos usando técnicas algorítmicas. C) Capacidades generales (RA1.1, PO: a) 1. Capacidad de abstracción, deducción e inducción. 2. Capacidad de comunicación oral y escrita usando correctamente el lenguaje de las matemáticas. 3. Capacidad para modelizar una situación real, descrita con palabras, mediante las técnicas propias de la matemática discreta. 4. Capacidad para interpretar la solución matemática de un problema, su fiabilidad y sus limitaciones.
Descripción de contenidos: Programa
El programa consta de tres grandes bloques: combinatoria, teoría de grafos y teoría de conjuntos. Más concretamente, se ha dividido la asignatura en los siguientes temas: 1. Teoría elemental de conjuntos. Definiciones generales. Operaciones conjuntistas y propiedades algebraicas. Cardinalidad. Principios elementales de recuento. Subconjuntos de un conjunto y el conjunto de las partes de un conjunto. Números combinatorios. Particiones de un conjunto. Refinamiento de una partición. Relaciones y funciones. Relaciones binarias. Funciones. Función característica. 2. Teoría de grafos. Generalidades. Representación de grafos. Isomorfismo de grafos. Recorridos y caminos en grafos. Conexión. Grafos ponderados. Grafos dirigidos. Árboles. Grafos planos. Fórmula de Euler y consecuencias. Teorema de Kuratowski. 3. Algoritmos en teoría de grafos. Árbol generador de peso mínimo (algoritmos de Prim y Kruskal). Camino de longitud mínima entre dos vértices (algoritmo de Dijkstra y generalizaciones). Grafos eulerianos y hamiltonianos. Algoritmos de construcción de recorridos eulerianos. El problema del viajante. Algoritmos aproximados. Algoritmos de búsqueda en árboles. 4. Técnicas avanzadas en combinatoria. Relaciones de recurrencia. Funciones generatrices. Números de interés en combinatoria. Problemas combinatorios en teoría de grafos: coloraciones propias, emparejamientos, etc. 5. Relaciones de equivalencia. Relaciones de equivalencia y particiones. Clases de equivalencia y conjunto cociente. Aplicación a la aritmética modular. 6. Relaciones de orden. Conjuntos parcialmente ordenados. Diagramas de Hasse. Elementos extremales. Conjuntos totalmente ordenados. Conjuntos bien ordenados: inducción matemática. Orden lexicográfico. Ordenación topológica. 7. Retículos. Retículos acotados, modulares y distributivos. Retículos complementados. Álgebras de Boole.
Actividades formativas, metodología a utilizar y régimen de tutorías
Enseñanza presencial teórica: 2.5 créditos ECTS (CGB3, RA1.1, PO: a). Sesiones de problemas con trabajo individual y en grupo: 2.5 créditos ECTS (CGB3, RA1.1, PO: a). Trabajo individual con ayuda de la página web de la asignatura (ejercicios de auto-evaluación, material multimedia, etc): 1 crédito ECTS (CGB3, RA1.1, PO: a). Régimen de tutorías: cada profesor tiene asignadas sus horas de tutoría según el reglamento de la UC3M. En particular, un mínimo de una hora por grupo docente (agregado o de teoría) y tratando de buscar horarios compatibles con los alumnos.
Sistema de evaluación
  • Peso porcentual del Examen Final 60
  • Peso porcentual del resto de la evaluación 40
Bibliografía básica
  • F. García Merayo. Matemática Discreta. Paraninfo. 2015
  • J. Matousek y J. Nesetril. Invitación a la matemática discreta. Reverté. 2008
  • K.H. Rosen. Matemática discreta y sus aplicaciones. McGraw-Hill. 2004
Bibliografía complementaria
  • N.L. Biggs. Matematica discreta. Vicens Vives. 1994
  • R.P. Grimaldi. Matemáticas discreta y combinatoria: una introducción con aplicaciones. Addison Wesley. 1997

El programa de la asignatura y la planificación semanal podrían sufrir alguna variación por causa de fuerza mayor debidamente justificada o por eventos académicos comunicados con antelación.