INTRO MATEMATICAS DISCRETAS
Páginas: 177 (44179 palabras)
Publicado: 27 de diciembre de 2014
´
E.T.S. DE INGENIER´IA INFORMATICA
Apuntes de
´
INTRODUCCION
A LA
´
MATEMATICA
DISCRETA
para la titulaci´
on de
´
INGENIER´IA INFORMATICA
Curso 2002-2003
por
Fco. Javier Cobos Gavala
DEPARTAMENTO DE
´
MATEMATICA
APLICADA I
Contenido
1 Aritm´
etica entera
1
1.1
El conjunto Z de los n´
umeros enteros . . . . . . . . . . . . . .
1
1.2Definiciones recursivas . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Inducci´on matem´atica . . . . . . . . . . . . . . . . . . . . . .
3
1.3.1
Conjuntos inductivos . . . . . . . . . . . . . . . . . . .
4
1.3.2
El m´etodo de inducci´on . . . . . . . . . . . . . . . . .
5
1.4
Divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.5
M´aximocom´
un divisor . . . . . . . . . . . . . . . . . . . . . .
10
1.5.1
Algoritmo de Euclides . . . . . . . . . . . . . . . . . .
11
1.6
La identidad de Bezout . . . . . . . . . . . . . . . . . . . . . .
14
1.7
M´ınimo com´
un m´
ultiplo . . . . . . . . . . . . . . . . . . . . .
18
1.8
Ecuaciones diof´anticas lineales . . . . . . . . . . . . . . . . . .
191.9
N´
umeros primos y factorizaci´on . . . . . . . . . . . . . . . . .
22
1.10 Distribuci´on de primos . . . . . . . . . . . . . . . . . . . . . .
27
1.11 Primos de Fermat y Mersenne . . . . . . . . . . . . . . . . . .
30
1.12 Test de primalidad y factorizaci´on . . . . . . . . . . . . . . . .
32
1.13 Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . ..
35
2 Aritm´
etica modular
2.1
2.2
41
Aritm´etica modular . . . . . . . . . . . . . . . . . . . . . . . .
41
2.1.1
Criterios de divisibilidad . . . . . . . . . . . . . . . . .
50
Congruencias lineales . . . . . . . . . . . . . . . . . . . . . . .
50
i
ii
Contenido
2.3
El Teorema Chino del Resto . . . . . . . . . . . . . . . . . . .
55
2.4La aritm´etica en Zp . . . . . . . . . . . . . . . . . . . . . . . .
63
2.4.1
El Peque˜
no Teorema de Fermat . . . . . . . . . . . . .
65
2.4.2
El Teorema de Wilson . . . . . . . . . . . . . . . . . .
67
2.5
Los tests de base a: pseudoprimos y n´
umeros de Carmichael .
68
2.6
Test de Lucas-Lehmer . . . . . . . . . . . . . . . . . . . . . .
73
2.7
Lafunci´on de Euler . . . . . . . . . . . . . . . . . . . . . . . .
74
2.8
Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
2.8.1
Criptograf´ıa RSA . . . . . . . . . . . . . . . . . . . . .
81
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
84
2.9
3 T´
ecnicas de contar
3.1
91
Funciones . . . . . . . . . . . . . . . .. . . . . . . . . . . . .
91
3.1.1
Enumeraci´on . . . . . . . . . . . . . . . . . . . . . . .
94
3.2
El principio de adici´on . . . . . . . . . . . . . . . . . . . . . .
94
3.3
El principio de inclusi´on y exclusi´on . . . . . . . . . . . . . . .
96
3.4
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
97
3.5
Funciones, palabras yvariaciones . . . . . . . . . . . . . . . .
98
3.5.1
Variaciones sin repetici´on
. . . . . . . . . . . . . . . .
99
3.5.2
Permutaciones . . . . . . . . . . . . . . . . . . . . . . .
100
N´
umeros bin´omicos . . . . . . . . . . . . . . . . . . . . . . . .
102
3.6.1
Combinaciones con repetici´on . . . . . . . . . . . . . .
105
3.6.2
Teorema del binomio . . .. . . . . . . . . . . . . . . .
107
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
108
3.6
3.7
4 Recursi´
on
113
4.1
Recurrencias lineales homog´eneas . . . . . . . . . . . . . . . .
113
4.2
Recurrencias lineales no homog´eneas . . . . . . . . . . . . . .
116
4.3
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . ....
E.T.S. DE INGENIER´IA INFORMATICA
Apuntes de
´
INTRODUCCION
A LA
´
MATEMATICA
DISCRETA
para la titulaci´
on de
´
INGENIER´IA INFORMATICA
Curso 2002-2003
por
Fco. Javier Cobos Gavala
DEPARTAMENTO DE
´
MATEMATICA
APLICADA I
Contenido
1 Aritm´
etica entera
1
1.1
El conjunto Z de los n´
umeros enteros . . . . . . . . . . . . . .
1
1.2Definiciones recursivas . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Inducci´on matem´atica . . . . . . . . . . . . . . . . . . . . . .
3
1.3.1
Conjuntos inductivos . . . . . . . . . . . . . . . . . . .
4
1.3.2
El m´etodo de inducci´on . . . . . . . . . . . . . . . . .
5
1.4
Divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.5
M´aximocom´
un divisor . . . . . . . . . . . . . . . . . . . . . .
10
1.5.1
Algoritmo de Euclides . . . . . . . . . . . . . . . . . .
11
1.6
La identidad de Bezout . . . . . . . . . . . . . . . . . . . . . .
14
1.7
M´ınimo com´
un m´
ultiplo . . . . . . . . . . . . . . . . . . . . .
18
1.8
Ecuaciones diof´anticas lineales . . . . . . . . . . . . . . . . . .
191.9
N´
umeros primos y factorizaci´on . . . . . . . . . . . . . . . . .
22
1.10 Distribuci´on de primos . . . . . . . . . . . . . . . . . . . . . .
27
1.11 Primos de Fermat y Mersenne . . . . . . . . . . . . . . . . . .
30
1.12 Test de primalidad y factorizaci´on . . . . . . . . . . . . . . . .
32
1.13 Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . ..
35
2 Aritm´
etica modular
2.1
2.2
41
Aritm´etica modular . . . . . . . . . . . . . . . . . . . . . . . .
41
2.1.1
Criterios de divisibilidad . . . . . . . . . . . . . . . . .
50
Congruencias lineales . . . . . . . . . . . . . . . . . . . . . . .
50
i
ii
Contenido
2.3
El Teorema Chino del Resto . . . . . . . . . . . . . . . . . . .
55
2.4La aritm´etica en Zp . . . . . . . . . . . . . . . . . . . . . . . .
63
2.4.1
El Peque˜
no Teorema de Fermat . . . . . . . . . . . . .
65
2.4.2
El Teorema de Wilson . . . . . . . . . . . . . . . . . .
67
2.5
Los tests de base a: pseudoprimos y n´
umeros de Carmichael .
68
2.6
Test de Lucas-Lehmer . . . . . . . . . . . . . . . . . . . . . .
73
2.7
Lafunci´on de Euler . . . . . . . . . . . . . . . . . . . . . . . .
74
2.8
Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
2.8.1
Criptograf´ıa RSA . . . . . . . . . . . . . . . . . . . . .
81
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
84
2.9
3 T´
ecnicas de contar
3.1
91
Funciones . . . . . . . . . . . . . . . .. . . . . . . . . . . . .
91
3.1.1
Enumeraci´on . . . . . . . . . . . . . . . . . . . . . . .
94
3.2
El principio de adici´on . . . . . . . . . . . . . . . . . . . . . .
94
3.3
El principio de inclusi´on y exclusi´on . . . . . . . . . . . . . . .
96
3.4
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
97
3.5
Funciones, palabras yvariaciones . . . . . . . . . . . . . . . .
98
3.5.1
Variaciones sin repetici´on
. . . . . . . . . . . . . . . .
99
3.5.2
Permutaciones . . . . . . . . . . . . . . . . . . . . . . .
100
N´
umeros bin´omicos . . . . . . . . . . . . . . . . . . . . . . . .
102
3.6.1
Combinaciones con repetici´on . . . . . . . . . . . . . .
105
3.6.2
Teorema del binomio . . .. . . . . . . . . . . . . . . .
107
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
108
3.6
3.7
4 Recursi´
on
113
4.1
Recurrencias lineales homog´eneas . . . . . . . . . . . . . . . .
113
4.2
Recurrencias lineales no homog´eneas . . . . . . . . . . . . . .
116
4.3
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . ....
Leer documento completo
Regístrate para leer el documento completo.