Matematica Discreta
Páginas: 185 (46217 palabras)
Publicado: 11 de noviembre de 2012
´
E.T.S. DE INGENIER´ INFORMATICA
IA
Apuntes de
´
INTRODUCCION
A LA
´
MATEMATICA DISCRETA
para la titulaci´n de
o
´
INGENIER´ INFORMATICA
IA
Curso 2001-2002
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
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
18
1.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
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 . . . . . . . . . . . . . . . . . . .
552.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 . . . . . . . . . . . . . . . . . . . . . .
732.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 Combinatoria
3.1
91
Funciones . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
91
3.1.1
Enumeraci´n . . . . . . . . . . . . . . . . . . . . . . .
o
94
3.2
El principio de adici´n . . . . . . . . . . . . . . . . . . . . . .
o
94
3.3
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
96
3.4
Funciones, palabras y variaciones . . . . . . . . . . . . . . . .
97
3.4.1
Variaciones sinrepetici´n
o
................
98
3.4.2
Permutaciones . . . . . . . . . . . . . . . . . . . . . . .
99
N´meros bin´micos . . . . . . . . . . . . . . . . . . . . . . . .
u
o
101
3.5.1
Combinaciones con repetici´n . . . . . . . . . . . . . .
o
103
3.5.2
Teorema del binomio . . . . . . . . . . . . . . . . . . .
105
3.6
El principio de inclusi´n yexclusi´n . . . . . . . . . . . . . . .
o
o
105
3.7
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
107
3.5
4 Recursi´n
o
111
4.1
Recurrencias lineales homog´neas . . . . . . . . . . . . . . . .
e
111
4.2
Recurrencias lineales no homog´neas . . . . . . . . . . . . . .
e
114
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 2001-2002
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
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
18
1.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
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 . . . . . . . . . . . . . . . . . . .
552.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 . . . . . . . . . . . . . . . . . . . . . .
732.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 Combinatoria
3.1
91
Funciones . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
91
3.1.1
Enumeraci´n . . . . . . . . . . . . . . . . . . . . . . .
o
94
3.2
El principio de adici´n . . . . . . . . . . . . . . . . . . . . . .
o
94
3.3
Contar en tablas . . . . . . . . . . . . . . . . . . . . . . . . .
96
3.4
Funciones, palabras y variaciones . . . . . . . . . . . . . . . .
97
3.4.1
Variaciones sinrepetici´n
o
................
98
3.4.2
Permutaciones . . . . . . . . . . . . . . . . . . . . . . .
99
N´meros bin´micos . . . . . . . . . . . . . . . . . . . . . . . .
u
o
101
3.5.1
Combinaciones con repetici´n . . . . . . . . . . . . . .
o
103
3.5.2
Teorema del binomio . . . . . . . . . . . . . . . . . . .
105
3.6
El principio de inclusi´n yexclusi´n . . . . . . . . . . . . . . .
o
o
105
3.7
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . .
107
3.5
4 Recursi´n
o
111
4.1
Recurrencias lineales homog´neas . . . . . . . . . . . . . . . .
e
111
4.2
Recurrencias lineales no homog´neas . . . . . . . . . . . . . .
e
114
4.3
Ejercicios propuestos . . . . . . . . . . . . . . ....
Leer documento completo
Regístrate para leer el documento completo.