Download Tema 6 Grafos y grafos dirigidos.

PROGRAM A DE ASIGNATURA
CURSO ACADÉMICO 2001/02
Fecha de Edición: 7/11/2001
Área de Titulación: Ingeniería Técnica en Informática de Sistemas
Asignatura: MATEMÁTICA DISCRETA
Curso: Primero
Duración (Anual/Cuatrimestral): Cuatrimestral
Carácter: Troncal
INDICE
Créditos: 7,5
1. Objetivos del programa
El objetivo de esta asignatura es enseñar los elementos básicos de Matemáticas que, siendo
importantes para la informática, no son cubiertos por los cursos tradicionales de Álgebra y Análisis
Matemático, o por cursos más específicos de introducción a la programación y a la informática
teórica. El programa trata de manera elemental materias de teoría de conjuntos, estructuras
algebraicas, combinatoria y teoría de grafos. Se hace especial énfasis en principios generales tales
como la inducción y la recursión. Se espera que los alumnos adquieran la capacidad de aplicar los
conceptos y técnicas aquí aprendidos en el contexto de otras asignaturas del plan de estudios.
2. Temario
Tema 1
Números.
Sistemas numéricos. Propiedades características de los números naturales y enteros.
Principio de Inducción. Definiciones recursivas. Números primos. Congruencias.
Aritmética modular.
Tema 2
Conjuntos, relaciones y funciones.
Operaciones entre conjuntos,. Leyes Booleanas. Relaciones. Relaciones de equivalencia.
Clasificaciones. Funciones parciales. Cardinales. Conjuntos finitos y numerables.
Conjuntos no numerables.
Tema 3
Conjuntos ordenados.
Relaciones de orden. Ordenes totales y parciales. Retículos. Algebras de Boole.
Tema 4
Estructuras algebraicas.
Cuerpos. Anillos. Grupos. Semigrupos.
Tema 5
Combinatoria.
Principios elementales de conteo. Variaciones, permutaciones y combinaciones. Números
binomiales y multinomiales. Principios de inclusión y exclusión.
Tema 6
Grafos y grafos dirigidos.
Recorridos en grafos. Grafos eulerianos y hamiltonianos. Coloreado de vértices. Grafos
conexos. Arboles. Redes.
Página 1 de 2
3. Desarrollo de la asignatura
Las clases de teoría consistirán en una presentación formal de los contenidos teóricos de la
asignatura. En las sesiones prácticas se discutirá la resolución de (algunos de) los ejercicios
asignados. Estas sesiones prácticas están pensadas para que los alumnos tengan la oportunidad de
tener un contacto más informal con el profesor y la materia, así como de resolver dudas más
específicas. La idea más importante, sin embargo, es que no se aprende Matemáticas viendo a alguien
resolver ejercicios en la pizarra. Es imprescindible que el alumno, antes de cada sesión práctica,
intente resolver los ejercicios correspondientes. En general se seguirá de manera bastante fiel el libro
Matemática Discreta y Lógica Matemática mencionado más abajo como bibliografía básica.
4. Forma de evaluación
El método de evaluación estará basado en un examen final en Febrero, que cubrirá todos los temas
del programa, y en un examen parcial en la séptima semana de clases. Esta prueba parcial, con
carácter opcional y de una hora de duración, estará basada en los ejercicios asignados semanalmente,
supondrá un 20% de la nota final y cubrirá los dos primeros puntos del temario. Tendrá lugar en la
hora de teoría del viernes 30 de noviembre.
Por su carácter opcional, la prueba parcial será considerada para la obtención de la calificación final sólo si mejora la nota
obtenida en el examen final.
A aquellos alumnos que decidan no tomar el examen parcial, se les considerará únicamente el
examen final de Febrero para su calificación final.
5. Bibliografía
Básica
Hortalá, M.T., Leach, J., Rodríguez, M. “Matemática Discreta y Lógica Matemática”. Editorial
Complutense, 1998. ISBN: 848978437X
Complementaria
Truss, J. K. “Discrete Mathematics for computer scientists”. Adidison-Wesley Publishing Company,
1991. ISBN: 0201360616
Grimaldi, R. P. “Matemática discreta y Combinatoria”, 3ª ed. Addison-Wesley, ISBN: 9684443242
Johnsonbaugh, R. “Matemáticas discretas”, Prentice Hall, ISBN: 9701702530
6. Enlaces de interés en Internet
CES Felipe II, www.cesfelipesegundo.com
Universidad Complutense de Madrid, www.ucm.es
Biblioteca UCM, www.ucm.es/BUCM/
Facultad de Informática, UCM, www.fdi.ucm.es
Facultad de Matemáticas, UCM, www.mat.ucm.es
La información actualizada sobre esta asignatura se encuentra disponible en www.cesfelipesegundo.com
Página 2 de 2