Discrete Mathematics II

Complemento de combinatoria

1.- Funciones generatrices. Función generatriz de una sucesión. Operaciones con funciones generatrices. Aplicación de las funciones generatrices a los problemas de conteo. El operador suma. Función generatriz exponencial y su aplicación.

2.- Relaciones de recurrencia lineales. Definición de los distintos tipos de relación de recurrencia. Relaciones de recurrencia lineales homogéneas con coeficientes constantes. Relaciones de recurrencia no homogéneas. Cálculo de la solución de una relación de recurrencia por métodos directos y utilizando funciones generatrices. Algoritmo divide y vencerás.

Bibliografía y direcciones de interés
R. P. Grimaldi. Matemáticas discreta y combinatoria, 3ª Edición. Ed. Addison-Wesley Iberoamericana.
R. L Graham, D. E. Knuth y O. Patashnik. Concrete mathematics, a foundation for computer science. Ed. Addison-Wesley.
Kenneth H. Rosen. 2ª Edición. Matemática Discreta. McGraw-Hill
Ejercicios I Soluciones I
Ejercicios II Soluciones II
Ejercicios III Soluciones III
Tabla de funciones generatrices

Verificación formal

1.- Sistemas de tipos
2.- Cálculo de Construcciones Inductivas
2.- Razonamiento automático.
3.- Construcción y manejo de pruebas.
4.- Generación de código.
5.- Corrección de programas