Matemática Discreta 

Ingeniería Técnica de Informática de Sistemas, de Gestión y doble titulación LADE+ITIG

ESCET

Curso 2009-2010

 (CALENDARIO DE CLASES, al final)

 


    

  • Profesores 

Roberto Muñoz Izquierdo (LADE- Informática de Gestión. Campus de Vicálvaro) 

La información para los alumnos de Vicálvaro se encuentra en este enlace.


Sergio Sánchez García(Informática de Gestión) 
Correo electrónico: sergio.sanchez@urjc.es
Tel.: 91 488 8126
Despacho: 019 (Edificio departamental II, Móstoles) 
Tutorías: :   miércoles de 11:00 a 13:00,  jueves de 12:00 a 14:00

                    viernes de 11:00 a 13:00

 

 

María Angustias Álvarez Cubero (Informática de Sistemas tarde. )

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.

Profesora de todos los grupos de Matemática Discreta del curso 2009-2010

 

Julio Flores  (Informática de Sistemas. Mañana )

Correo electrónico: julio.flores@urjc.es

Telf: 91 488 8145

Despacho: 033, Dept II

Tutorías:   miércoles de 11:00 a 13:00 y de 15:30 a 17:30

                   jueves de 15:30 a 17:30
                 

 

  • 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 

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, Clave 221)
Prácticas y problemas resueltos con Maple V (Versión html)

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.
 

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. 
  • El material de la asignatura se encuentra disponible en el servicio de reprografía de la universidad (con las clave indicadas) y en el directorio de Matemática Discreta en Prácticas en Mortadelo(W:).

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. 
Matemática Discreta. C. García, J. Ma López, Dolors Puigjaner. Pearson Educación (Prentice Hall), 2002.
 
 

 

  • Normas de evaluación 

 

Informática de Sistemas

Convocatoria de febrero: 

 

La evaluación consistirá en:

    -   Un examen parcial,

    -  Prácticas con el sistema de computación simbólica Maple  en los laboratorios informáticos,

     -  Un examen final. 

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

            Examen parcial:                     20%
            Prácticas de Maple:              10%
            Examen final:                         70%   

 

- El examen parcial se realizará en hora de clase en una fecha que se avisará con antelación. 

- El temario evaluado en el examen parcial volverá a ser evaluado también en el examen final.

- En los exámenes finales se permitirá la utilización de una hoja resumen de los apuntes. 

- No se guardan las notas de Maple de cursos anteriores.

- Las prácticas de Maple son 5. Cada una de ellas contiene un test.

- IMPORTANTE: A los alumnos que no se presenten al examen final no se les corregirá ni el examen parcial ni la prácticas, y aparecerán en actas como NP.

        La nota del curso se obtendrá del siguiente modo:

(Nota ex parcial sobre 10)*0,2 + ( Nota prácticas sobre 10)*0,1 +(Nota Ex. Final sobre 10)*0,7

 

 

Convocatoria de septiembre:

  • La convocatoria de septiembre se evaluará solamente sobre un examen  que no incluirá Maple

 


Informática de Gestión:

Convocatoria de febrero: La evaluación será continua y consistirá en: un examen parcial, tests en clase, prácticas con el sistema de computación simbólica Maple  en los laboratorios informáticos, un examen final con Maple  y un examen final. 

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

            Examen parcial:                     20%
            Prácticas de Maple:              10%
            Examen final:                         70%   

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

En los exámenes finales se permitirá la utilización de un resumen de los apuntes. 

El examen parcial se realizará en hora de clase en una fecha que se avisará con antelación. 

En la evaluación de las prácticas de Maple  y en el examen final de Maple  se permitirá la utilización de apuntes, libros y disquettes. No se guarda la nota de Maple de cursos anteriores, ni la de este curso para septiembre.

De cada hoja de problemas se pedirá a los alumnos que resuelvan en clase (15 minutos) uno de estos problemas (o uno de carácter similar) que se corregirá y conformará la nota de los tests. Cada test se evaluará sobre 2 puntos. Durante los tests no se permitirá la utilización de apuntes y libros.

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

Las prácticas de Maple son 5. Cada una de ellas contiene un test. La obtención de la nota máxima en el test da la evaluación con un 1 por cada práctica. El examen de prácticas se hará en el período de exámenes.

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

Convocatoria de septiembre:

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

Examen del curso 2009-2010:

  • La convocatoria de dicho curso se evaluará solamente sobre un examen  que no incluirá Maple  (día 21 de enero a las 15h)


 

 

  • Prácticas 

Las siguientes prácticas se realizarán empleando Maple. La primera práctica será introductoria al sistema Maple. El resto de las prácticas estarán relacionadas con el contenido de la asignatura. 

 
CALENDARIO DE PRÁCTICAS
 

    • Informática de Gestión:
      Prácticas:
      • Práctica 1: 16 de enero, de 16:00 a 18:00,  el aula 102  del aulario I
      • Práctica 2 y 3: 20 de enero de 15 a 17 h., el aula 101 del aulario I
      • Práctica 4: 21 de enero 18 a 19 h del aula 102 del Laboratorio III
      • Informática de Sistemas tarde: 
        Prácticas: (en horario de clase)
      • Práctica 1: 9 Enero el aula 102 del aulario I
      • Práctica 2 y 3: 13 Enero aula 101 del aulario I (práctica 1)
      • Práctica 4 : 14 Enero aula 102 del Laboratorio III (práctica 2 y 3)
      • La práctica 4: 23 de enero aula 102 del aulario I de 16 a 18
        h.                             
      • Informática de Sistemas mañana:
        Ver página web del profesor

 

 

La reserva de aulas informáticas en la ESCET para las distintas asignaturas se puede consultar en la página: http://www.escet.urjc.es/z_files/ad/ad03/reserva/lunes.php
 

  • 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 - Lógica –Solución Hoja 1           

                Hoja 2-Algoritmos - Solución Hoja 2  

 

                Hoja 4-Combinatoria - Solución Hoja 4  

 

                Hoja 3-Aritmética Modular- Solución Hoja 3

 

                Hoja 5-Aritmética Modular- Solución Hoja 5

 

  • Controles y exámenes resueltos

Fechas del control:

 

 

Exámenes resueltos


                 Modelo A / Modelo B 

 

 

Notas: En esta sección se publicarán las notas de las distintas titulaciones

     calendario

 

 La sala reservada en Vicálvaro el día 20 de octubre de 15 a 19 es la 263 del edificio departamental, y para el día 30 de noviembre en el mismo horario la sala 164 del departamental.