Matemtica Discreta Grado en Ingeniera Informtica (Plan 2011)
Curso Acadmico: ( 2012 / 2013 ) Departamento de Ciencia e Ingeniera de Materiales e Ingenieria Qumica Formacin bsica ( Rama: Ingeniera y Arquitectura ) Crditos ECTS : 6.0 Curso : 1 Cuatrimestre : Profesor Coordinador : SALAS MARTINEZ, JESUS
MATERIAS QUE SE RECOMIENDA HABER SUPERADO Clculo y lgebra COMPETENCIAS QUE ADQUIERE EL ESTUDIANTE Y RESULTADOS DEL APRENDIZAJE El objetivo de este curso es proporcional al alumno las herramientas matemticas necesarias para entender buena parte de los problemas fundamentales de la informtica. A) Conocimientos (PO: a) 1. Conocer los conceptos bsicos acerca de la teora de conjuntos, relaciones binarias y retculos, as como su importancia en las aplicaciones informticas. 2. Conocer las tcnicas de recuento elementales, entender el concepto de recurrencia y saber cmo resolver relaciones de recurrencia lineales. 3. Comprender el concepto de funcin generatriz y su relevancia en combinatoria y saber cmo usar esta tcnica para resolver problemas sencillos. 4. Entender el lenguaje propio de la teora de grafos y aprender cmo modelizar problemas reales en trminos de grafos. 5. Aprender a resolver problemas tpicos de teora de grafos usando mtodos algortmicos. B) Capacidades especficas (PO: a) 1. Capacidad para manejar las propiedades abstractas de la teora de conjuntos y de las relaciones binarias. 2. Capacidad de resolver problemas de ordenacin y enumeracin. 3. Capacidad para modelizar problemas reales mediante tcnicas de teora de grafos y resolverlos usando tcnicas algortmicas. 4. Capacidad para utilizar software matemtico e interpretar los resultados. C) Capacidades generales (PO: a) 1. Capacidad de abstraccin, deduccin e induccin. 2. Capacidad de comunicacin oral y escrita usando correctamente el lenguaje de las matemticas. 3. Capacidad para modelizar una situacin real, descrita con palabras, mediante las tcnicas propias de la matemtica discreta. 4. Capacidad para interpretar la solucin matemtica de un problema, su fiabilidad y sus limitaciones.
DESCRIPCIN DE CONTENIDOS: PROGRAMA 1. Teora 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. Nmeros combinatorios. Particiones de un conjunto. Refinamiento de una particin. Relaciones y funciones. Relaciones binarias. Funciones. Funcin caracterstica. 2. Relaciones de equivalencia. Relaciones de equivalencia y particiones. Clases de equivalencia y conjunto cociente.
Pgina 1 de 2
3. Relaciones de orden. Conjuntos parcialmente ordenados. Diagramas de Hasse. Elementos extremales. Conjuntos totalmente ordenados. Conjuntos bien ordenados: induccin matemtica. Orden lexicogrfico. Ordenacin topolgica. 4. Retculos. Retculos acotados, modulares y distributivos. Retculos complementarios. lgebras de Boole. 5. Tcnicas avanzadas en combinatoria. Relaciones de recurrencia. Funciones generatrices. Nmeros de inters en combinatoria. 6. Teora de grafos. Generalidades. Representacin de grafos. Isomorfismo de grafos. Recorridos y caminos en grafos. Conexin. Grafos ponderados. Grafos dirigidos. rboles. Grafos planos. Frmula de Euler y consecuencias. Teorema de Kuratowski. 7. Algoritmos en teora de grafos. rbol generador de peso mnimo (algoritmos de Prim y Kruskal). Camino de longitud mnima entre dos vrtices (algoritmo de Dijkstra y generalizaciones). Grafos eulerianos y hamiltonianos. Algoritmos de construccin de recorridos eulerianos. El problema del viajante. Algoritmos aproximados. Algoritmos de bsqueda en rboles. Problemas combinatorios en teora de grafos: coloraciones propias, emparejamientos, etc.
ACTIVIDADES FORMATIVAS, METODOLOGA A UTILIZAR Y RGIMEN DE TUTORAS Enseanza presencial terica: 2 crditos ECTS (PO: a). Sesiones de problemas con trabajo individual y en grupo: 2 crditos ECTS (PO: a). Clases prcticas de laboratorio en las que se utilizar software especfico: 1 crdito ECTS (PO: a). Trabajo individual con ayuda de la pgina web de la asignatura (ejercicios de auto-evaluacin, material multimedia, etc): 1 crdito ECTS (PO: a). SISTEMA DE EVALUACIN Se seguir un sistema de evaluacin continua ms un examen final. Tanto la evaluacin continua como el examen final contribuirn con un peso del 50% a la calificacin final. 1) La evaluacin continua constar de una prueba escrita y de varias sesiones de laboratorio informtico que contribuirn, respectivamente, con un 30% y un 20% a la nota final. Estas pruebas sern acumulativas y tendrn lugar durante el horario de la asignatura, segn las normas vigentes. La prueba escrita se realizar (aproximadamente) una vez hayan transcurrido dos tercios del curso. 2) El examen final ser obligatorio, contribuir con un peso del 50% a la calificacin de la asignatura y se realizar al final del cuatrimestre (PO: a). Peso porcentual del Examen Final: Peso porcentual del resto de la evaluacin: 50 50
BIBLIOGRAFA BSICA - J. Matousek y J. Nesetril Invitacin a la matemtica discreta, Revert, 2008 - K.H. Rosen Matemtica discreta y sus aplicaciones, McGraw-Hill, 2004 BIBLIOGRAFA COMPLEMENTARIA - F. Garca Merayo Matemtica discreta, Thomson, 2005 - N.L. Biggs Matematica discreta, Vicens Vives, 1994 - R.P. Grimaldi Matemticas discreta y combinatoria: una introduccin con aplicaciones, Addison Wesley, 1997
Pgina 2 de