Discrete Mathematics II (2002-2003)

Department of Computer Science

Última modificación: 9-Febrero-2003

Faculty

• José Luis Freire Nistal(LFCIA)
• José Luis Doncel Juárez(LFCIA)

Student Profile

• Students site in the Faculty of Informatics (CEU, in galician)
• Ingeniería Informática (Engineer, 5 years)
• fourth year, mandatory, fall term, 6 credits (4.5 theory, 1.5 practice) (60 hours, 15 weeks)
• Charlas (Grp. A): Lunes (10'30-11'30), Martes (10'30-11'30), Miércoles (10'30-11'30), Aula 3.3
• Charlas (Grp. B):  Lunes (4-5), Martes (4-5), Miércoles (6-7), Aula 3.3
• Prácticas: Miercoles  12'30-1'30 LP1-4 Grp. A-1;
                                       1'30-2'30  LP1-4 Grp. A-2;
                                       4-5 LP2-1 Grp. B-2.

             Jueves       4-5 LP2-1 Grp. B-1

EXAMEN ALTERNATIVO: DIA 6 DE FEBRERO, DE 4 A 6 (GRUPO A) Y DE 6 A 8 (GRUPO B)  EN LOS LABORATORIOS 1-1 Y 1-4.

Contents

    Combinatoria y recursión

1.- Principios fundamentales del conteo.
Las reglas de la suma y el producto. Tipos de distribuciones: Variaciones, permutaciones y combinaciones con y sin repetición. Principio de inclusión exclusión.

2.- 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.

3.- 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
R. P. Grimaldi. Matemáticas discreta y combinatoria, 3ª Edición. Ed. Addison-Wesley Iberoamericana.
J. L. Mott, A. Kandel y T. P. Baker;. Discrete Mathematics for computers scientists & mathematicians. Ed. Prentice Hall.
R. L Graham, D. E. Knuth y O. Patashnik. Concrete mathematics, a foundation for computer science. Ed. Addison-Wesley.
Liu, C. L. 2ª Edición. Elementos de Matemáticas Discretas. McGraw-Hill.
 
 

Técnicas deductivas.

• Sistemas de tipos.
• Razonamiento automático.
• Manejo de pruebas.
• Generación de código.