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