Matemáticas discreta y combinatoria : una introducción con aplicaciones /
Ralph P. Grimaldi.
- 3ra. [i.e. en inglés, 1ra. en español]
- México : Addison-Wesley, 1997
- 874 p.
CONTENIDO PARTE 1 Fundamentos de las matemáticas discretas 1 1 Principios fundamentales del conteo 3 1.1 Las reglas de la suma y del producto 3 1.2 Permutaciones 6 1.3 Combinaciones: El teorema del binomio 19 1.4 Combinaciones con repetición: Distribuciones 33 1.5 Una aplicación a las ciencias físicas (Opcional) 43 1.6 Resumen y repaso histórico 44 2 Fundamentos de lógica 51 2.1 Conectivas básicas y tablas de verdad 51 2.2 Equivalencia lógica: Las leyes de la lógica 61 2.3 Implicación lógica: Reglas de inferencia 77 2.4 El uso de cuantificadores 98 2.5 Cuantificadores, definiciones y la demostración de teoremas 121 2.6 Resumen y repaso histórico 137 3 Teoría de conjuntos 143 3.1 Conjuntos y subconjuntos 143 3.2 Operaciones de conjuntos y las leyes de la teoría de conjuntos 156 3.3 Técnicas de conteo y diagramas de Venn 169 3.4 Unas palabras en cuanto a la probabilidad 172 3.5 Resumen y repaso histórico 176 4 Propiedades de los enteros: Inducción matemática 183 4.1 El principio del buen orden: Inducción matemática 183 4.2 Definiciones recursivas 201 4.3 El algoritmo de la división: Números primos 213 4.4 El máximo común divisor: El algoritmo de Euclides 225 4.5 El teorema fundamental de la aritmética 232 4.6 Resumen y repaso histórico 238 5 Relaciones y funciones 245 5.1 Productos cartesianos y relaciones 246 5.2 Funciones: en general e inyectivas 251 5.3 Funciones sobreyectivas: Números de Stirling del segundo tipo 260 5.4 Funciones especiales 267 5.5 El principio del palomar 275 5.6 Composición de funciones y funciones inversas 280 5.7 Complejidad computacional 293 5.8 Análisis de algoritmos 297 5.9 Resumen y repaso histórico 308 6 Lenguajes: Máquinas de estados finitos 315 6.1 Lenguaje: La teoría de conjuntos de las cadenas 316 6.2 Máquinas de estado finito: Un primer encuentro 327 6.3 Máquinas de estado finito: Un segundo encuentro 335 6.4 Resumen y repaso histórico 343 7 Relaciones: La segunda vuelta 349 7.1 Repaso de relaciones: Propiedades de las relaciones 349 7.2 Reconocimiento por computador: Matrices cero-uno, y grafos dirigidos 357 7.3 Órdenes parciales: Diagramas de Hasse 371 7.4 Relaciones de equivalencia y particiones 382 7.5 Máquinas de estado finito: El proceso de minimización 388 7.6 Resumen y repaso histórico 394 PARTE 2 Temas adicionales de conteo 401 8 El principio de inclusión y exclusión 403 8.1 El principio de inclusión y exclusión 403 8.2 Generalizaciones del principio 413 8.3 Desórdenes: Nada está en el lugar correcto 418 8.4 Polinomios de torre 420 8.5 Disposiciones con posiciones prohibidas 424 8.6 Resumen y repaso histórico 428 9 Funciones generatrices 433 9.1 Ejemplos introductorios 433 9.2 Definiciones y ejemplos: Técnicas de cálculo 436 9.3 Particiones de enteros 445 9.4 La función generatriz exponencial 449 9.5 El operador de suma 454 9.6 Resumen y repaso histórico 456 10 Relaciones de recurrencia 461 10.1 La relación de recurrencia lineal de primer orden 461 10.2 La relación de recurrencia lineal homogénea de segundo orden con coeficientes constantes 571 10.3 La relación de recurrencia no homogénea 482 10.4 El método de las funciones generatrices 493 10.5 Un tipo especial de relación de recurrencia no lineal (Opcional) 499 10.6 Algoritmos divide y vencerás (Opcional) 511 10.7 Resumen y repaso histórico 521 PARTE 3 Teoría de grafos y aplicaciones 527 11 Una introducción a la teoría de grafos 529 11.1 Definiciones y ejemplos 529 11.2 Subgrafos, complementos e isomorfismos de grafos 537 11.3 Grado de un vértice: recorridos y circuitos eulerianos 550 11.4 Grafos planos 560 11.5 Caminos y ciclos hamiltonianos 578 11.6 Coloración de grafos y polinomios cromáticos 588 11.7 Resumen y repaso histórico 598 12 Árboles 607 12.1 Definiciones, propiedades y ejemplos 607 12.2 Árboles con raíz 614 12.3 Árboles y ordenaciones 634 12.4 Árboles ponderados y códigos prefijo 638 12.5 Componentes biconexas y puntos de articulación 644 12.6 Resumen y repaso histórico 650 13 Optimización y emparejamiento 657 13.1 Algoritmo del camino más corto de Dijkstra 657 13.2 Árboles recubridores minimales: Los algoritmos de Kruskal y Prim 665 13.3 Redes de transporte: El teorema de flujo máximo y corte mínimo 671 13.4 Teoría de emparejamiento 683 13.5 Resumen y repaso histórico 694 PARTE 4 Algebra moderna aplicada 699 14 Anillos y aritmética modular 701 14.1 La estructura de anillo: definición y ejemplos 701 14.2 Propiedades y subestructuras de un anillo 709 14.3 Los enteros módulo n 717 14.4 Homomorfismos e isomorfismos de anillo 722 14.5 Resumen y repaso histórico 730 15 Algebra booleana y funciones de conmutación 735 15.1 Funciones de intercambio: Formas normales disjuntiva y conjuntiva 735 15.2 Redes de puertas: Suma minimal de productos y mapas de Karnaugh 745 15.3 Aplicaciones adicionales: Condiciones de indiferencia 756 15.4 La estructura de un álgebra booleana (Opcional) 762 15.5 Resumen y repaso histórico 772 16 Grupos, teoría de la codificación y método de enumeración de Polya 777 16.1 Definiciones, ejemplos y propiedades elementales 777 16.2 Homomorfismos, isomorfismos y grupos cíclicos 784 16.3 Clases laterales y teorema de Lagrange 791 16.4 Elementos de la teoría de la codificación 793 16.5 La métrica de Hamming 798 16.6 La verificación de paridad y matrices generadoras 801 16.7 Códigos de grupo: Decodificación con líderes de clase 806 16.8 Matrices de Hamming 810 16.9 Enumeración y equivalencia: Teorema de Burnside 812 16.10 El índice de ciclo 820 16.11 El inventario de patrones: Método de enumeración de Polya 824 16.12 Resumen y repaso histórico 829 17 Cuerpos finitos y diseños combinatorios 835 17.1 Anillos de polinomios 835 17.2 Polinomios irreducibles: Cuerpos finitos 843 17.3 Cuadrados latinos 853 17.4 Geometrías finitas y planos afines 859 17.5 Diseños de bloques y planos proyectivos 865 17.6 Resumen y repaso histórico 871 Apéndice 1 Funciones exponenciales y logarítmicas A-1 Apéndice 2 Matrices, operaciones con matrices y determinantes A-13 Apéndice 3 Conjuntos numerables y no numerables A-27
9684443422
MATEMATICAS-PROBLEMAS PROGRAMACION DE COMPUTADORAS-PROBLEMAS ALGEBRA DE BOOLE MATEMATICAS DISCRETAS CONTEO MATEMATICO ANILLOS ARBOLES GRAFOS GRUPOS CUERPOS FINITOS