Volver

Escuela Técnica Superior de Informática

Universidad Autónoma de Madrid

Matemática Discreta

Resumen:

Este curso es una introduccion a algunos de los conceptos matematicos mas relevantes para las ciencias de la computacion, relacionados con la combinatoria, los grafos y la recurrencia. En el primer tema se hacen incursiones en problemas basicos de teoria de numeros relacionados con el mismo; en el segundo se estudian problemas clasicos, como la busqueda en grafos y el teorema de los cinco colores; por ultimo, en el estudio de la recurrencia se estudian las funciones generatrices.

1. Combinatoria Enumerativa. Contar y Listas
   

   Conjuntos y listas.
   Tres principios para contar.
   Listas sin/con repetición, listas circulares. Teorema de Fermat.
   k-conjuntos sin repetición.
   Números combinatorios. Recursión.
   Números combinatorios. Función generatriz..
   k-conjuntos con repetición.
   Criba. Principio de exclusión-inclusión.
   Algunas aplicaciones a la teoría de números.
   Principio del palomar.
   Permutaciones. Listas
   Estructuras con simetrías.
   Problemas de asignación. Teorema de matrimonios de Hall.
   Lema de Sperner. Sistemas de representantes.
   

   
   

2. Teoría de grafos
   

   Definiciones básicas.
   Coloreado de grafos. Problemas de horarios.
   Polinomio cromático.
   Grafos bipartidos.
   Grafos planos. Teorema de los cinco colores.
   Arboles.
   Arboles enraizados.
   Arboles abarcadores, algoritmos de búsqueda. Códigos de Hamming. Algoritmo de camino más corto.
   Problemas de asignación.
   Redes eléctricas.
   Grafos dirigidos
   Redes y flujos.
   

   
   

3. Recurrencias. Funciones generatrices
   

   Ejemplos de recurrencias.
   Solución de relaciones lineales de recurrencia..
   Bisección recursiva.
   Funciones generatrices.
   Funciones generatrices y enumeración.
   Particiones.
   Función generatriz exponencial.
   Método de sumación.
   Relaciones de recurrencia y funciones generatrices.
   

   
   

Bibliografía

• Bender-Williamson: 'Foundations od Applied Combinatorics', Addison Wesley,
  
• Grimaldi: 'Matemáticas Discreta y Combinatoria', Addison Wesley,
  
• Ross-Wright: 'Matemáticas Discretas', Prentice-Hall
  
• Tucker: 'Applied Combinatories', Wiley
  
• Graham-Knuth-Patashnik: 'Concrete Mathematics', Addison-Wesley
  
• Wilson: 'Introducción a la Teoría de Grafos', Alianza
  
• Biggs: 'Discrete Mathematics', Oxford University Press