recursivas y sucesiones, matematica discreta
Páginas: 161 (40242 palabras)
Publicado: 19 de marzo de 2013
´
FACULTAD DE INFORMATICA Y ESTAD´
ISTICA
´
INGENIER´ INFORMATICA
IA
Apuntes de
´
INTRODUCCION
A LA
´
MATEMATICA DISCRETA
para el curso 2000-2001
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.2
Definiciones 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.5
M´ximo com´ndivisor . . . . . . . . . . . . . . . . . . . . . .
a
u
9
1.5.1
Algoritmo de Euclides . . . . . . . . . . . . . . . . . .
10
1.6
La identidad de Bezout . . . . . . . . . . . . . . . . . . . . . .
13
1.7
M´
ınimo com´n m´ltiplo . . . . . . . . . . . . . . . . . . . . .
u
u
17
1.8
Ecuaciones diof´nticas lineales . . . . . . . . . . . . . . . . . .
a
181.9
N´meros primos y factorizaci´n . . . . . . . . . . . . . . . . .
u
o
21
1.10 Distribuci´n de primos . . . . . . . . . . . . . . . . . . . . . .
o
26
1.11 Primos de Fermat y Mersenne . . . . . . . . . . . . . . . . . .
30
1.12 Test de primalidad y factorizaci´n . . . . . . . . . . . . . . . .
o
32
1.13 Ejercicios propuestos . . . . . . . . . . . . . . . . . . . .. . .
34
2 Aritm´tica modular
e
2.1
43
43
2.1.1
2.2
Aritm´tica modular . . . . . . . . . . . . . . . . . . . . . . . .
e
Criterios de divisibilidad . . . . . . . . . . . . . . . . .
52
Congruencias lineales . . . . . . . . . . . . . . . . . . . . . . .
52
i
ii
Contenido
2.3
El Teorema Chino del Resto . . . . . . . . . . . . . . . . . . .
57
2.4La aritm´tica en Zp . . . . . . . . . . . . . . . . . . . . . . . .
e
65
2.4.1
El Peque˜o Teorema de Fermat . . . . . . . . . . . . .
n
67
2.4.2
El Teorema de Wilson . . . . . . . . . . . . . . . . . .
69
2.5
Los tests de base a: pseudoprimos y n´meros de Carmichael .
u
70
2.6
La funci´n de Euler . . . . . . . . . . . . . . . . . . . . . . . .
o
752.7
Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
2.7.1
Criptograf´ RSA . . . . . . . . . . . . . . . . . . . . .
ıa
82
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
85
2.8
3 Combinatoria
3.1
89
Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
3.1.1
Enumeraci´n . . . . . . . . . . . . .. . . . . . . . . .
o
92
3.2
El principio de adici´n . . . . . . . . . . . . . . . . . . . . . .
o
92
3.3
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
94
3.4
Funciones, palabras y variaciones . . . . . . . . . . . . . . . .
95
3.4.1
Variaciones sin repetici´n
o
................
96
3.4.2
Permutaciones . . . . . . . . . . . . .. . . . . . . . . .
97
N´meros bin´micos . . . . . . . . . . . . . . . . . . . . . . . .
u
o
99
3.5
3.5.1
Combinaciones con repetici´n . . . . . . . . . . . . . .
o
101
3.5.2
Teorema del binomio . . . . . . . . . . . . . . . . . . .
103
3.6
El principio de inclusi´n y exclusi´n . . . . . . . . . . . . . . .
o
o
103
3.7
Ejercicios propuestos . . .. . . . . . . . . . . . . . . . . . . .
105
4 Recursi´n
o
109
4.1
Recurrencias lineales homog´neas . . . . . . . . . . . . . . . .
e
109
4.2
Recurrencias lineales no homog´neas . . . . . . . . . . . . . .
e
112
4.3
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
114
´
Indice
117
1. Aritm´tica entera
e
Dado que se supone que...
FACULTAD DE INFORMATICA Y ESTAD´
ISTICA
´
INGENIER´ INFORMATICA
IA
Apuntes de
´
INTRODUCCION
A LA
´
MATEMATICA DISCRETA
para el curso 2000-2001
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.2
Definiciones 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.5
M´ximo com´ndivisor . . . . . . . . . . . . . . . . . . . . . .
a
u
9
1.5.1
Algoritmo de Euclides . . . . . . . . . . . . . . . . . .
10
1.6
La identidad de Bezout . . . . . . . . . . . . . . . . . . . . . .
13
1.7
M´
ınimo com´n m´ltiplo . . . . . . . . . . . . . . . . . . . . .
u
u
17
1.8
Ecuaciones diof´nticas lineales . . . . . . . . . . . . . . . . . .
a
181.9
N´meros primos y factorizaci´n . . . . . . . . . . . . . . . . .
u
o
21
1.10 Distribuci´n de primos . . . . . . . . . . . . . . . . . . . . . .
o
26
1.11 Primos de Fermat y Mersenne . . . . . . . . . . . . . . . . . .
30
1.12 Test de primalidad y factorizaci´n . . . . . . . . . . . . . . . .
o
32
1.13 Ejercicios propuestos . . . . . . . . . . . . . . . . . . . .. . .
34
2 Aritm´tica modular
e
2.1
43
43
2.1.1
2.2
Aritm´tica modular . . . . . . . . . . . . . . . . . . . . . . . .
e
Criterios de divisibilidad . . . . . . . . . . . . . . . . .
52
Congruencias lineales . . . . . . . . . . . . . . . . . . . . . . .
52
i
ii
Contenido
2.3
El Teorema Chino del Resto . . . . . . . . . . . . . . . . . . .
57
2.4La aritm´tica en Zp . . . . . . . . . . . . . . . . . . . . . . . .
e
65
2.4.1
El Peque˜o Teorema de Fermat . . . . . . . . . . . . .
n
67
2.4.2
El Teorema de Wilson . . . . . . . . . . . . . . . . . .
69
2.5
Los tests de base a: pseudoprimos y n´meros de Carmichael .
u
70
2.6
La funci´n de Euler . . . . . . . . . . . . . . . . . . . . . . . .
o
752.7
Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
2.7.1
Criptograf´ RSA . . . . . . . . . . . . . . . . . . . . .
ıa
82
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
85
2.8
3 Combinatoria
3.1
89
Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
3.1.1
Enumeraci´n . . . . . . . . . . . . .. . . . . . . . . .
o
92
3.2
El principio de adici´n . . . . . . . . . . . . . . . . . . . . . .
o
92
3.3
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
94
3.4
Funciones, palabras y variaciones . . . . . . . . . . . . . . . .
95
3.4.1
Variaciones sin repetici´n
o
................
96
3.4.2
Permutaciones . . . . . . . . . . . . .. . . . . . . . . .
97
N´meros bin´micos . . . . . . . . . . . . . . . . . . . . . . . .
u
o
99
3.5
3.5.1
Combinaciones con repetici´n . . . . . . . . . . . . . .
o
101
3.5.2
Teorema del binomio . . . . . . . . . . . . . . . . . . .
103
3.6
El principio de inclusi´n y exclusi´n . . . . . . . . . . . . . . .
o
o
103
3.7
Ejercicios propuestos . . .. . . . . . . . . . . . . . . . . . . .
105
4 Recursi´n
o
109
4.1
Recurrencias lineales homog´neas . . . . . . . . . . . . . . . .
e
109
4.2
Recurrencias lineales no homog´neas . . . . . . . . . . . . . .
e
112
4.3
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
114
´
Indice
117
1. Aritm´tica entera
e
Dado que se supone que...
Leer documento completo
Regístrate para leer el documento completo.