Matemáticas discretas 2a ed

Descripción

Un conjunto es discreto si sus elementos están separados. Los conjuntos finitos y los subconjuntos infinitos de números enteros son conjuntos discretos, pero el conjunto de los números reales no lo es. La matemática discreta es el estudio de estructuras matemáticas definidas sobre conjuntos discretos. Aunque los orígenes de la matemática discreta se remontan a la antigüedad, no ha sido sino hasta años recientes que ha cobrado importancia, por sus aplicaciones a diversos campos, en particular a las ciencias de la computación y a la investigación de operaciones. Este libro de texto está dirigido a estudiantes de ciencias básicas e ingeniería y en él se exponen los fundamentos de esta área de las matemáticas que es uno de los pilares de la ciencia de la computación.

La obra consta de cuatro partes: Fundamentos, Métodos algebraicos, Enumeración combinatoria y Teoría de grafos. Para esta nueva edición se han agregado nuevas secciones, se ha ampliado el número de problemas propuestos al final de cada capítulo y se han incluido más aplicaciones relacionadas con la ciencia de la computación.

VENTAJAS

• Cada uno de los capítulos inicia con un listado de objetivos del mismo y una introducción, asimismo, al final de cada capítulo se encuentra un resumen y una serie de ejercicios.
• A lo largo del libro hay múltiples ejemplos que contribuyen a la mejor comprensión de los temas.
• Contiene una plataforma virtual de contenidos interactivos.

CONOZCA

• Algunas de las aplicaciones más importantes de las matemáticas discretas como son cambio de base, complejidad computacional, circuitos lógicos, espacios finitos de probabilidad.
• Los axiomas de los números enteros y el método de inducción matemática.
• El mínimo común múltiplo y cómo se relaciona con el máximo común divisor.
• La relación entre la notación binaria y la notación hexadecimal.

APRENDA A

• Identificar las nociones de función recursiva primitiva, función recursiva parcial y función recursiva.
• Definir el producto cartesiano de dos conjuntos y la función de conjunto finito.
• Representar y manipular relaciones binarias finitas por medio de matrices booleanas.
• Identificar las características del álgebra booleana y algunos ejemplos importantes.

DESARROLLE SUS HABILIDADES PARA

• Diferenciar algoritmos computacionales.
• Distinguir las propiedades de congruencias y aplicarlas en la determinación del día de la semana para una fecha cualquiera, así como en el sistema criptográfico RSA.
• Aplicar los polinomios en los campos de Galois.
• Identificar las características de los coeficientes de polinomios y sus implicaciones en las nociones de divisibilidad, del máximo común divisor y el algoritmo de Euclides.

A QUIÉN VA DIRIGIDO

Este libro está dirigido a estudiantes y profesores de ciencias básicas e ingeniería.

CONTENIDO

Prólogo
Parte I
Fundamentos

Capítulo I
Lógica y conjuntos
1.1 Introducción
1.2 Proposiciones y conectivos lógicos
1.3 Implicación y equivalencia lógica
1.4 Reglas de inferencia
1.5 Conjuntos
1.6 Predicados y cuantificadores
1.7 Operaciones con conjuntos
1.8 Resumen
1.9 Ejercicios

Capítulo II
Los enteros
2.1 Introducción
2.2 Axiomas de los números enteros
2.3 Orden en los enteros
2.4 Método de inducción matemática
2.5 El principio del buen orden
2.6 Resumen
2.7 Ejercicios

Capítulo III
Divisibilidad
3.1 Introducción
3.2 Divisibilidad
3.3 Aplicación: cambio de base
3.4 Números primos
3.5 Máximo común divisor
3.6 El teorema fundamental de la aritmética
3.7 Resumen
3.8 Ejercicios

Capítulo IV
Funciones
4.1 Introducción
4.2 Producto cartesiano
4.3 Funciones
4.4 Funciones biyectivas
4.5 Composición de funciones
4.6 Conjuntos finitos
4.7 El principio de la pichonera
4.8 Conjuntos infinitos
4.9 Operaciones binarias
4.10 Resumen
4.11 Ejercicios

Capítulo V
Relaciones binarias
5.1 Introducción
5.2 Tipos de relaciones binarias
5.3 Relaciones de equivalencia
5.4 La matriz de una relación
5.5 Resumen
5.6 Ejercicios

Parte II
Métodos algebraicos

Capítulo VI
Retículos y álgebras booleanas
6.1 Introducción
6.2 Relaciones de orden
6.3 Retículos
6.4 Álgebras booleanas
6.5 Orden en álgebras booleanas
6.6 Expresiones y funciones booleanas
6.7 Simplificación de expresiones booleanas
6.8 Aplicación: circuitos lógicos
6.9 Resumen
6.10 Ejercicios

Capítulo VII
Computabilidad y complejidad computacional
7.1 Introducción
7.2 Funciones recursivas
7.3 Máquinas de Turing
7.4 Complejidad computacional
7.5 Problemas NP-completos
7.6 Resumen
7.7 Ejercicios

Capítulo VIII
Aritmética modular
8.1 Introducción
8.2 Congruencias
8.3 Aplicación: calendario perpetuo
8.4 El teorema chino del residuo
8.5 El teorema de Euler
8.6 El criptosistema RSA
8.7. Los enteros módulo m
8.8 Resumen
8.9 Ejercicios

Capítulo IX
Grupos
9.1 Introducción
9.2 Semigrupos y monoides
9.3 Grupos
9.4 Propiedades de grupos
9.5 Subgrupos
9.6 Códigos de grupo
9.7 Homomorfismos
9.8 Grupos cíclicos
9.9 El teorema de Lagrange
9.10 Resumen
9.11 Ejercicios

Capítulo X
Anillos, campos y polinomios
10.1 Introducción
10.2 Anillos
10.3 Campos
10.4 Polinomios
10.5 Divisibilidad
10.6 Máximo común divisor
10.7 Polinomios irreducibles
10.8 Construcción de campos finitos
10.9 Resumen
10.10 Ejercicios

Parte III
Enumeración combinatoria

Capítulo XI
Conteo
11.1 Introducción
11.2 Permutaciones y combinaciones
11.3 Teorema del binomio
11.4 Coeficientes multinomiales
11.5 Ecuaciones lineales diofantinas
11.6 Espacios finitos de probabilidad
11.7 Resumen
11.8 Ejercicios

Capítulo XII
El principio de inclusión-exclusión
12.1 Introducción
12.2 El principio de inclusión-exclusión
12.3 Aplicaciones especiales
12.4. Extensión del principio
12.5 Resumen
12.6 Ejercicios

Capítulo XIII
Funciones generadoras
13.1 Introducción
13.2 Series de potencias formales
13.3 Funciones generadoras ordinarias
13.4 Particiones de enteros
13.5 Funciones generadoras exponenciales
13.6 Funciones generadoras de probabilidad
13.7 Resumen
13.8 Ejercicios

Capítulo XIV
Relaciones de recurrencia
14.1 Introducción
14.2 Recurrencias lineales de orden uno
14.3 Recurrencias lineales homogéneas de orden dos
14.4 Solución con funciones generadoras
14.5 Resumen
14.6 Ejercicios

Parte IV
Teoría de grafos

Capítulo XV
Grafos
15.1 Introducción
15.2 Grafos y subgrafos
15.3 Caminos y grafos conexos
15.4 Grafos isomorfos
15.5 Paseos eulerianos
15.6 Resumen
15.7 Ejercicios

Capítulo XVI
Árboles
16.1 Introducción
16.2 Propiedades de árboles
16.3 Árboles con raíz
16.4 Contando árboles
16.5 Árboles de búsqueda
16.6 Árbol de recubrimiento mínimo
16.7 Resumen
16.8 Ejercicios

Capítulo XVII
Grafos dirigidos
17.1 Introducción
17.2 Grafos dirigidos
17.3 Grafos orientados y torneos
17.4 Cerradura transitiva
17.5 El problema de la ruta más corta
17.6 Flujo máximo en una red
17.7 Resumen
17.8 Ejercicios

Capítulo XVIII
Temas selectos de grafos
18.1 Introducción
18.2 Ciclos hamiltonianos
18.3 Emparejamientos
18.4 Grafos aplanables
18.5 Coloración de vértices
18.6 El problema de los cuatro colores
18.7 Resumen
18.8 Ejercicios

Bibliografía

Índice analítico

Prólogo