Matemática Discreta 

(LADE+)ITIG


Curso 2008-2009



Información para el curso 2009-2010

 

Profesora para todos los grupos del 2009-2010

María Angustias Álvarez Cubero

Correo electrónico: maria.alvarez@urjc.es

Telf: 91 488 70 98

Despacho: 016

Tutorías:   Lunes y Martes de 15 a 19 h. Previo cita.

 

Calendario de clases 2009-2010

 


  • Profesores 

 

Roberto Muñoz
Correo electrónico: roberto.munoz@urjc.es
Tel.: 91 664 74 80  (Móstoles) 91 488 77 15
Despacho: 025 (Edificio departamental II, Móstoles)  Sala de Profesores 062 (Edificio departamental de Vicálvaro)
Tutorías: Lunes de 11 a 14, Martes de 10 a 13 (contactar antes con el profesor personalmente o por correo electrónico)
 

 

  • Introducción 

 

La matemática discreta es la parte de las matemáticas que estudia objetos discretos. Definir el concepto discreto sin entrar en demasiadas formalidades no es sencillo pero podemos apelar a ciertos ejemplos matemáticos conocidos y contraponerlo al concepto de continuo que es la idea central del curso de Bases de Matemáticas. Lo discreto es lo finito o lo que, si no es finito, presenta el aspecto de los números naturales, objetos bien separados entre sí; lo continuo es lo no finito, lo infinitesimalmente próximo, como los números reales, y de ahí el concepto de límite y las ideas que de dicho concepto se derivan. 
La matemática discreta surge como una disciplina que unifica diversas áreas tradicionales de las Matemáticas (combinatoria, probabilidad, geometría de polígonos, aritmética, grafos,...), como consecuencia de, entre otras cosas, su interés en la informática y las telecomunicaciones: la información se manipula y almacena en los ordenadores en forma discreta (palabras formadas por ceros y unos), se necesita contar objetos (unidades de memorias, unidades de tiempo), se precisa estudiar relaciones entre conjuntos finitos (búsquedas en bases de datos), es necesario analizar procesos que incluyan un número finito de pasos (algoritmos)... 

Para hacernos una idea algo más clara del contenido de esta disciplina veamos algunas preguntas que podemos plantearnos en informática y que se pueden responder con métodos de matemática discreta: 
¿Hay alguna conexión entre dos ordenadores de una red? 
Dada una tecnología de cableado, ¿cuál es el diseño de red más económico para cierta empresa? 
¿Cómo puede ordenarse una lista de números enteros (o de tareas de una cadena) en forma creciente? 
¿Cuántas palabras clave válidas hay para acceder a un sistema? 
¿Cómo se puede codificar de forma adecuada y segura un mensaje? 

Responderemos alguna de estas preguntas en este curso. La matemática discreta proporciona, por otro lado, algunas bases matemáticas para otros aspectos de la informática: estructuras de datos, algorítmica, bases de datos, teoría de autómatas, sistemas operativos, investigación operativa,... así como ayuda al desarrollo de ciertas capacidades fundamentales para un ingeniero: capacidad de formalizar, de razonar rigurosamente, de representar adecuadamente algunos conceptos... 
 

  • Objetivos 

 

- Introducir algunos métodos y conceptos básicos de la Matemática Discreta. 
- Describir algunas de sus aplicaciones a la Informática. 
- Introducir el programa MAPLE en sus aplicaciones a la Matemática Discreta. 

  • Programa  (versión para imprimir aquí)

 

Tema 1. Lógica y Razonamiento Matemático (12 h., 8 T + 4 P).
Lógica e Informática. Lógica y modelos matemáticos. Lógica proposicional: los conectivos lógicos, forma de una proposición, tautologías y razonamientos válidos, el método de refutación. Lógica de predicados: predicados y objetos, los cuantificadores universal y existencial, forma de predicados, ejemplos de sentencias verdaderas, contraejemplos, modelización de expresiones en forma simbólica. El razonamiento por inducción. Inducción completa y estructural. Lógica con Maple. Aplicaciones: Corrección de algoritmo y verificación de programas, sistemas expertos. 

Tema 2. Algoritmos (9 h., 3 T + 6 P).
Algoritmos: definiciones y ejemplos. Algoritmos de búsqueda. Algoritmos de ordenación. Complejidad. Algoritmos de búsqueda con Maple: secuencial y binaria. Algoritmos de ordenación con Maple: burbuja y selección.

Tema 3. Aritmética modular (15 h., 9 T + 6 P).
Los números naturales y los números enteros. Teorema de la división. Divisibilidad, MCD y factorización. Relaciones de congruencia. Sistemas de de ecuaciones módulo enteros. Sistemas de numeración. Sistemas de numeración con Maple. Aplicaciones: criptología, funciones hash.

Tema 4. Combinatoria (10 h., 6 T + 4 P).
Introducción. Técnicas de conteo. Variaciones. Permutaciones. Combinaciones. Probabilidad: nociones básicas. Asignación de probabilidades. Probabilidad condicionada. Experimentos de Bernoulli. Variables aleatorias. 

Tema 5.  Grafos (17 h., 12 T + 5 P).                                                Definiciones básicas. Grafos, digrafos y multigrafos. Grafos simples especiales. Construcción de grafos a partir de grafos. Isomorfismo de grafos. Representación de grafos: matriz de adyacencias, matriz de incidencias. Caminos, ciclos y grafos conexos. Grafos eulerianos y hamiltonianos. Grafos etiquetados y algoritmo de Dijkstra. Árboles: definiciones básicas. Árboles de búsqueda binarios. Árboles de decisión. Códigos prefijos. Árboles generadores. Otros aspectos de la teoría de grafos. Aplicaciones: Modelización de redes.

Tema 6. Relaciones (12 h., 7 T + 5 P).
Producto cartesiano, relación, propiedad reflexiva, simétrica, antisimétrica, transitiva, relación de orden, relación de equivalencia. Representación de las relaciones: tablas, grafos dirigidos y matrices. Clausura reflexiva, simétrica y transitiva de una relación. Conjuntos parcialmente ordenados: diagramas de Hasse, elementos característicos, inclusión de un orden parcial en uno total. Álgebras de Boole.
 

  • Bibliografía básica 

 

Apuntes de la asignatura y problemas resueltos (Versión pdf  y Servicio de Reprografía de la URJC.)
 

-Discrete Mathematics and its applications. K.H. Rosen. Mc Graw Hill, 1995 y 1999.  --Edición en Español: Matemática Discreta y sus aplicaciones. Mc Graw Hill 2004.
-Students Solution Guide for Discrete Mathematics and its applications. K.H. Rosen. Mc Graw Hill, 1999. 
-Discrete Mathematics (2nd Ed.). S. Lipschutz, M. L. Lipson.
McGraw-Hill, 1997.

-Matemática Discreta Problemas y ejercicios resueltos. C. García, J. M. López, D. Puigjaner. Prentice-Hall, 2002.

- Matemática Discreta para Informáticos. Ejercicios Resueltos. R. Caballero, T. Hortalá, N. Martí, S. Nieva, A. Pareja, M. Rodríguez.  Prentice-Hall, 2007.

NOTAS:

  • Algunos ficheros del material de la asignatura están en el formato pdf. Para abrirlos se puede usar el programa de libre difusión Acrobat Reader
  • Los alumnos de la URJC pueden comprar una copia del programa MapleV utilizando el formulario que aparece en la página:   http://www.addlink.es/Maple-Urjc.asp


Bibliografía complementaria 

Matemática discreta y combinatoria. R.P. Grimaldi. Addison-Wesley, 1989. 
Exploring discrete Mathematics with Maple. K.H. Rosen. Mc Graw Hill, 1997. 
Estructuras de Matemáticas discretas para la computación. Kolman, Busby, Ross, Prentice Hall, 1997. 
Fundamentos Matemáticos. R. Criado, A. Bujosa, C. Vega, R. Banerjee. Centro de estudios Ramón Areces, 1998. 
 
 

  • Normas de evaluación 

Convocatoria de febrero: La evaluación será continua y consistirá en: dos exámenes parciales, un examen final con Maple  y un examen final. 

Los diferentes apartados tendrán el siguiente peso en la calificación final:

     Examen parcial: (15% cada uno)     30%
     Examen final con Maple:                 20%
     Examen final:                                    55% 
     Total:                                              ¡105%! 

La aportación de los tres primeros apartados sólo será efectiva en el caso de que en el examen final se haya obtenido un mínimo de 20 puntos sobre los 55 posibles.

En los exámenes parciales y en el final se podrán usar apuntes.

En el examen final de Maple se permitirá la utilización de apuntes, libros y disquetes. No se guarda la nota de Maple de cursos anteriores, ni la de febrero para septiembre.

El temario evaluado en cada examen parcial podrá volver a ser evaluado en los sucesivos y también en el examen final.

La calificación final será el máximo entre la nota de la evaluación continua y la nota formada solamente por los exámenes final (80%) y de Maple (20%). 

Convocatoria de septiembre:

 

  • La convocatoria de septiembre se evaluará sobre un examen final (80%) y un examen de Maple (20%).
  • Para aprobar la asignatura será preciso obtener al menos el 50% de la calificación máxima.  

 

Prácticas: Las siguientes prácticas se realizarán empleando MAPLE en el aula informática EG 101 (Edificio de Gestión) en un trabajo individual supervisado por el profesor. Jueves de 15.30 a 18.00 (a partir del 16 de octubre).


CALENDARIO

o        Examen parcial 1: 10 de noviembre (Capítulos 1 y 2)

o        Examen parcial 2: 12 de enero (Hasta 5.7, incluído)

o        Examen de febrero: 3 de febrero

1.      Maple de 12 a 14 horas en EG101

2.      Teoría de 15 a 18 horas en las aulas 108 y 109

 

 

  • Maple en Clase 

 

En esta sección se publicarán ficheros MAPLE/HTML usados o presentados en clase, complementarios al desarrollo de la asignatura. 

 

Lógica
Búsqueda
Ordenación
Aritmética modular
Bases de numeración

 

  • Problemas

Hoja 1

Soluciones de la Hoja 1
Hoja 2

Soluciones de la Hoja 2 
Hoja 3

Soluciones de la Hoja 3 
Hoja 4

Soluciones de la Hoja 4 
Hoja 5 

Soluciones de la Hoja 5 

 

  • Controles y exámenes resueltos

 

Notas: Ver a través del campus virtual

 

Anuncios

 

En esta sección se publicará información relevante sobre la asignatura: erratas de los apuntes, cambios de última hora, recuperación de clases, fechas de controles... 
Se recomienda mirar periódicamente esta sección para estar al día del desarrollo de la asignatura.

 

·        Documento de presentación del curso

·        Presentación sobre algoritmos

·        Presentación sobre conexión

·        Presentación sobre grafos eulerianos