|
|
|
|
Matemática discreta / Norman L. Biggs ; traducido por Marc Noy.
AUTOR:
Norman L. Biggs - Marc Noy
ISBN:
8431633115
EDITOR:
Vicens Vives
IDIOMA:
spa
PÁGINAS:
XII, 545
AÑO:
1994
|
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
RESUMEN
|
El rápido desarrollo de titulaciones tales como la ingeniería informática, la electrónica o la estadística han llevado a que la matemática discreta cobre día a día mayor auge. Este manual ofrece: -un curso completo de matemática discreta de forma estructurada, coherente y sintética. -un nivel descriptivo accesible a cualquiera que disponga de los conocimientos básicos de aritmética y álgebra. -descripciones de algoritmos con una estructura similar a la de un lenguaje de programación. Tanto el estudiante de matemáticas que busque una primera aproximación a la teoría de los grafos, a la combinatoria o al álgebra abstracta, como el estudiante de informática o de electrónica que desee obtener una visión global de la materia, encontrarán en este texto una magnífica herramienta de trabajo. |
|
| |
|
INDICE
|
PARTE I NÚMEROS Y ENUMERACIÓN
1. Enteros
1.1 Aritmética ....3
1.2 Ordenación de los enteros ....5
1.3 Definiciones recursivas ....9
1.4 El principio de inducción ....12
1.5 Cociente y resto ....16
1.6 Divisibilidad ....19
1.7 El máximo común divisor ....20
1.8 Factorización en números primos ....24
1.9 Ejercicios diversos ....28
2. Funciones y enumeración
2.1 Funciones ....31
2.2 Funciones exhaustivas, inyectivas y biyectivas ....34
2.3 Contar ....38
2.4 El principio de las cajas ....42
2.5 ¿Finito o infinito? ....44
2.6 Ejercicios diversos ....48
3. Principios enumerativos
3.1 El principio de la adición ....50
3.2 Contar conjuntos de pares ....52
3.3 La función de Euler ....56
3.4 Funciones, palabras y selecciones ....59
3 5 Inyecciones como selecciones ordenadas sin repetición ....61
3.6 Permutaciones ....63
3.7 Ejercicios diversos ....68
4. Subconjuntos y diseños
4.1 Números binominales ....70
4.2 Selecciones no ordenadas con repetición ....75
4.3 El teorema del binomio ....77
4.4 El principio de la criba ....80
4.5 Algunas aplicaciones aritméticas ....84
4.6 Diseños ....90
4.7 t-diseños ....94
4.8 Ejercicios diversos ....98
5. Particiones, clasificaciones y distribuciones
5.1 Particiones de un conjunto ....101
5.2 Clasificación y relaciones de equivalencia ....104
5.3 Distribuciones y números multinomiales ....108
5.4 Particiones de un entero positivo ....113
5.5 Clasificación de las permutaciones ....115
5.6 Permutaciones pares e impares ....118
5.7 Ejercicios diversos ....125
6. Aritmética modular
6.1 Congruencias ....128
6.2 Zm y su aritmética ....131
6.3 Elementos invertibles de Zm ....135
6.4 Construcciones cíclicas de diseños ....138
6.5 Cuadrados latinos ....143
6.6 Ejercicios diversos ....147
PARTE II GRAFOS Y ALGORITMOS
7. Algoritmos y su eficiencia
7.1 ¿Qué es un algoritmo? ....151
7.2 El lenguaje de los programas ....153
7.3 Algoritmos y programas ....158
7.4 Demostración de que un algoritmo es correcto ....160
7.5 E6ciencia de los algoritmos ....163
7.6 Ordenes de crecimiento: la notación O ....167
7.7 Comparación de algoritmos ....169
7.8 Introducción a los algoritmos de ordenación ....172
7.9 Ejercicios diversos ....176
8. Grafos
8.1 Los grafos y su representación ....178
8.2 Isomorfismo de grafos ....181
8.3 Grados ....184
8.4 Caminos y ciclos ....186
8.5 Árboles ....190
8.6 Colorear los vértices de un grafo ....193
8.7 El algoritmo voraz para las vértice-coloraciones ....195
8.8 Ejercicios diversos ....200
9. Árboles, ordenación y búsqueda
9.1 Contar las hojas de un árbol con raíz ....203
9.2 Árboles y algoritmos de ordenación ....208
9.3 Árboles generadores y el problema AGM ....213
9.4 Búsqueda en profundidad ....218
9.5 Búsqueda en anchura ....222
9.6 El problema del camino más corto ....225
9.7 Ejercicios diversos ....228
10. Grafos bipartidos y problemas de emparejamientos
10.1 Relaciones y grafos bipartidos ....231
10.2 Arista-coloraciones de grafos ....234
10.3 Arista-coloraciones y cuadrados latinos ....237
10.4 Emparejamientos ....242
10.5 Emparejamientos máximos ....246
10.6 Transversales de familias de conjuntos finitos ....250
10.7 Ejercicios diversos ....252
11. Digrafos, redes y flujos
11.1 Digrafos ....255
11.2 Redes y caminos críticos ....258
11.3 Flujos y cortes ....262
11.4 El teorema del Hujo máximo y el corte mínimo ....265
11.5 El algoritmo de etiquetaje para flujos en redes ....270
11.6 Ejercicios diversos ....275
12. Técnicas recursivas
12.1 Generalidades sobre la recursividad ....278
12.2 Recurrencias lineales ....280
12.3 Bisección recursiva ....283
12.4 Optimización recursiva ....286
12.5 El marco de la programación dinámica ....290
12.6 Ejemplos del método de la programación dinámica ....293
12.7 Ejercicios diversos ....297
PARTE III MÉTODOS ALGEBRAICOS
13. Grupos
13.1 Los axiomas de grupo ....305
13.2 Ejemplos de grupos ....307
13.3 Álgebra básica en grupos ....310
13.4 El orden de un elemento en un grup ....313
13.5 Isomorfismo de grupos ....316
13.6 Grupos cíclicos ....317
13.7 Subgrupos ....321
13.8 Clases laterales y el teorema de Lagrange ....325
13.9 Caracterización de los grupos cíclicos ....331
13.10 Ejercicios diversos ....334
14. Grupos de permutaciones
14.1 Definiciones y ejemplos ....338
14.2 Órbitas y estabilizadores ....342
14.3 El tamaño de una órbita ....345
14.4 El número de órbitas ....348
14.5 Representación de grupos mediante permutaciones ....353
14.6 Aplicaciones de la teoría de grupos ....356
14.7 Ejercicios diversos ....360
15. Anillos, cuerpos y polinomios
15.1 Anillos ....362
15.2 Elementos inversibles de un anillo ....364
15.3 Cuerpos ....366
15.4 Polinomios ....369
15.5 El algoritmo de división para polinomios ....372
15.6 El algoritmo de Euclides para polinomios ....376
15.7 Factorización teórica de polinomios ....379
15.8 Factorización práctica de polinomios ....380
15.9 Ejercicios diversos ....384
16. Cuerpos finitos y aplicaciones
16.1 Un cuerpo con nueve elementos ....387
16.2 El orden de un cuerpo finito ....389
16.3 Construcción de cuerpos finitos ....392
16.4 El teorema del elemento primitivo ....394
16.5 Cuerpos finitos y cuadrados latinos ....399
16.6 Geometrías finitas y diseños ....402
16.7 Planos proyectivos ....406
16.8 Cuadrados en cuerpos finitos ....410
16.9 Existencia de cuerpos finitos ....414
16.10 Ejercicios diversos ....419
17. Códigos correctores de errores
17.1 Palabras, códigos y errores ....422
17.2 Códigos lineales ....427
17.3 Construcción de códigos lineales ....430
17.4 Corrección de errores en códigos lineales ....433
17.5 Códigos cíclicos ....437
17.6 Clasificación y propiedades de los códigos cíclicos ....441
17.7 Ejercicios diversos ....446
18. Funciones generadoras
18.1 Series de potencias y sus propiedades algebraicas ....449
18.2 Fracciones simples ....453
18.3 El teorema del binomio para exponentes negativos ....459
18.4 Funciones generadoras ....463
18.5 Recurrencias lineales homogéneas ....466
18.6 Recurrencias lineales no homogéneas ....471
18.7 Ejercicios diversos ....474
19. Particiones de un entero positivo
19.1 Particiones y diagramas ....477
19.2 Particiones conjugadas ....480
19.3 Particiones y funciones generadoras ....482
19.4 Funciones generadoras de particiones restringidas ....486
19.5 Una identidad misteriosa ....489
19.6 El cálculo de p(n) ....494
19.7 Ejercicios diversos ....496
20. Simetría y enumeración
20.1 El índice de ciclos de un grupo de permutaciones ....499
20.2 Simetría cíclica y diedral ....502
20.3 Simetría en tres dimensiones ....507
20.4 El número de coloraciones no equivalentes ....511
20.5 Conjuntos de coloraciones y funciones generadoras ....516
20.6 El teorema de Pólya ....519
20.7 Ejercicios diversos ....523
Soluciones a ejercicios escogidos ....525
|
|
| |
|
